Диаграмма Гейла - Gale diagram

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

Определения

Преобразовать

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

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

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

Поскольку преобразование Гейла определено только с точностью до линейного преобразования, его ненулевые векторы можно нормализовать так, чтобы все ${ Displaystyle (п-д-1)}$ -размерный единичные векторы. Линейная диаграмма Гейла - это нормализованная версия преобразования Гейла, в которой все векторы являются нулевыми или единичными векторами.^[5]

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

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

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

Примеры

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

Симплексы

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

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

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

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

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

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

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

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

Приложения

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

Построенные таким образом многогранники включают:

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

Заметки

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

использованная литература

Гейл, Дэвид (1956), "Соседние вершины выпуклого многогранника", Линейные неравенства и родственная система, Анналы математических исследований, вып. 38, Princeton University Press, Princeton, N.J., pp. 255–263, Г-Н 0085552
Штурмфельс, Бернд (1988), "Некоторые приложения аффинных диаграмм Гейла к многогранникам с небольшим числом вершин", Журнал SIAM по дискретной математике, 1 (1): 121–133, Дои:10.1137/0401014, Г-Н 0936614
Томас, Рекха Р. (2006), "Глава 5: Диаграммы штормов", Лекции по геометрической комбинаторике, Студенческая математическая библиотека, 33, Институт перспективных исследований (IAS), Принстон, штат Нью-Джерси, стр. 37–45, Дои:10.1090 / stml / 033, ISBN 0-8218-4140-8, Г-Н 2237292
Wotzlaw, Ronald F .; Циглер, Гюнтер М. (2011), «Утерянный контрпример и проблема освещенных многогранников», Американский математический ежемесячный журнал, 118 (6): 534–543, Дои:10.4169 / amer.math.monthly.118.06.534, Г-Н 2812284
Циглер, Гюнтер М. (1995), "Глава 6: Двойственность, диаграммы Гейла и приложения", Лекции по многогранникам, Тексты для выпускников по математике, 152, Нью-Йорк: Springer-Verlag, стр. 149–190, Дои:10.1007/978-1-4613-8431-1_6, ISBN 0-387-94365-X, Г-Н 1311028

[FOOTNOTEGale1956-1] Гейл (1956).

[2] Томас (2006), Определение 5.2, с. 38

[3] Томас (2006), Теорема 5.6, с. 41 год

[z170-4] а ^б Зиглер (1995), п. 170

[FOOTNOTESturmfels1988-5] Штурмфельс (1988).

[6] Томас (2006), п. 43–44.

[7] Зиглер (1995), Определение 6.17, с. 168

[z171-8] а ^б ^c ^d ^е Зиглер (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

[FOOTNOTEWotzlawZiegler2011-16] Вотцлав и Циглер (2011).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]