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

Многогранник Біркгофа B_n, який також називають многогранником призначень, многогранником двічі стохастичних матриць або многогранником досконалих парувань повного двочасткового графа ${\displaystyle K_{n,n}}$^[1], це опуклий многогранник в R^N (де ${\displaystyle N=n^{2}}$), точками якого є двічі стохастичні матриці, тобто n × n матриці, елементами яких є невід'ємні дійсні числа і сума рядків і стовпців цих матриць дорівнює 1.

Многогранник Біркгофа має n! вершин, по одній вершині на кожну перестановку n елементів^[1]. Це випливає з теореми Біркгофа — фон Неймана, яка стверджує, що екстремальні точки^[en] многогранника Біркгофа — це матриці перестановок, і тому, що будь-яку двічі стохастичну матрицю можна подати у вигляді опуклої комбінації матриць перестановок. Це довів 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]. Наступну асимптотичну формулу знайшли Родні Кенфілд і Брендан Маккей^[en][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).}$

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

• Многогранник Біркгофа є окремим випадком транспортного многогранника, многогранником прямокутних матриць з невід'ємними елементами з заданими сумами рядків і стовпців. Цілі точки такого многогранника називають таблицями спряженості. Вони відіграють важливу роль у баєсовій статистиці.
• Многогранник Біркгофа є окремим випадком многогранника парувань^[en], визначеного як опукла оболонка досконалих парувань скінченного графа. Опис фасет у цьому узагальненні дав Джек Едмондс^[en] (1965) і вони пов'язані з алгоритмом Едмондса.

• Пермутоедр^[ru]

• Günter M. Ziegler. Lectures on Polytopes = 2006. — 7th. — New York : Springer, 2007. — Т. 152. — (Graduate Texts in Mathematics) — ISBN 978-0-387-94365-7.
• Garrett Birkhoff. Tres observaciones sobre el algebra lineal [Three observations on linear algebra] // Univ. Nac. Tucumán. Revista A.. — 1946. — Т. 5 (2 серпня). — С. 147–151.
• Dénes Kőnig. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére // Matematikai és Természettudományi Értesítő. — 1916. — Т. 34 (2 серпня).
• Igor Pak. Four questions on Birkhoff polytope // Annals of Combinatorics. — 2000. — Т. 4 (2 серпня). — DOI:10.1007/PL00001277.
• Jesus A. De Loera, Fu Liu, Ruriko Yoshida. Formulas for the volumes of the polytope of doubly-stochastic matrices and its faces // Journal of Algebraic Combinatorics. — 2007. — Т. 30 (2 серпня). — arXiv:math.CO/0701866. — DOI:10.1007/s10801-008-0155-y.
• Rodney E. Canfield, Brendan D. McKay. The asymptotic volume of the Birkhoff polytope. — 2007. — 2 серпня.
• Matthias Beck and Dennis Pixton (2003), The Ehrhart polynomial of the Birkhoff polytope, Discrete and Computational Geometry, Vol. 30, pp. 623—637. The volume of B₉.

• Багтогранник Біркгофа [Архівовано 6 березня 2016 у Wayback Machine.] — вебсайт Деніса Пікстона (Dennis Pixton) і Матіаса Бека (Matthias Beck) з посиланнями на статті.