Комбинаторные 2-усеченные кубы и приложения тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

Математический институт им. В. А. Стсклова РАН

Отдел геометрии и топологии

На правах рукописи УДК 514.172.45

Володин Вадим Дмитриевич Комбинаторные 2-усеченные кубы и приложения

Специальность: 01.01.04 - геометрия и топология

7 НОЯ 2013

АВТОРЕФЕРАТ диссертации па соискание ученой степени кандидата физико-математических паук

005537280

Москва - 2013

005537280

Работа выполнена в отделе геометрии и топологии Математического института им. В. А. Стеклова РАН

(

Научный руководитель: '

член-корреспоидспт РАН, доктор физико-математических наук, профессор Виктор Матвеевич Бухштабер.

Официальные оппоненты:

ведущий научный сотрудник Лаборатории информационных технологии в управлении и робототехнике ФГБУН Санкт-Петербургский институт информатики и автоматизации РАН, доктор физико-математических наук, профессор Гаяпе Юрьевна Панина,

старший научный сотрудник ФГБУН Вычислительный центр им. А. А. Дородницина кандидат физико-математических наук Сергей Павлович Тарасов.

Ведущая организация:

ФГБУН Институт математики им. С. Л. Соболева Сибирского отделения

Защита диссертации состоится 28 ноября 2013г. в 14е2 па заседании диссертационного совета Д 002.022.03 при МИАИ по адресу: 119991, Москва, ул. Губкина, д.8, конференц-зал (9 этаж).

С диссертацией можно ознакомиться в библиотеке МИ АН но адресу: 119991, Москва, ул. Губкина, д.8, 8 этаж. '

Автореферат разослан октября 2013г.

Ученый секретарь диссертационного совета

РАН.

Д 002.022.03 при МИАН, д. ф.-м. н. профессор

Общая характеристика работы

Актуальность темы

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

Важным комбинаторным инвариантом выпуклого многогранника является /-вектор, г-я компонента которого равна числу его ¿-.мерных граней. В случае простых многогранников особую роль играют также и "у-

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

Задача о верхних и нижних границах для /-векторов простых многогранников с фиксированным числом гиперграней решена Д. Барнсттом и П. МакМюллсиом. Фундаментальная задача описания условий на целочисленный вектор, необходимых и достаточных, чтобы он был /-вектором некоторого простого многогранника, была решена в Р. Стэнли, Л. Бнллсрой и К. Ли. Ответ в этой задаче был сформулирован МакМюлленом в виде гипотезы в терминах д-векторов. Первым необходимость условий Мак-Мюллсна доказал Стенли, используя что /?,-вектор простого многогранника совпадает с вектором четных чисел Бетти соответствующего торического многообразия (возможно, особого). Этот факт позволил свести задачу к задаче о коммутативных градуированных конечномерных алгебрах, порожденных элементами степени 2, и применить фундаментальные результаты алгебраической геометрии. Результат получил название д-тсоремы. В настоящее время имеется ряд доказательств (¡»-теоремы, основанных на связях выпуклых многогранников с другими разделами математики. Общая проблема описания /-векторов выпуклых многогранников до сих пор является открытой.

Множество выпуклых многогранников в К." является коммутативной полугруппой относительно суммы Минковского. Классическими являются задачи о многогранниках, представляющих собой сумму Минковского интервалов в К" (задачи о зонотопах). Обобщением этих задач являются

известные в выпуклой геометрии задачи о многогранниках в R", которые разлагаются в сумму Минковского некоторого множества симплексов. В работах Е.-М. Фейхтнср, Б. Стумфелс и А. Постникова было введено понятие производящего множества (building set) на [п + 1] как структуры на системе подмножеств множества из (п + 1) точки. Каждому подмножеству из этой системы канонически сопоставляется симплекс в Rn+1 и доказывается, что сумма Минковского всех таких симплексов является простым многогранником. позже названным иестоэдром. Термины building set и nested set восходят к известной задаче о топологии дополнения конфигурации подпространств в Ж". Впервые они появляются в работах К.деКончини и К. Прочези.

Благодаря симнлектической геометрии появились простые многогранники Дельзанта. Каждому такому многограннику Р" соответствует га-мильтоново торическое многообразие М2п, для которого он является образом отображения моментов. Классический результат торической геометрии утверждает, что нечетные числа Бетти b2i~i(M2n) нулевые, а четные b2i(M2n) равны г-м компонентам h-вектора многогранника Р". Существует взаимно однозначное соответствие между многогранниками Дельзанта и гамильтоновыми торическими многообразиями. Таким образом, задача описания /i-вскторов многогранников Дельзанта эквивалентна важной задаче описания векторов чисел Бетти гамильтоновых торичсских многообразий.

Замечательно, что каждый нестоэдр является многогранником Дельзанта (непосредственное доказательство следует из результатов Е.-М. Фейхтнер и Б. Стумфелс). Таким образом, мы имеем широкий класс многогранников Дельзанта. Не менее замечательным является тот факт, что каждому графу на множестве из (n + 1) вершины соответствует производящее множество на [п+1], составленное из множеств вершин связных подграфов данного графа. Таким образом, множество нестоэдров включает в себя большой подкласс простых многогранников, названных граф-ассоциэдрами.

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

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

С. Девадосс, Т. Хит и В. Виписыакул показали, что некоторые разбиения пространств модулей ориентируемых поверхностей с отмеченными точками являются многогранными. В их работе вводится класс простых флаговых многогранников, граф-кубиэдров, как обобщение многогранников, отвечающих пространствам модулей. Граф-кубиэдр строится по графу как многогранник, полученный из куба определенной последовательностью срезок граней (произвольной размерности).

Выпуклый многогранник называется флаговым, если любой набор его ноиарно пересекающихся граней имеет непустое пересечение. Среди нсстоэдров много флаговых многогранников, например, каждый граф-ассоциэдр является флаговым многогранником. С флаговыми простыми многогранниками связана известная гипотеза Черни-Дэвиса, которая формулируется в терминах /¿-векторов. Эта гипотеза, подсказана САТ(О) неравенствами Громова. Плодотворное обобщение этой гипотезы нашел С. Гал: компоненты 7-вектора флагового простого многогранника неотрицате-лены. В работе С. Гала, где сформулирована эта гипотеза, она доказана для многогранников, размерность которых не превосходит пяти. В работе А. Постникова, В. Райнера и Л. Виллиамс показано, что для класса так называемых хордовых производящих множеств неетоэдры удовлетворяют гипотезе Гала. В работах Н. Ероховца и А. Фенн эта гипотеза разными способами доказана для нсстоэдров, отвечающих полным двудольным графам. Соответствующие производящие множества в этом случае не являются хордовыми.

В работе Э.Нево и Т. Петерсона представлена гипотеза, усиливающая гипотезу Гала: 7-вектор флагового простого многогранника реализуется как /-вектор некоторого симплициального комплекса. Эта гипотеза накладывает- дополнительные условия на 7-векторы простых флаговых многогранников, вытекающие из известных неравенств Крускала-Катона для /-векторов симплициальных комплексов. В той же работе требуемые комплексы построены для некоторых серий многогранников, в частности для многогранников Сташефа и многогранников Ботта-Таубса. В работе Н. Айсбет требуемые комплексы построены для флаговых нсстоэдров. Приведенная там конструкция опиралась на специфику производящих мно-

з

жеств и использовала результат автора о том, что каждый флаговый нссто-эдр является 2-усечеииым кубом, т.е. может быть получен из куба срезками граней коразмерности 2.

Цель работы.

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

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

В диссертации получены следующие основные результаты:

1. Введен и исследован класс 2-усеченных кубов. Показано, что флаговые нестоэдры, граф-ассоциэдры и граф-к.убиэдры являются 2-усеченными кубами.

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

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

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

Основные методы исследования.

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

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

Апробация работы.

Результаты диссертации докладывались на следующих научно-исследовательских семинарах и научных конференциях:

1. Семинар «Алгебраическая топология и сё приложения» им. М. М. Постникова под руководством чл.-корр. РАН В. М. Бухнггабера, проф. А. В. Чернавского, проф. И.А.Дынникова, проф. Т.Е.Панова, доц. Л.А.Алания и доц.

Д. В. Миллиошцикова, МГУ, 2010 г и 2012 г.;

2. Международная конференция «Ломоносов 2010», г. Москва, 12-15 апреля 2010 г.;

3. Международная конференция «Геометрия, топология, алгебра и теория чисел, приложения», посвященная 120-летию Б. Н. Делоне, г.Москва, 16-20 августа 2010 г.;

4. Семинар «Выпуклые многогранники» под руководством проф. Н. П. Долбилина, МГУ, 2011г.;

5. Международная конференция «Торическая топология и автоморфные функции», г. Хабаровск, 5-10 сентября 2011 г.;

6. Семинар «Геометрия в целом» иод руководством нроф. И. X. Сабитова, МГУ, 2012 г..

7. Семинар «Теория сложности» под руководством к.ф.-м.н. С. П. Тарасова, ВЦ РАН, 2012 г..

8. Международная Конференция «Александровские чтения», г. Москва, 21-25 мая 2012 г.;

9. Poster session, 6th European Congress of Mathematics, Krakow, 1-7 June, 2012;

10. Международная конференция «Дискретная геометрия», посвященная 100-летию А.Д.Александрова, г. Ярославль, 13-18 августа 2012 г.;

11. Семинар «Дискретная и комбинаторная геометрия» иод руководством к.ф.-м.н. О. Мусина, д.ф.-м.н. А. Гайфуллина, и проф. Г. Кабатянского, ИППИ, 2013 г..

Публикации.

Основное содержание диссертации опубликовано в четырех работах, список

которых приведен в конце автореферата |1-4].

Структура и объем диссертации.

Диссертационная работа изложена на 80 страницах и состоит из введения, пяти глав и приложения. Библиография включает 60 наименований.

Краткое содержание работы

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

Содержание главы 1

В главе 1 вводятся понятия простых и флаговых многогранников, а также их перечисляющих полиномов, включая важные для флаговых простых многогранников 7-полиномы. Рассматривается кольцо простых многогранников, введенное В. М. Бухштабером. Формулируются хорошо известные свойства рассматриваемых многогранников. Дается описание важного для работы класса многогранников, нестоэдров, доказываются некоторые вспомогательные утверждения про этот класс многогранников.

Содержание главы 2

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

Исследуются перечисляющие полиномы 2-усечеченных кубов. В результате индукции по числу срезанных граней для данного класса доказывается положительное решение известной гипотезы Гада, утверждающей, что коэффициенты 7-вектора флагового простого многогранника неотрицательны.

Предложение 1. Для любого 2-усечеиного куба Р выполнено 7¿(Р) > 0.

Далее доказывается положительное решение гипотезы Э. Нево и Т. Петерсена для 2-усеченных кубов. Эта гипотеза является усилением гипотезы Гала и утверждает, что для 7-всктор флагового простого многогранника реализуется как /-вектор некоторого симплициального комплекса.

Теорема 2. Для любого 2-усечениого куба Р существует флаговый сим-плициальпый комплекс АР, такой что 7(Р) = ДАр)-

