Содержание к диссертации
Введение
1 Выпуклые многогранники 11
1.1 Простые и симплициальные многогранники 11
1.2 Перечисляющие полиномы 14
1.3 Флаговые простые многогранники 16
1.4 Нестоэдры 17
2 Комбинаторные 2-усеченные кубы 26
2.1 Операция срезки грани и ее свойства 26
2.2 Дифференциальное кольцо 2-усеченных кубов 30
2.3 Геометрические реализации 2-усеченных кубов 31
2.4 Гипотеза Гала 32
2.5 Гипотеза Е. Нево и Т. Петерсена 33
3 Классы 2-усеченных кубов 39
3.1 Флаговые нестоэдры 39
3.1.1 Кубические реализации флаговых нестоэдров 42
3.2 Обобщенные ассоциэдры 46
3.3 Граф-кубиэдры и их обобщения 49
4 Перечисляющие полиномы серий 2-усеченных кубов 53
4.1 Индуктивные формулы для серий граф-ассоциэдров 53
4.1.1 Ассоциэдры 55
4.1.2 Циклоэдры 57
4.1.3 Пермутоэдры 60
4.1.4 Стеллоэдры 61
4.2 Точные верхние и нижние границы для семейств граф-ассоциэдров 63
4.3 Производящие функции семейств граф-ассоциэдров 64
5 Флаговые симплициальные сферы 66
5.1 Операция стягивания ребра и ее свойста 66
5.2 Комбинаторика флаговых симплициальных 3-многогранников 67
6 Приложения 71
6.1 Торические многообразия над 2-усеченными кубами 71
6.2 Мылые накрытия 2-усеченных кубов 72
- Перечисляющие полиномы
- Геометрические реализации 2-усеченных кубов
- Кубические реализации флаговых нестоэдров
- Пермутоэдры
Введение к работе
Актуальность темы
Выпуклый многогранник размерности п называется простым, соли каждая его вершина принадлежит ровно п гиперграням. Такие многогранники естественно возникают и' играют важную роль в современной алгебраической и симилсктичсской геометрии, алгебраической топологии и теории особенностей. Они являются ключевыми объектами торической геометрии и торической топологии.
Важным комбинаторным инвариантом выпуклого многогранника является /-вектор, г-я компонента которого равна числу его г-мерных граней. В случае простых многогранников особую роль играют также g-,h- и "у-вскторы, которые получаются из /-вектора применением соответствующих невырожденных линейных операторов. В терминах этих векторов формулируются комбинаторные свойства как всех простых многогранников, так и их специальных классов.
Задача о верхних и нижних границах для /-векторов простых многогранников с фиксированным числом гиперграней решена Д. Барнсттом и П. МакМюлленом. Фундаментальная задача описания условий на целочисленный вектор, необходимых и достаточных, чтобы он был /-вектором некоторого простого многогранника, была решена в Р. Стэнли, Л. Бнллсрой и К. Ли. Ответ в этой задаче был сформулирован МакМюлленом в виде гипотезы в терминах g-векторов. Первым необходимость условии Мак-Мюллсна доказал Стенли, используя что /?,-вектор простого многогранника совпадает с вектором четных чисел Бетти соответствующего торпческого многообразия (возможно, особого). Этот факт позволил свести задачу к задаче о коммутативных градуированных конечномерных алгебрах, порожденных элементами степени 2, и применить фундаментальные результаты алгебраической геометрии. Результат получил название g-тсоремы. В настоящее время имеется ряд доказательств g-теоремы, основанных на связях выпуклых многогранников с другими разделами математики. Общая проблема описания /-векторов выпуклых многогранников до сих пор является открытой.
Множество выпуклых многогранников в К." является коммутативной полугруппой относительно суммы Минковского. Классическими являются задачи о многогранниках, представляющих собой сумму Минковского интервалов в R" (задачи о зонотопах). Обобщением этих задач являются
известные в выпуклой геометрии задачи о многогранниках в Ш", которые разлагаются в сумму Минковского некоторого множества симплексов. В работах Е.-М. Фейхтнср, Б. Стумфелс и А. Постникова было введено понятие производящего множества [building set) на [п + 1] как структуры на системе подмножеств множества из (п + 1) точки. Каждому подмножеству из этой системы канонически сопоставляется симплекс в Rn+1 и доказывается, что сумма Минковского всех таких симплексов является простым многогранником, позже названным пестоэдром. Термины building set и nested set восходят к известной задаче о топологии дополнения конфигурации подпространств в Шп. Впервые они появляются в работах К. де Кончини и К. Прочсзи.
Благодаря симнлектической геометрии появились простые многогранники Дельзанта. Каждому такому многограннику Р" соответствует га-мильтоново торическое многообразие М2", для которого он является образом отображения моментов. Классический результат торической геометрии утверждает, что нечетные числа Бетти b2i-i(M2n) нулевые, а четные b2i(M2n) равны г-м компонентам ft-вектора многогранника Р". Существует взаимно однозначное соответствие между многогранниками Дельзанта и гамильтоновыми торическими многообразиями. Таким образом, задача описания /i-вскторов многогранников Дельзанта эквивалентна важной задаче описания векторов чисел Бетти гамильтоновых торических многообразий.
Замечательно, что каждый нсстоэдр является многогранником Дельзанта (непосредственное доказательство следует из результатов Е.-М. Фейхтнср и Б. Стумфелс). Таким образом, мы имеем широкий класс многогранников Дельзанта. Не менее замечательным является тот факт, что каждому графу на множестве из (n + 1) вершины соответствует производящее множество на [п+1], составленное из множеств вершин связных подграфов данного графа. Таким образом, множество нсстоэдров включает в себя большой подкласс простых многогранников, названных граф-ассоциэдрами.
К граф-ассоциэдрам привлечено большое внимание, т.к. они являются обобщением таких важных в топологии, алгебре и комбинаторике, а также математической и статистической физике многогранников как ассоциэдры (многогранники Сташефа), циклоэдры (многогранники Ботта-Таубса), пер-мутоэдры и стеллоэдры. С другой стороны соответствие (граф-)-нестоэдр) устанавливает связь классической теории графов с теорией простых многогранников и позволяет строить инварианты графов в терминах комбина-
торной структуры нсстоэдров и, наоборот, выделять важные классы граф-ассоциэдров, вводить конструкции граф-ассоциэдров, используя понятия и результаты классической теории графов. Например, в диссертации изучаются нестоэдры, отвечающие двусвязным графам и деревьям.
С. Девадосс, Т. Хит и В. Виписмакул показали, что некоторые разбиения пространств модулей ориентируемых поверхностей с отмеченными точками являются многогранными. В их работе вводится класс простых флаговых многогранников, граф-кубиэдров, как обобщение многогранников, отвечающих пространствам модулей. Граф-кубиэдр строится но графу как многогранник, полученный из куба определенной последовательностью срезок граней (произвольной размерности).
Выпуклый многогранник называется флаговым, если любой набор его попарно пересекающихся граней имеет непустое пересечение. Среди нсстоэдров много флаговых многогранников, например, каждый граф-ассоциэдр является флаговым многогранником. С флаговыми простыми многогранниками связана известная гипотеза Черни-Дэвиса, которая формулируется в терминах /і-векторов. Эта гипотеза, подсказана САТ(О) неравенствами Громова. Плодотворное обобщение этой гипотезы нашел С. Гал: компоненты "/-вектора флагового простого многогранника неотрицате-леиы. В работе С. Гала, где сформулирована эта гипотеза, она доказана для многогранников, размерность которых не превосходит пяти. В работе А. Постникова, В. Райнера и Л. Виллиамс показано, что для класса так называемых хордовых производящих множеств нестоэдры удовлетворяют гипотезе Гала. В работах Н. Ероховца и А. Фснн эта гипотеза разными способами доказана для нсстоэдров, отвечающих полным двудольным графам. Соответствующие производящие множества в этом случае не являются хордовыми.
В работе Э.Нево и Т. Петерсона представлена гипотеза, усиливающая гипотезу Гала: "/-вектор флагового простого многогранника реализуется как f-вектор некоторого симплицшльного комплекса. Эта гипотеза накладывает' дополнительные условия на 7-векторы простых флаговых многогранников, вытекающие из известных неравенств Крускала-Катона для /-векторов симплициальных комплексов. В той же работе требуемые комплексы построены для некоторых серий многогранников, в частности для многогранников Сташефа и многогранников Ботта-Таубса. В работе Н. Айсбст требуемые комплексы построены для флаговых нсстоэдров. Приведенная там конструкция опиралась на специфику производящих мно-
жеств и использовала результат автора о том, что каждый флаговый нссто-эдр является 2-усечеииым кубом, т.е. может быть получен из куба срезками граней коразмерности 2.
Цель работы.
Настоящая работа посвящена развитию теории флаговых простых многогранников с целью исследовать их перечисляющие полиномы и построить класс многогранников, объединяющий известные семейства многогранников, возникших в ряде современных областей математики.
Научная новизна.
В диссертации получены следующие основные результаты:
-
Введен и исследован класс 2-усеченных кубов. Показано, что флаговые нестоэдры, граф-ассоциэдры и граф-кубиэдры являются 2-усеченными кубами.
-
Доказано, что для каждого 2-усеченного куба Р существует флаговый симплициальный комплекс, /-вектор которого совпадает с 7-вектором многогранника Р. Как следствие получены оценки на перечисляющие полиномы 2-усеченных кубов.
-
Показано, что любой трехмерный флаговый симплициальный многогранник может быть приведен к октаэдру последовательностью стягиваний ребер, так что все промежуточные многогранники будут флаговыми.
-
Получены точные верхние и нижние границы коэффициентов перечисляющих полиномов для граф-ассоциэдров, соотвествующих связным графам, для граф-ассоциэдров, соответствующих двусвязным графам и для граф-ассоциэдров, соответствующих деревьям.
Основные методы исследования.
В работе используются методы комбинаторики и выпуклой геометрии.
Теоретическая и практическая ценность работы.
Диссертация носит теоретический характер. Полученные в диссертации результаты представляют интерес для комбинаторики, выпуклой геометрии и торической топологии.
Апробация работы.
Результаты диссертации докладывались на следующих научно-исследовательских семинарах и научных конференциях:
1. Семинар «Алгебраическая топология и сё приложения» им. М. М. Постникова
под руководством чл.-корр. РАН В. М. Бухиггабера, проф. А. В. Чсрнавского,
проф. И.А.Дынникова, проф. Т.Е.Панова, доц. Л.А.Алания и доц.
Д. В. Миллионщикова, МГУ, 2010 г. и 2012 г.;
-
Международная конференция «Ломоносов 2010», г. Москва, 12-15 апреля 2010 г.;
-
Международная конференция «Геометрия, топология, алгебра и теория чисел, приложения», посвященная 120-летию Б. Н. Делоне, г.Москва, 16-20 августа 2010 г.;
-
Семинар «Выпуклые многогранники» под руководством ироф. Н. П. Долбилина, МГУ, 2011г.;
-
Международная конференция «Торическая топология и автоморфные функции», г. Хабаровск, 5-10 сентября 2011 г.;
-
Семинар «Геометрия в целом» под руководством проф. И. X. Сабитова, МГУ, 2012 г..
-
Семинар «Теория сложности» под руководством к.ф.-м.н. С. П. Тарасова, ВЦ РАН, 2012 г..
-
Международная Конференция «Александровские чтения», г. Москва, 21-25 мая 2012 г.;
-
Poster session, 6th European Congress of Mathematics, Krakow, 1-7 June, 2012;
-
Международная конференция «Дискретная геометрия», посвященная 100-летию А.Д.Александрова, г. Ярославль, 13-18 августа 2012 г.;
-
Семинар «Дискретная и комбинаторная геометрия» под руководством к.ф.-м.н. О. Мусина, д.ф.-м.н. А. Гайфуллина и проф. Г. Кабатянского, ИППИ, 2013 г..
Публикации.
Основное содержание диссертации опубликовано в четырех работах, список которых приведен в конце автореферата |1-4].
Структура и объем диссертации.
Перечисляющие полиномы
Два предыдущих определения эквивалентны, т.е. подмножество в Шп является выпуклой оболочкой конечного числа точек тогда и только тогда, когда оно ограничено и является конечным пересечением полупространств.
Размерность многогранника - это размерность его аффинной оболочки. Далее мы будем предполагать, что гг-мерный многогранник (п-многогранник) содержится в гг-мерном объемлющем пространстве Шп. Аффинная гиперплоскость Н, пересекающая многогранник Рп называется несущей (или опорной) гиперплоскостью, если многогранник целиком содержится в одном из определяемых ей замкнутых полупространств. В этом случае пересечение Рп П Н называется гранью многогранника. Сам многогранник также считается гранью; остальные его грани называются собственными. Объединение всех собственных граней называется границей многогранника дРп. Каждая грань гг-многогранника в свою очередь является многогранником размерности не выше п. Нульмерные грани называются вершинами, одномерные грани - ребрами, а грани коразмерности один - гипергранями.
Два многогранника Р\ С К"-1 и Р2 С К"-2 одной размерности называются аффинно эквивалентными (или аффинно изоморфными), если существует аффинное отображение К"4 — К"-2, устанавливающее взаимнооднозначное соответствие между точками этих многогранников. Два многогранника называются комбинаторно эквивалентными, если имеется взаимно-однозначное соответствие между их множествами граней, сохраняющее отношение включения, т.е. их множества граней изоморфны как частично упорядоченные множества. Заметим, что любые два аффинно изоморфных многогранника комбинаторно эквивалентны, но не наоборот, определение комбинаторной эквивалентности использует понятия частично упорядоченного множества и решётки.
Два различных определения выпуклых многогранников приводят к двум различным понятиям многогранников общего положения.
Набор из т п точек W1 находится в общем положении, если никакие п + 1 из них не лежат на одной аффинной гиперплоскости. Тогда, с точки зрения определения 1.1, выпуклый многогранник является многогранником общего положения, если он является выпуклой оболочкой набора точек в общем положении. Все собственные грани такого многогранника являются симплексами, то есть любая гипергрань имеет минимальное возможное число вершин (а именно, п). Такие многогранники называются симплициалъными. Заметим, что граница любого симплициального многогранника размерности п является симплициальным комплексом размерности (п — 1).
С другой стороны, скажем, что набор из т п гиперплоскостей ІіХ = СІІ, li Є (Ега) , х Є Ега, ЬІ Є Е (г = 1,... ,т) находится в общем положении, если никакая точка не содержится более чем в п гиперплоскостях из этого набора. С точки зрения определения 1.2, выпуклый многогранник Рп является многогранником общего положения, если ограничивающие его гиперплоскости находятся в общем положении. В каждой вершине такого многогранника Рп сходится в точности п гиперграней. Многогранники с таким свойством называются простыми. Заметим, что каждая грань простого многогранника есть снова простой многогранник.
Определение 1.4. Для любого выпуклого многогранника Р С Шп опре делим его полярное множество Р С (Ега) как Р = {І Є (Ега) : (/, х) 1 для всех х Є Р}. В выпуклой геометрии хорошо известно, что полярное множество Р является выпуклым полиэдром в двойственном пространстве (Кга) . Более того, если многогранник Р содержит 0 в своей внутренности, то Р является выпуклым многогранником (т.е. ограничен) и (р ) = Р; см., например, [Zil, 2.3]. Многогранник Р называется полярным (или двойственным) к Р. Частично упорядоченное множество граней многогранника Р получается из множества граней многогранника Р обращением отношения порядка. В частности, если Р — простой многогранник, то Р — симпли-циальный, и наоборот.
Пример. Любой многоугольник (2-многогранник) является одновременно простым и симплициальным. В размерностях больше 2 единственным многогранником, обладающим этим свойством, является симплекс. Куб является простым многогранником. Полярным многогранником для симплекса снова является симплекс. Полярным многогранником для трехмерного куба является октаэдр.
Для любых двух простых многогранников Pi и Р2, их произведение Р\ х Р2 снова является простым многогранником.
Геометрические реализации 2-усеченных кубов
В работе [Bui] было введено кольцо V простых многогранников. Как абеле-ва группа V является свободной группой, порожденной комбинаторными простыми многогранниками. Произведение в кольце задается декартовым произведением многогранников.
Кольцо V является биградуированным дифференциальным кольцом. Биградуированная компонента размерности (п,т — п) порождена п-мерными многогранниками с т гипергранями. Дифференциал d на элементах Р Є V определяется как формальная сумма гиперграней многогранника Р.
Определение 2.10. Многогранник Р называется неразложимым, если он не может быть представлен как декартово произведение многогранников менынеих размерностей.
В работе [БЕ] было доказано, что любой многогранник единственным образом представляется в виде произведения неразложимых многогранников. Следовательно, V является кольцом полиномов от переменных, соответствующих неразложимым простым многогранникам.
Очевидно, что произведение 2-усеченных кубов также будет 2-усеченным кубом. Рассмотрим подкольцо рсиЬе кольца V, порожденное 2-усеченными кубами.
Подколъцо Vcuhe является дифференциальным подколъцом V , изоморфным кольцу полиномов от, неразложимых 2-усеченных кубов. Доказательство. Для доказательства предложения достаточно убедить ся, что если произведение Р = Р\Х Р2 является 2-усеченным кубом, то мно гогранники Pi и Р2 также являются 2-усеченными кубами. Действительно, Pi и Р2 являются гранями 2-усеченного куба Рив силу предложения 2.9 сами являются 2-усеченными кубами. 2.3 Геометрические реализации 2-усеченных кубов
Предположим, что многогранник Р задан последовательностью срезок граней, то есть дана последовательность многогранников (/"", Р\,... , Р), в которой Pi+i получается из Pi срезкой грани Gi С РІ. Для реализации многогранника Р в пространстве W1 необходимо каждой гиперграни F С Р поставить в соответствие неравенство 1рХ Ьр. Здесь W1 и W1 отож-дествляются с помощью скалярного произведения. В качестве реализации стандартного куба Іп Є Кга возьмем множество {х Є Кга : 0 х% 1}.
Определим реализации остальных многогранников рекурсивно. Пусть Pj+i получается из Pi срезкой грани Gi С Р . При этом грань Gj является пересечением гиперграней Ріх и РІ2, а гипергрань сечения обозначим Fi С Pj+i.
Определение 2.12. Два выпуклых гг-мерных многогранника Р\ и Р в W1 называются аналогичными (см. например [Ти]), если между их гипергранями можно установить взаимно однозначное соответствие, такое что соответствующие гиперграни параллельны и аналогичны как (п— 1)-мерные многогранники в IR"--1 при параллельном переносе в одну гиперплоскость. Другими словами, два многогранника аналогичны, если их нормальные вееры совпадают. Любые два отрезка аналогичны по определению.
Описанная выше геометрическая реализация 2-усеченного куба Р однозначно определяется выбором последовательности срезок граней в классе аналогичных многогранников. Предложение 2.13. Пусть Р С Кп многогранник Делъзанта и G = Fi П Fk его грань, пусть многогранник Q получается из многогранника Р срезкой грани G так, что внешняя нормаль к гиперграни сечения F0 равна vo = v\ + Vk, где Vi - целочисленные примитивные внешние нормали к гиперграням Fj. Тогда многогранник Q является многогранником Делъзанта.
Доказательство. Необходимо лишь проверить, что для каждой новой вершины q многогранника Q (т.е. принадлежащей гиперграни Fo) внешние нормали, содержащие вершину q, образуют базис целочисленной решетки. В силу замечания 2.7, q = F0 П Fx П П Fk П G , где некоторое Fi пропущено, а пересечение G П G является вершиной в Р (т.е. в выражении F\ П П Ft П G некоторый Fj заменяется на Fo). Без ограничения общности полагаем, что г = 1.
Как известно, перечисляющие вектора простых многогранников полностью описаны. Этот результат носит название (/-теоремы. Аналогичный вопрос об ограничениях на перечисляющие вектора возникает и для класса флаговых простых многогранников.
В работе [ChD] сформулирована известная гипотеза Черни-Девиса, утверждающая, что для флагового многогранника четной размерности знакопеременная сумма компонент Л,-вектора неотрицательна. Это эквивалентно неотрицательности старшего коэффициента 7-вектора.
Гипотеза (Е. Nevo, K.Petersen, [NP], 2010). Для любого флагового многогранника Р существует симплициалъный комплекс А(-Р), такой что f-вектор комплекса А(Р) совпадает с -вектором Р.
В той же работе необходимые комплексы построены для многогранников Сташефа, многогранников Ботта-Таубса и пермутоэдров. В работе [Ai] гипотеза была доказана для всех флаговых нестоэдров. В рамках диссертационной работы был получен следующий результат. Теорема 2.16. Для любого 2-усеченного куба Р существует флаговый симплициалъный комплекс А(-Р), такой что j(P) = /(Д(Р)).
Пусть многогранник Р получен из многогранника Р путем 2-у сечения вдоль грани G С Р. В этом случае новая гипергрань сечения F0 будет, комбинаторно эквивалентна многограннику G х I. Произвольная грань Q многогранника Р либо не меняет, комбинаторный тип (при, Q D G или, Q П G = %), либо подвергается 2-усечению вдоль грани, Q П G. Поэтому, для каждой грани, многогранника Q С Р существует единственная грань Q С Р, такая что либо грань Q получена из грани, Q путем 2-у сечения вдоль грани, GC\Q, либо грань Q равна (или, аналогична) грани Q С Р, либо Q QxIcGxI.
Конструкция 2.18. Для Р = 1п имеем W(P) = 0, поэтому A(Q) = 0 для всех граней Q С Р. Предположим, семейство комплексов уже построено для всех граней многогранника Р, полученного из куба последовательностью 2-усечений граней, соответствующих гиперграням сечения F1;... , Fm_\ многогранника Р. Пусть многогранник Р получен из многогранника Р путем 2-усечения вдоль грани Gm С Р. Тогда, W(P) = W(P) U {w(Fm)}, где w(Fm) соответствует гиперграни Fm многогранника P.
Кубические реализации флаговых нестоэдров
Обобщенные ассоциэдры предсталяют еще один пример простых флаговых многогранников. Такие многогранники возникают в теории кластерных алгебр и являются двойственными к кластерным комплексам алгебр конечного типа (см. [FZ3]). Каждый такой многогранник канонически соответствует дизъюнктному объединению диаграмм Дынкина. Многогранники Сташефа соответствуют диаграммам Дынкина Ап, многогранники Ботта-Таубса соответствуют диаграммам Дынкина Вп и Сп.
Поскольку многогранники Сташефа и Ботта-Таубса реализуются как граф-ассоциэдры, они принадлежат классу 2-усеченных кубов. М. Горский получил следующий важный результат, схема доказательства которого будет изложена в настоящем разделе.
Для доказательства потребуются следующие известные факты: (і) Множество гиперграней многогранника Asn биективно соответствует множеству диагоналей (п-\- 3)-угольника. Две гиперграни пересекаются тогда и только тогда, когда соответствующие диагонали не имеют общих внутренних точек (см. [Lee]).
(ii) Множество гиперграней многогранника Dn биективно соответсв-тует Diag U D U D , где множество Diag состоит из неупорядоченных пар центрально симметричных (друг другу) диагоналей правильного 2п-угольника; каждое из множеств D и D состоит из диаметров 2гг-угольника. Удобно предполагать, что все диаметры множества D окрашены в один цвет, а все диаметры множества D - в другой. Две гиперграни пересекаются тогда и только тогда, когда они соответствуют парам диагоналей, не имеющих общих внутренних точек, либо диаметрам одного цвета, либо диаметрами разных цветов, соединяющих одинаковые противоположные точки (см. [FZ3]). Данные факты позволяют описать границу обобщенных ассоциэдров типа D.
Доказательство. У 2?г-угольника есть ровно п пар симметричных диаго налей, которые делит его на два (fc + З)—угольника и 2(п — к — 1)-угольник, содержащий центр. Легко видеть, что гипергрань многогранника Dn, соот ветствующая каждой такой паре, есть произведение Ask х Dn-k l, Кроме того, можно проверить также, что каждому из 2п крашеных диаметров соответствует гипергрань Dn, являющаяся Asa l. В качестве немедленного следствия предложения 1.19, описывающего комбинаторику нестоэдров, получаем следующее.
Предложение 3.15 (М.Горский, [Го], 2010). Пусть п-многогранник Р не разлагается в нетривиальное прямое произведение и имеет, не менее (2п + 3) гиперграней, не разлагающихся в нетривиальное прямое произведение. Тогда Р не является нестоэдром.
Доказательство. Предположим, что многогранник Р строится по неко торому производящему множеству В. Поскольку он не раскладывается в прямое произведение, производящее множество В связно. Нетрудно ви деть, что тогда В есть производящее множество на множестве [п + 1]. Определим, сколько у соответствующего ему многогранника может быть гиперграней, не раскладывающихся в нетривиальное прямое произведе ние. Из предложения 1.19 следует, что неразложимые гиперграни отвеча ют таким элементам производящего множества І Є В, что либо B\j, ли бо В/1 оказывается одноэлементным множеством. Это означает, что либо /, либо [п + 1]\/ - одноэлементное множество. Тогда таких / не больше 2(п + 1) = 2п + 2. Следовательно, у многогранника Р не более (2п + 2) неразложимых гиперграней. Мы пришли к противоречию с предположе нием, что и доказывает требуемое утверждение. Хорошо известно, что ассоциэдры не раскладываются в нетривиальное прямое произведение. Следовательно, используя предложения 3.14 и 3.15, по индукции получаем следующее.
Доказательство индукцией по п : можно показать, что Dn получается из Dn l х / последовательностью срезок граней коразмерности 2. Последовательность срезок можно выбрать так, что сначала срезаются (п — 1) граней нижнего основания Dn l х 0, затем грань, являющаяся пересечением гиперграней (одна из них получена срезкой, а другая лежит в Dn l х I) соответствующих двум диаметрам разных цветов, и далее срезаются (п—3) грани того же основания. Поскольку Dn является флаговым многогранником, его комбинаторная структура определяется попарными пересечениями гиперграней. В терминах диагоналей 2гг-угольника легко проверить, что данная процедура приводит к требуемому результату. Замечание 3.18. Используя консткрукцию из раздела J .2, можно явно определить последовательность срезок, приводящую многогранник jyn-i х j к многогранниКу Dn и определить явные выражения для полиномов j(Dn) через полиномы j(Dk) и j(Ask), к п. Также эти выражения можно получить, применяя технику производящих функции (см. [Bui]) к формуле из предложения З.Ц.
Пусть Г связный граф, а -В (Г) производящее множество. Следуя терминологии работы [DHV], элементы производящего множества В (Г) будем называть трубками (англ. термин tubes), а набор {Si,..., Sk} Є Af(B(T)) будем называть совместным набором трубок (англ. термин tubing).
Класс граф-кубиэдров был впервые введен в работе [DHV]. Для того, чтобы сформулировать определение, необходимо ввести понятие совместным набором фигурных трубок (англ. термин design tubing).
Определение 3.19. Пусть Г связный граф. Круглыми трубками (англ. термин round tube) будем называть множества вершин S графа Г, которые индуцируют связный подграф Г . Квадратными (англ. термин square tube) будем называть отдельные вершины S = {v} графа Г. Таким образом, каждая вершина образует одну круглую и одну квадратную трубку. Круглые и квадратные трубки в совокупности называются фигурными трубками (англ. термин design tubes) графа Г. Две фигурные трубки называются совместными, если выполнено одно из двух условий: 1) обе трубки круглые и совместны как обычные трубки графа Г; 2) обе трубки образованы разными вершинами и имеют разный тип.
Совместным набором трубок (англ. термин tubing) графа Г называется набор попарно совместных трубок графа Г. Для графа Г на п вершинах, определим комбинаторный гг-мерный куб Г, В котором каждая пара противоположных гиперграней соответствует некоторой вершине Г. А именно, одна из пары гиперграней соответствует круглой трубке, а другая соответствует квадратной трубке. Таким образом, грани куба будут соответствовать подмножествам вершин Г, где каждая вершина выбрана круглой или квадратной.
Определение 3.20. Пусть G простой граф на п вершинах. Будем срезать грани гг-мерного куба Пс, соответствующие совместным наборам круглых трубок так, что трубки с большим количеством вершин срезаются раньше, чем трубки с меньшим количеством вершин. Полученный многогранник CG называется граф-кубиэдром.
Теорема 3.21 ([DHV], Theorem 12). Для графа G на п вершинах граф-кубиэдр CG является простим п-мерным многогранником, частично-упорядоченное множество граней которого изоморфно частично-упорядоченному множеству совместных наборов фигурных трубок G.
Пермутоэдры
Важную роль в классификации трехмерных флаговых многогранников будет играть операция стягивания ребра. Эта операция двойственна операции объединения двух гиперграней путем стирания ребра (вместе с его вершинами) между ними.
Для симплициального комплекса данная операция кроме топологического стягивания ребра подразумевает отождествление всех кратных симплексов.
Если исходный комплекс является флаговой симплициальной сферой, то полученный комплекс может не быть таковым. После топологического стягивания ребра граница многогранника превращается в симплициально-клеточный комплекс, гомеоморфный сфере. Поэтому, комплекс может пе рестать быть гомеоморфным сфере только после отождествления кратных ребер и граней.
Если К2 флаговая симплициалъная сфера, то для любого ребра е комплекс К2/е является симплициалъной сферой, но необязательно флаговой. Доказательство. Если комплекс К2/е не является многогранным, то ис пользуя теорему Штейница можно показать, что найдется ребро е , содер жащее образ стянутого ребра е, такое что комплекс (К2/е) \ е является несвязным. Очевидно, что прообраз такого ребра является недостающей гранью в К2, что противоречит его флаговости.
Обратную операцию проще всего описать в двойственных терминах для простых трехмерных многогранников. Стягивание ребра у симплициаль-ной сферы двойственно стиранию ребра между двумя гипергранями простого многогранника. Операцию, обратную к стиранию ребра, можно описать следующим образом. Пусть Р - флаговый простой 3-многогранник, а F - его гипергрань. Пошевелим F двумя разными способами и получим две гиперграни F[ и F2, пересекающиеся по ребру е. Получившийся простой, но необязательно флаговый, многогранник обозначим через Q. Заметим, что Р получается из Q стиранием ребра е. Назовем описанную операцию разрезанием грани F на грани Fi и F2.
Введем частичный порядок на множестве флаговых симплициальных многогранников. Считаем Q Р, если Q может быть получен из Р последовательностью стягиваний ребер. Далее мы будем исследовать граф Г, определяемый данным частичным порядком, называемый диаграммой Хассе данного частично упорядоченного множества. Таким образом, минимальными относительно данного порядка будут многогранники, не допускающие стягивания ребер. Такие многогранники соответствуют начальным вершинам графа Г и далее будут называться минимальными.
Теорема 5.2. Пусть Р флаговый симплициалъный многогранник. Тогда существует последовательность стягиваний ребер, в результате которой получается октаэдр, а все промежуточные многогранники будут, флаговыми.
Следствие 5.3. Вершина графа Г, соответствующая октаэдру, является единственной начальной вершиной графа Г.
Определение 5.4. Скажем, что множество вершин {1 ,1 , 3, 4} симпли-циального многогранника образует пояс , если симплициальный подкомплекс, порожденный данными вершинами, является границей квадрата.
Лемма 5.5. Пусть К флаговая симплициалъная сфера, а е некоторое ее ребро . Симплициалъная сфера К/е является флаговой тогда и только тогда, когда е не содержится ни в одном поясе в К. Следствие 5.6. Пусть VK - вершина графа Г, соответствующая флаговой симплициалъной сфере К. Тогда число ребер Г, входящих в VK не превосходит, число ребер сфреры, К, не содержащихся ни в одном поясе. Доказательство. Идея доказательства заключается в том, что любой пояс в К является прообразом недостающего треугольника комплекса К /е. Если ребро е содержится в некотором поясе, то стягивание ребра е приведет к образованию недостающего треугольника в комплексе К /е. Допустим, после стягивания ребра е = {іі,іг} С К в вершину v полу ченный комплекс К/е стал не флаговым. Рассмотрим минимальную недо стающую грань V = {УІ}І комплекса К /е. Из минимальности недостающей грани V следует, что \V\ = 3, а в силу флаговости К имеем v Є V. Пусть V = {v,v3,V4}, тогда v3,V4 Є lk Wi U lk , но поскольку V . К/є, одна из вершин г з и г 4 не содержится в lkx г і, а другая не содержится в lk 1. Следовательно, { 1, 2, 3, 4} и есть искомый пояс. Лемма 5.7. Пусть К минимальный флаговый симплициальный комплекс. Тогда найдется вершина w, такая что ее линк lkKw является четырехугольником.
Доказательство. Каждый пояс делит К на две части W1 и W2. Рассмотрим некоторую вершину V.
Найдется пояс По, содержащий v, такой что любой пояс , содержащий v и пересекающий WQ пересекает WQ. Действительно, рассмотрим пояс Пі, содержащий v. Он разбивает К на две части W\ и W\. Если пояс П2 содержится в Пі U W\, то рассмотрим пояс П2. Он снова разбивает К на две части W\ и W2, причем W\ С W\. Далее продолжим выбирать П так что W} С W}_x. На некотором шаге эта последовательность прервется, и мы получим искомый пояс П0.
Пусть w Є П0 и {v,w} не ребро. Каждое ребро {w ,v},w Є WQ1 содержится в некотором поясе \3W/, пересекающем WQ. Очевидно, что По П nw/ = {w}. Следовательно, все вершины из WQ1, смежные с v смеж ны вершине w. В силу флаговости многогранника, других вершин WQ1 не содержит, а в силу минимальности многогранника {WQ1] = 1, а значит 1кк w = По. Доказательство теоремы 5.2. Пусть Р минимальный флаговый симпли циальный многогранник. Покажем, что Р - октаэдр. Пусть w - вершина из леммы 5.7. Рассмотри пояс Пі, содержащий w и пояс Пг, содержащий w и вершины из lkap w \ Пі. Поясы Пі и П2 пересекаются в вершине w, а значит имеют еще одну точку пересечения v, противоположную w. Та ким образом, симплициальный все вершины из Ikgpw смежны вершинам w и v. В силу флаговости, других вершин Р не имеет, и, следовательно эквивалентен октаэдру. П
Лемма 5.8. Пусть многогранник Q получен из флагового простого многогранника Р разрезанием грани F на грани F\ и F2. Многогранник Q является флаговым тогда и только тогда, когда ни одна из граней F\ и F2 не является треугольником. Доказательство. Необходимость отсутствия треугольников очевидна. Те перь допустим, что многогранник Q не является флаговым, а Т = {F{\j минимальный набор гиперграней, пересекающихся попарно, но не пересе кающихся в совокупности. Очевидно, что J\{Fi, F2} ф 0. Без ограничения общности считаем, что F\ Є Т. Если заменить F\ на F\ UF2, то полученный набор множеств будет иметь непустое пересечение в силу флаговости Р. Следовательно, все гиперграни из набора Т пересекаются с i , а значит грань i 2 является двумерным нефлаговым многогранником, т.е. треуголь ником.
Доказательство. Рассмотрим простой многогранник Р, двойственный К. Если Q - минимальный многогранник, который больше Р, то Q получается из Р разрезанием некоторой грани F на грани F\ и F2, не являющие треугольными. Если грань F имеет к вершин, то число способов разрезать ее указанным образом равно числу диагоналей fc-угольника, которое равно
