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

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

Властивості

Вершини

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

Ребра

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

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

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

Фасети

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

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

Симетрії

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

Об'єм

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

$\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).$

Многочлен Ергарта

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

Узагальнення

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

Див. також

• Пермутоедр

Література

• 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 (25 квітня). — С. 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 (25 квітня).
• Igor Pak. Four questions on Birkhoff polytope // Annals of Combinatorics. — 2000. — Т. 4 (25 квітня). — 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 (25 квітня). — 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. — 25 квітня.
• 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) з посиланнями на статті.