Диаграмма Гейла

В математической дисциплине полиэдральной комбинаторики преобразование Гейла превращает вершины любого выпуклого многогранника в набор векторов или точек в пространстве другой размерности, диаграмму Гейла многогранника. Его можно использовать для описания многогранников высокой размерности с небольшим количеством вершин, преобразуя их в наборы с тем же количеством точек, но в пространстве гораздо меньшей размерности. Процесс также можно обратить, чтобы построить многогранники с желаемыми свойствами из их диаграмм Гейла. Преобразование Гейла и диаграмма Гейла названы в честь Дэвида Гейла , который представил эти методы в статье 1956 года о соседских многогранниках . ^[1]

Определения

Трансформировать

Дан -мерный многогранник с вершинами, присоединить 1 к декартовым координатам каждой вершины, чтобы получить -мерный вектор-столбец . Матрица этих векторов-столбцов имеет размерности , определяя линейное отображение из -пространства в -пространство, сюръективное с рангом . Ядро описывает линейные зависимости между исходными вершинами с коэффициентами, сумма которых равна нулю; это ядро ​​имеет размерность . Преобразование Гейла представляет собой матрицу размерности , векторы-столбцы которой являются выбранным базисом для ядра . Тогда имеет векторы-строки размерности . Эти векторы-строки образуют диаграмму Гейла многогранника. Другой выбор базиса для ядра изменяет результат только линейным преобразованием. ^[2] ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle (d+1)}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle (d+1)\times n}$ ${\displaystyle n}$ ${\displaystyle (d+1)}$ ${\displaystyle d+1}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle n-d-1}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n\times (n-d-1)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle n-d-1}$

Обратите внимание, что векторы в диаграмме Гейла находятся в естественной биекции с вершинами исходного -мерного многогранника, но размерность диаграммы Гейла меньше, когда . ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle n\leq 2d}$

Собственное подмножество вершин многогранника образует множество вершин грани многогранника, если и только если дополнительный набор векторов преобразования Гейла имеет выпуклую оболочку , содержащую начало координат в своей относительной внутренней части . Эквивалентно, подмножество вершин образует грань, если и только если его аффинная оболочка не пересекает выпуклую оболочку дополнительных векторов. ^[3]

Линейная диаграмма

Поскольку преобразование Гейла определено только с точностью до линейного преобразования, его ненулевые векторы могут быть нормализованы ко всем be -мерным единичным векторам . Линейная диаграмма Гейла представляет собой нормализованную версию преобразования Гейла, в которой все векторы являются нулевыми или единичными векторами. ^[4] ${\displaystyle (n-d-1)}$

Аффинная диаграмма

Учитывая диаграмму Гейла многогранника, то есть набор единичных векторов в -мерном пространстве, можно выбрать -мерное подпространство через начало координат, которое избегает всех векторов, и параллельное подпространство , которое не проходит через начало координат. Затем центральная проекция из начала координат в даст набор -мерных точек. Эта проекция теряет информацию о том, какие векторы лежат выше , а какие ниже, но эта информация может быть представлена ​​путем назначения знака (положительный, отрицательный или нулевой) или, что эквивалентно, цвета (черный, белый или серый) каждой точке. Результирующий набор подписанных или цветных точек является аффинной диаграммой Гейла данного многогранника. Эта конструкция имеет преимущество перед преобразованием Гейла в использовании на одно измерение меньше для представления структуры данного многогранника. ^[5] ${\displaystyle n}$ ${\displaystyle (n-d-1)}$ ${\displaystyle (n-d-2)}$ ${\displaystyle S}$ ${\displaystyle S'}$ ${\displaystyle S'}$ ${\displaystyle (n-d-2)}$ ${\displaystyle S}$

Преобразования Гейла и линейные и аффинные диаграммы Гейла также могут быть описаны через двойственность ориентированных матроидов . ^[6] Как и в случае с линейной диаграммой, подмножество вершин образует грань тогда и только тогда, когда не существует аффинной функции (линейной функции с возможно ненулевым постоянным членом), которая присваивает неотрицательное значение каждому положительному вектору в дополнительном наборе и неположительное значение каждому отрицательному вектору в дополнительном наборе. ^[7]

Примеры

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

