Пермутоэдр

Перммутоэдр 4-го порядка

В математике , то перестановочный многогранник порядка п является ( п - 1) -мерном многогранник вкладывается в п - мерном пространстве. Его вершинные координаты (метки) являются перестановками первых п натуральных чисел . Ребра определяют кратчайшие возможные пути (наборы транспозиций ), которые соединяют две вершины (перестановки). Две перестановки, соединенные ребром, различаются только двумя местами (одна транспозиция ), и числа на этих местах являются соседними (различаются по значению на 1).

На изображении справа показан пермутоэдр 4-го порядка, который является усеченным октаэдром . Его вершины - это 24 перестановки из (1, 2, 3, 4). Параллельные кромки имеют одинаковый цвет кромки. 6 цветов краев соответствуют 6 возможным перестановкам 4 элементов, то есть они указывают, в каких двух местах соединенные перестановки различаются. (Например, красные края соединяют перестановки, которые различаются в двух последних местах.)

История [ править ]

Согласно Гюнтеру М. Циглеру ( 1995 ), пермутоэдры были впервые изучены Питером Хендриком Шуте ( 1911 ). Название permutoèdre было придумано Жоржем Т. Гильбо и Пьер Розенштиль ( 1963 ). Они описывают это слово как варварское, но легко запоминающееся и подвергают критике своих читателей. ^[1]

Иногда также используется альтернативное написание permut a hedron . ^[2] Пермутоэдры иногда называют многогранниками перестановок , но эта терминология также используется для связанного многогранника Биркгофа , определяемого как выпуклая оболочка матриц перестановок . В более общем плане В. Джозеф Боуман ( 1972 ) использует этот термин для любого многогранника, вершины которого имеют биекцию с перестановками некоторого множества.

Вершины, ребра и фасеты [ править ]

вершины , ребра , грани , грани
Размер грани

d = n - k

.

 k = 1 2 3 4 5 n 1  1  1 2  1  2  3 3 1 6  6  13 4 1 14  36  24  75 5 1 30 150 240  120  541

У пермутоэдра порядка $n$ есть $n!$ вершин, к каждой из которых примыкает еще $n - 1$ . Количество ребер $(п - 1) п! / 2$ , а их длина $\sqrt 2$ .

Две соединенные вершины различаются местами двух координат, значения которых отличаются на 1. ^[3] Пара переставленных мест соответствует направлению ребра. (На изображении в качестве примера вершины $(3, 2, 1, 4)$ и $(2, 3, 1, 4)$ соединены синим краем и отличаются перестановкой 2 и 3 местами в первых двух местах. Значения 2 и 3 отличаются на 1. Все синие края соответствуют перестановкам координат в первых двух местах.)

Количество фасетов равно $2 n - 2$ , потому что они соответствуют непустым собственным подмножествам $S$ из ${1 ... n}$ . Общим для вершин фасеты, соответствующей подмножеству $S$ , является то, что их координаты в точках $S$ меньше остальных . ^[4]

Примеры фасетов
Для порядка 3 гранями являются 6 граней, а для порядка 4 - 14 граней . Координаты в местах $i,$ где $i \in S$ , отмечены темным фоном. Видно, что они меньше остальных. Квадрат сверху соответствует подмножеству ${3, 4}$ . В четырех его вершинах координаты двух последних мест имеют наименьшие значения (а именно 1 и 2).
заказ 3		заказ 4
1-элементные подмножества	2-элементные подмножества	1-элементные подмножества	2-элементные подмножества	3-элементные подмножества

В более общем смысле, грани размеров от 0 (вершины) до $n - 1$ (сам пермутоэдр) соответствуют строгим слабым порядкам множества ${1 ... n}$ . Таким образом, число всех граней является $п$ -го заказать номер Bell . ^[5] Грань размерности $d$ соответствует упорядочению с $k = n - d$ классами эквивалентности.

Примеры лиц

заказ 3

заказ 4

На изображениях выше показаны решетки граней пермутоэдров порядка 3 и 4 (без пустых граней) .
Каждый центр грани помечен строгим слабым порядком. Например, квадрат сверху как 3 4 | 1 2 , который представляет $({3, 4}, {1, 2})$ .
Упорядочения частично упорядочены по уточнению , причем более тонкие находятся снаружи.
Двигаться по краю внутрь означает объединение двух соседних классов эквивалентности.

