Перечисление карт с одной гранью тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Краско Евгений Сергеевич

• Краско Евгений Сергеевич
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Краско Евгений Сергеевич

Введение

Глава 1. Перечисление планарных деревьев

1.1 Перечисление г-рассечений

1.2 Перечисление 5-рассечений

1.3 Асимптотические оценки роста числа рассечений

Глава 2. Перечисление хордовых диаграмм

2.1 Помеченные беспетлевые хордовые диаграммы

2.2 Непомеченные беспетлевые хордовые диаграммы

2.3 Помеченные простые хордовые диаграммы

2.4 Непомеченные простые хордовые диаграммы

Глава 3. Перечисление г-регулярных карт рода д с одной гранью

3.1 Постановка задачи

3.2 Операции склейки и разрезания карт. Понятие трисекции

3.3 Перечисление корневых 4-регулярных карт рода д с одной гранью

3.4 Перечисление корневых ¿-регулярных карт с одной гранью в

случае

3.5 Основные принципы перечисления некорневых карт на многообразиях

3.6 Подсчет 4-регулярных непомеченных карт с одной гранью

3.7 Перечисление регулярных карт с одной гранью в случае простого

2

3.8 Перечисление максимальных хордовых диаграмм

Глава 4. Перечисление регулярных карт с несколькими гранями

4.1 Перечисление корневых карт

4.2 Перечисление некорневых карт

Заключение

Список литературы

Список рисунков

Список таблиц

Введение диссертации (часть автореферата) на тему «Перечисление карт с одной гранью»

Введение

Под (топологической) картой М на замкнутой двумерной ориентируемой поверхности X рода д понимается такое вложение связного мультиграфа С в поверхность X, при котором вершины графа отображаются в различные точки на поверхности X, ребра представляют собой несамопересекающиеся кривые, не имеющие общих точек, отличных от общих концевых вершин, а X \ С представляет собой набор из / связных областей, называемых гранями карты М. Под ¿-регулярными картами понимаются карты, в которых каждая из вершин имеет одну и ту же степень ¿. Карта М с выделенным и ориентированным ребром называется корневой картой. Две карты считаются эквивалентными, если существует гомеоморфизм поверхности (сохраняющий ориентацию поверхности или не сохраняющий ее), переводящий вершины, ребра и грани одной карты в вершины, ребра и грани другой.

Перечисление карт на поверхностях является важным, интересным и динамично развивающимся разделом современной перечислительной комбинаторики. С одной стороны, техника перечисления таких карт использует современные результаты теории графов, комбинаторики, алгебраической топологии и др. С другой стороны, полученные в этой области результаты используются в теории узлов [1], топологии, биоинформатике, теории представлений, теории алгоритмов и в других разделах современной математики и теоретической физики [2].

Задачи перечисления непомеченных дискретных структур, в частности, непомеченных карт на поверхностях, интересны в том числе и потому, что они лежат на стыке нескольких дисциплин, а именно, комбинаторной топологии, теории групп и перечислительной комбинаторики. Разработка подходов и методов решения такого рода задач и определяет актуальность данного исследования.

Важным подклассом карт, подробно исследуемым в данной работе, является подкласс ¿-регулярных карт. Эти карты имеют множество приложений в различных областях математики (таких, например, как теория узлов и зацеплений), биоинформатики, физики и др. Перечисление ¿-регулярных карт на сфере началось еще с работ Татта и его учеников. Однако в области перечисления ¿-регулярных карт на поверхностях результатов к настоящему моменту получено не очень много. Так, в работе Гао [3] было показано, что соответствующие произво-

дящие функции являются алгебраическими. В работах [4], [5], [6] были получены отдельные результаты для перечисления корневых 4-регулярных карт на сфере, торе, проективной плоскости и бутылке Клейна. Работы, посвященные перечислению ¿-регулярных карт на поверхностях, отличных от сферы, с точностью до гомеоморфизмов, сохраняющих и/или изменяющих ориентацию поверхности, к настоящему моменту отсутствуют.

В данной работе решаются следующие задачи:

1. перечисление так называемых 1 ^ ¿-регулярных деревьев на сфере (плоскости) с точностью до всех гомеоморфизмов.

2. перечисление помеченных и непомеченных хордовых диаграмм без петель, а также без петель и кратных ребер; первые из них отвечают картам с одной гранью без листьев, а вторые — без листьев и вершин степени 2;

3. перечисление непомеченных ¿-регулярных карт с одной гранью на поверхности фиксированного рода д;

4. обобщение полученных выше результатов на случай ¿-регулярных карт с произвольным числом граней на поверхности фиксированного рода д.