Хорошо известные неравенства Франкла-Фюреди-Калаи, характеризуют /-вектора, симплициальных комплексов с хроматическим числом не более г, а теорема Э. Фрохмадера, утверждает, что /-вектор флагового симнли-циального комплекса реализуется как /-вектор сбалансированного симилн-циального комплекса. Благодаря этим результатам, как следствие получаются оценки на 7-вектора 2-усеченных кубов.

Следствие 3. Пусть Рп - 2-усечепиый куб размерности п, тогда:

1. 7о = 1;

2. 0 < 7,-1 < 7<0г, где >■ = [?]■

Операция определяется в тексте диссертации.

Содержание главы 3

В главе 3 показывается, что многие важные классы простых многогранников являются 2-усечснными кубами.

Для флаговых нестоэдров (рассмотренных в главе 1) сначала доказывается более сильное свойство: если В\ и В2 - связные флаговые производящие множества на [га + 1] и В г С В2, тогда РВг получается из Рв, последовательной срезкой гранен коразмерности 2. Как следствие, получается желаемый факт.

Теорема 4. Каждый флаговый иестоэдр является '¿-усеченным кубом.

Доказательство данной теоремы даст алгоритм, с помощью которого можно получить заданный флаговый нестоэдр из куба последовательное™ срезок граней коразмерности 2. В результате применения этого алгоритма к многогранникам Сташефа получаются ранее не известные геометрические реализации многогранников Сташефа как многогранников Дельзанта.