Симплексы

-мерный многогранник с вершинами, минимально возможным, является симплексом . В этом случае линейная диаграмма Гейла является 0-мерной, состоящей только из нулевых векторов. Аффинная диаграмма имеет серые точки. ^[8] ${\displaystyle d}$ ${\displaystyle n=d+1}$ ${\displaystyle n}$

Одна дополнительная вершина

В -мерном многограннике с вершинами линейная диаграмма Гейла является одномерной, причем вектор, представляющий каждую точку, является одним из трех чисел , , или . В аффинной диаграмме точки являются нульмерными, поэтому они могут быть представлены только их знаками или цветами без какого-либо значения местоположения. Для того чтобы представить многогранник, диаграмма должна иметь по крайней мере две точки с каждым ненулевым знаком. Две диаграммы представляют один и тот же класс комбинаторной эквивалентности многогранников, когда они имеют одинаковое количество точек каждого знака или когда они могут быть получены друг из друга путем отрицания всех знаков. ^[8] ${\displaystyle d}$ ${\displaystyle n=d+2}$ ${\displaystyle -1}$ ${\displaystyle 0}$ ${\displaystyle +1}$

Для единственной возможностью являются две точки каждого ненулевого знака, представляющие выпуклый четырехугольник . Для существуют две возможные диаграммы Гейла: диаграмма с двумя точками каждого ненулевого знака и одной нулевой точкой представляет квадратную пирамиду , тогда как диаграмма с двумя точками одного ненулевого знака и тремя точками с другим знаком представляет треугольную бипирамиду . ^[8] ${\displaystyle d=2}$ ${\displaystyle d=3}$

В общем случае число различных диаграмм Гейла с , а также число классов комбинаторной эквивалентности -мерных многогранников с вершинами равно . ^[8] ${\displaystyle n=d+2}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle \lfloor d^{2}/4\rfloor }$

Две дополнительные вершины

В -мерном многограннике с вершинами линейная диаграмма Гейла состоит из точек на единичной окружности (единичных векторов) и в ее центре. Аффинная диаграмма Гейла состоит из помеченных точек или кластеров точек на линии. В отличие от случая вершин, не совсем тривиально определить, когда две диаграммы Гейла представляют один и тот же многогранник. ^[8] ${\displaystyle d}$ ${\displaystyle n=d+3}$ ${\displaystyle n=d+2}$

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

• Правильный октаэдр имеет линейную диаграмму Гейла, состоящую из трех пар равных точек на единичной окружности (представляющих пары противоположных вершин октаэдра), делящую окружность на дуги с углом, меньшим . Его аффинная диаграмма Гейла состоит из трех пар точек с одинаковым знаком на прямой, причем средняя пара имеет противоположный знак по отношению к двум внешним парам. ^[9] ${\displaystyle \pi }$
• Треугольная призма имеет линейную диаграмму Гейла, состоящую из шести точек на окружности, в трех диаметрально противоположных парах, причем каждая пара представляет вершины призмы, которые являются смежными на двух квадратных гранях призмы. Соответствующая аффинная диаграмма Гейла имеет три пары точек на линии, как и правильный октаэдр, но с одной точкой каждого знака в каждой паре. ^[10]

Приложения

Диаграммы Гейла использовались для предоставления полного комбинаторного перечисления -мерных многогранников с вершинами, ^[11] и для построения многогранников с необычными свойствами. К ним относятся: ${\displaystyle d}$ ${\displaystyle n=d+3}$

