Birkhoff polytop

Birkhoff -polytopen B _n (även kallad tilldelningen polytop , polytopen av dubbelstokastiska matriser , eller den perfekt matchande polytopen för den kompletta tvådelade grafen ${\displaystyle K_{n,n}} )$ är den konvexa polytopen i R ^N (där N = n ² ) vars punkter är de dubbelstokastiska matriserna , dvs de n × n matriserna vars poster är icke-negativa reella tal och vars rader och kolumner var och en summerar till 1. Den är uppkallad efter Garrett Birkhoff .

Egenskaper

Vertices

Birkhoff-polytopen har n ! hörn, en för varje permutation på n objekt. Detta följer av Birkhoff–von Neumann-satsen , som säger att ytterpunkterna för Birkhoff-polytopen är permutationsmatriserna, och därför att vilken dubbelstokastisk matris som helst kan representeras som en konvex kombination av permutationsmatriser; detta angavs i ett papper från 1946 av Garrett Birkhoff , men motsvarande resultat i språken för projektiva konfigurationer och regelbundna tvådelade grafmatchningar , respektive, visades mycket tidigare 1894 i Ernst Steinitzs avhandling och 1916 av Dénes Kőnig . Eftersom alla vertexkoordinater är noll eller en, är Birkhoff-polytopen en integrerad polytop .

Kanter

Kanterna på Birkhoff-polytopen motsvarar par av permutationer som skiljer sig åt med en cykel:

(\sigma ,\omega )

så att

\sigma ^{-1}\omega

är en cykel.

Detta innebär att grafen för B _n är en Cayley-graf för den symmetriska gruppen S _n . Detta innebär också att grafen för B ₃ är en komplett graf K ₆ , och därför är B _{3 en} grannpolytop .

Fasett

Birkhoff-polytopen ligger inom ett ( n ² − 2 n + 1) -dimensionellt affint delrum av det n ² -dimensionella rummet av alla n × n matriser: detta delrum bestäms av de linjära likhetsbegränsningarna som summan av varje rad och av varje kolumn vara en. Inom detta delrum definieras det av n ² linjära olikheter , en för varje koordinat i matrisen, vilket anger att koordinaten är icke-negativ. Därför, för $n\geq 3$ , har den exakt n ² fasetter . För n = 2 finns det två aspekter, angivna av a ₁₁ = a ₂₂ = 0, och a ₁₂ = a ₂₁ = 0.

Symmetrier

Birkhoff-polytopen B _n är både vertextransitiv och facetttransitiv (dvs den dubbla polytopen är vertextransitiv). Det är inte regelbundet för n>2 .

Volym

Ett enastående problem är att hitta volymen på Birkhoff-polytoperna. Detta har gjorts för n ≤ 10. Det är känt att det är lika med volymen av en polytop associerad med standard Young-tablåer . En kombinatorisk formel för alla n gavs 2007. Följande asymptotiska formel hittades av Rodney Canfield och Brendan McKay :

\mathop {\mathrm {vol} } (B_{n})\,=\,\exp \left(-(n-1)^{2}\ln n+n^{2}-(n -{\frac {1}{2}})\ln(2\pi )+{\frac {1}{3}}+o(1)\right).

För små värden $n\leq 15$ uppskattades volymen 2014 medan liknande uppskattningar följer.

Ehrhart polynom

Att bestämma Ehrhart-polynomet för en polytop är svårare än att bestämma dess volym, eftersom volymen lätt kan beräknas från den ledande koefficienten för Ehrhart-polynomet. Ehrhart-polynomet associerat med Birkhoff-polytopen är bara känt för små värden. Det antas att alla koefficienter för Ehrhart-polynomen är icke-negativa.

Generaliseringar

Birkhoff-polytopen är ett specialfall av transportpolytopen , en polytop av icke-negativa rektangulära matriser med givna rad- och kolumnsummor. Heltalspunkterna i dessa polytoper kallas kontingenstabeller ; de spelar en viktig roll i Bayesiansk statistik .
Birkhoff-polytopen är ett specialfall av den matchande polytopen , definierad som ett konvext skrov med perfekta matchningar i en finit graf. Beskrivningen av fasetter i denna generalitet gavs av Jack Edmonds (1965), och är relaterad till Edmonds matchningsalgoritm .
Birkhoff-polytopen är ett specialfall av flödespolytopen av icke-negativa flöden genom ett nätverk. Det är relaterat till Ford–Fulkerson-algoritmen som beräknar det maximala flödet i ett flödesnätverk.

Se även

externa länkar

Birkhoff polytopwebbplats av Dennis Pixton och Matthias Beck, med länkar till artiklar och volymer.