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

Многогранник Биркгофа Bn(также называемый многогранником назначений, многогранником дважды стохастических матриц, или многогранник идеального соответствия полного двудольного графа $K\; n,\; n\; \{\backslash \; displaystyle\; K\_\; \{n,\; n\}\}$) - это выпуклый многогранник в R (где N = n), точками которого являются дважды стохастические матрицы, т. Е. N × n матрицы, элементы которых являются неотрицательными действительными числами, а каждая строка и столбец в сумме дают 1. Он назван в честь Гарретта Биркгофа.

• 1 Свойства
  • 1.1 Вершины
  • 1.2 Ребра
  • 1.3 Грани
  • 1.4 Симметрии
  • 1.5 Объем
  • 1.6 Полином Эрхарта
• 2 Обобщения
• 3 См. Также
• 4 Ссылки
• 5 Внешние links

Вершины

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

Ребра

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

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

Это означает, что граф B n является графом Кэли симметрической группы Sn. Это также означает, что граф B 3 является полным графом K6, и, таким образом, B 3 является соседним многогранником.

Facets

Многогранник Биркгофа лежит в пределах (n - 2n + 1) -мерного аффинного подпространства n-мерного пространства всех n × n-матриц: это подпространство определяется ограничениями линейного равенства, что сумма каждой строки и каждого столбца равна единице. Внутри этого подпространства оно определяется n линейными неравенствами, по одному для каждой координаты матрицы, определяя, что координата неотрицательна. Следовательно, для $n\; \ge \; 3\; \{\backslash \; displaystyle\; n\; \backslash \; geq\; 3\}$у него ровно n фасетов. Для n = 2 есть два аспекта, заданные как 11 = a 22 = 0 и 12 = a 21 = 0.

Симметрии

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

Объем

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

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

Для малых значений $n\; \le \; 15\; \{\backslash \; displaystyle\; n\; \backslash \; leq\; 15\}$объем был оценен в 2014 году, в то время как следуют аналогичные оценки.

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

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

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

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

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