1. Исследование первой из перечисленных выше задач началось еще в ХУШ веке и было связано с задачей перечисления всех диагональных триангуляций правильного (п + 2)-угольника. По всей видимости, первыми, кто решил эту задачу для случая правильного (п + 2)-угольника с выделенным и ориентированным ребром, были Йоханн Андреас фон Зегнер [7] и Леонард Эйлер [8]. При решении этой задачи ими была получена последовательность чисел, известная ныне как последовательность чисел Каталана. Существует большое количество комбинаторных объектов, которые описываются числами Сп (см. например [9]). Нас в данной работе будет особо интересовать еще одна эквивалентная комбинаторная интерпретация этих чисел: количество тривалентных планарных деревьев с (п+2) вершинами степени 1, одна из которых выбрана в качестве корня (корневых деревьев). Соответствие между рассечениями (п + 2)-угольника с выделенным внешним ребром на треугольники и такими деревьями показано на рис. 1.

Рассмотрим теперь задачу перечисления всех диагональных триангуляций правильного (п + 2)-угольника в случае, когда ни одно из его ребер не выделено. В силу внутренней симметрии количество возможных рассечений (п + 2)-угольника уменьшится (рис. 2). В частности, имеется по одной триангуляции квадрата (п = 2) и пятиугольника (п = 3), а также три или четыре различных три-

а) Корневые б) Некорневые

Рисунок 1 — Двойственные структуры

ангуляции правильного шестиугольника в зависимости от того, допускаем ли мы отражения относительно его осей. Соответствующие этим триангуляциям три-валентные деревья показаны на рис. 2 пунктирными линиями. В терминологии Харари и Палмера [10] деревья, перечисляемые без учета отражений, называются плоскими (plane), а с их учетом — планарными (planar).

Рисунок 2 — Триангуляции при малых п.

Первые решения задач, связанных с перечислением некорневых триангуля-ций появились только во второй половине двадцатого века. В статье [11] впервые была получена числовая последовательность, описывающая количество некорневых триангуляций многоугольника в пространстве. В работах [12], [13] и [14] были описаны некоторые специальные методы получения простых аналитических выражений для соответствующих чисел. В книге [10] Харари и Палмер получили явное выражение для производящей функции, описывающей количество пла-нарных 2-деревьев, а следовательно и количество всех некорневых триангуляций (п + 2)-угольника в пространстве, с использованием теории Редфилда-Пойа [15], [16] и теоремы Оттера [17] о неподобии для деревьев. Наконец, в работе [18] Хара-ри, Палмер и Рид обобщили полученный результат на случай рассечения правильного (п(г — 2) + 2)-угольника на п г-угольников, или, что то же самое, перечислили все г-гональные планарные 2-деревья с п вершинами. Однако окончательные

выражения для производящих функций были довольно громоздкими, что не поз-

тИО

волило им получить явные выражения для чисел УП , описывающих количество таких деревьев.

Дальнейший прогресс в решении задач перечисления планарных деревьев был связан с появлением в начале восьмидесятых годов двадцатого века теории

комбинаторных видов [19], [20]. Изящная переформулировка теоремы Оттера [17] на языке теории комбинаторных видов позволила достаточно элегантно решить многие задачи, связанные с перечислением древовидных структур. В работе [21] Лабелль, Ламант и Леруа представили решение задачи о перечислении всех пла-нарных 2-деревьев на языке теории видов, а также получили молекулярное разложение этих видов. Отметим также работу [22], в которой было продемонстрировано приложение полученных результатов к перечислению полиеновых углеводородов с молекулярной формулой Сп Нп+2.

Несмотря на впечатляющий прогресс в решении описанных выше задач, явные формулы для количества всех некорневых рассечений многоугольников в пространстве на г-угольники до сих пор получены не были. Связано это, прежде всего, со сложностью учета симметрий отражения в таких задачах. Достаточно простые формулы для производящих функций, описывающих количество рассечений многоугольника на г-угольники с учетом только симметрий вращения, получены еще в работе [18]. Еще более просто эти формулы можно получить с использованием теории комбинаторных видов. Использование же теоремы о неподобии для учета симметрий отражения даже в наиболее изученном случае г = 3 (триангуляций (п + 2)-угольников) достаточно сильно усложняет окончательный результат [21].

Между тем, еще в 1964 году Уильям Браун в работе [23] предложил альтернативный и достаточно простой подход к учету симметрий отражения. Указанная работа была посвящена решению значительно более сложной задачи, связанной с подсчетом количества всех триангуляций правильного (т + 3)-угольника с п внутренними точками. Впервые эту задачу для случая триангуляций с выделенным ориентированным внешним ребром поставил и решил Уильям Татт [24]. В упомянутой выше работе [23] его ученик, Уильям Браун, обобщил решение этой задачи на случай триангуляций правильного (т + 3)-угольника без выделенного ребра, то есть на случай триангуляций с учетом всех возможных симметрий триангулированного многоугольника.

2. Естественным обобщением понятия дерева на плоскости является понятие карты с одной гранью на замкнутой ориентируемой поверхности произвольного рода д > 0. Такого рода карты удобно изображать с помощью так называемых хордовых диаграмм (рис. 3). Хордовая диаграмма строится следующим об-

