Birkhoff poliéder

A B n Birkhoff-politóp , más néven hozzárendelési politóp , duplán sztochasztikus mátrixpolitóp , vagy a teljes bipartit gráf  [1] tökéletesen illeszkedő politópja , egy konvex politóp RN -ben ( ahol ), amelynek pontjai kétszeresen sztochasztikus mátrixok , azaz , n × n mátrixok, amelyek elemei nemnegatív valós számok, és e mátrixok sorainak és oszlopainak összege 1.

Tulajdonságok

Peaks

A Birkhoff poliéder n ! csúcsok, egy csúcs minden n elem permutációjához [1] . Ez a Birkhoff-Von Neumann tételből következik , amely kimondja, hogy a Birkhoff-politóp szélső pontjai permutációs mátrixok , és mivel bármely kétszeresen sztochasztikus mátrix ábrázolható permutációs mátrixok konvex kombinációjaként. Ezt Garrett Birkhoff [2] 1946-os cikkében bebizonyította , de a reguláris kétrészes gráfok konfigurációi és illesztése tekintetében már jóval korábban, 1894-ben Ernst Steinitz , 1916-ban pedig Denesh König [3] mutatott be ezzel egyenértékű eredményeket .

Bordák

A Birkhoff-poliéder élei olyan permutációpároknak felelnek meg, amelyek ciklusban különböznek:

Ebből következik, hogy a B n politóp gráfja az S n szimmetrikus csoport Cayley-gráfja . Ez azt is jelenti, hogy a B 3 gráf egy teljes K 6 gráf , majd B 3  egy szomszédsági politóp .

Facets

A Birkhoff-poliéder az összes n × n mátrix n 2 -dimenziós terének ( n 2 − 2 n + 1) -dimenziós affin alterében található – ezt az alteret a lineáris megszorítások adják, hogy az egyes sorok és oszlopok összege egyenlő eggyel. Ezen az altéren belül n 2 lineáris egyenlőtlenség van beállítva , minden koordinátához egy, ami megköveteli a koordináták negativitását.

Így egy poliédernek pontosan n 2 fazettája van [1] .

Szimmetriák

A B n Birkhoff-politóp vertex-tranzitív és arc -tranzitív (vagyis a kettős politóp csúcstranzitív ). A poliéder nem tartozik a helyesek közé n >2 esetén .

kötet

Megoldatlan probléma a Birkhoff poliéder térfogatának megtalálása. Megtalált kötet a [4] számára . Ismeretes, hogy a térfogat megegyezik a standard Young-diagrammal [5] társított poliéder térfogatával . Az összes n -re vonatkozó kombinatorikus képlet 2007-ben van megadva [6] . A következő aszimptotikus képletet találta Rodney Canfield és Brendan McKay [7] :

Earhart polinomja

Egy poliéder Earhart-polinomjának megtalálása nehezebb, mint a térfogat megtalálása, mivel a térfogat könnyen kiszámítható az Earhart-polinom vezető együtthatójából. A Birkhoff-politóphoz társított Earhart-polinom csak kis értékekről ismert, és csak egy sejtés van, hogy az Earhart-polinomok összes együtthatója (a Birkhoff-politópokra) nem negatív.

Általánosítások

• A Birkhoff-politóp egy speciális esete a transzportpolitópnak, egy téglalap alakú mátrixok politópja, amelyek nemnegatív bejegyzéseket tartalmaznak adott sor- és oszlopösszegekkel. Egy ilyen poliéder egész pontjait kontingenciatáblázatoknak nevezzük . Fontos szerepet játszanak a bayesi statisztikákban .
• A Birkhoff-politóp az illeszkedő politóp speciális esete , amelyet egy véges gráf tökéletes illeszkedésének konvex burkaiként definiálunk . Az általánosításban szereplő aspektusok leírását Jack Edmonds (1965) adta, és ezek az Edmonds-algoritmushoz kapcsolódnak .

Lásd még

• Permutációs poliéder

Jegyzetek

1. ↑ 1 2 3 Ziegler, 2007 , p. húsz.
2. ↑ Birkhoff, 1946 , p. 147–151.
3. ↑ Kőnig, 1916 , p. 104–119.
4. ↑ The Volumes of Birkhoff polytopes archiválva : 2012. február 5., a Wayback Machine for n ≤ 10.
5. ↑ Csomag, 2000 .
6. ↑ De Loera, Liu, Yoshida, 2007 , p. 113–139.
7. ↑ Canfield, McKay, 2007 .

Irodalom

• Günter M. Ziegler . Előadások a politópokról. — 7. - New York: Springer, 2007. - V. 152. - (Graduate Texts in Mathematics). — ISBN 978-0-387-94365-7 .
• Garrett Birkhoff . Tres observaciones sobre el algebra linear [Három megfigyelés a lineáris algebráról] // Univ. Nac. Tucuman. Revista A .. - 1946. - T. 5 . – S. 147–151 .
• Kőnig Dénes . Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére // Matematikai és Természettudományi Értesítő. - 1916. - T. 34 .
• Igor Pack. Négy kérdés a Birkhoff-politópról // Annals of Combinatorics. - 2000. - T. 4 . - doi : 10.1007/PL00001277 .
• Jesus A. De Loera, Fu Liu, Ruriko Yoshida. Képletek a duplán sztochasztikus mátrixok politópjának térfogatához és lapjaihoz // Journal of Algebraic Combinatorics. - 2007. - T. 30 . - doi : 10.1007/s10801-008-0155-y . - arXiv : math.CO/0701866 .
• Rodney E. Canfield, Brendan D. McKay. A Birkhoff-politóp aszimptotikus térfogata. – 2007.

Olvasás további olvasáshoz

• Matthias Beck és Dennis Pixton (2003), A Birkhoff-politóp Ehrhart-polinomja, Discrete and Computational Geometry , Vol. 30, pp. 623-637. A B kötet 9 .

Linkek

• Dennis Pixton és Matthias Beck Birkhoff -politóp webhelye cikkekre és kötetekre mutató hivatkozásokkal.