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

• Володин, Вадим Дмитриевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Володин, Вадим Дмитриевич

Оглавление

Введение

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

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

1.2 Перечисляющие полиномы

1.3 Флаговые простые многогранники

1.4 Нестоэдры

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

2.1 Операция срезки грани и ее свойства

2.2 Дифференциальное кольцо 2-усеченных кубов

2.3 Геометрические реализации 2-усеченных кубов

2.4 Гипотеза Гала

2.5 Гипотеза Е. Нево и Т. Петерсена

3 Классы 2-усеченных кубов

3.1 Флаговые нестоэдры

3.1.1 Кубические реализации флаговых нестоэдров

3.2 Обобщенные ассоциэдры

3.3 Граф-кубиэдры и их обобщения

4 Перечисляющие полиномы серий 2-усеченных кубов

4.1 Индуктивные формулы для серий граф-ассоциэдров

4.1.1 Ассоциэдры

4.1.2 Циклоэдры

4.1.3 Пермутоэдры

4.1.4 Стеллоэдры

4.2 Точные верхние и нижние границы для семейств граф-ассоциэдров

4.3 Производящие функции семейств граф-ассоциэдров

5 Флаговые симплициальные сферы

5.1 Операция стягивания ребра и ее свойста

5.2 Комбинаторика флаговых симплициальных 3-многогранников

6 Приложения

6.1 Торические многообразия над 2-усеченными кубами

6.2 Мылые накрытия 2-усеченных кубов

Введение диссертации (часть автореферата) на тему «Комбинаторные 2-усеченные кубы и приложения»

Введение