разом: на окружности выбираются 2п равномерно распределенных точек; затем эти точки разбиваются на пары, и каждая пара соединяется хордой.

14

9 7

8

Рисунок 3 — Хордовая диаграмма

Для установления явной биекции между хордовыми диаграммами и картами с одной гранью следует, прежде всего, перейти от хордовой диаграммы к карте М* у которой имеются несколько граней и только одна вершина х (см. рис. 4,Ь). Эту вершину х мы должны поместить вне окружности и соединить ее 2п ребрами с точками на окружности. Если теперь поставить по вершине в каждой из граней карты М* и соединить эти вершины ребрами так, чтобы каждому ребру М* соответствовало новое ребро, пересекающее его, то мы получим двойственную М* карту М с одной гранью, которая и отвечает исходной хордовой диаграмме.

4 3

5/У I \2

12

9 10

а) б)

Рисунок 4 — Хордовая диаграмма и соответствующая карта

1

4

5

1

6

7

X

На практике возникают различные классы хордовых диаграмм [25; 26]. В данной работе мы изучаем два таких класса — беспетлевые и простые диаграммы. Говорят, что хорда является петлей, если она соединяет две соседние точки на окружности (например, хорда {1,2} на рис. 3). Беспетлевой диаграммой называется диаграмма, не имеющая петель. Две хорды в диаграмме, построенной на 2п точках, называются параллельными, если одна из них соединяет точки г и ] + 1, а вторая — ] и г + 1, или если одна из них соединяет точки 2п и ] + 1, а вторая — ] и 1. Например, хорды {3,12} и {4,11} на рис. 3 являются параллельными, так же как и хорды {4,11} и {5,10}. При этом, однако, хорды {3,12} и {5,10} параллельными не считаются. Под простой диаграммой мы будем понимать диаграмму, которая не имеет ни петель, ни параллельных ребер. Оба типа диаграмм достаточно часто встречаются в различных комбинаторных задачах, касающихся перечисления узлов и зацеплений [1; 27]. Кроме того, есть и другие комбинаторные задачи, в которых возникают такие диаграммы [27]. Простые же диаграммы отвечают так называемым формам — картам без листьев и вершин степени 2 [28]. Формы оказываются важны для анализа карт с одной гранью, так как они в некотором смысле описывают их базовую структуру: любая такая карта может быть получена из вполне определенной формы подразбиением ребер и подклейкой деревьев к вершинам [28].

