Permutohedron - Permutohedron

v matematika, permutohedron řádu n je (n - 1) -dimenzionální polytop vložený do n-rozměrný prostor. Své vrchol souřadnice jsou obměny první n přirozená čísla. Okraje jsou nejkratší možným spojením mezi těmito body. Dvě permutace spojené hranou se liší na dvou místech a čísla na těchto místech jsou sousedé.
Obrázek vpravo ukazuje permutohedron řádu 4, což je zkrácený osmistěn. Jeho vrcholy jsou 24 permutací (1, 2, 3, 4). Paralelní hrany mají stejnou barvu hran. 6 barev okrajů odpovídá 6 možným transpozice ze 4 prvků, tj. označují, na kterých dvou místech se spojené permutace liší. (Např. Červené okraje spojují permutace, které se liší na posledních dvou místech.)
Dějiny
Podle Günter M. Ziegler (1995 ), permutohedra byly nejprve studovány Pieter Hendrik Schoute (1911 ). Název permutoèdre vytvořil Georges Th. Guilbaud a Pierre Rosenstiehl (1963 ). Popisují toto slovo jako barbarské, ale snadno zapamatovatelné a podrobují ho kritice svých čtenářů.[1]
Alternativní hláskování permutahedron se někdy také používá.[2] Permutohedry se někdy nazývají permutační polytopy, ale tato terminologie se používá také pro související Birkhoffův mnohostěn, definovaný jako konvexní trup permutační matice. Obecněji V. Joseph Bowman (1972 ) používá tento výraz pro jakýkoli mnohostěn, jehož vrcholy mají a bijekce s obměnami nějaké množiny.
Vrcholy, hrany a fazety
vrcholy, hrany, fazety, tváře Rozměr obličeje d = n − k. |
k = 1 2 3 4 5n1 1 12 1 2 33 1 6 6 134 1 14 36 24 755 1 30 150 240 120 541 |
Permutohedron řádu n má n! vrcholy, z nichž každý sousedí s n − 1 Počet hran je (n − 1) n!/2a jejich délka je √2.
Dva spojené vrcholy se liší zaměněním dvou souřadnic, jejichž hodnoty se liší o 1.[3] Dvojice zaměněných míst odpovídá směru hrany. (V ukázkový obrázek vrcholy (3, 2, 1, 4) a (2, 3, 1, 4) jsou spojeny modrým okrajem a liší se zaměněním 2 a 3 na prvních dvou místech. Hodnoty 2 a 3 se liší o 1. Všechny modré hrany odpovídají swapům souřadnic na prvních dvou místech.)
Počet fazety je 2n − 2, protože odpovídají neprázdnému vlastnímu podmnožiny S z {1 … n}Vrcholy fazety odpovídající podmnožině S mají společné, že jejich souřadnice na místech v S jsou menší než zbytek. [4]
Fazetové příklady | ||||
---|---|---|---|---|
U objednávky 3 jsou fazety 6 hran a u objednávky 4 jsou to 14 tváře. | ||||
objednávka 3 | objednávka 4 | |||
1prvkové podmnožiny | 2prvkové podmnožiny | 1prvkové podmnožiny | 2prvkové podmnožiny | 3prvkové podmnožiny |
![]() | ![]() | ![]() | ![]() | ![]() |
Obecněji, tváře rozměrů 0 (vrcholy) až n − 1 (samotný permutohedron) odpovídá přísné slabé objednávky sady {1 … n}. Takže počet všech tváří je n-th objednal Bell číslo.[5]Tvář dimenze d odpovídá objednávce u k = n − d třídy ekvivalence.
Příklady tváří | |||||||
---|---|---|---|---|---|---|---|
objednávka 3 | objednávka 4 | ||||||
![]() | ![]() | ||||||
Obrázky výše ukazují obličejové mřížky permutohedry řádu 3 a 4 (bez prázdných tváří). Štítky vrcholů a | b | c | d interpretovány jako permutace (abeceda) jsou ti, kteří tvoří Cayleyův graf.
|
Počet ploch dimenze d = n − k v permutohedronu řádu n je dáno trojúhelníkem T (sekvence A019538 v OEIS ):
s zastupující Stirlingova čísla druhého druhu
Je zobrazen vpravo spolu se součty řádků, objednal Bell čísla.
Další vlastnosti