Вершина помечает a | б | c | d, интерпретируемые как перестановки (a, b, c, d) , образуют граф Кэли.

Грани среди лиц

Вышеупомянутые фасеты находятся среди этих граней и соответствуют порядкам с двумя классами эквивалентности.
Первый используется как подмножество $S,$ назначенное фасету, поэтому порядок равен $(S, S c)$ .

Изображения ниже показывает , как фасетки $п$ -permutohedron соответствует симплициальной проекции $п$ - куб .
Метки двоичных координат соответствуют подмножествам $S$ , например, от 0011 до ${3, 4}$ .
(Вершина, спроецированная на центр, не соответствует фасете. Не соответствует и ее противоположная вершина в $n$ -кубе, который не является частью проекции.)

Количество граней размерности $d = n - k$ в пермутоэдре порядка $n$ задается треугольником $T$ (последовательность A019538 в OEIS ): с представлением чисел Стирлинга второго рода Он показан справа вместе со строкой суммы, заказанные номера Bell .
$T(n,k)=k!\cdot \left\{{n \atop k}\right\}$ $\textstyle \left\{{n \atop k}\right\}$

Другие свойства [ править ]

Подобный пермутоэдру граф Кэли S ₄ (см. Здесь для сравнения с пермутоэдром)

Пермутоэдр вершинно-транзитивен : симметрическая группа S _n действует на пермутоэдр перестановкой координат.

Перестановочный многогранник является zonotope ; переведенная копия перестановочного многогранника может быть сформирована как сумма Минковской из п ( п - 1) / 2 отрезков, соединяющих пары в стандартных базисных векторах. ^[6]

Вершины и ребро перестановочного многогранника являются изоморфно одному из графов Кэлей в симметрической группе , а именно тот , генерируемый с помощью транспозиций , что своп последовательных элементов. Вершины графа Кэли являются перестановками, обратными перестановкам в пермутоэдре. ^[7] На изображении справа показан граф Кэли S 4 . Цвета его краев представляют 3 образующих транспозиции: (1, 2) , (2, 3) , (3, 4)

Этот граф Кэли гамильтонов ; гамильтонов цикл может быть найден с помощью алгоритма Штейнхауса – Джонсона – Троттера .

Тесселяция пространства [ править ]

Месселяция пространства пермутоэдрами 3-го и 4-го порядков.

Перммутоэдр порядка n целиком лежит в ( n - 1 ) -мерной гиперплоскости, состоящей из всех точек, сумма координат которых равна числу

1 + 2 + ... + п = п ( п + 1) / 2.

Более того, эта гиперплоскость может быть выложена бесконечно большим количеством переведенных копий пермутоэдра. Каждый из них отличается от основного пермутоэдра элементом некоторой ( n - 1) -мерной решетки , которая состоит из n -конечностей целых чисел, сумма которых равна нулю и вычеты (по модулю n ) равны:

х ₁ + х ₂ + ... + х _n = 0

Икс ₁ ≡ Икс ₂ ≡ ... ≡ Икс _N (по модулю N ).

Это решетка , то двойственная решетка из корневой решетки . Другими словами, пермутоэдр - это ячейка Вороного для . Соответственно, эту решетку иногда называют пермутоэдрической решеткой. ^[8] $A_{n-1}^{*}$ A n − 1 {\displaystyle A_{n-1}} $A_{n-1}^{*}$

Таким образом, пермутоэдр 4-го порядка, показанный выше, разбивает трехмерное пространство на мозаику путем сдвига. Здесь 3-мерное пространство - это аффинное подпространство 4-мерного пространства R ⁴ с координатами x , y , z , w, которое состоит из 4-х наборов действительных чисел, сумма которых равна 10,

х + у + г + ш = 10.

Легко проверить, что для каждого из следующих четырех векторов

(1,1,1, −3), (1,1, −3,1), (1, −3,1,1) и (−3,1,1,1),

сумма координат равна нулю, и все координаты совпадают с 1 (mod 4). Любые три из этих векторов порождают решетку трансляций.

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

Примеры [ править ]

Заказ 2	Заказ 3	Заказ 4	Заказ 5	Заказ 6
2 вершины	6 вершин	24 вершины	120 вершин	720 вершин

отрезок	шестиугольник	усеченный октаэдр	омниусеченный 5-элементный	омниусеченный 5-симплексный