Последовательность, описывающая количество помеченных беспетлевых хордовых диаграмм (http://oeis.org/A003436), впервые появилась в работе [29] как результат перечисления гамильтоновых циклов в п-мерных октаэдрах. Рекуррентное соотношение для этих чисел было получено в [30] с использованием биективного подхода. Для непомеченного случая соответствующие числа (http://oeis.org/A0034 37) были найдены с помощью компьютера в [29] для п < 8. При этом аналитического выражения получено не было. Несмотря на многочисленные применения, аналитические выражения для простых хордовых диаграмм не существовали ни для помеченного, ни для непомеченного случая.

3. Подход, связанный с перечислением хордовых диаграмм, не позволяет провести классификацию карт с одной гранью по роду отвечающей данной карте поверхности. Первой работой, посвященной перечислению корневых карт на поверхностях рода д, была работа Уолша и Лемана [31]. В этой работе было получено явное выражение для количества ед (п) карт с одной гранью на поверхности рода д, построенных на п ребрах, а также выведена формула для количества кор-

невых 3-регулярных карт с одной гранью рода д. В работе [32] для числа е9 (п) было получено удобное рекуррентное соотношение. В работе [33] с помощью достаточно оригинального подхода, основанного на декомпозиции карты с одной гранью в аналогичную карту меньшего рода, было получено новое рекуррентное соотношение для чисел е9 (п). В той же работе было показано, как использовать данную технику для вывода специальных типов карт, например, 3-регулярных карт.

В восьмидесятые годы прошлого века появились первые работы [34], [35], посвященные перечислению некорневых карт в планарном случае. Идеи работы [34] были существенным образом развиты и усовершенствованы в статье [36]. В этой работе для задачи перечисления некорневых карт на ориентируемой поверхности заданного рода при фиксированном числе ребер было введено понятие фактор-карты на орбифолде, то есть на факторе поверхности относительно действия конечной подгруппы группы автоморфизмов. Используя эту идею, Медных и Недела получили явную формулу для количества некорневых карт на ориентированной поверхности рода д с заданным числом ребер п. Для этого им, в частности, понадобилось вывести формулы для количества сохраняющих порядок эпиморфизмов из фундаментальной группы орбифолда в циклическую группу Z^.

Подход Медных и Неделы достаточно хорошо разработан для перечисления карт с точностью до сохраняющих ориентацию гомеоморфизмов поверхности. Однако на сегодняшний день известно не так много результатов, в которых учитываеся род поверхности, а перечисление проводится с точностью до всех гомеоморфизмов. Существует формула [37] для количества всех рассечений многоугольника (объектов, изоморфных планарным деревьям), два различных подхода [35] [38] к перечислению карт на сфере произвольного вида, однако ни один из этих результатов не был обобщен на случай поверхности рода д > 0.

Вместе с тем имеется интересный класс хордовых диаграмм, с которого, ввиду простоты его описания, кажется разумным начать решение подобного рода перечислительных задач. Этот класс, а именно, класс непомеченных хордовых диаграмм рода д, имеющих 2д хорд, впервые был рассмотрен Кори и Маркусом в работе [39]. Авторы назвали такие диаграммы максимальными и нашли перечислительную формулу для количества классов эквивалентности таких диаграмм [39]. Использованное ими отношение эквивалентности включало только вращения окружности, на которой изображена диаграмма.

Естественно попытаться обобщить этот результат и перечислить максимальные диаграммы относительно действия наиболее полной группы симметрий — группы диэдра Бп. Эта задача может быть переформулирована как задача перечисления карт рода д, имеющих в точности одну грань и одну вершину, с точностью до всех гомеоморфизмов поверхности — как сохраняющих, так и не сохраняющих ее ориентацию.

4. Работа Уолша и Лемана [31], посвященная перечислению корневых карт на замкнутой ориентируемой поверхности рода д, была основана на подходе Тат-та [40], [41] к перечислению планарных карт. Идея Татта состояла в том, чтобы классифицировать карты в зависимости от типа структуры, получающейся в результате удаления корневого ребра, а затем подсчитать количество карт в каждом классе. Уолш и Леман обобщили этот подход на случай произвольной поверхности рода д, подсчитав количество вложенных в нее карт для фиксированного числа ребер.

Техника построения аналитических решений рекуррентных соотношений для произвольных (не обязательно имеющих одну грань) карт на поверхности заданного рода была развита в работах Бендера и Канфильда в восьмидесятых - девяностых годах прошлого века (см., например, [42], [43]). Для некоторых частных случаев (карты на торе, проективной плоскости) ими были получены точные аналитические формулы. Для более сложных случаев они вывели асимптотические формулы, позволяющие оценить количество корневых карт при больших значениях входящих в задачу параметров. В дальнейших исследованиях были сделаны попытки обобщить полученные результаты на поверхности более высокого рода (см., например, [43], [44]). Последние достижения в этой области описаны в работе [45].

Работы Лисковца [34] и Вормальда [35], посвященные перечислению некорневых карт в планарном случае, не были ограничены случаем карт с одной гранью. Обобщение этого подхода, разработанное в статье Медных и Неделы [36], позволяет получать явные формулы для некоторых классов карт. Основная трудность при этом состоит в том, что необходимо аналитически описать и классифицировать все орбифолды, которые оказываются допустимы для перечисляемого класса. Вместе с тем, даже если такое описание оказывается невозможно, для поверхностей рода д > 1 список орбифолдов является не только конечным, но и поддающимся генерации в явном виде с помощью компьютера. Для поверхностей рода

0 (сфера) и 1 (тор), имеющих бесконечные семейства допустимых орбифолдов, эти семейства имеют вид, поддающийся классификации. Одной из особенностей подхода Медных и Неделы оказывается то, что задача описания и классификации орбифолдов может быть решена независимо от типа дискретных структур, которые необходимо перечислить на поверхности рода д. Так, в работе [46] результаты перечисления карт на поверхности рода д были перенесены на гиперкарты.

Целью работы является перечисление карт с единственной гранью при дополнительных ограничениях на структуру таких карт.

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Перечислить непомеченные деревья на плоскости, имеющие заданные степени внутренних вершин.

2. Перечислить хордовые диаграммы без петель, а также без петель и кратных ребер.

3. Перечислить регулярные карты с одной гранью, а также карты с одной гранью и одной вершиной с учётом рода поверхности вложения.

4. Обобщить полученные результаты на случай регулярных карт, имеющих несколько граней.

Научная новизна:

1. Впервые получены простые аналитические соотношения для числа непомеченных деревьев на плоскости с учётом отражений.

2. Впервые построены производящие функции для помеченных хордовых диаграмм при ограничениях на их структуру.

3. Впервые перечислены непомеченные гамильтоновы циклы в п-мерном октаэдре.

4. Впервые выписаны рекуррентные соотношения, позволяющие подсчитать количество непомеченных хордовых диаграмм без петель, а также без петель и параллельных хорд.

5. Впервые получены аналитические выражения для числа 4-регулярных карт с одной гранью.

6. Впервые получены рекурретные соотношения для числа непомеченных карт с одной гранью и одной вершиной на поверхности заданного рода, учитывающие все гомеоморфизмы.

7. Впервые построен алгоритм перечисления непомеченных г-регулярных карт на поверхности заданного рода.

Научная и практическая значимость. Работа носит теоретический характер. Результаты работы могут быть использованы для дальнейшего изучения свойств помеченных и непомеченных ¿-регулярных карт на поверхностях. Описанные в диссертации формулы для перечисления хордовых диаграмм могут быть использованы при классификации узлов и зацеплений над поверхностями различного рода. Разработанные подходы могут быть эффективны при решении перечислительных задач, связанных с картами на многообразиях.

Методология и методы исследования. В работе используются методы перечислительной комбинаторики, а также теории групп и асимптотических методов.

Основные положения, выносимые на защиту:

1. Явные аналитические выражения, позволяющие подсчитать некорневые деревья с заданной степенью внутренних вершин с точностью до вращений и отражений плоскости.

2. Производящие функции для помеченных хордовых диаграмм, классифицирующие их по числу хорд, петель и параллельных хорд.

3. Рекуррентные соотношения, позволяющие перечислять непомеченные хордовые диаграммы без петель и параллельных хорд по числу рёбер.

4. Явные аналитические выражения для количества непомеченных ¿-регулярных карт с одной гранью при конкретных значениях параметра

5. Рекуррентные соотношения для количества непомеченных карт с одной гранью и одной вершиной, учитывающие гомеоморфизмы, изменяющие ориентацию поверхности.

6. Алгоритм, позволяющий вычислять количество регулярных карт с фиксированным числом рёбер на поверхности заданного рода.

Степень достоверности полученных результатов обеспечивается строгими математическими доказательствами сформулированных в работе утверждений. Правильность формул была потверждена непосредственной генерацией соответствующих дискретных структур. Результаты находятся в соответствии с численными результатами, полученными другими авторами.

Апробация работы. Основные результаты работы докладывались на SIAM Conference on Discrete Mathematics [47] (Atlanta, Georgia, USA, 2016), на семинарах по дискретной математике и математической кибернетике в ПОМИ им. В. А. Стеклова РАН, СПбГУ, Высшей школе экономики, Санкт-Петербургском Академическом университете.

Публикации. Основные результаты диссертации опубликованы в рецензируемых научных изданиях [48-51], входящих в список журналов, рекомендованных ВАК.

Личный вклад. Работы [48-51] написаны в соавторстве с научным руководителем.

В работе [48] научному руководителю принадлежит постановка задачи, а также гипотеза о явном виде формулы для количества симметричных относительно отражений корневых r-рассечений. Комбинаторное доказательство этой формулы принадлежит диссертанту. Формулы для перечисления некорневых S-рассечений, их комбинаторное доказательство и асимптотический анализ принадлежат диссертанту

В работе [51] научному руководителю принадлежит постановка задачи; диссертанту принадлежат явные формулы для количества 3- и 4-регулярных карт с одной гранью, рекуррентные формулы для количества почти-^-регулярных карт с несколькими гранями и алгоритм перечисления непомеченных ¿-регулярных карт.

В работе [49] научному руководителю принадлежит постановка задачи, а также вывод перечислительной формулы для (1 + d) -деревьев на плоскости. Диссертантом доказано сведение задачи перечисления (1 ^ 4)-карт рода g с одной гранью к перечислению деревьев на плоскости и получен явный вид формулы для помеченных 4-регулярных карт с одной гранью. Анализ допустимых орбифолдов для непомеченных карт и явная перечислительная формула для таких карт также принадлежат диссертанту.

В работе [50] научному руководителю принадлежит постановка задачи. Диссертанту принадлежит вывод рекуррентных формул для количества помеченных и непомеченных хордовых и линейных диаграмм, анализ производящих функций для данных типов диаграмм, вывод рекуррентных соотношений для количества d-симметричных хордовых и линейных диаграмм, а также комбинатор-

ное доказательство биекции между беспетлевыми хордовыми диаграммами и га-мильтоновыми циклами в октаэдрах.

Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации составляет 113 страниц. Список литературы содержит 56 наименований.

Глава 1. Перечисление планарных деревьев

1.1 Перечисление г-рассечений

Простейшим классом карт с одной гранью являются деревья на плоскости. Вместо деревьев нам будет удобнее перечислять изоморфные им структуры — так называемые рассечения. Рассмотрим правильный (п(г — 2) + 2)-угольник. Добавляя к нему не пересекающие друг друга хорды до тех пор, пока каждая внутренняя область не станет г-угольником, мы получаем некоторое рассечение исходного многоугольника на п г-угольников, которое далее мы будем называть г-рассечением. Производящая функция ¡г (х), описывающая количество рассечений с выделенным и ориентированным внешним ребром, удовлетворяет следующему функциональному уравнению:

Это уравнение достаточно хорошо известно. В [18] оно сформулировано как формула (2.2) в несколько иных терминах: в [18] рассечение не может содержать нулевое число областей; нам же будет удобно разрешать такие рассечения. Поэтому функция ¡г (х) равна иг (х) + 1 в терминах [18]. Используя формулу обращения Лагранжа, из уравнения (1.1) можно получить явное выражение для количества

7»

Ьп г-рассечений:

В частности, в случае г = 3 мы получаем, что количество триангуляций правильного (п + 2)-угольника с выделенным и ориентированным внешним ребром описывается числами Каталана. В общем случае имеем так называемую последовательность Фусса-Каталана [52].

Рассмотрим соответствующую задачу для некорневых многоугольников. Обозначим через иг (х) производящую функцию, описывающую количество и^ неизоморфных рассечений правильного (п(г — 2) + 2)-угольника на г-угольники с учетом только симметрии вращений (г-рассечений некорневых многоугольников на плоскости). Эту функцию достаточно просто выразить через производящую

¡г (х) = 1 + х/ 1 (х).

(1.1)

п> 0.

(1.2)

функцию ¡т(х) (1.1) (см., например, формулу (4.3) в [18]):

иг(х) = х^(Сг; ¡т(х)) + /г(х) + ¡т(х) — ^(х). (1.3)

Здесь Z (Сг) есть цикловой индекс группы Сг вращений правильного г-угольника,

1

Z(Сг;¡г(х)) = -^ФУ) •

