Birkhoffův mnohostěn - Birkhoff polytope

The Birkhoffův mnohostěn B_n (nazývané také přiřazení polytop, polytop dvojnásobně stochastických matic, nebo dokonale sladěný polytop z kompletní bipartitní graf  ${displaystyle K_ {n, n}}$^[1]) je konvexní mnohostěn v R^N (kde N = n²) jehož body jsou dvojnásobně stochastické matice, tj n × n matice jejichž položky jsou nezáporné reálná čísla a jejichž řádky a sloupce přidávají každý až 1. Je pojmenován po Garrett Birkhoff.

Vlastnosti

Vrcholy

Birkhoffův polytop má n! vrcholy, jeden pro každou permutaci na n položky.^[1] To vyplývá z Birkhoff – von Neumannova věta, ve kterém se uvádí, že extrémní body z Birkhoffova polytopu jsou permutační matice, a proto může být jakákoli dvojnásobně stochastická matice reprezentována jako konvexní kombinace permutačních matic; toto bylo uvedeno v dokumentu z roku 1946 od Garrett Birkhoff,^[2] ale ekvivalentní výsledky v jazycích projektivní konfigurace a ze dne pravidelný bipartitní graf párování, v uvedeném pořadí, byly uvedeny mnohem dříve v roce 1894 v Ernst Steinitz práce a v roce 1916 autorem Dénes Kőnig.^[3] Protože všechny souřadnice vrcholů jsou nula nebo jedna, Birkhoffův polytop je integrální polytop.

Hrany

Okraje Birkhoffova polytopu odpovídají dvojicím permutací, které se liší cyklem:

${displaystyle (sigma, omega)}$ takhle ${displaystyle sigma ^ {- 1} omega}$ je cyklus.

To znamená, že graf z B_n je Cayleyův graf z symetrická skupina S_n. Z toho také vyplývá, že graf B₃ je kompletní graf K.₆, a tudíž B₃ je sousedský polytop.

Fazety

Birkhoffův polytop leží uvnitř (n² − 2n + 1)-dimenzionální afinní podprostor z n²-dimenzionální prostor všech n × n matice: tento podprostor je určen omezením lineární rovnosti, že součet každého řádku a každého sloupce je jeden. V tomto podprostoru je definován n² lineární nerovnosti, jedna pro každou souřadnici matice, která určuje, že souřadnice musí být nezáporná. Proto pro ${displaystyle ngeq 3}$, má to přesně n² fazety.^[1] Pro n = 2 existují dvě fazety dané A₁₁ = A₂₂ = 0 a A₁₂ = A₂₁ = 0.

Symetrie

Birkhoffův mnohostěn B_n je obojí vrchol-tranzitivní a fazeta-tranzitivní (tj duální polytop je vrchol-tranzitivní). Není pravidelný pro n> 2.

Objem

Vynikajícím problémem je najít objem polytopů Birkhoff. To bylo provedeno pro n ≤ 10.^[4] Je známo, že se rovná objemu polytopu spojeného se standardem Mladé obrazy.^[5] Kombinatorický vzorec pro všechny n byl uveden v roce 2007.^[6] Následující asymptotický vzorec byl nalezen uživatelem Rodney Canfield a Brendan McKay:^[7]

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

Pro malé hodnoty ${displaystyle nleq 15}$ objem byl odhadnut v roce 2014^[8] zatímco podobné odhady následují.^[9]

Ehrhartův polynom

Určení Ehrhartův polynom polytopu je těžší než určit jeho objem, protože objem lze snadno vypočítat z hlavního koeficientu Ehrhartova polynomu. Ehrhartův polynom spojený s Birkhoffovým polytopem je znám pouze pro malé hodnoty.^[10] Předpokládá se, že všechny koeficienty Ehrhartových polynomů jsou nezáporné.

Zobecnění

• Birkhoffův polytop je zvláštním případem dopravní polytop, polytop nezáporných obdélníkových matic s danými součty řádků a sloupců.^[11] Celé body v těchto polytopech se nazývají kontingenční tabulky; hrají důležitou roli v Bayesovské statistiky.
• Birkhoffův polytop je zvláštním případem odpovídající mnohostěn, definované jako a konvexní obal z perfektní párování v konečném grafu. Popis fazet v této obecnosti byl dán Jack Edmonds (1965) a souvisí s Edmondsův srovnávací algoritmus.
• Birkhoffův polytop je zvláštním případem tokový mnohostěn nezáporných toků sítí.^[12] Souvisí to s Algoritmus Ford-Fulkerson který vypočítává maximální tok v síti toku.

Viz také

• Birkhoffův algoritmus
• Permutohedron
• Stabilní odpovídající polytop

Reference

externí odkazy

• Birkhoffův mnohostěn Web Dennis Pixton a Matthias Beck, s odkazy na články a svazky.