Далее вводится класс многогранников, называемый обобщенными ассо-циэдрами. Каждый такой многогранник соответствует некоторой конечной системе корней (или диаграмме Дынкина). Хорошо известно, что обобщенные ассоциэдры серии А комбинаторно эквивалентны многогранникам Сташефа, а обобщенные ассоциэдры серий В и С комбинаторно эквивалентны многогранникам Ботга-Таубеа. Многогранники Сташефа и Ботта-Таубса

входят в число флаговых нестоэдров, потому являются 2-усечснньши кубами. Для обобщенных ассоциэдров серии О приводится следующий результат, полученный М.Горским.

Теорема 5 (М.Горский, 2010). Обобщенные ассоциэдры типа Д, являются 2-усеченными кубами. Но при п > 4 обобщенные ассоциэдры типа Пп не являются нестоэдрами.

Далее рассматривается класс многогранников под названием граф-кубиэдры, введенный в работе авторов С.Девадосс, Т. Хит и В. Виписмакул. Такие многогранники связаны с разбиениями пространств модулей ориентируемых поверхностей с отмеченными точками. Граф-кубиэдры по определению получаются из куба срезкой граней (произвольной размерности), соответствующих элементам графического производящего множества. В диссертации вводится обобщение этого класса многогранников до многогранников, соответствующих произвольному производящему множеству. Используя данное обобщение доказывается следующий факт.