в\т

Ф(д) — функция Эйлера. Доказательство формулы (1.3) можно найти в [18], где она появляется как формула (4.3). Заметим еще раз, что ¡т (х) в данной главе равно ит (х) + 1 в терминах [18], так что точный вид вышеупомянутых формул несколько отличается друг от друга. Заметим, что слагаемое xZ(Ст; ¡т(х)) перечисляет рассечения с корнем в некотором г-угольнике. Этот факт можно доказать с использованием знаменитой теоремы Пойа.

Список литературы диссертационного исследования кандидат наук Краско Евгений Сергеевич, 2017 год

Список литературы

1. Enumerating the k-tangle projections / A. Bogdanov, V. Meshkov, A. Omelchenko, M. Petrov // Journal of Knot Theory and Its Ramifications. — 2012. — Vol. 6.

2. Goulden I.P., Jackson D.M. The KP hierarchy, branched covers, and triangulations // Advances in Mathematics. — 2008. — Vol. 219, no. 3. — Pp. 932-951.

3. Gao Z. C. The number of degree restricted maps on a surface // Discrete Math. — 1993. — Vol. 123. — P. 47-63.

4. Ren Han, Yaprei Liu. Enumeration of near-4-regular maps on the sphere and torus // Discrete Appl. Math. — 2001. — Vol. 110. — Pp. 273-288.

