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

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

Властивості

Вершини

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

Ребра

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

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

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

Фасети

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

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

Симетрії

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

Об'єм

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

${\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]

Примітки

1. Ziegler, 2007, с. 20.
2. Birkhoff, 1946, с. 147–151.
3. Kőnig, 1916, с. 104–119.
4. The Volumes of Birkhoff polytopes [Архівовано 5 лютого 2012 у Wayback Machine.] for n ≤ 10.
5. Pak, 2000.
6. De Loera, Liu, Yoshida, 2007, с. 113–139.
7. Canfield, McKay, 2007.

Література

• . Lectures on Polytopes = 2006. — 7th. — New York : Springer, 2007. — Т. 152. — (Graduate Texts in Mathematics) — .
• 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) з посиланнями на статті.