Теорема 6. Каэ/сдый граф-кубиэдр является 2-усеченным кубом.

Содержание главы 4

В главе 4 рассматриваются подклассы граф-ассоциэдров, соответствующие связным графам, двусвязньш графам и деревьям. Приводятся две конструкции, которые позволяют получить (п + 1)-мсрный граф-ассоциэдр из п-мерного с помощью умножения на отрезок и срезок некоторых граней коразмерности 2 оснований полученного цилиндра. С помощью данных конструкций получаются индуктивные формулы для перечисляющих полиномов серий многогранников (ассоциэдры, циклоэдры, пермутоэдры и стэллоэдры). Эти формулы эквивалентны дифференциальным и функцио-ныльным уравнениям на производящие функции перечисляющих полиномов данных серий многогранников. Некоторые из указанных формул получены В. М. Бухштабером с использованием свойств введенного им кольца простых многогранников. Благодаря приведенным конструкциям и индуктивным формулам получаются основные результаты данной главы, точные верхние и нижние оценки для перечисляющих векторов рассматриваемых семейств.

Теорема 7. Имеют место следующие тонные оценки:

1) 7¿(Ав") < 7£(Рг„+1) < и{Реп) для любого связного графа Г„+1 на [п+1];

2) 7г(Суп) < 7г(-Рг„+1) < (>ЛЯ любого дву связного графа Г„+1 на [п+1];

3) 7¡(Лй") < ц{Рг,^) < п№п) для дерева Г„+1 на \п + 1].

Более того, аналогичные оценки верны для ¡-.у- и к-векторов и достигаются, только па. указанных сериях многогранников.

Содержание главы 5

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

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

Доказательство осуществляется введением отношения порядка на множестве флаговых симплициальных 3-многогранников: Р\ < Р>, если Рг получается из Р\ последовательностью стягиваний ребер, в которой все промежуточные многогранники флаговые.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю члену-корреспонденту РАН, профессору Виктору Матвеевичу Бухштаберу за постановки задач и постоянное внимание. Автор благодарен Т. Е. Панов}', Н. Ю. Ероховцу, п А. А. Гайфуллину за полезные обсуждения. Автор также благодарен всему коллективу кафедры высшей геометрии и топологии механико-математического МГУ и отделу геометрии и топологии МИАН за поддержку и внимание.

