Многогранник Биркгофа Bn, который также называется многогранником назначений, многогранником дважды стохастических матриц или многогранником совершенных паросочетаний полного двудольного графа K n , n {displaystyle K_{n,n}} , это выпуклый многогранник в RN (где N = n 2 {displaystyle N=n^{2}} ), точками которого являются дважды стохастические матрицы, то есть n × n матрицы, элементами которых служат неотрицательные вещественные числа и сумма строк и столбцов этих матриц равна 1.
Свойства
Вершины
Многогранник Биркгофа имеет n! вершин, по одной вершине на каждую перестановку n элементов. Это следует из теоремы Биркгофа — Фон Неймана, которая утверждает, что экстремальные точки многогранника Биркгофа — это матрицы перестановок, и потому, что любая дважды стохастическая матрица может быть представлена в виде выпуклой комбинации матриц перестановок. Это доказал в 1946 году в своей статье Гаррет Биркгоф, но эквивалентные результаты в терминах конфигураций и паросочетаний регулярных двудольных графов показали много ранее в 1894 году Эрнст Штайниц в своих тезисах и в 1916 году Денеш Кёниг.
Рёбра
Рёбра многогранника Биркгофа соответствуют парам перестановок, различающихся циклом:
перестановка ( σ , ω ) {displaystyle (sigma ,omega )} такая, что σ − 1 ω {displaystyle sigma ^{-1}omega } является циклом.Из этого следует, что граф многогранника Bn является графом Кэли симметрической группы Sn. Отсюда также следует, что граф B3 является полным графом K6, а тогда B3 — смежностный многогранник.
Фасеты
Многогранник Биркгофа лежит внутри (n2 − 2n + 1)-мерного аффинного подпространства n2-мерного пространства всех n × n матриц — это подпространство задаётся линейными ограничениями, что сумма по каждой строке и каждому столбцу равна единице. Внутри этого подпространства накладывается n2 линейных неравенств, по одному на каждую координату, требующих неотрицательности координат.
Таким образом, многогранник имеет в точности n2 фасет.
Симметрии
Многогранник Биркгофа Bn вершинно транзитивен и гранетранзитивен (то есть двойственный многогранник вершинно транзитивен). Многогранник не входит в число правильных для n>2.
Объём
Нерешённой задачей является нахождение объёма многогранников Биркгофа. Объём найден для n ⩽ 10 {displaystyle nleqslant 10} . Известно, что объём равен объёму многогранника, ассоциированного со стандартной диаграммой Юнга. Комбинаторная формула для всех n дана в 2007. Следующую асимптотическую формулу нашли Родни Кэнфилд и Брендан МакКэй:
v o l ( B n ) = exp ( − ( n − 1 ) 2 ln n + n 2 − ( n − 1 2 ) ln ( 2 π ) + 1 3 + o ( 1 ) ) . {displaystyle mathop {mathrm {vol} } (B_{n}),=,exp left(-(n-1)^{2}ln n+n^{2}-left(n-{frac {1}{2}} ight)ln(2pi )+{frac {1}{3}}+o(1) ight).}Многочлен Эрхарта
Нахождение многочлена Эрхарта многогранника сложнее, чем нахождение объёма, поскольку объём можно легко вычислить из ведущего коэффициента многочлена Эрхарта. Многочлен Эрхарта, ассоциированный с многогранником Биркгофа, известен только для малых значений и только имеется гипотеза, что все коэффициенты многочленов Эрхарта (для многогранников Биркгофа) неотрицательны.
Обобщения
- Многогранник Биркгофа является специальным случаем транспортного многогранника, многогранником прямоугольных матриц с неотрицательными элементами с заданными суммами по строкам и столбцам. Целые точки такого многогранника называются таблицами сопряжённости. Они играют важную роль в байесовой статистике.
- Многогранник Биркгофа является специальным случаем многогранника паросочетаний, определённого как выпуклая оболочка совершенных паросочетаний конечного графа. Описание фасет в этом обобщении дал Джек Эдмондс (1965) и они связаны с алгоритмом Эдмондса.