Loading AI tools
З Вікіпедії, вільної енциклопедії
Многогранник Біркгофа Bn, який також називають многогранником призначень, многогранником двічі стохастичних матриць або многогранником досконалих парувань повного двочасткового графа [1], це опуклий многогранник в RN (де ), точками якого є двічі стохастичні матриці, тобто n × n матриці, елементами яких є невід'ємні дійсні числа і сума рядків і стовпців цих матриць дорівнює 1.
Многогранник Біркгофа має n! вершин, по одній вершині на кожну перестановку n елементів[1]. Це випливає з теореми Біркгофа — фон Неймана, яка стверджує, що екстремальні точки[en] многогранника Біркгофа — це матриці перестановок, і тому, що будь-яку двічі стохастичну матрицю можна подати у вигляді опуклої комбінації матриць перестановок. Це довів 1946 року в своїй статті Гаррет Біркгоф[2], але еквівалентні результати в термінах конфігурацій і парувань регулярних двочасткових графів показали значно раніше Ернст Штайніц у своїх тезах (1894) і Денеш Кеніг (1916)[3].
Ребра многогранника Біркгофа відповідають парам перестановок, що відрізняються циклом:
З цього випливає, що граф многогранника Bn є графом Келі симетричної групи Sn. Звідси також випливає, що граф B3 є повним графом K6, а тоді B3 — суміжнісний многогранник.
Многогранник Біркгофа лежить усередині (n2 − 2n + 1)-вимірного афінного підпростору n2-вимірного простору всіх n × n матриць — цей підпростір задається лінійними обмеженнями, що сума в кожному рядку і кожному стовпці дорівнює одиниці. Всередині цього підпростору накладається n2 лінійних нерівностей, по одній на кожну координату, які вимагають невід'ємність координат.
Многогранник Біркгофа Bn вершинно-транзитивний і гране-транзитивний (тобто дуальний многогранник вершинно-транзитивний). Многогранник не належить до правильних для n>2.
Нерозв'язаною задачею є знаходження об'єму многогранників Біркгофа. Об'єм знайдено для [4]. Відомо, що об'єм дорівнює об'єму многогранника, асоційованого зі стандартною діаграмою Юнга[5]. Комбінаторну формулу для всіх n дано 2007 року[6]. Наступну асимптотичну формулу знайшли Родні Кенфілд і Брендан Маккей[en][7]:
Знайти многочлен Ергарта многогранника складніше, ніж знайти об'єм, оскільки об'єм можна легко вирахувати зі старшого коефіцієнта многочлена Ергарта. Многочлен Ергарта, асоційований з многогранником Біркгофа, відомий тільки для малих значень і є тільки гіпотеза, що всі коефіцієнти многочленів Ергарта (для многогранників Біркгофа) невід'ємні.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.