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

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

Свойства

Вершины

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

Края

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

$(\sigma ,\omega )$ такой, что $\sigma ^{-1}\omega$ это цикл.

Отсюда следует граф Bn что _Кэли является графом симметрической группы Sn _. , Отсюда также следует, что граф B ₃ является полным графом K ₆ и, следовательно, B ₃ является соседним многогранником .

Фасеты

Многогранник Биркгофа лежит внутри ( n ² − 2 n 1) -мерное аффинное подпространство n + ² -мерное пространство всех матриц размера n × n : это подпространство определяется ограничениями линейного равенства, согласно которым сумма каждой строки и каждого столбца равна единице. Внутри этого подпространства оно определяется n ² линейные неравенства , по одному для каждой координаты матрицы, указывающие, что координата неотрицательна. Поэтому для $n\geq 3$, оно имеет ровно n ² грани . Для n = 2 есть две грани: a ₁₁ = a ₂₂ = 0 и a ₁₂ = a ₂₁ = 0.

Симметрии

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

Объем

Нерешенной задачей является нахождение объема многогранника Биркгофа. Это было сделано для n ≤ 10. Известно, что он равен объему многогранника, связанного со стандартными таблицами Юнга . Комбинаторная формула для всех n была дана в 2007 году. Следующая асимптотическая формула была найдена Родни Кэнфилдом и Бренданом Маккеем :

$\mathop {\mathrm {vol} } (B_{n})\,=\,\exp \left(-(n-1)^{2}\ln n+n^{2}-(n-{\frac {1}{2}})\ln(2\pi )+{\frac {1}{3}}+o(1)\right).$

Для небольших значений $n\leq 15$ объем оценивался в 2014 году хотя следуют аналогичные оценки.

Эрхарта

Определить полином Эрхарта многогранника сложнее, чем определить его объем, поскольку объем можно легко вычислить по старшему коэффициенту полинома Эрхарта. Полином Эрхарта, связанный с многогранником Биркгофа, известен только для небольших значений. Предполагается, что все коэффициенты полиномов Эрхарта неотрицательны.

Обобщения

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

См. также

• Алгоритм Биркгофа
• Пермутоэдр
• Стабильный совпадающий многогранник

Внешние ссылки

• Веб-сайт многогранников Биркгофа Денниса Пикстона и Матиаса Бека со ссылками на статьи и тома.