Многогранник Біркгофа Bn, який також називають многогранником призначень, многогранником двічі стохастичних матриць або многогранником досконалих парувань повного двочасткового графа , це опуклий многогранник в RN (де ), точками якого є двічі стохастичні матриці, тобто n × n матриці, елементами яких є невід'ємні дійсні числа і сума рядків і стовпців цих матриць дорівнює 1.
Властивості
Вершини
Многогранник Біркгофа має n! вершин, по одній вершині на кожну перестановку n елементів. Це випливає з теореми Біркгофа — фон Неймана, яка стверджує, що [en] многогранника Біркгофа — це матриці перестановок, і тому, що будь-яку двічі стохастичну матрицю можна подати у вигляді опуклої комбінації матриць перестановок. Це довів 1946 року в своїй статті Гаррет Біркгоф, але еквівалентні результати в термінах конфігурацій і парувань регулярних двочасткових графів показали значно раніше у своїх тезах (1894) і Денеш Кеніг (1916).
Ребра
Ребра многогранника Біркгофа відповідають парам перестановок, що відрізняються циклом:
- перестановка така, що є циклом.
З цього випливає, що граф многогранника Bn є графом Келі симетричної групи Sn. Звідси також випливає, що граф B3 є повним графом K6, а тоді B3 — суміжнісний многогранник.
Фасети
Многогранник Біркгофа лежить усередині (n2 − 2n + 1)-вимірного афінного підпростору n2-вимірного простору всіх n × n матриць — цей підпростір задається лінійними обмеженнями, що сума в кожному рядку і кожному стовпці дорівнює одиниці. Всередині цього підпростору накладається n2 лінійних нерівностей, по одній на кожну координату, які вимагають невід'ємність координат.
Таким чином, многогранник має рівно n2 фасет.
Симетрії
Многогранник Біркгофа Bn вершинно-транзитивний і гране-транзитивний (тобто дуальний многогранник вершинно-транзитивний). Многогранник не належить до правильних для n>2.
Об'єм
Нерозв'язаною задачею є знаходження об'єму многогранників Біркгофа. Об'єм знайдено для . Відомо, що об'єм дорівнює об'єму многогранника, асоційованого зі стандартною діаграмою Юнга. Комбінаторну формулу для всіх n дано 2007 року. Наступну асимптотичну формулу знайшли Родні Кенфілд і [en]:
Многочлен Ергарта
Знайти многочлен Ергарта многогранника складніше, ніж знайти об'єм, оскільки об'єм можна легко вирахувати зі старшого коефіцієнта многочлена Ергарта. Многочлен Ергарта, асоційований з многогранником Біркгофа, відомий тільки для малих значень і є тільки гіпотеза, що всі коефіцієнти многочленів Ергарта (для многогранників Біркгофа) невід'ємні.
Узагальнення
- Многогранник Біркгофа є окремим випадком транспортного многогранника, многогранником прямокутних матриць з невід'ємними елементами з заданими сумами рядків і стовпців. Цілі точки такого многогранника називають таблицями спряженості. Вони відіграють важливу роль у баєсовій статистиці.
- Многогранник Біркгофа є окремим випадком [en], визначеного як опукла оболонка досконалих парувань скінченного графа. Опис фасет у цьому узагальненні дав [en] (1965) і вони пов'язані з алгоритмом Едмондса.
Див. також
- [ru]
Примітки
- Ziegler, 2007, с. 20.
- Birkhoff, 1946, с. 147–151.
- Kőnig, 1916, с. 104–119.
- The Volumes of Birkhoff polytopes [Архівовано 5 лютого 2012 у Wayback Machine.] for n ≤ 10.
- Pak, 2000.
- De Loera, Liu, Yoshida, 2007, с. 113–139.
- 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 (10 листопада). — С. 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 (10 листопада).
- Igor Pak. Four questions on Birkhoff polytope // Annals of Combinatorics. — 2000. — Т. 4 (10 листопада). — DOI: .
- 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 (10 листопада). — arXiv:math.CO/0701866. — DOI: .
- Rodney E. Canfield, Brendan D. McKay. The asymptotic volume of the Birkhoff polytope. — 2007. — 10 листопада.
- 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.
Посилання
- Багтогранник Біркгофа [Архівовано 6 березня 2016 у Wayback Machine.] — вебсайт Деніса Пікстона (Dennis Pixton) і Матіаса Бека (Matthias Beck) з посиланнями на статті.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Mnogogrannik Birkgofa Bn yakij takozh nazivayut mnogogrannikom priznachen mnogogrannikom dvichi stohastichnih matric abo mnogogrannikom doskonalih paruvan povnogo dvochastkovogo grafa K n n displaystyle K n n 1 ce opuklij mnogogrannik v RN de N n 2 displaystyle N n 2 tochkami yakogo ye dvichi stohastichni matrici tobto n n matrici elementami yakih ye nevid yemni dijsni chisla i suma ryadkiv i stovpciv cih matric dorivnyuye 1 Zmist 1 Vlastivosti 1 1 Vershini 1 2 Rebra 1 3 Faseti 1 4 Simetriyi 1 5 Ob yem 1 6 Mnogochlen Ergarta 2 Uzagalnennya 3 Div takozh 4 Primitki 5 Literatura 6 PosilannyaVlastivostired Vershinired Mnogogrannik Birkgofa maye n vershin po odnij vershini na kozhnu perestanovku n elementiv 1 Ce viplivaye z teoremi Birkgofa fon Nejmana yaka stverdzhuye sho ekstremalni tochki en mnogogrannika Birkgofa ce matrici perestanovok i tomu sho bud yaku dvichi stohastichnu matricyu mozhna podati u viglyadi opukloyi kombinaciyi matric perestanovok Ce doviv 1946 roku v svoyij statti Garret Birkgof 2 ale ekvivalentni rezultati v terminah konfiguracij i paruvan regulyarnih dvochastkovih grafiv pokazali znachno ranishe Ernst Shtajnic u svoyih tezah 1894 i Denesh Kenig 1916 3 Rebrared Rebra mnogogrannika Birkgofa vidpovidayut param perestanovok sho vidriznyayutsya ciklom perestanovka s w displaystyle sigma omega nbsp taka sho s 1 w displaystyle sigma 1 omega nbsp ye ciklom Z cogo viplivaye sho graf mnogogrannika Bn ye grafom Keli simetrichnoyi grupi Sn Zvidsi takozh viplivaye sho graf B3 ye povnim grafom K6 a todi B3 sumizhnisnij mnogogrannik Fasetired Mnogogrannik Birkgofa lezhit useredini n2 2n 1 vimirnogo afinnogo pidprostoru n2 vimirnogo prostoru vsih n n matric cej pidprostir zadayetsya linijnimi obmezhennyami sho suma v kozhnomu ryadku i kozhnomu stovpci dorivnyuye odinici Vseredini cogo pidprostoru nakladayetsya n2 linijnih nerivnostej po odnij na kozhnu koordinatu yaki vimagayut nevid yemnist koordinat Takim chinom mnogogrannik maye rivno n2 faset 1 Simetriyired Mnogogrannik Birkgofa Bn vershinno tranzitivnij i grane tranzitivnij tobto dualnij mnogogrannik vershinno tranzitivnij Mnogogrannik ne nalezhit do pravilnih dlya n gt 2 Ob yemred Nerozv yazanoyu zadacheyu ye znahodzhennya ob yemu mnogogrannikiv Birkgofa Ob yem znajdeno dlya n 10 displaystyle n leqslant 10 nbsp 4 Vidomo sho ob yem dorivnyuye ob yemu mnogogrannika asocijovanogo zi standartnoyu diagramoyu Yunga 5 Kombinatornu formulu dlya vsih n dano 2007 roku 6 Nastupnu asimptotichnu formulu znajshli Rodni Kenfild i Brendan Makkej en 7 v o l B n exp n 1 2 ln n n 2 n 1 2 ln 2 p 1 3 o 1 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 nbsp Mnogochlen Ergartared Dokladnishe Mnogochlen Ergarta Znajti mnogochlen Ergarta mnogogrannika skladnishe nizh znajti ob yem oskilki ob yem mozhna legko virahuvati zi starshogo koeficiyenta mnogochlena Ergarta Mnogochlen Ergarta asocijovanij z mnogogrannikom Birkgofa vidomij tilki dlya malih znachen i ye tilki gipoteza sho vsi koeficiyenti mnogochleniv Ergarta dlya mnogogrannikiv Birkgofa nevid yemni Uzagalnennyared Mnogogrannik Birkgofa ye okremim vipadkom transportnogo mnogogrannika mnogogrannikom pryamokutnih matric z nevid yemnimi elementami z zadanimi sumami ryadkiv i stovpciv Cili tochki takogo mnogogrannika nazivayut tablicyami spryazhenosti Voni vidigrayut vazhlivu rol u bayesovij statistici Mnogogrannik Birkgofa ye okremim vipadkom mnogogrannika paruvan en viznachenogo yak opukla obolonka doskonalih paruvan skinchennogo grafa Opis faset u comu uzagalnenni dav Dzhek Edmonds en 1965 i voni pov yazani z algoritmom Edmondsa Div takozhred Permutoedr ru Primitkired a b v Ziegler 2007 s 20 Birkhoff 1946 s 147 151 Konig 1916 s 104 119 The Volumes of Birkhoff polytopes Arhivovano 5 lyutogo 2012 u Wayback Machine for n 10 Pak 2000 De Loera Liu Yoshida 2007 s 113 139 Canfield McKay 2007 Literaturared Gunter M Ziegler Lectures on Polytopes 2006 7th New York Springer 2007 T 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 Tucuman Revista A 1946 T 5 10 listopada S 147 151 Denes Konig Grafok es alkalmazasuk a determinansok es a halmazok elmeletere Matematikai es Termeszettudomanyi Ertesito 1916 T 34 10 listopada Igor Pak Four questions on Birkhoff polytope Annals of Combinatorics 2000 T 4 10 listopada 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 T 30 10 listopada 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 10 listopada 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 Posilannyared Bagtogrannik Birkgofa Arhivovano 6 bereznya 2016 u Wayback Machine vebsajt Denisa Pikstona Dennis Pixton i Matiasa Beka Matthias Beck z posilannyami na statti Otrimano z https uk wikipedia org w index php title Mnogogrannik Birkgofa amp oldid 43026870