Русская Википедия:Многогранник Биркгофа
Многогранник Биркгофа Bn, который также называется многогранником назначений, многогранником дважды стохастических матриц или многогранником совершенных паросочетаний полного двудольного графа <math>K_{n,n}</math>Шаблон:Sfn, это выпуклый многогранник в RN (где <math>N = n^2</math>), точками которого являются дважды стохастические матрицы, то есть Шаблон:Nowrap матрицы, элементами которых служат неотрицательные вещественные числа и сумма строк и столбцов этих матриц равна 1.
Свойства
Вершины
Многогранник Биркгофа имеет n! вершин, по одной вершине на каждую перестановку n элементовШаблон:Sfn. Это следует из теоремы Биркгофа — Фон Неймана, которая утверждает, что Шаблон:Не переведено 5 многогранника Биркгофа — это матрицы перестановок, и потому, что любая дважды стохастическая матрица может быть представлена в виде выпуклой комбинации матриц перестановок. Это доказал в 1946 году в своей статье Гаррет БиркгофШаблон:Sfn, но эквивалентные результаты в терминах конфигураций и паросочетаний регулярных двудольных графов показали много ранее в 1894 году Эрнст Штайниц в своих тезисах и в 1916 году Денеш КёнигШаблон:Sfn.
Рёбра
Рёбра многогранника Биркгофа соответствуют парам перестановок, различающихся циклом:
- перестановка <math>(\sigma,\omega)</math> такая, что <math>\sigma^{-1}\omega</math> является циклом.
Из этого следует, что граф многогранника Bn является графом Кэли симметрической группы Sn. Отсюда также следует, что граф B3 является полным графом K6, а тогда B3 — смежностный многогранник.
Фасеты
Многогранник Биркгофа лежит внутри Шаблон:Nowrapмерного аффинного подпространства n2-мерного пространства всех Шаблон:Nowrap матриц — это подпространство задаётся линейными ограничениями, что сумма по каждой строке и каждому столбцу равна единице. Внутри этого подпространства накладывается n2 линейных неравенств, по одному на каждую координату, требующих неотрицательности координат.
Таким образом, многогранник имеет в точности n2 фасетШаблон:Sfn.
Симметрии
Многогранник Биркгофа Bn вершинно транзитивен и гранетранзитивен (то есть двойственный многогранник вершинно транзитивен). Многогранник не входит в число правильных для n>2.
Объём
Нерешённой задачей является нахождение объёма многогранников Биркгофа. Объём найден для <math>n \leqslant 10</math>[1]. Известно, что объём равен объёму многогранника, ассоциированного со стандартной диаграммой ЮнгаШаблон:Sfn. Комбинаторная формула для всех n дана в 2007Шаблон:Sfn. Следующую асимптотическую формулу нашли Шаблон:Не переведено 5 и Шаблон:Не переведено 5Шаблон:Sfn:
- <math>\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) .</math>
Многочлен Эрхарта
Нахождение многочлена Эрхарта многогранника сложнее, чем нахождение объёма, поскольку объём можно легко вычислить из ведущего коэффициента многочлена Эрхарта. Многочлен Эрхарта, ассоциированный с многогранником Биркгофа, известен только для малых значений и только имеется гипотеза, что все коэффициенты многочленов Эрхарта (для многогранников Биркгофа) неотрицательны.
Обобщения
- Многогранник Биркгофа является специальным случаем транспортного многогранника, многогранником прямоугольных матриц с неотрицательными элементами с заданными суммами по строкам и столбцам. Целые точки такого многогранника называются таблицами сопряжённости. Они играют важную роль в байесовой статистике.
- Многогранник Биркгофа является специальным случаем Шаблон:Не переведено 5, определённого как выпуклая оболочка совершенных паросочетаний конечного графа. Описание фасет в этом обобщении дал Шаблон:Не переведено 5 (1965) и они связаны с Шаблон:Не переведено 5.
См. также
Примечания
Литература
Литература для дальнейшего чтения
- 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 B9.
Ссылки
- Birkhoff polytope Web site by Dennis Pixton and Matthias Beck, with links to articles and volumes.
- ↑ The Volumes of Birkhoff polytopes Шаблон:Wayback for n ≤ 10.