См. Также [ править ]

Викискладе есть медиафайлы по теме пермутоэдра .

Ассоциэдр
Циклоэдр

Заметки [ править ]

^ Оригиналфранцузском языке: "Le словцо permutoèdre Est barbare, Маис иль EST FACILE à retenir; soumettons-ле Окс критика де lecteurs."
^ Томас (2006) .
^ Gaiha & Гупта (1977) .
↑ Lancia (2018) , стр. 105 (см. Главу Пермутаэдр ).
^ См., Например, Ziegler (1995) , стр. 18.
^ Зиглер (1995) , стр. 200.
^ Эта разметка графа Кэли показана, например, Зиглером (1995) .
^ Пэк, Adams & Долсон (2013) .

Ссылки [ править ]

Пэк, Чонмин; Адамс, Эндрю; Долсон, Дженнифер (2013), "решетка на основе высокой мерной гауссова фильтрации и permutohedral решетки", Журнал математической обработки изображений и видения , 46 (2): 211-237, DOI : 10.1007 / s10851-012-0379-2 , ЛВП : 1721,1 / 105344 , МР 3061550
Bowman, В. Джозеф (1972), "Перестановка многогранники", SIAM журнал по прикладной математике , 22 (4): 580-589, DOI : 10,1137 / 0122054 , JSTOR 2099695 , МР 0305800.
Гайха, Прабха; Гупта, С. К. (1977), "смежных вершин на перестановочный многогранник", SIAM журнал по прикладной математике , 32 (2): 323-327, DOI : 10,1137 / 0132025 , JSTOR 2100417 , МР 0427102.
Guilbaud, Georges Th .; Rosenstiehl, Пьер (1963), «Анализируйте algébrique d'un scrutin» , Mathématiques et Sciences Humaines , 4 : 9–33.
Lancia, Giuseppe (2018), Компактные расширенные модели линейного программирования , Cham, Швейцария: Springer, ISBN 978-3-319-63975-8.
Schoute, Питер Хендрик (1911), "Аналитическая обработка многогранников, регулярно получаемых из правильных многогранников", Verhandelingen der Koninklijke Akademie van Wetenschappen Te Amsterdam , 11 (3): 87 стр. Googlebook, 370–381 Также онлайн в цифровой библиотеке KNAW по адресу http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495
Томас, Рекха Р. (2006), «Глава 9. Пермутаэдр», Лекции по геометрической комбинаторике , Студенческая математическая библиотека: IAS / Park City Mathematical Subseries, 33 , Американское математическое общество , стр. 85–92, ISBN 978-0-8218-4140-2.
Циглер, Гюнтер М. (1995), Лекции по многогранникам , Springer-Verlag, Тексты для выпускников по математике 152.

Дальнейшее чтение [ править ]

Le Conte de Poly-Barbut, Cl. (1990), "Le diagramme du treillis permutoèdre est crossction des diagrammes de deux produits directs d'ordres totaux", Mathématiques, Informatique et Sciences Humaines , 112 : 49–53.
Постников, Александр (2009), «Перммутоэдры, ассоциаэдры и не только», International Mathematics Research Notices (6): 1026–1106, arXiv : math.CO/0507163 , doi : 10.1093 / imrn / rnn153 , MR 2487491
Сантмайер, Джо (2007), «Взгляните на пермутоэдр на всех возможных расстояниях», Mathematics Magazine , 80 (2): 120–125, doi : 10.1080 / 0025570X.2007.11953465

Внешние ссылки [ править ]

Брайан Джейкобс, «Пермутоэдр» , MathWorld

[1] Оригиналфранцузском языке: "Le словцо permutoèdre Est barbare, Маис иль EST FACILE à retenir; soumettons-ле Окс критика де lecteurs."

[2] Томас (2006) .

[3] Gaiha & Гупта (1977) .

[4] Lancia (2018) , стр. 105 (см. Главу Пермутаэдр ).

[zface-5] См., Например, Ziegler (1995) , стр. 18.

[FOOTNOTEZiegler1995200-6] Зиглер (1995) , стр. 200.

[7] Эта разметка графа Кэли показана, например, Зиглером (1995) .

[FOOTNOTEBaekAdamsDolson2013-8] Пэк, Adams & Долсон (2013) .

[1]