• Многогранник Перлеса, 8-мерный многогранник с 12 вершинами, который не может быть реализован с помощью рациональных декартовых координат . Миха Перлес построил его из конфигурации Перлеса (девять точек и девять линий на плоскости, которые не могут быть реализованы с помощью рациональных координат), удвоив три точки, присвоив знаки полученным 12 точкам и обработав полученную конфигурацию со знаком как диаграмму Гейла многогранника. Хотя известны иррациональные многогранники с размерностью всего четыре, ни один не известен с меньшим количеством вершин. ^[12]
• Многогранник Кляйншмидта, 4-мерный многогранник с 8 вершинами, 10 тетраэдрическими гранями и одной октаэдрической гранью, построенный Петером Кляйншмидтом. Хотя октаэдрическая грань имеет ту же комбинаторную структуру, что и правильный октаэдр, она не может быть правильной. ^[13] Две копии этого многогранника можно склеить по их октаэдрическим граням, чтобы получить многогранник с 10 вершинами, в котором некоторые пары реализаций не могут быть непрерывно деформированы друг в друга. ^[14]
• Бипирамида над квадратной пирамидой — это 4-мерный многогранник с 7 вершинами, обладающий двойственным свойством: форма одной из его вершинных фигур (вершины его центральной пирамиды) не может быть предписана. Первоначально найденный Дэвидом В. Барнеттом, он был переоткрыт Берндом Штурмфельсом с использованием диаграмм Гейла. ^[15]
• Построение малых «несоседних многогранников», то есть многогранников без универсальной вершины , и «освещенных многогранников», в которых каждая вершина инцидентна диагонали, проходящей через внутреннюю часть многогранника. Перекрестные многогранники обладают этими свойствами, но в 16 или более измерениях существуют освещенные многогранники с меньшим количеством вершин, а в 6 или более измерениях освещенные многогранники с наименьшим количеством вершин не обязательно должны быть симплициальными. Построение включает диаграммы Гейла. ^[16]

Примечания

1. Гейл (1956).
2. Томас (2006), Определение 5.2, стр. 38
3. Томас (2006), Теорема 5.6, стр. 41
4. Штурмфельс (1988).
5. Томас (2006), стр. 43–44.
6. Циглер (1995), Определение 6.17, стр. 168
7. Циглер (1995), стр. 170
8. Ziegler (1995), стр. 171.
9. Циглер (1995), Пример 6.18, стр. 169
10. Томас (2006), стр. 39 и 44.
11. Штурмфельс (1988), с. 121; Зиглер (1995), с. 172
12. Циглер (1995), Раздел 6.5(a) «Нерациональный 8-многогранник», стр. 172–173; Томас (2006), Теорема 6.11, стр. 51–52
13. Циглер (1995), Раздел 6.5(b) «Граниты 4-многогранников не могут быть предписаны», стр. 173–175, и Упражнение 6.18, стр. 188; Штурмфельс (1988), стр. 129–130
14. Циглер (1995), Раздел 6.5(d) «Многогранники, нарушающие гипотезу изотопии», стр. 177–179
15. Циглер (1995), Раздел 6.5(b) «Граниты 4-многогранников не могут быть предписаны», стр. 173–175; Штурмфельс (1988), Предложение 5.1, стр. 130; Томас (2006), Теорема 6.12, стр. 53–55
16. Вотцлав и Циглер (2011).

Ссылки

• Гейл, Дэвид (1956), «Соседние вершины выпуклого многогранника», Линейные неравенства и связанные с ними системы , Annals of Mathematics Studies, № 38, Princeton University Press, Принстон, Нью-Джерси, стр. 255–263, MR  0085552
• Sturmfels, Bernd (1988), «Некоторые приложения аффинных диаграмм Гейла к многогранникам с небольшим числом вершин», SIAM Journal on Discrete Mathematics , 1 (1): 121–133, doi :10.1137/0401014, MR  0936614
• Томас, Рекха Р. (2006), «Глава 5: Диаграммы Гейла», Лекции по геометрической комбинаторике , Студенческая математическая библиотека, т. 33, Институт перспективных исследований (IAS), Принстон, Нью-Джерси, стр. 37–45, doi :10.1090/stml/033, ISBN 0-8218-4140-8, г-н  2237292
• Вотцлав, Рональд Ф.; Циглер, Гюнтер М. (2011), «Потерянный контрпример и проблема с освещенными многогранниками», American Mathematical Monthly , 118 (6): 534–543, CiteSeerX  10.1.1.249.4822 , doi :10.4169/amer.math.monthly.118.06.534, MR  2812284, S2CID  15007113
• Циглер, Гюнтер М. (1995), «Глава 6: Двойственность, диаграммы Гейла и приложения», Лекции по многогранникам , Graduate Texts in Mathematics, т. 152, Нью-Йорк: Springer-Verlag, стр. 149–190, doi :10.1007/978-1-4613-8431-1_6, ISBN 0-387-94365-X, МР  1311028