Багатогранник Біркгофа

Багатогранник Біркгофа має n! вершин, по одній вершині на кожну перестановку n елементів[1]. Це випливає з теореми Біркгофа — фон Неймана, яка стверджує, що екстремальні точки багатогранника Біркгофа — це матриці перестановок, і тому, що будь-яку двічі стохастичну матрицю можна подати у вигляді опуклої комбінації матриць перестановок. Це довів 1946 року в своїй статті Гаррет Біркгоф[2], але еквівалентні результати в термінах конфігурацій і парувань регулярних двочасткових графів показали значно раніше Ернст Штайніц у своїх тезах (1894) і Денеш Кеніг (1916)[3].

Ребра багатогранника Биркгофа відповідають парам перестановок, що відрізняються циклом:

перестановка ${\displaystyle (\sigma ,\omega )}$ така, що ${\displaystyle \sigma ^{-1}\omega }$ є циклом.

З цього випливає, що граф багатогранника B_n є графом Келі симетричної групи S_n. Звідси також випливає, що граф B₃ є повним графом K₆, а тоді B₃ — суміжнісний багатогранник.

Багатогранник Біркгофа лежить усередині (n² − 2n + 1)-вимірного афінного підпростору n²-вимірного простору всіх n × n матриць — цей підпростір задається лінійними обмеженнями, що сума в кожному рядку і кожному стовпці дорівнює одиниці. Всередині цього підпростору накладається n² лінійних нерівностей, по одній на кожну координату, які вимагають невід'ємність координат.

Таким чином, багатогранник має рівно n² фасет[1].

Багатогранник Біркгофа B_n вершинно-транзитивний і гране-транзитивний (тобто двоїстий багатогранник вершинно-транзитивний). Багатогранник не належить до правильних для n>2.

Нерозв'язаною задачею є знаходження об'єму багатогранників Біркгофа. Об'єм знайдено для ${\displaystyle n\leqslant 10}$[4]. Відомо, що об'єм дорівнює об'єму багатогранника, асоційованого зі стандартною діаграмою Юнга[5]. Комбінаторну формулу для всіх n дано 2007 року[6]. Наступну асимптотичну формулу знайшли Родні Кенфілд і Брендан МакКэй[7]:

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

Знайти многочлен Ергарта багатогранника складніше, ніж знайти об'єм, оскільки об'єм можна легко вирахувати зі старшого коефіцієнта многочлена Ергарта. Многочлен Ергарта, асоційований з багатогранником Біркгофа, відомий тільки для малих значень і є тільки гіпотеза, що всі коефіцієнти многочленів Ергарта (для багатогранників Біркгофа) невід'ємні.