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

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

Определения

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

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

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

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

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

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

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

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

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

Примеры

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

Они просты

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

Еще одна вершина

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

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

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

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

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

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

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

Приложения

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

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

Примечания

^ Гейл (1956) .
^ Томас (2006) , Определение 5.2, с. 38
^ Томас (2006) , Теорема 5.6, с. 41
^ Шторм-Рок (1988) .
^ Томас (2006) , с. 43–44.
^ Циглер (1995) , Определение 6.17, с. 168
^ Зиглер (1995) , с. 170
^ Перейти обратно: ^а ^б ^с ^д ^и Зиглер (1995) , с. 171.
^ Циглер (1995) , Пример 6.18, стр. 169
^ Томас (2006) , стр. 39 и 44.
^ Штурмфельс (1988) , с. 121; Зиглер (1995) , с. 172
^ Циглер (1995) , Раздел 6.5 (а) «Нерациональный 8-многогранник», стр. 172–173; Томас (2006) , Теорема 6.11, стр. 51–52.
^ Циглер (1995) , Раздел 6.5(b) «Невозможно предписать грани 4-многогранников», стр. 173–175, и Упражнение 6.18, стр. 173–175. 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, Принстон, Нью-Джерси, стр. 255–263, MR 0085552.
Штурмфельс, Бернд (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 , МР 2812284 , S2CID 15007113
Циглер, Гюнтер М. (1995), «Глава 6: Дуальность, диаграммы Гейла и приложения», Лекции по многогранникам , Тексты для аспирантов по математике, том. 152, Нью-Йорк: Springer-Verlag, стр. 149–190, номер документа : 10.1007/978-1-4613-8431-1_6 , ISBN. 0-387-94365-Х , МР 1311028

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

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

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

[FOOTNOTESturmfels1988-4] Шторм-Рок (1988) .

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

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

[z170-7] Зиглер (1995) , с. 170

[z171-8] Перейти обратно: ^а ^б ^с ^д ^и Зиглер (1995) , с. 171.

[9] Циглер (1995) , Пример 6.18, стр. 169

[10] Томас (2006) , стр. 39 и 44.

[11] Штурмфельс (1988) , с. 121; Зиглер (1995) , с. 172

[12] Циглер (1995) , Раздел 6.5 (а) «Нерациональный 8-многогранник», стр. 172–173; Томас (2006) , Теорема 6.11, стр. 51–52.

[13] Циглер (1995) , Раздел 6.5(b) «Невозможно предписать грани 4-многогранников», стр. 173–175, и Упражнение 6.18, стр. 173–175. 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]