5. Ren Han, Liu Yanpei. 4-Regular Maps on the Klein Bottle // Journal of Combinatorial Theory, Series B. — 2001. — Vol. 82. — Pp. 118-137.

6. Ren Han, Liu Yanpei. The Number of Loopless 4-Regular Maps on the Projective Plane // Journal of Combinatorial Theory, Series B. — 2002. — Vol. 84. — Pp. 8499.

7. Segner A. Enumeratio modorum quibus figurae planae rectilineae per diagonales dividuntur in triangula // Novis Commentar. Petropolit. — 1758. — Vol. 7. — Pp. 203-209.

8. Euler L. Summarium // Novis Commentar. Petropolit. — 1758. — Vol. 7. — Pp. 13-15.

9. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. — М.: Мир, 2005.

10. Harary F., Palmer E. M. Graphical enumeration. — Academic Press, New York, 1973.

11. Motzkin T. S. Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products // Bull. Amer. Math. Soc. — 1948. — Vol. 54. — Pp. 352-360.

12. Guy R. K. Dissecting a Polygon Into Triangles // Bull. Malays. Math. Soc. — 1958.

— Vol. 5. — Pp. 57-60.

13. Moon J. W, Moser L. Triangular dissections of n-gons // Canad. Math. Bull. — 1963. — Vol. 6. — Pp. 175-178.

14. Stockmeyer P. K. The charm bracelet problem and its applications // Graphs and Combinatorics, (eds. R. A. Bari and F. Harary). — 1973. — Vol. 45, no. 406. — Pp. 339-349.

15. Redfield H. J. The theory of group-reduced distributions // J. Amer. Math. Soc. — 1927. — Vol. 49. — Pp. 433-455.

16. Polya G., Read R. C. Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. — New York: Springer-Verlag, 1987.

17. Otter R. The number of trees // Ann. Math. — 1948. — Vol. 49. — Pp. 583-599.

18. Harary F., Palmer E. M., Read R. C. On the cell-growth problem for arbitrary polygons // Discrete Mathematics. — 1975. — Vol. 11. — Pp. 371-389.

19. Joyal André. Une théorie combinatoire des séries formelles // Advances in Mathematics. — 1981. — Vol. 42. — Pp. 1-82.

20. Bergeron F., Labelle G., Leroux P. Combinatorial Species and Tree-Like Structures.

