Многогранник Биркгофа Bn, который также называется многогранником назначений, многогранником дважды стохастических матриц или многогранником совершенных паросочетаний полного двудольного графа , это выпуклый многогранник в RN (где ), точками которого являются дважды стохастические матрицы, то есть матрицы, элементами которых служат неотрицательные вещественные числа и сумма строк и столбцов этих матриц равна 1.
Свойства
Вершины Многогранник Биркгофа имеет n! вершин, по одной вершине на каждую перестановку n элементов. Это следует из теоремы Биркгофа — Фон Неймана, которая утверждает, что многогранника Биркгофа — это матрицы перестановок, и потому, что любая дважды стохастическая матрица может быть представлена в виде выпуклой комбинации матриц перестановок. Это доказал в 1946 году в своей статье Гаррет Биркгоф, но эквивалентные результаты в терминах конфигураций и паросочетаний регулярных двудольных графов показали много ранее в 1894 году Эрнст Штайниц в своих тезисах и в 1916 году Денеш Кёниг.
Рёбра Рёбра многогранника Биркгофа соответствуют парам перестановок, различающихся циклом: перестановка такая, что является циклом. Из этого следует, что граф многогранника Bn является графом Кэли симметрической группы Sn. Отсюда также следует, что граф B3 является полным графом K6, а тогда B3 — смежностный многогранник.
Фасеты Многогранник Биркгофа лежит внутри мерного аффинного подпространства n2-мерного пространства всех матриц — это подпространство задаётся линейными ограничениями, что сумма по каждой строке и каждому столбцу равна единице. Внутри этого подпространства накладывается n2 линейных неравенств, по одному на каждую координату, требующих неотрицательности координат.
Таким образом, многогранник имеет в точности n2 фасет.
Симметрии Многогранник Биркгофа Bn вершинно транзитивен и гранетранзитивен (то есть двойственный многогранник вершинно транзитивен). Многогранник не входит в число правильных для n>2.
Объём Нерешённой задачей является нахождение объёма многогранников Биркгофа. Объём найден для The Volumes of Birkhoff polytopes for n ≤ 10.. Известно, что объём равен объёму многогранника, ассоциированного со стандартной диаграммой Юнга. Комбинаторная формула для всех n дана в 2007. Следующую асимптотическую формулу нашли и :
Многочлен Эрхарта Нахождение многочлена Эрхарта многогранника сложнее, чем нахождение объёма, поскольку объём можно легко вычислить из ведущего коэффициента многочлена Эрхарта. Многочлен Эрхарта, ассоциированный с многогранником Биркгофа, известен только для малых значений и только имеется гипотеза, что все коэффициенты многочленов Эрхарта (для многогранников Биркгофа) неотрицательны.
Обобщения Многогранник Биркгофа является специальным случаем транспортного многогранника, многогранником прямоугольных матриц с неотрицательными элементами с заданными суммами по строкам и столбцам. Целые точки такого многогранника называются таблицами сопряжённости. Они играют важную роль в байесовой статистике. Многогранник Биркгофа является специальным случаем , определённого как выпуклая оболочка совершенных паросочетаний конечного графа. Описание фасет в этом обобщении дал (1965) и они связаны с .
См. также Перестановочный многогранник
Примечания
Литература
Литература для дальнейшего чтения 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.
Категория:Типы матриц Категория:Многогранники