Birkhoffův mnohostěn

Birkhoffův polytop B n , nazývaný také polytop přiřazení , dvojitě stochastický maticový polytop nebo dokonale odpovídající polytop úplného bipartitního grafu  [1] , je konvexní polytop v RN ( kde ), jehož body jsou dvojité stochastické matice , tzn. , n × n matic, jejichž prvky jsou nezáporná reálná čísla a součet řádků a sloupců těchto matic je 1.

Vlastnosti

Vrcholy

Birkhoffův mnohostěn má n ! vrcholy, jeden vrchol pro každou permutaci n prvků [1] . Toto vyplývá z Birkhoff-Von Neumannovy věty , která říká, že extrémní body Birkhoffova polytopu jsou permutační matice , a protože každá dvojnásobně stochastická matice může být reprezentována jako konvexní kombinace permutačních matic. To bylo dokázáno v roce 1946 ve svém článku Garretta Birkhoffa [2] , ale ekvivalentní výsledky, pokud jde o konfigurace a shody regulárních bipartitních grafů , ukázal mnohem dříve v roce 1894 Ernst Steinitz ve svých tezích a v roce 1916 Denesh König [3] .

Žebra

Okraje Birkhoffova mnohostěnu odpovídají párům permutací, které se liší v cyklu:

permutace taková, že jde o cyklus.

Z toho vyplývá, že graf polytopu B n je Cayleyovým grafem symetrické grupy S n . To také znamená, že graf B 3 je úplný graf K 6 a pak B 3  je polytop sousedství .

Fazety

Birkhoffův mnohostěn leží uvnitř ( n 2 − 2 n + 1) -rozměrného afinního podprostoru n 2 -rozměrného prostoru všech n × n matic – tento podprostor je dán lineárními vazbami, které součet za každý řádek a každý sloupec se rovná jedné. Uvnitř tohoto podprostoru je uloženo n 2 lineárních nerovností , jedna pro každou souřadnici, což vyžaduje nezápornost souřadnic.

Mnohostěn má tedy přesně n 2 faset [1] .

Symetrie

Birkhoffův polytop Bn je vertex -tranzitivní a face -tranzitivní (to znamená, že duální polytop je vertex-tranzitivní). Mnohostěn nepatří mezi ty správné pro n>2 .

Svazek

Nevyřešeným problémem je zjištění objemu Birkhoffových mnohostěnů. Nalezen svazek pro [4] . Je známo, že objem je roven objemu mnohostěnu spojeného se standardním Youngovým diagramem [5] . Kombinatorický vzorec pro všechna n je uveden v roce 2007 [6] . Následující asymptotický vzorec našli Rodney Canfield a Brendan McKay [7] :

Earhartův polynom

Najít Earhartův polynom mnohostěnu je obtížnější než najít objem, protože objem lze snadno vypočítat z vedoucího koeficientu Earhartova polynomu. Earhartův polynom spojený s Birkhoffovým polytopem je znám pouze pro malé hodnoty a existuje pouze domněnka, že všechny koeficienty Earhartových polynomů (pro Birkhoffovy polytopy) jsou nezáporné.

Zobecnění

Viz také

Poznámky

  1. ↑ 1 2 3 Ziegler, 2007 , str. dvacet.
  2. ↑ Birkhoff, 1946 , s. 147–151.
  3. ↑ Kőnig, 1916 , s. 104–119.
  4. ↑ The Volumes of Birkhoff polytopes Archived 5. února 2012 na Wayback Machine pro n ≤ 10.
  5. ↑ Pack, 2000 .
  6. ↑ De Loera, Liu, Yoshida, 2007 , str. 113–139.
  7. ↑ Canfield, McKay, 2007 .

Literatura

Čtení pro další čtení

Odkazy