э

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

[1] В. M. Бухштабер, В.Д.Володин, Точные верхние и нижние границы для иестоэдров. Изв. РАН. Сер. ма-тем., 75:6 (2011), 17-46.

[2| V. M. Buchstabcr, V. D.Volodin, Combinatorial 2-truncated cubes and applications, Associahedra, Tamari Lattices, and Related Structures, Tamari Memorial Festschrift, Progress in Mathematics, Vol. 299, pp 161186, 2012.

|3] В.Д.Володин, Кубические реализации флаговых иестоэдров и доказательство гипотезы Гала для них, УМН, 65:1(391) (2010), 183-184.

[4] В.Д.Володин, Геометрическая реализация ■у-векторов 2-усечениых кубов, УМН, 67:3(405) (2012), 181-182.

iO

Подписано в печать 19.09.2013 г. Печать трафаретная. Усл. печ. л. - 0,6 Заказ № 2627 Тираж: 100 экз. Типография «Sanprint®» 119334, Москва, Ленинский пр-т. Д.37А (495) 626-42-43 www.sanprint.ru / www.sanpromo.ru

РОССИЙСКАЯ АКАДЕМИЯ НАУК МАТЕМАТИЧЕСКИЙ ИНСТИТУТ ИМ. В. А. СТЕКЛОВА

На правах рукописи

¡м^,,,/«, УЛК 514 172 45

и<г¿и 1 гот-о N ^дп

Володин Вадим Дмитриевич

Комбинаторные 2-усеченные кубы и приложения

01.01.04 — геометрия и топология

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: член-корреспондент РАН, профессор В. М. Бухштабер

Москва — 2013

Оглавление

Введение 3

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

Введение

Выпуклый многогранник размерности п называется простым, если каждая его вершина принадлежит ровно п гиперграням. Такие многогранники естественно возникают и играют важную роль в современной алгебраической и симплектической геометрии, алгебраической топологии и теории особенностей. Они являются ключевыми объектами торической геометрии и торической топологии (см. [В11], [БП]).

Важным комбинаторным инвариантом выпуклого многогранника является /-вектор, г-я компонента которого равна числу его г-мерных граней. В случае простых многогранников важную роль играют также д-,Н-и 7-векторы, которые получаются из /-вектора применением соответствующих невырожденных линейных операторов. В терминах этих векторов формулируются комбинаторные свойства как всех простых многогранников, так и их специальных классов.

