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 grafo 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 de 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 establecido en un artículo de 1946 por Garrett Birkhoff , [2] pero resultados equivalentes en los lenguajes de configuraciones proyectivas y de emparejamientos 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 el gráfico de B n es un gráfico de Cayley del grupo simétrico S n . Esto también implica que el gráfico de B 3 es un gráfico completo K 6 , y por lo tanto B 3 es un politopo vecino .
El politopo de Birkhoff se encuentra dentro de un subespacio afín de dimensión ( n 2 − 2 n + 1) del espacio de dimensión n de todas las matrices n × n : este subespacio está determinado por las restricciones de igualdad lineal de que la suma de cada fila y de cada columna sea uno. Dentro de este subespacio, está definido por n 2 desigualdades lineales , una para cada coordenada de la matriz, especificando que la coordenada no sea 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 por faceta (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 tablas de Young estándar . [5] En 2007 se proporcionó una fórmula combinatoria para todos los n . [6] Rodney Canfield y Brendan McKay encontraron la siguiente fórmula asintótica : [7]
Para valores pequeños el volumen fue estimado en 2014 [8] y a continuación se presentan 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 solo se conoce para valores pequeños. [4] Se conjetura que todos los coeficientes de los polinomios de Ehrhart son no negativos.
