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

Свойства

Вершины

Многогранник Биркгофа имеет n ! вершин, по одной вершине на каждую перестановку n элементов . Это следует из теоремы Биркгофа — Фон Неймана , которая утверждает, что многогранника Биркгофа — это матрицы перестановок , и потому, что любая дважды стохастическая матрица может быть представлена в виде выпуклой комбинации матриц перестановок. Это доказал в 1946 году в своей статье Гаррет Биркгоф , но эквивалентные результаты в терминах конфигураций и паросочетаний регулярных двудольных графов показали много ранее в 1894 году Эрнст Штайниц в своих тезисах и в 1916 году Денеш Кёниг .

Рёбра

Рёбра многогранника Биркгофа соответствуют парам перестановок, различающихся циклом:

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

Из этого следует, что граф многогранника B _n является графом Кэли симметрической группы S _n . Отсюда также следует, что граф B ₃ является полным графом K ₆ , а тогда B ₃ — смежностный многогранник .

Фасеты

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

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

Симметрии

Многогранник Биркгофа B _n вершинно транзитивен и гранетранзитивен (то есть двойственный многогранник вершинно транзитивен). Многогранник не входит в число правильных для n>2 .

Объём

Нерешённой задачей является нахождение объёма многогранников Биркгофа. Объём найден для ${\displaystyle n\leqslant 10}$ . Известно, что объём равен объёму многогранника, ассоциированного со стандартной диаграммой Юнга . Комбинаторная формула для всех n дана в 2007 . Следующую асимптотическую формулу нашли и :

${\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).}$

Многочлен Эрхарта

Нахождение многочлена Эрхарта многогранника сложнее, чем нахождение объёма, поскольку объём можно легко вычислить из ведущего коэффициента многочлена Эрхарта. Многочлен Эрхарта, ассоциированный с многогранником Биркгофа, известен только для малых значений и только имеется гипотеза, что все коэффициенты многочленов Эрхарта (для многогранников Биркгофа) неотрицательны.

Обобщения

• Многогранник Биркгофа является специальным случаем транспортного многогранника, многогранником прямоугольных матриц с неотрицательными элементами с заданными суммами по строкам и столбцам. Целые точки такого многогранника называются таблицами сопряжённости . Они играют важную роль в байесовой статистике .
• Многогранник Биркгофа является специальным случаем , определённого как выпуклая оболочка совершенных паросочетаний конечного графа. Описание фасет в этом обобщении дал (1965) и они связаны с .

См. также

• Перестановочный многогранник

Примечания

Литература

• Günter M. Ziegler . Lectures on Polytopes. — 7th. — New York: Springer, 2007. — Т. 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. Tucumán. Revista A.. — 1946. — Т. 5 . — С. 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 .
• Igor Pak. Four questions on Birkhoff polytope // Annals of Combinatorics. — 2000. — Т. 4 . — 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 . — doi : . — arXiv : .
• Rodney E. Canfield, Brendan D. McKay. The asymptotic volume of the Birkhoff polytope. — 2007.

Литература для дальнейшего чтения

• Matthias Beck and Dennis Pixton (2003), The Ehrhart polynomial of the Birkhoff polytope, , Vol. 30, pp. 623—637. The volume of B ₉ .

Ссылки

• Web site by Dennis Pixton and Matthias Beck, with links to articles and volumes.