Задача о верхних и нижних границах для /-векторов простых многогранников с фиксированным числом гиперграней решена в [Ва1],[Ва2] и [Мс1]. Фундаментальная задача описания условий на целочисленный вектор, необходимых и достаточных, чтобы он был /-вектором некоторого простого многогранника, была решена в [ВЬ], [Б^. Ответ в этой задаче был сформулирован П. МакМюлленом (см. [Мс2]) в виде гипотезы в терминах ^-векторов. Первым необходимость условий МакМюллена доказал Р. Стенли (см. [Б^), используя что /¿-вектор простого многогранника совпадает с вектором четных чисел Бетти соответствующего торического многообразия (возможно, особого). Этот факт позволил свести задачу к задаче о

коммутативных градуированных конечномерных алгебрах, порожденных элементами степени 2, и применить фундаментальные результаты алгебраической геометрии. Результат получил название ^-теоремы. В настоящее время имеется рад доказательств g-теоремы, основанных на связях выпуклых многогранников с другими разделами математики (см. [МсЗ], [Мс4], [Ти]). Общая проблема описания /-векторов выпуклых многогранников до сих пор является открытой (см. [Zi2]).

Множество выпуклых многогранников в Rn является коммутативной полутруппой относительно суммы Минковского. Классическими являются задачи о многогранниках, представляющих собой сумму Минковского интервалов в Rn (задачи о зонотопах). Обобщением этих задач являются известные в выпуклой геометрии задачи о многогранниках в Rn, которые разлагаются в сумму Минковского некоторого множества симплексов. В работах [FS] и [Ро] было введено понятие производящего множества (building set) на [n +1] как структуры на системе подмножеств множества из (п + 1) точки. Каждому подмножеству из этой системы канонически сопоставляется симплекс в Rn+1 и доказывается, что сумма Минковского всех таких симплексов является простым многогранником, позже названным нестоэдром в работе [PRW]. Термины building set и nested set восходят к известной задаче о топологии дополнения конфигурации подпространств в Rn. Впервые они появляются в работах [DP], [FMc], [FK].

Благодаря симплектической геометрии появились простые многогранники Дельзанта. Каждому такому многограннику Рп соответствует га-ми льтоново торическое многообразие М2п, для которого он является образом отображения моментов. Классический результат торической геометрии (см. [Да]) утверждает, что нечетные числа Бетти fe2i-i(-^2n) нулевые, а четные Ь2г(М2п) равны г-м компонентам /г-вектора Рп. Существует взаимно однозначное соответствие между многогранниками Дельзанта и га-мильтоновыми торическими многообразиями (см. [Del],[CdS]). Таким образом, задача описания h-векторов многогранников Дельзанта эквивалентна важной задаче описания векторов чисел Бетти гамильтоновых торических

многообразий.

Замечательно, что каждый нестоэдр является многогранником Дель-занта (непосредственное доказательство следует из результатов [ЕЭ]). Таким образом, мы имеем широкий класс многогранников Дельзанта. Не менее замечательным является тот факт, что каждому графу на множестве из (п + 1) вершины соответствует производящее множество на [п + 1], составленное из множеств вершин связных подграфов данного графа. Таким образом, множество нестоэдров включает в себя большой подкласс простых многогранников, названных в работе [СГ>] граф-ассоциэдрами.

К граф-ассоциэдрам привлечено большое внимание, т.к. они являются обобщением таких важных в топологии, алгебре и комбинаторике, а также математической и статистической физике (см. [МБ8]) многогранников как ассоциэдры (многогранники Сташефа), циклоэдры (многогранники Ботта-Таубса), пермутоэдры и стеллоэдры. С другой стороны соответствие (граф—^нестоэдр) устанавливает связь классической теории графов с теорией простых многогранников и позволяет строить инварианты графов в терминах комбинаторной структуры нестоэдров и, наоборот, выделять важные классы граф-ассоциэдров, вводить конструкции граф-ассоциэдров, используя понятия и результаты классической теории графов. Например, в рамках данной диссертации изучаются нестоэдры, отвечающие двусвязным графам и деревьям.

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

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

ассоциэдр является флаговым многогранником. С флаговыми простыми многогранниками связана известная гипотеза Черни-Дэвиса (см. [ChD], [БП]), которая формулируется в терминах h-векторов. Эта гипотеза подсказана САТ(О) неравенствами Громова. Плодотворное обобщение этой гипотезы нашел С. Гал: компоненты 7-вектора простого флагового многогранника неотрицателены. В работе [Gal], где сформулирована эта гипотеза, она доказана для многогранников, размерность которых не превосходит пяти. В работе [PRW] показано, что для класса так называемых хордовых производящих множеств нестоэдры удовлетворяют гипотезе Га-ла. В работах [Ер] и [Fe] эта гипотеза разными способами доказана для нестоэдров, отвечающих полным двудольным графам. Соответствующие производящие множества в этом случае не являются хордовыми.

В работе [NP] представлена гипотеза, усиливающая гипотезу Гала: 7-вектор флагового простого многогранника реализуется как f-вектор некоторого симплициального комплекса. Эта гипотеза накладывает дополнительные условия на 7-векторы простых флаговых многогранников, вытекающие из известных неравенств Крускала-Катона для /-векторов симплициальных комплексов. В [NP] требуемые комплексы построены для некоторых серий многогранников, в частности для многогранников Сташе-фа и многогранников Ботта-Таубса. В работе [Ai] требуемые комплексы построены для флаговых нестоэдров. Приведенная там конструкция опиралась на специфику производящих множеств и использовала результат автора (см. главу 3.1 или [VI],[В1]) о том, что каждый флаговый нестоэдр является 2-усеченным кубом, т.е. может быть получен из куба срезками граней коразмерности 2.

В работе [Bul] Д-вектору выпуклого многогранника сопоставлен полином Н от двух переменных, который в случае простых многогранников является симметрическим. Это позволяет ввести 7-вектор как вектор коэффициентов полинома Н, записанного как полином от элементарных симметрических полиномов. В работах [VI, В1] было замечено, что при срезке грани коразмерности 2 простого многогранника 7-вектор изменяется сле-

дующим образом.

Предложение. Пусть многогранник <5 получен из простого п-многогранника Р срезкой грани С коразмерности 2, тогда

7(3) = 7 (Р) + Т7(С).

Известно, что 7-вектор куба равен (1,0,..., 0). Используя это предложение было доказано важное свойство комбинаторных 2-усеченных кубов, т.е. многогранников полученных из куба последовательностью срезок граней коразмерности 2.

Предложение. Каждый 2-усеченный куб имеет неотрицательный 7-вектор, т.е, удовлетворяет гипотезе Гала.

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

Теорема. Каждый флаговый нестоэдр является 2-у сеченным кубом.

На основе полученных выше фактов построены новые геометрические реализации многогранников Сташефа как многогранников Дельзанта. Эти реализации не являются аффинно-эквивалентными известным реализациям многогранников Сташефа, рассматриваемым в [Ви2, СЪ, Ьо].

В совместных работах [БВ, ВУ] (которые являются развитием работ [VI, В1]) исследовались различные подклассы 2-усеченных кубов. В

частности, исследована комбинаторика серий граф-ассоциэдров. Приведены конструкции, позволяющие срезкой граней коразмерности 2 получить n-мерный граф-ассоциэдр из цилиндра над (п — 1)-мерным граф-ассоциэдром. С помощью данных конструкций были получены дифференциальные и функциональные уравнения на производящие функции перечисляющих полиномов ассоциэдров Asn, циклоэдров Суп, пермутоэдров Реп и стеллоэдров Stn. Некоторые из этих уравнений были получны ранее в [Bul] с помощью алгебры простых многогранников. Были получены точные верхние и нижние границы для перечисляющих векторов граф-ассоциэдров.

Теорема. Имеют место следующие оценки:

1) тi(Asn) < 7¿(Pr„+1) < 7i(Pen), если Г„+1 - связный граф на [п + 1];

2) тi(Cyn) < 7¿(Prn+i) < 7¿(Pen), если Гп+1 - двусвязный граф на [гг+1];

