Многогранник Біркгофа Bn, який також називають многогранником призначень, многогранником двічі стохастичних матриць або многогранником досконалих парувань повного двочасткового графа , це опуклий многогранник в RN (де ), точками якого є двічі стохастичні матриці, тобто матриці, елементами яких є невід'ємні дійсні числа і сума рядків і стовпців цих матриць дорівнює 1.
Властивості
Вершини Многогранник Біркгофа має n! вершин, по одній вершині на кожну перестановку n елементів. Це випливає з теореми Біркгофа — фон Неймана, яка стверджує, що многогранника Біркгофа — це матриці перестановок, і тому, що будь-яку двічі стохастичну матрицю можна подати у вигляді опуклої комбінації матриць перестановок. Це довів 1946 року в своїй статті Гаррет Біркгоф, але еквівалентні результати в термінах конфігурацій і парувань регулярних двочасткових графів показали значно раніше Ернст Штайніц у своїх тезах (1894) і Денеш Кеніг (1916).
Ребра Ребра многогранника Біркгофа відповідають парам перестановок, що відрізняються циклом:
перестановка така, що є циклом.
З цього випливає, що граф многогранника Bn є графом Келі симетричної групи Sn. Звідси також випливає, що граф B3 є повним графом K6, а тоді B3 — суміжнісний многогранник.
Фасети Многогранник Біркгофа лежить усередині вимірного афінного підпростору n2-вимірного простору всіх матриць — цей підпростір задається лінійними обмеженнями, що сума в кожному рядку і кожному стовпці дорівнює одиниці. Всередині цього підпростору накладається n2 лінійних нерівностей, по одній на кожну координату, які вимагають невід'ємність координат.
Таким чином, многогранник має рівно n2 фасет.
Симетрії Многогранник Біркгофа Bn вершинно-транзитивний і гране-транзитивний (тобто дуальний многогранник вершинно-транзитивний). Многогранник не належить до правильних для n>2.
Об'єм Нерозв'язаною задачею є знаходження об'єму многогранників Біркгофа. Об'єм знайдено для The Volumes of Birkhoff polytopes for n ≤ 10.. Відомо, що об'єм дорівнює об'єму многогранника, асоційованого зі стандартною діаграмою Юнга. Комбінаторну формулу для всіх n дано 2007 року. Наступну асимптотичну формулу знайшли Родні Кенфілд і :
Многочлен Ергарта
Знайти многочлен Ергарта многогранника складніше, ніж знайти об'єм, оскільки об'єм можна легко вирахувати зі старшого коефіцієнта многочлена Ергарта. Многочлен Ергарта, асоційований з многогранником Біркгофа, відомий тільки для малих значень і є тільки гіпотеза, що всі коефіцієнти многочленів Ергарта (для многогранників Біркгофа) невід'ємні.
Узагальнення Многогранник Біркгофа є окремим випадком транспортного многогранника, многогранником прямокутних матриць з невід'ємними елементами з заданими сумами рядків і стовпців. Цілі точки такого многогранника називають таблицями спряженості. Вони відіграють важливу роль у баєсовій статистиці. Многогранник Біркгофа є окремим випадком , визначеного як опукла оболонка досконалих парувань скінченного графа. Опис фасет у цьому узагальненні дав (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 B9.
Посилання Багтогранник Біркгофа — вебсайт Деніса Пікстона (Dennis Pixton) і Матіаса Бека (Matthias Beck) з посиланнями на статті.