Выпуклый многогранник размерности п называется простым, если каждая его вершина принадлежит ровно п гиперграням. Такие многогранники естественно возникают и играют важную роль в современной алгебраической и симплектической геометрии, алгебраической топологии и теории особенностей. Они являются ключевыми объектами торической геометрии и торической топологии (см. [В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 —> М"2, устанавливающее взаимнооднозначное соответствие между точками этих многогранников. Два многогранника называются комбинаторно эквивалентнъши, если имеется взаимно-однозначное соответствие между их множествами граней, сохраняющее отношение включения, т.е. их множества граней изоморфны как частично упорядоченные множества. Заметим, что любые два аффинно изоморфных многогранника комбинаторно эквивалентны, но не наоборот, определение комбинаторной эквивалентности использует понятия частично упорядоченного множества и решётки.

Определение 1.3. Под комбинаторным многогранником мы будем понимать класс комбинаторно эквивалентных выпуклых многогранников.

Пример (симплекс и куб). Симплексом Дп размерности п называется выпуклая оболочка набора из (п + 1) точек в 1", не лежащих в одной аффинной гиперплоскости. Все грани п-симплекса являются симплексами размерности не более п. Любые два п-симплекса аффинно эквивалентны. Стандартным п-симплексом называется выпуклая оболочка точек (1,0,...,0), (0,1,...,0), ...,(0,...,0,1) и (0,...,0) в Кп. Эквивалентно, стандартный п-симплекс задаётся (п +1) неравенствами

Х{ > 0, г = 1,... ,п, и Х1 + ... + хп<1. (1.2)

Правильным п-симплексом называется выпуклая оболочка точек (1,0,. ..,0), (0,1,... ,0), ..., (0,...,0,1) в Еп+1.

Стандартным д-кубом называется выпуклый многогранник Iя С М9, задаваемый как

= {(Ш, ■•■,!/,) е 0 <а<1, г = 1,...,д}. (1.3)

Эквивалентно, стандартный д-куб есть вьшуклая оболочка 2я точек в М9, каждая из координат которых есть 0 или 1.

Два различных определения выпуклых многогранников приводят к двум различным понятиям многогранников общего положения.

Набор из т> п точек К" находится в общем положении, если никакие п + 1 из них не лежат на одной аффинной гиперплоскости. Тогда, с точки зрения определения 1.1, выпуклый многогранник является многогранником общего положения, если он является выпуклой оболочкой набора точек в общем положении. Все собственные грани такого многогранника являются симплексами, то есть любая гипергрань имеет минимальное возможное число вершин (а именно, п). Такие многогранники называются симплициальными. Заметим, что граница любого симплициального многогранника размерности п является симплициальным комплексом размерности (п — 1).

С другой стороны, скажем, что набор из т > п гиперплоскостей ^х = а*, и 6 (Мп)*, х 6 Мп, Ьг € Е (г = 1,..., т) находится в общем положении, если никакая точка не содержится более чем в п гиперплоскостях из этого набора. С точки зрения определения 1.2, выпуклый многогранник Рп является многогранником общего положения, если ограничивающие его гиперплоскости находятся в общем положении. В каждой вершине такого многогранника Рп сходится в точности п гиперграней. Многогранники с таким свойством называются простыми. Заметим, что каждая грань простого многогранника есть снова простой многогранник.

Определение 1.4. Для любого выпуклого многогранника Рс1п опре-

делим его полярное множество Р* С (Еп)* как

Р* = {I € (К")*: (I,х) < 1 для всех х е Р}.

В выпуклой геометрии хорошо известно, что полярное множество Р* является выпуклым полиэдром в двойственном пространстве (Еп)*. Более того, если многогранник Р содержит 0 в своей внутренности, то Р* является выпуклым многогранником (т.е. ограничен) и (Р*)* = Р, см., например, [¿И, §2.3]. Многогранник Р* называется полярным (или двойственным) к Р. Частично упорядоченное множество граней многогранника Р* получается из множества граней многогранника Р обращением отношения порядка. В частности, если Р — простой многогранник, то Р* — симпли-циальный, и наоборот.

Пример. Любой многоугольник (2-многогранник) является одновременно простым и симплициальным. В размерностях больше 2 единственным многогранником, обладающим этим свойством, является симплекс. Куб является простым многогранником. Полярным многогранником для симплекса снова является симплекс. Полярным многогранником для трехмерного куба является октаэдр.

Для любых двух простых многогранников Рх и Р2, их произведение Р\ х Р2 снова является простым многогранником.

1.2 Перечисляющие полиномы

Пусть fi - количество ¿-мерных граней простого п-многогранника Р. Набор чисел (/о,..., /п) многогранника Р называется его /-вектором. Классическим /-полиномом Р называется полином

/(р)(г) = г + Д-!*"-1 + • ■ • + д* + /0.

Классическим /«.-полиномом Р называется полином, полученный из / подстановкой (£ — 1) в качестве аргумента.

И{Р){1) = £п + Нп-гГ-1 + ••• + М + Ло = /(*-!)■

Коэффициенты (h0,..., hn) составляют /i-вектор многогранника Р. В работе [Bul] аналогично введены понятия F- и Я-полиномов Р двух переменных:

F(P)(a, t) = а11 + fn-Xan-4 + • • • + hatn~l + f0tn = anf(a/t).

H(P)(a,t) = hnan+hn-ian~1t+- ■ ■+hlatn~1+hotn = F(P)(a-t, t) = anh(a/t)

Набор чисел (go,9i, ■ ■ •,<?[§])> гДе до = 1, gi = К — hi-\,i > 0, называется ^-вектором простого многогранника Р.

Соотношения Дена-Соммервилля (см. [БП] и [Zil]) утверждают, что полином Н(Р) симметричен для простых многогранников, следовательно, может быть представлен как полином от элементарных симметрических полиномов a = a + tnb = at:

[-]

= + (1-4)

¿=o

Набор чисел (7о, 7ъ ■ ■ • > 7[f]) называется 7-вектором простого многогранника Р, а 7-полином многогранника Р определяется следующим образом:

7 (Р)(т) = 7о + 7ir +----1-

Лемма 1.5. Пусть Рг и - простые п-многогранники. Тогда неравенство (г) влечет неравенство (i + 1), где

(1) li(Pi) < ц{Р*),

(2) 9Í(Pi) < 9Í(P2),

(3) hi(Pi) < ЧР2),

(4) fi(Pi) < MP2).

Доказательство. Следующая формула для простых п-многогранников (см. [Bul]) доказывает (1) =>• (2).

Ь{Р) = {п- » + 1) ¿ (" - J)I<(Р)■ (1'5)

Следующие формулы, полученные из определений д- и /¿-векторов доказывает, что (2) (3) и (3) =>• (4).

В доказательстве мы воспользовались тем, что все коэффициенты формул неотрицательны. Отметим, что из нижних неравенств не следуют верхние, поскольку коэффициенты соответствующих формул будут иметь отрицательные коэффициенты. Например, коэффициенты полинома /г(/4) = /г(/)4 = (1 + £)4 превосходят коэффициенты полинома Д(Д2 х Д2) = /г(Д2)2 = (1 + £ + ¿2)2, но коэффициент при ¿2 у полинома 7(/4) = 7(/)4 = I4 = 1 меньше, чем у полинома

Определение 1.6. Пусть Г - простой граф на множестве вершин V. Кликой графа Г называется набор попарно инцидентных вершин графа Г. Кликовым комплексом называется симплициальный комплекс на множестве вершин V, состоящий из всех клик графа Г.

Определение 1.7. Симплициальный комплекс называется флаговым, если он совпадает с кликовым комплексом своего одномерного остова.

Определение 1.8. Простой многогранник называется флаговым, если любой набор его попарно пересекающихся граней (эквивалентно гиперграней) имеет непустое пересечение.

Заметим, граница флагового простого многогранника является флаговым симплициальным комплексом. Легко проверить, что произведение флаговых многогранников является флаговым многогранником, и каждая грань флагового многогранника является флаговым многогранником.

(1.6)

□

7(Д2 х Д2) = 7(Д2)2 = (1 - ¿)2.

1.3 Флаговые простые многогранники

Пример. Куб 1П является флаговым многогранником как произведение п отрезков.

Пример. Симплекс Дга не является флаговым многогранником при п > 2, поскольку все его гиперграни пересекаются попарно, но в совокупности имеют пустое пересечение.

1.4 Нестоэдры

В этом разделе мы сформулируем необходимые факты о нестоэдрах, а также исследуем некоторые их важные свойства. Недостающие доказательства их можно найти в рБ, Ро, 2е]. Обозначим через [п] и \ъ,]\ множества {1,...,п} и {г,...,.?'}.

Определение 1.9. Система В непустых подмножеств [п + 1] называется производящим множеством на [п + 1], если выполнены следующие условия:

1) Пусть Я2 е В и П Б2 ф 0, тогда ^ и Я2 <Е В-,

2) {г} е В для всех г е [п + 1].

Производящее множество В называется связным, если [п+1] 6 В.

Замечание 1.10. При работе с производящими множествами часто удобно рассматривать некоторое множество А, состоящее из п + 1 элемента вместо множества [п + 1]. Производящие множества рассматриваются с точностью до следующей эквивалентности: производящие множества В\ на А\ и В2 на А2 эквивалентны, если существует биек-ция а : А\ —> А2, которая индуцирует биекцию В\ —> В2. Если специально не оговаривается, мы считаем А = [п + 1].

Ограничением производящего множества В на 5 € В называется следующее производящее множество на О^]:

В|5 = {5"е5: 5'С5}.

Сжатием производящего множества В вдоль S £ В называется следующее производящее множество на [п + 1 — |5|]:

B/S = {S' С [п + 1] \ S: S' G В или S' U S е В} = {S' \ S, S' € В}.

Произведением Вг ■ В2 = В\ U В2 производящих множеств Вг и В2 на [rii + 1] и [п2 + 1] называется производящее множество на [ni -f 1] U [ri2 -f 1] = [ni + П2 + 2], составленное из элементов обоих множеств.

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

Определение 1.11. Пусть Г - простой граф на множестве вершин [п+1]. Графическим производящим множеством В(Г) называется система всех непустых подмножеств S С [n +1], для которых индуцированный подграф r|s на множестве вершин S является связным.

Замечание 1.12. Производящее множество В (Г) связно тогда и только тогда, когда связен граф Г.

Замечание 1.13. Пусть Г - простой граф на множестве вершин [n + 1] и S G -В(Г), тогда ,B(r)|s и B(T)/S являются графическими производящими множествами, соответствующими графам, обозначаемым Г¡5 и Г/S. Вершинами графа Г/S является множество [п + 1] \ S; вершины v и w смежны если либо они смежны в графе Г; либо смежны некоторым вершинам из S. Заметим, что если граф Г связен, то для любого элемента S G В (Г) граф T/S также связен.

Определение 1.14. Пусть Mi и М2 - подмножества М". Суммой Минков-ского Mi и М-2 называется следующее подмножество R":

Mi + М2 = {х Е W1: х = Xi + х2; где хг Е Мг,х2 G М2}.

Если Mi и М2 являются выпуклыми многогранниками, то Mi + М2 также является выпуклым многогранником.

Определение 1.15. Пусть е*,г = 1,...,п+1- конечные точки базисных векторов К.п+1. Нестоэдр Рд, соответствующий производящему множеству В, определяется следующим образом:

Рв = ^ А5, где А5 = сопу{вг, г Е Б}, вев

Если -В (Г) - графическое производящее множество, то многогранник Рг = Рв{т) называется граф-ассоциэдром.

Определение 1.16. Назовем производящее множество В флаговым, если соответствующий нестоэдр Рв является флаговым многогранником.

Пример 1.17. Следующие нестоэдры и граф-ассоциэдры будут играть важную роль в диссертации:

• Пусть В = {[п + 1], {г},г € [п + 1]}, тогда Рв ~ Дп.

• Пусть Ьп+1 - граф пути на множестве [п + 1], тогда многогранник Рьп+1 называется ассоциэдром (многогранником Сташефа) и обозначается Азп. В этом случае В(Ьп+х) = {[г,где г < ]} - множество всех интервалов, лежащих в [п +1].

• Пусть Сп+1 - циклический граф на [п + 1], тогда многогранник РСп+1 называется циклоэдром (многогранником Ботта-Таубса) и обозначается Суп. В этом случае В(С7п+1) = {[г,Л где г < 3} и {[п + 1] \ [г,Л где 1 < г < 3 < п + 1}.

Список литературы диссертационного исследования кандидат наук Володин, Вадим Дмитриевич, 2013 год

Литература

[Ai] N. Aisbett, Frankl-Furedi-Kalai Inequalities on the 7-vectors of flag nestohedra.

arXiv:1203.4715vl, 2012.

[Bal] D. Barnette, The minimum number of vertices of a simple polytope. Israel Journal of Mathematics, vol. 10, pp. 121-125, 1971.

[Ba2] D. Barnette, A proof for the lower bound conjecture for convex polytopes. Pacific Journal of Mathematics, vol. 46, no. 2, pp. 349-354, 1973.

[BL] L. J. Billera, C. W. Lee, A proof of the sufficiency of McMullen's conditions for f - vectors of simplicial polytopes. J. Combin. Theory Ser. A 31, 237-255, 1981.

[Bui] V. Buchstaber, Ring of simple polytopes and differential equations. Trudy Matematicheskogo Instituta imeni V.A. Steklova, vol. 263, pp. 18-43, 2008.

[Bu2] V. Buchstaber, Lectures on Toric Topology. Toric Topology Workshop, KAIST 2008, Trends in Mathematics, Information Center for Mathematical Sciences, vol. 11, no. 1, pp. 1-55, 2008.

[BR] V. Buchstaber, N. Ray, An invitation to toric topology: vertex four of a remarkable

tetrahedron. Toric topology, Contemporary Mathematics (AMS), vol. 460, Providence, R.I., pp. 1-27, 2008.

[BV] V. Buchstaber, V. Volodin, Combinatorial 2-truncated cubes and applications.

Associahedra, Tamari Lattices, and Related Structures, Tamari Memorial Festschrift, Progress in Mathematics, Vol. 299, pp 161-186, 2012.

[CdS] A. Cannas da Silva, Lectures on symplectic geometry. Lecture Notes in Mathematics, 1764; Springer-Verlag, 2001.

[CD] M. Carr, S.Devadoss, Coxeter complexes and graph associahedra. Topology and

its Applications, vol. 153, pp. 2155-2168, 2006; arXiv:math/0407229v2.

[CZ] C. Ceballos, G. Ziegler, Three non-equivalent realizations of the associahedron.

arXiv:1006.3487vl, 2010.

[CFZ] F. Chapoton, S. Fomin, A. Zelevinsky, Polytopal realizations of generalized associahedra. Canad. Math. Bull. 45, 537-566, 2002; arXiv:math/0202004vl.

[ChD] R.Charney, M.Davis, The Euler characteristic of a nonpositively curved, piecewise Euclidean manifold. Pacific J. Math. 171, no. 1, 117-137, 1995.

[DHV] S. Devadoss, T. Heath, W. Vipismakul, Deformations of bordered surfaces and convex polytopes. Notices of the AMS 58 530-541, 2011.

[DJ] M. Davis, T. Januszkiewicz, Convex polytopes, Coxeter orbifolds and torus

actions. Duke Mathematical Journal, vol. 62, no. 2, pp. 417-451, 1991.

[DP] C. De Concini, C. Procesi, Wonderful models of subspace arrangements. Selecta

Mathematica (N.S.), vol. 1, pp. 459-494, 1995.

[Del] T. Delzant, Hamiltoniens périodiques et image convexe de l'application moment.

Bulletin de la Société Mathématique de France, vol. 116, no. 3, pp. 315-339,1988.

[Dev] S. Devadoss, A Realization of Graph Associahedra. Discrete Mathematics 309, 271-276, 2009; arXiv:math/0612530vl.

[FK] E. M. Feichtner, D.Kozlov, Incidence combinatorics of resolutions. Selecta Mathematica (N.S.) 10, 37-60, 2004; arXiv:math/0305154v2.

[FM] E. M. Feichtner, I. Mueller, On the topology of nested set complexes. Proceedings of American Mathematical Society, vol. 133, no. 4, pp. 999-1006, 2005; arXiv:math/0311430vl.

[FS] E. M. Feichtner, B.Sturmfels, Matroid polytopes, nested sets, and Bergman

fans. Portugaliae Mathematica (N.S.), .vol. 62, no. 4, pp. 437-468, 2005; arXiv:math/0411260vl.

[Fe] A.Fenn, Generating Functions of Nestohedra and Applications. arXivrhep-

th/0111053, 2001.

[FZ3] S. Fomin, A. Zelevinsky, Y- systems and generalized associahedra. arXiv:0908.0605vl, 2009.

[FFR] P. Frankl, Z. Furedi, G. Kalai, Shadows of colored complexes. Math. Scand. 63, 1988.

[Ft] A. Frohmader, Face vectors of flag complexes. arXiv:math/0605673vl, 2006.

[FMc] W. Fulton, R. MacPherson, A compactification of configuration space. Annals of. Mathematics, 139, 183-225, 1994.

[Gal] S.Gal, Real root conjecture fails for five- and higher-dimensional spheres.

Discrete & Computational Geometry, vol. 34, no. 2, pp. 269-284, 2005; arXiv:math/0501046vl.

[GKZ] I. Gelfand, M. Kapranov, A. Zelevinsky. Discriminants, Resultants, and Multidimensional Determinants. Birkhauser, Boston, 1994.

[HL] C. Hohlweg, C. Lange, Realizations of the Associahedron and Cyclohedron.

Discrete Comput Geom 37, 517-543, 2007; arXiv:math/0510614v3.

[Od] T. Oda, Convex Bodies and Algebraic Geometry: An Introduction to the Theory

of Toric Varieties. Springer-Verlag, Berlin, 1998.

[Li] W. B. R. Lickorish, Simplicial moves on complexes and manifolds. Geom. Topol.

Monogr. 2, 299-320, 1999; arXiv:math/9911256vl.

[Lo] J.-L. Loday, Realization of the Stasheff polytope. Archiv Math. 83 (2004), 267-

278. arXiv:math/0212126vl.

[Lee] C.W.Lee. The associahedron and triangulations of the n-gon. European J. Combin. 10:6, 1989, 551-560.

[Mcl] P. McMuIlen, The maximum numbers of faces of a convex polytope. Mathematika, vol. 17, pp. 179-184, 1970.

[Mc2] P. McMuIlen, The numbers of faces of simplitial polytopes. Israel J.Math., V9, 559-570, 1971.

[Mc3] P. McMuIlen, On Simple Polytopes. Invent, math. 113, 419-444, 1993.

[Mc4] P. McMuIlen, Weights on polytopes. Discrete Comput. Geom. 15, 363- 388, 1996.

[MSS] M. Markl, S. Shnider, J. Stasheff. Operads in algebra, topology and physics. Math. Surv. and Monographs, 96. AMS, Providence, RI, 2002.

[NP] E.Nevo, T.Peterson, On -vectors satisfying the Kruskal-Katona inequalities.

Discrete Comput. Geom. 45, no. 3, 503-521, 2011.

[PRV] T.Panov, N.Ray, R.Vogt, Colimits, stanley-reisner algebras, and loop spaces In Categorical Decomposition Techniques in Algebraic Topology, volume 215 of Progress in Mathematics. Birkhauser, Verlag, 261-291, 2004.

[PRW] A.Postnikov, V.Reiner, L.Williams, Faces of generalized permutohedra. Documenta Mathematica, vol. 13, pp. 207-273, 2008; arXiv:math/0609184v2.

[Po] A. Postnikov, Permutohedra, associahedra, and beyond. International

Mathematics Research Notices, no. 6, pp. 1026-1106, 2009; arXiv:math/0507163vl.

R. Stanley. The number effaces of simplitial convex polytope. Advances in Math. V.35, №3, pp. 236-238, 1980.

A. Zelevinsky, Nested set complexes and their polyhedral realizations. Pure and Applied Mathematics Quarterly, vol. 2, no. 3, pp. 655-671, 2006; arXiv:math/0507277v4.

G.Ziegler, Lectures on Polytopes. Springer-Verlag, 1995. (Graduate Texts in Math. V.152).

G. Ziegler, Face numbers of 4-polytopes and 3-spheres. Proceedings of the ICM, 2002, vol. Ill, 625-634, 2002.

V. Volodin, Cubical realizations of flag nestohedra and Gal's conjecture. arXiv:0912.5478, 2009.

V. Volodin, Combinatorics of flag simplicial 3-polytopes. arXiv:1210.0398, 2013.

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

В. Бухштабер, Н. Ероховец, Многогранники, числа Фибоначчи, алгебры Хопфа и квазисимметрические функции. УМН, 66:2(398), 67-162, 2011.

В. Бухштабер, Т. Панов. Торические действия в топологии и комбинаторике. Издательство МЦНМО, Москва, 2004

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

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

М.Горский, Доказательство гипотезы Гала для обобщенных ассоциаэдров серии D. УМН, 65:6(396), 185-186, 2010.

H. Ю. Ероховец, Гипотеза Гала для нестоэдров, отвечающих полным двудольным графам., Геометрия, топология и математическая физика. II, Сборник статей. К 70-летию со дня рождения академика Сергея Петровича Новикова, Тр. МИАН, 266, МАИК, М., 127-139, 2009.

В.Данилов, Геометрия торических многообразий. УМН, 33:2(200), 85-134, 1978.

В. Сачков, Введение в комбинаторные методы дискретной математики. М.: МЦНМО, 2004.

[Ти] В.Тиморин. Аналог соотношений Ходжа-Римана для простых выпуклых

многогранников. УМН, 54:2(326), 113-162, 1999.