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

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

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

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

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

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

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

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

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

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

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