— Cambridge University Press, 1998.

21. Labelle G., Lamathe C., Leroux P. A Classification of Plane and Planar 2-trees // Theor. Comput. Sci. — 2003.

22. Enumeration of polyene hydrocarbons: a complete mathematical solution / S. Cyvin, J. Brunvoll, E. Brendsdal et al. // J. Chem. Inform. Comput. Sci. — 1995.

— Vol. 35(4). — Pp. 743-751.

23. Brown W. G. Enumeration of triangulations of the disk // Proc. London Math. Soc.

— 1964. — Vol. 14(3). — Pp. 746-768.

24. Tutte W. T. A census of planar triangulations // Canadian J. Math. — 1962. — Vol. 14.— Pp. 21-38.

25. Stanley Richard P. Enumerative Combinatorics, Volume 2. — Cambridge University Press, 2001.

26. Aigner Martin. A Course in Enumeration. — Springer, 2007.

27. Jablan Slavik, Sazdanovic Radmila. Knots, Links, and Self-Avoiding Curves // Forma. — 2007. — Vol. 22, no. 1. — Pp. 5-13.

28. G. Chapuy, M. Marcus, G. Schaeffer. A Bijection for Rooted Maps on Orientable Surfaces // SIAM J. Discrete Math. — 2009. — Vol. 23, no. 3. — Pp. 1587-1611.

29. Singmaster David. Hamiltonian circuits on the n-dimensional octahedron // Journal of Combinatorial Theory, Series B. — 1975. — Vol. 19, no. 1. — Pp. 1-4.

30. Hazewinkel M., V.V.Kalashnikov. Counting Interlacing Pairs on the Circle. Department of Analysis, Algebra and Geometry: Report AM. — Stichting Mathematisch Centrum, 1995.

31. Walsh T.R.S., Lehman A.B. Counting rooted maps by genus, I // J. Combin. Theory Ser. B. — 1972. — Vol. 13. — Pp. 192-218.

32. Harer J., Zagier D. The Euler characteristic of the moduli space of curves // Invent. Math. — 1986. — Vol. 85. — Pp. 457-485.

33. Chapuy G. A new combinatorial identity for unicellular maps, via a direct bijective approach // Advances in Applied Mathematics. — 2011. — Vol. 47. — Pp. 874893.

34. Liskovets V. A. Enumeration of nonisomorphic planar maps // Selecta Math. Sovietica. — 1985. — Vol. 4. — Pp. 303-323.

35. Wormald N.C. Counting unrooted planar maps // Discrete Math. — 1981. — Vol. 36, no. 205-225.

36. Mednykh A., Nedela R. Enumeration of unrooted maps of a given genus // J. Combin. Theory Ser. B. — 2006. — Vol. 96, no. 5. — Pp. 709-729.

37. Read R.C. On general dissections of a polygon // Aeq. Math. — 1978. — Vol. 18. — Pp. 370-388.

38. Liskovets V. A. A reductive technique for enumerating non-isomorphic planar maps // Discrete Mathematics. — 1996. — Vol. 156. — Pp. 197-217.

39. Cori R., Marcus M. Counting non-isomorphic chord diagrams // Theoretical Computer Science. — 1998. — Vol. 204. — Pp. 55-73.

40. Tutte William T. A census of planar maps // Canad. J. Math. — 1963. — Vol. 15.

— Pp. 249-271.

41. Tutte William T. On the enumeration of planar maps // Bull. Amer. Math. Soc. — 1968. — Vol. 74. — Pp. 64-74.

42. E.A Bender, E.R. Canfield, R.W. Robinson. The enumeration of maps on the torus and the projective plane // Canad. Math. Bull. — 1988. — Vol. 31. — Pp. 257-271.

43. Bender E., Canfield E. The number of rooted maps on an orientable surface // Journal of Combinatorial Theory, Series B. — 1991. — Vol. 53. — Pp. 293-299.

44. Giorgetti Alain. Combinatoire bijective et enumerative des cartes pointees sur une surface: Ph.D. thesis / Universite de Marne-la-Vallee, Institut Gaspard Monge. — 1998.

45. Walsh Timothy R. S., Giorgetti Alain. Efficient enumeration of rooted maps of a given orientable genus by number of faces and vertices // ARS MATHEMATICA CONTEMPORANEA. — 2014. — Vol. 7, no. 2. — Pp. 263-280.

46. Mednykh Alexander, Nedela Roman. Enumeration of unrooted hypermaps of a given genus // Discrete Mathematics. — 2010. — Vol. 310. — Pp. 518-526.

47. E.S.Krasko, A.V.Omelchenko. Counting 4-regular one-face maps // SIAM Conference on Discrete Mathematics. — 2016.

48. E.S.Krasko, A.V.Omelchenko. Brown's theorem and its application for enumeration of dissections and planar trees // The Electronic Journal of Combinatorics. — 2015.

— Vol. 22, no. 1.

