El politopo Birkhoff B n (también llamado politopo de asignación , el politopo de matrices doblemente estocásticas o el politopo de coincidencia perfecto 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 n × n matrices cuyas entradas son números reales no negativosy cuyas filas y columnas suman cada una 1. Lleva el nombre de Garrett Birkhoff .
Propiedades
Vértices
El politopo Birkhoff tiene n ! vértices, uno por cada permutación en n elementos. [1] Esto se sigue 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, 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 emparejamientos de gráficos 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 del vértice son cero o uno, el politopo de Birkhoff es un politopo integral .
Bordes
Los bordes del politopo Birkhoff corresponden a pares de permutaciones que difieren en un ciclo:
- tal que es 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 el gráfico de B 3 es un gráfico completo K 6 y, por lo tanto, B 3 es un politopo vecino .
Facetas
Las mentiras Birkhoff polytope dentro de un ( n 2 - 2 n + 1) - dimensional subespacio afín de la n 2 espacio dimensional de todos n × n matrices: este subespacio es determinado por las restricciones de igualdad lineales que la suma de cada fila y de cada columna sea una. Dentro de este subespacio, se define 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.
Simetrías
El Birkhoff politopo B n es a la vez vértice-transitivo y faceta-transitivo (es decir, el doble politopo es vértice-transitivo). No es regular para n> 2 .
Volumen
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 de Young estándar . [5] En 2007 se dio 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], mientras que a continuación se presentan estimaciones similares. [9]
Polinomio de Ehrhart
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 por valores pequeños. [10] Se conjetura que todos los coeficientes de los polinomios de Ehrhart son no negativos.
Generalizaciones
- El politopo de Birkhoff es un caso especial del politopo de transporte , un politopo de matrices rectangulares no negativas con sumas de filas y columnas dadas. [11] Los puntos enteros en estos politopos se denominan tablas de contingencia ; juegan un papel importante en las estadísticas bayesianas .
- El politopo Birkhoff es un caso especial del politopo correspondiente , definido como un casco convexo de los emparejamientos perfectos en un gráfico finito. La descripción de las facetas en esta generalidad fue dada por Jack Edmonds (1965) y está relacionada con el algoritmo de emparejamiento de Edmonds .
- El politopo de Birkhoff es un caso especial del politopo de flujo de flujos no negativos a través de una red. [12] Está relacionado con el algoritmo de Ford-Fulkerson que calcula el flujo máximo en una red de flujo.
Ver también
- Algoritmo de Birkhoff
- Permutoedro
- Politopo a juego estable
Referencias
- ^ a b c Ziegler, Günter M. (2007) [2006], Conferencias sobre politopos , Textos de posgrado en matemáticas, 152 (séptima impresión de la 1ª ed.), Nueva York: Springer, p. 20, ISBN 978-0-387-94365-7
- ^ Birkhoff, Garrett (1946), "Tres observaciones sobre el álgebra lineal [Tres observaciones sobre el álgebra lineal]", Univ. Nac. Tucumán. Revista A. , 5 : 147–151, MR 0020547.
- ^ Kőnig, Dénes (1916), "Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére", Matematikai és Természettudományi Értesítő , 34 : 104-119.
- ^ Los volúmenes de politopos de Birkhoff para n ≤ 10.
- ^ Pak, Igor (2000), "Four questions on Birkhoff polytope", Annals of Combinatorics , 4 : 83–90, doi : 10.1007 / PL00001277 , S2CID 1250478.
- ^ De Loera, Jesús A .; Liu, Fu; Yoshida, Ruriko (2007), "Fórmulas para los volúmenes del politopo de matrices doblemente estocásticas y sus caras", Journal of Algebraic Combinatorics , 30 : 113-139, arXiv : math.CO/0701866 , doi : 10.1007 / s10801- 008-0155-y , S2CID 5837937.
- ^ Canfield, E. Rodney; McKay, Brendan D. (2007), "El volumen asintótico del politopo Birkhoff", arXiv : 0705.2422 [ math.CO ]
- ^ Emiris, Ioannis; Fisikopoulos, Vissarion (2014), "Efficient Random-Walk Methods for Approximating Polytope Volume", Simposio anual sobre geometría computacional - SOCG'14 , ACM, págs. 318–327, arXiv : 1312.2873 , doi : 10.1145 / 2582112.2582133 , ISBN 9781450325943, S2CID 372936
- ^ Primos, Ben; Vempala, Santosh (2016), "Un algoritmo de volumen práctico", Computación de programación matemática , 8 (2): 133–160, doi : 10.1007 / s12532-015-0097-z , S2CID 10365756
- ^ Beck, Matthias; Pixton, Dennis (1 de octubre de 2003), "The Ehrhart Polynomial of the Birkhoff Polytope", Geometría discreta y computacional , 30 (4): 623–637, arXiv : math / 0202267 , doi : 10.1007 / s00454-003-2850-8 , S2CID 7164663
- ^ Emelichev, VA; Kovalev, MM; Kravtsov, MK (1984), Politopos, gráficos y optimización , Cambridge University Press
- ^ Baldoni-Silva, W .; De Loera, JA; Vergne, M. (2004), "Contando flujos enteros en redes", Fundamentos de las matemáticas computacionales , 4 (3): 277–314, arXiv : math / 0303228 , doi : 10.1007 / s10208-003-0088-8 , S2CID 2541019
enlaces externos
- Sitio web Birkhoff polytope de Dennis Pixton y Matthias Beck, con enlaces a artículos y volúmenes.