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

Gale diagram

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

Определения

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

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

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

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

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

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

Учитывая диаграмму Гейла многогранника, т. Е. Набор единичные векторы в -мерное пространство, можно выбрать -мерное подпространство через начало координат, которое избегает всех векторов, и параллельное подпространство что не проходит через происхождение. Потом центральная проекция от происхождения до произведет набор -размерные точки. Эта проекция теряет информацию о том, какие векторы лежат выше и которые находятся под ним, но эта информация может быть представлена ​​путем присвоения каждой точке знака (положительный, отрицательный или ноль) или, что эквивалентно, цвета (черный, белый или серый). Результирующий набор подписанных или цветных точек и есть аффинная диаграмма Гейла данного многогранника. Эта конструкция имеет преимущество перед преобразованием Гейла в том, что для представления структуры данного многогранника используется на одно измерение меньше.[6]

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

Примеры

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

Симплексы

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

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

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

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

В общем, количество различных диаграмм Гейла с , а количество классов комбинаторной эквивалентности -мерные многогранники с вершины, это .[8]

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

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

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

Приложения

Диаграммы штормов были использованы для обеспечения полного комбинаторное перечисление из -мерный многогранник с вершины,[11] и строить многогранники с необычными свойствами.

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

  • В Многогранник Перла, 8-мерный многогранник с 12 вершинами, который не может быть реализован с помощью рациональных Декартовы координаты. Этот многогранник был построен Миха Перлес от Конфигурация Perles (девять точек и девять линий на плоскости, которые не могут быть реализованы с помощью рациональных координат) путем удвоения трех точек конфигурации Перлеса, присвоения знаков полученным 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. ^ а б Зиглер (1995), п. 170
  5. ^ Штурмфельс (1988).
  6. ^ Томас (2006), п. 43–44.
  7. ^ Зиглер (1995), Определение 6.17, с. 168
  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
  16. ^ Вотцлав и Циглер (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