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

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

Властивості

Вершини

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

Ребра

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

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

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

Фасети

Многогранник Біркгофа лежить усередині Шаблон:Nobrвимірного афінного підпростору n²-вимірного простору всіх Шаблон:Nobr матриць — цей підпростір задається лінійними обмеженнями, що сума в кожному рядку і кожному стовпці дорівнює одиниці. Всередині цього підпростору накладається n² лінійних нерівностей, по одній на кожну координату, які вимагають невід'ємність координат.

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

Симетрії

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

Об'єм

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

$\mathrm{v}\mathrm{o}\mathrm{l}(B_n)=\exp (-(n-1{)}^2\ln n+n^2-(n-\frac{1}{2})\ln (2\pi )+\frac{1}{3}+o(1)).$

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

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

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

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

Див. також

• Шаблон:Нп

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• 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₉.

Посилання

• Багтогранник Біркгофа Шаблон:Webarchive — вебсайт Деніса Пікстона (Dennis Pixton) і Матіаса Бека (Matthias Beck) з посиланнями на статті.