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

Многогранник Биркгофа Bn, который также называется многогранником назначений, многогранником дважды стохастических матриц или многогранником совершенных паросочетаний полного двудольного графа [1], это выпуклый многогранник в RN (где ), точками которого являются дважды стохастические матрицы, то есть n × n матрицы, элементами которых служат неотрицательные вещественные числа и сумма строк и столбцов этих матриц равна 1.

Свойства

Вершины

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

Рёбра

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

перестановка такая, что является циклом.

Из этого следует, что граф многогранника Bn является графом Кэли симметрической группы Sn. Отсюда также следует, что граф B3 является полным графом K6, а тогда B3 — смежностный многогранник.

Фасеты

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

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

Симметрии

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

Объём

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

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

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

Обобщения

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

См. также

Примечания

  1. Ziegler, 2007, с. 20.
  2. Birkhoff, 1946, с. 147–151.
  3. Kőnig, 1916, с. 104–119.
  4. The Volumes of Birkhoff polytopes for n ≤ 10.
  5. Pak, 2000.
  6. De Loera, Liu, Yoshida, 2007, с. 113–139.
  7. Canfield, McKay, 2007.

Литература

  • Günter M. Ziegler. Lectures on Polytopes. — 7th. — New York: Springer, 2007. — Т. 152. — (Graduate Texts in Mathematics). — ISBN 978-0-387-94365-7.
  • Garrett Birkhoff. Tres observaciones sobre el algebra lineal [Three observations on linear algebra] // Univ. Nac. Tucumán. Revista A.. — 1946. Т. 5. С. 147–151.
  • Dénes Kőnig. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére // Matematikai és Természettudományi Értesítő. — 1916. Т. 34.
  • Igor Pak. Four questions on Birkhoff polytope // Annals of Combinatorics. — 2000. Т. 4. doi:10.1007/PL00001277.
  • Jesus A. De Loera, Fu Liu, Ruriko Yoshida. Formulas for the volumes of the polytope of doubly-stochastic matrices and its faces // Journal of Algebraic Combinatorics. — 2007. Т. 30. doi:10.1007/s10801-008-0155-y. arXiv:math.CO/0701866.
  • Rodney E. Canfield, Brendan D. McKay. The asymptotic volume of the Birkhoff polytope. — 2007.

Литература для дальнейшего чтения

  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.