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

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

СвойстваПравить

ВершиныПравить

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

РёбраПравить

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

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

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

ФасетыПравить

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

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

СимметрииПравить

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

ОбъёмПравить

Нерешённой задачей является нахождение объёма многогранников Биркгофа. Объём найден для $n⩽<!--\; ⩽\; -->10$$n\leqslant 10$ . Известно, что объём равен объёму многогранника, ассоциированного со стандартной диаграммой Юнга. Комбинаторная формула для всех n дана в 2007. Следующую асимптотическую формулу нашли Родни Кэнфилд^[en] и Брендан МакКэй^[en]:

$\mathrm{v}\mathrm{o}\mathrm{l}<!--\; \; -->(B_n)=\exp <!--\; \; -->\left(-<!--\; -\; -->(n-<!--\; -\; -->1{)}^2\ln <!--\; \; -->n+n^2-<!--\; -\; -->\left(n-<!--\; -\; -->\frac{1}{2}\right)\ln <!--\; \; -->(2\mathrm{\pi <!--\; \pi \; -->})+\frac{1}{3}+o(1)\right).$$\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).$ 

Многочлен ЭрхартаПравить

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

ОбобщенияПравить

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

См. такжеПравить

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

ЛитератураПравить

• 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: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. — Т. 30. — doi:10.1007/s10801-008-0155-y. — arXiv:math.CO/0701866.
• 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, Discrete and Computational Geometry, Vol. 30, pp. 623—637. The volume of B₉.

СсылкиПравить

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