3) ji(Asn) < 7¿(Prn+1) < 7i(Stn), если Гп+1 - дерево на [п + 1];

Аналогичные неравенства имеют место для /-, д- и h-векторов. Более того, данные границы являются неулучшаемыми и достигаются только на указанных многогранниках.

В работе [BV] также изучаются граф-кубиэдры, введенные в работе [DHV] как обобщение многогранников, отвечающих пространствам модулей. Граф-кубиэдры обобщаются до так называемых обобщенных несто-эдров (англ. термин nested polytopes), задаваемых производящими множествами. Это позволяет доказать, что последовательность срезок граней (произвольной размерности) из определения граф-кубиэдра можно заменить на последовательность срезок граней коразмерности 2.

Теорема. Каждый граф-кубиэдр является 2-усеченным кубом.

В работах [БВ, BV] подробно исследована связь производящих множеств и соответствующих нестоэдров, в частности получены следующие результаты.

• Найдено необходимое и достаточное условие на производящее множество, при выполнении которого нестоэдр является флаговым многогранником.

• Найдено необходимое и достаточное условие на производящее множество, при выполнении которого нестоэдр является произведением симплексов.

В работе [В2] для семейства 2-усеченных кубов доказывается гипотеза о реализации 7-векторов простых флаговых многогранников /-векторами симплициальных комплексов, поставленная в [ЫР]. Для доказательства следующей теоремы введена конструкция, которая 2-усеченному кубу Р с заданной последовательностью срезок граней сопоставляет симплициаль-ный комплекс Д(Р). Симплициальный комплекс называется флаговым, если его он не содержит недостающих граней.

