¿Implica Birkhoff - von Neumann alguno de los teoremas fundamentales de la combinatoria?

Question

Hace poco tuve la ocasión de reflexionar sobre Teorema del matrimonio de Hall por primera vez desde mi clase de combinatoria en la universidad hace más de una década. Leyendo el artículo de la wikipedia enlazado arriba, me interesó ver que se considera equivalente a varios otros teoremas fundamentales de la combinatoria, por ejemplo Teorema de Dilworth en posets de anchura finita y Teorema de König sobre el emparejamiento en grafos (¿finitos?). He podido encontrar las pruebas de estas equivalencias en Internet.

Sin embargo, el artículo también afirma que el Teorema del Matrimonio de Hall es equivalente al Teorema de (König-)Birkhoff - von Neumann que afirma que una matriz real es doblemente estocástica si es una combinación convexa de matrices de permutación (si se conoce la teoría de Minkowski-Krein-Milman de los puntos extremos en conjuntos convexos, entonces una afirmación equivalente es que las matrices doblemente estocásticas forman un subconjunto convexo compacto de $M_n(\mathbb{R})$ con puntos extremos precisamente las matrices de permutación, y como hay finitamente muchos puntos extremos se tiene de hecho un politopo convexo, el Politopo de Birkhoff ).

Pero la atribución aquí es extraña: la única cita es a esta serie de diapositivas de R.D. Borgersen cuyo título es "Equivalencia de siete teoremas principales en combinatoria"... ¡pero sólo muestra algunas de las implicaciones! En particular, no se muestra que Birkhoff - von Neumann implica ninguno de los teoremas anteriores. Así que ahora llegamos a la pregunta de mi título: ¿lo hace?

Como pregunta secundaria, ¿existe una buena fuente que trate todos estos teoremas (quizá no Birkhoff - von Neumann, pero sí los otros cinco o seis, según se cuente) a la vez? En particular, gran parte de la literatura que he encontrado parece ser un poco descuidada en cuanto a la necesidad de que las estructuras implicadas sean finitas: parece que se necesitan "algunas, pero no todas" las condiciones de finitud para que estos teoremas se mantengan y que se entiende que la equivalencia folclórica se aplica sólo en el caso finito. ¿Es esto correcto?

Answer 1

El libro que buscas es Reichmeider, La equivalencia de algunos teoremas de correspondencia combinatoria. Por desgracia, hace tiempo que está descatalogado.

[ Añadido por PLC: Me tomo la libertad de reproducir la reseña de MathSciNet. Nótese que no menciona a Birkhoff - von Neumann, aunque esto no es concluyente].

Es bien sabido que varios teoremas relativos a los emparejamientos bipartitos y los flujos de red son todos "equivalentes", en el sentido de que cualquiera de ellos puede deducirse fácilmente de cualquier otro. Este trabajo expositivo organiza y presenta minuciosamente varias pruebas de estos resultados y de las relaciones. Se centra en los teoremas de König y Egerváry, Hall, Dilworth, Menger, Ford y Fulkerson, y Hoffman. El libro trata sólo el caso finito, y no considera los matroides ni los algoritmos. (Reseña de Colin J.H. McDiarmid)

Answer 2

Ciertamente implica el teorema del matrimonio de Koenig. Dado un grafo bipartito regular en el conjunto de vértices $U \sqcup V$ definan una matriz de adyacencia "modificada" $A = (a_{ij})$ por $a_{ij} = 1$ si el elemento $i$ de $U$ es adyacente al elemento $j$ de $V$ y $a_{ij} = 0$ de lo contrario. Dado que cada fila y columna de $A$ se suma al grado, se puede normalizar para obtener una matriz doblemente estocástica cuyas entradas no nulas siguen registrando la adyacencia en el gráfico. Escriba esto como una combinación convexa de matrices de permutación, elija una de ellas y utilícela como matriz de adyacencia modificada de un emparejamiento (ya que sus entradas no nulas deben ser no nulas en $A$ (esto está contenido en el gráfico original).

Para obtener el teorema de Hall completo, hay que comprobar que la condición de Hall es suficiente para hacer la normalización doblemente estocástica, lo cual no veo pero suena razonable.

EDIT: He entendido mal a qué teorema de Koenig te referías. Lo siento.