49. E.S.Krasko, A.V.Omelchenko. Enumeration of 4-regular one-face maps // European Journal of Combinatorics. — 2017. — Vol. 62. — Pp. 167-177.

50. E.S.Krasko, A.V.Omelchenko. Enumeration of Chord Diagrams without Loops and Parallel Chords // The Electronic Journal of Combinatorics. — 2017. — Vol. 24.

51. Е.С.Краско, А.В.Омельченко. Перечисление регулярных карт на поверхностях заданного рода // Записки научных семинаров ПОМИ РАН. — 2016. — Vol. 450. — Pp. 74-108.

52. Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics. — Addison-Wesley, Reading, MA, 1990.

53. Brown W. G. Enumeration of quadrangular dissections of the disk // Canad. J. Math.

— 1965. — Vol. 17. — Pp. 302-317.

54. Flajolet P., SedgewickR. Analytic Combinatorics. — Book in preparation, preliminary version available at http://algo.inria.fr/flajolet/Publications.

55. Courant R., Hilbert D. Methods of Mathematical Physics. Volume 2: Partial Differential Equations. — Interscience Publishers, New York, 1962.

56. Ledoux M. A recursion formula for the moments of the Gaussian orthogonal ensemble // Annales de l'Institut Henri Poincaré - Probabilités et Statistiques. — 2009.

— Vol. 45, no. 3. — Pp. 754-769.

Список рисунков

1 Двойственные структуры................................................6

2 Триангуляции при малых n................................................6

3 Хордовая диаграмма......................................................8

4 Хордовая диаграмма и соответствующая карта........................8

1.1 Симметричное рассечение с выделенным ребром; r = 2 k + 1. ... 19

1.2 Симметричные рассечения с выделенныой вершиной; r = 2k + 1. . 20

1.3 Симметричные рассечения с выделенной вершиной; r = 2k.....21

1.4 Симметричные рассечения с выделенным ребром; r = 2k......21

1.5 Комбинаторное доказательство равенства (1.13)............22

1.6 {3,4,8}-рассечение............................24

1.7 Типы рассечений, перечисляемых QS (x) и RS (x)...........26

1.8 Типы S-рассечений с выделенным ребром...............27

1.9 Симметричные S-рассечения с выделенной вершиной........27

2.1 Хордовая диаграмма...........................33

2.2 Линейная диаграмма ..........................34

2.3 Перечисление линейных диаграмм...................35

2.4 3-симметричные линейные диаграммы................39

2.5 ¿-симметричные беспетлевые линейные диаграммы.........39

2.6 Специальные случай ¿-симметричной беспетлевой линейной диаграммы ................................................................41

2.7 Диаграммы с симметрией отражения.................42

2.8 Соответствие между гамильтоновыми циклами в октаэдрах и хордовыми диаграммами ................................................44

2.9 Перечисление линейных диаграмм по числу параллельных хорд и петель ......................................................................45

2.10 Подсчет простых ¿-симметричных линейных диаграмм, ¿ нечетное 49

2.11 Подсчет простых ¿-симметричных линейных диаграмм, ¿ четное . 50

2.12 Специальные типы ¿-симметричных линейных диаграмм......51

2.13 Подсчет 2-симметричных хордовых диаграмм ........................52

2.14 Подсчет ¿-симметричных хордовых диаграмм, ¿> 2 ........53

2.15 Простые диаграммы, имеющие симметрию отражения........54

2.16 Подсчет диаграмм, имеющих симметрию отражения ........54

2.17 Подчет диаграмм с симметрией отражения..............56

3.1 Помеченные карты............................60

3.2 Автоморфизмы тора...........................71

3.3 Фактор-карта...............................73

3.4 Хордовые диаграммы и склейки многоугольников..........89

3.5 Обход грани и симметрии карт.....................91

3.6 Обход грани в максимальных диаграммах...............92

4.1 Стягивание ребра............................96

4.2 Стягивание ребра с понижением рода.................96

4.3 Стягивание ребра, соединяющего корневые вершины........98

4.4 Разрезание одной карты на две.....................98

Список таблиц

1 Число планарных ¿-рассечений п-угольника..............29

2 Коэффициенты асимптотической оценки числа планарных ¿"-рассечений...............................32

3 Беспетлевые диаграммы по числу хорд................57

4 Простые диаграммы по числу хорд ..................58

5 Помеченные ¿-регулярные карты....................88

6 Непомеченные ¿-регулярные карты..................88

7 Количество максимальных диаграмм по роду.............95

8 Помеченные 3-регулярные карты....................103

9 Непомеченные 3-регулярные карты..................103

10 Помеченные 4-регулярные карты....................103

11 Непомеченные 4-регулярные карты..................104

12 Помеченные 5-регулярные карты....................104

13 Непомеченные 5-регулярные карты..................104

14 Помеченные 6-регулярные карты....................104

15 Непомеченные 6-регулярные карты..................104