Теорема. Для произвольного 2-усеченного куба Р симплициальный комплекс А(Р) является флаговым и /(Д(Р)) = 7(Р).

Согласно [Ег], /-вектор любого флагового симплициального комплекса является /-вектором некоторого сбалансированного симплициального комплекса. Используя неравенства Франкла-Фюреди-Калаи (см. [Рт]) для /-векторов симплициальных комплексов, получены дополнительные условия на 7-векторы 2-усеченных кубов.

Следствие. Пусть Рп - 2-усеченный куб, тогда 0 < 7*+1 < где

г = [|]. Здесь - аналог комбинаторной степени.

Срезка грани коразмерности 2 простого многогранника двойственна звездному подразделению вдоль ребра (кратко, реберному подразделению) границы симплициального многогранника. Операция реберного подразделения у симплициального комплекса является в определенном смысле правой обратной операцией к стягиванию ребра.

Симплициальные многогранники, двойственные 2-усеченным кубам (реберные подразделения кросс-политопов), могут быть приведены к

кросс-политопу стягиваниями ребер. Однако, уже в размерности 3 существует пример (икосаэдр) флагового симплициального многогранника, не являющегося реберным подразделением октаэдра, но приводимого к октаэдру стягиванием ребер.

В работе [У2] было получено следующее важное свойство флаговых симплициальных многогранников.

Теорема. Любой трехмерный флаговый симплициальный многогранник может быть приведен к октаэдру последовательностью стягиваний ребер так, что все промежуточные многогранники будут флаговыми.

Глава 1

Выпуклые многогранники

1.1 Простые и симплициальные многогранники

Определение 1.1. Выпуклым многогранником называется выпуклая оболочка конечного набора точек в некотором пространстве Мп.

Определение 1.2. Выпуклым полиэдром называется пересечение Р конечного набора полупространств в некотором пространстве Мп:

Р={хеШп : (и, х) < аи г = 1,..., ш}, (1.1)

где ¿г е (Еп)* - некоторые линейные функции, щ е К, г = 1,... ,ш. Ограниченный выпуклый полиэдр называется выпуклым многогранником.

Два предыдущих определения эквивалентны, т.е. подмножество в Е" является выпуклой оболочкой конечного числа точек тогда и только тогда, когда оно ограничено и является конечным пересечением полупространств.

Размерность многогранника - это размерность его аффинной оболочки. Далее мы будем предполагать, что п-мерный многогранник (п-многогранник) содержится в п-мерном объемлющем пространстве Аффинная гиперплоскость Н, пересекающая многогранник Рп называется

несущей (или опорной) гиперплоскостью, если многогранник целиком содержится в одном из определяемых ей замкнутых полупространств. В этом случае пересечение Рп Г\ Н называется гранью многогранника. Сам многогранник также считается гранью; остальные его грани называются собственными. Объединение всех собственных граней называется границей многогранника дРп. Каждая грань п-многогранника в свою очередь является многогранником размерности не выше п. Нульмерные грани называются вершинами, одномерные грани - ребрами, а грани коразмерности один - гипергранями.

Два многогранника Р\ С М"1 и Ръ С К"2 одной размерности называются аффинно эквивалентными (или аффинно изоморфными), если существует аффинное отображение М"1 ��