Permutohedron je vrchol-tranzitivní: symetrická skupina Sn činy na permutohedron permutací souřadnic.
Permutohedron je a zonotop; přeloženou kopii permutohedronu lze vygenerovat jako Minkowského součet z n(n − 1)/2 úsečky, které spojují páry standardní základ vektory.[6]
Vrcholy a okraje permutohedronu jsou izomorfní k jednomu z Cayleyovy grafy z symetrická skupina a sice ten generováno podle transpozice že zaměňují po sobě jdoucí prvky. Vrcholy Cayleyova grafu jsou inverzní permutace těch v permutohedronu.[7] Obrázek vpravo ukazuje Cayleyův graf S.4. Barvy jeho hran představují 3 generující transpozice: (1, 2), (2, 3), (3, 4)
Tento Cayleyův graf je Hamiltonian; Hamiltoniánský cyklus lze najít pomocí Algoritmus Steinhaus – Johnson – Trotter.
Teselace prostoru
Permutohedron řádu n leží zcela v (n - 1) -rozměrná nadrovina skládající se ze všech bodů, jejichž souřadnice se shodují s číslem
- 1 + 2 + … + n = n(n + 1)/2.
Navíc tato hyperplán může být kachlová nekonečně mnoho přeloženo kopie permutohedronu. Každý z nich se liší od základního permutohedronu určitým prvkem (n - 1) -dimenzionální mříž, který se skládá z n-tuples celých čísel, jejichž součet je nula a jejichž zbytky (modulo n) jsou si všichni rovni:
- X1 + X2 + … + Xn = 0, X1 ≡ X2 ≡ … ≡ Xn (mod n).
To je mříž , dvojitá mříž z kořenová mřížka . Jinými slovy, permutohedron je Voronoiova buňka pro . V souladu s tím se tato mřížka někdy nazývá permutohedrální mřížka.[8]
Permutohedron řádu 4, který je zobrazen výše, tedy překládá trojrozměrný prostor. Zde je trojrozměrný prostor afinní podprostor 4-dimenzionálního prostoru R4 se souřadnicemi X, y, z, w který se skládá ze 4 n-tic reálných čísel, jejichž součet je 10,
- X + y + z + w = 10.
Jeden snadno zkontroluje, že pro každý z následujících čtyř vektorů,
- (1,1,1, -3), (1,1, -3,1), (1, -3,1,1) a (-3,1,1,1),
součet souřadnic je nula a všechny souřadnice jsou shodné s 1 (mod 4). Jakékoli tři z těchto vektorů generovat překladová mřížka.
Teselace vytvořené tímto způsobem z řádu 2, řádu 3 a řádu 4 jsou příslušně apeirogon pravidelný šestihranný obklad a bitunovaný kubický plástev. Duální teselace obsahují vše simplexní fazety, i když to nejsou pravidelné polytopy nad řádem 3.
Příklady
Objednávka 2 | Objednávka 3 | Objednávka 4 | Objednávka 5 | Objednávka 6 |
---|---|---|---|---|
2 vrcholy | 6 vrcholů | 24 vrcholů | 120 vrcholů | 720 vrcholů |
![]() | ![]() | ![]() | ![]() | ![]() |
úsečka | šestiúhelník | zkrácený osmistěn | omnitruncated 5-cell | všestranný 5-simplex |
Viz také
Poznámky
- ^ Původní francouzština: „le mot permutoèdre est barbare, mais il est facile à retenir; soumettons-le aux critiques des lecteurs.“
- ^ Thomas (2006).
- ^ Gaiha & Gupta (1977).
- ^ Lancia (2018), str. 105 (viz kapitola Permutahedron ).
- ^ Viz např. Ziegler (1995), str. 18.
- ^ Ziegler (1995), str. 200.
- ^ Toto označení grafu Cayley je zobrazeno např Ziegler (1995).
- ^ Baek, Jongmin; Adams, Andrew (2009). „Některé užitečné vlastnosti permutohedrální mřížky pro Gaussovo filtrování“ (PDF). Tech. Rep. Stanfordská Univerzita.
Reference
- Bowman, V. Joseph (1972), „Permutation polyhedra“, SIAM Journal on Applied Mathematics, 22 (4): 580–589, doi:10.1137/0122054, JSTOR 2099695, PAN 0305800.
- Gaiha, Prabha; Gupta, S. K. (1977), „Sousedící vrcholy na permutohedronu“, SIAM Journal on Applied Mathematics, 32 (2): 323–327, doi:10.1137/0132025, JSTOR 2100417, PAN 0427102.
- Guilbaud, Georges Th .; Rosenstiehl, Pierre (1963), „Analyse algébrique d'un scrutin“, Mathématiques et Sciences Humaines, 4: 9–33.
- Lancia, Giuseppe (2018), Kompaktní rozšířené modely lineárního programováníCham, Švýcarsko: Springer, ISBN 978-3-319-63975-8.
- Schoute, Pieter Hendrik (1911), „Analytické zpracování polytopů pravidelně odvozených z běžných polytopů“, Verhandelingen der Koninklijke Akademie van Wetenschappen Te Amsterdam, 11 (3): 87 stran Googlebook, 370–381 Také online v digitální knihovně KNAW na adrese http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495
- Thomas, Rekha R. (2006), „Kapitola 9. Permutahedron“, Přednášky z geometrické kombinatoriky, Student Mathematical Library: IAS / Park City Mathematical Subseries, 33, Americká matematická společnost, str. 85–92, ISBN 978-0-8218-4140-2.
- Ziegler, Günter M. (1995), Přednášky na PolytopechSpringer-Verlag, postgraduální texty z matematiky 152.
Další čtení
- Le Conte de Poly-Barbut, Cl. (1990), „Le diagramme du treillis permutoèdre est intersection des diagrammes de deux produits directs d'ordres totaux“, Mathématiques, Informatique et Sciences Humaines, 112: 49–53.
- Santmyer, Joe (2007), „Pro všechny možné vzdálenosti hledejte permutohedron“, Matematický časopis, 80 (2): 120–125, doi:10.1080 / 0025570X.2007.11953465
externí odkazy
- Bryan Jacobs. "Permutohedron". MathWorld.
- Alexander Postnikov (2005). „Permutohedra, associahedra a ještě dále“. arXiv:math.CO/0507163.