El politopo de Birkhoff B n (también llamado politopo de asignación , politopo de matrices doblemente estocásticas o politopo de coincidencia perfecta del gráfico bipartito completo [1] ) es el politopo convexo en R N (donde N = n 2 ) cuyos puntos son las matrices doblemente estocásticas , es decir, las matrices n × n cuyas entradas son números reales no negativos y cuyas filas y columnas suman cada una 1. Lleva el nombre de Garrett Birkhoff .
El politopo Birkhoff tiene n ! vértices, uno para cada permutación en n elementos. [1] Esto se desprende del teorema de Birkhoff-von Neumann , que establece que los puntos extremos del politopo de Birkhoff son las matrices de permutación y, por lo tanto, que cualquier matriz doblemente estocástica puede representarse como una combinación convexa de matrices de permutación; esto fue declarado en un artículo de 1946 por Garrett Birkhoff , [2] pero resultados equivalentes en los lenguajes de configuraciones proyectivas y de coincidencias de grafos bipartitos regulares , respectivamente, se mostraron mucho antes en 1894 en la tesis de Ernst Steinitz y en 1916 por Dénes Kőnig. . [3] Debido a que todas las coordenadas de los vértices son cero o uno, el politopo de Birkhoff es un politopo integral .
Los bordes del politopo de Birkhoff corresponden a pares de permutaciones que difieren en un ciclo:
Esto implica que la gráfica de B n es una gráfica de Cayley del grupo simétrico S n . Esto también implica que la gráfica de B 3 es una gráfica completa K 6 y, por lo tanto, B 3 es un politopo vecino .
El politopo de Birkhoff se encuentra dentro de un subespacio afín dimensional ( n 2 − 2 n + 1 ) del espacio n 2 -dimensional de todas las matrices n × n : este subespacio está determinado por las restricciones de igualdad lineal que la suma de cada fila y de cada columna sea una. Dentro de este subespacio, está definido por n 2 desigualdades lineales , una para cada coordenada de la matriz, especificando que la coordenada sea no negativa. Por lo tanto, para , tiene exactamente n 2 facetas . [1] Para n = 2, hay dos facetas, dadas por a 11 = a 22 = 0, y a 12 = a 21 = 0.
El politopo de Birkhoff B n es transitivo por vértice y transitivo por facetas (es decir, el politopo dual es transitivo por vértice). No es regular para n>2 .
Un problema pendiente es encontrar el volumen de los politopos de Birkhoff. Esto se ha hecho para n ≤ 10. [4] Se sabe que es igual al volumen de un politopo asociado con cuadros estándar de Young . [5] En 2007 se proporcionó una fórmula combinatoria para todo n. [6] Rodney Canfield y Brendan McKay encontraron la siguiente fórmula asintótica : [7]
Para valores pequeños, el volumen se estimó en 2014 [8], aunque a continuación se realizan estimaciones similares. [9]
Determinar el polinomio de Ehrhart de un politopo es más difícil que determinar su volumen, ya que el volumen se puede calcular fácilmente a partir del coeficiente principal del polinomio de Ehrhart. El polinomio de Ehrhart asociado con el politopo de Birkhoff sólo se conoce para valores pequeños. [4] Se conjetura que todos los coeficientes de los polinomios de Ehrhart son no negativos.
