Teoremas de tipo Hall para hipergrafías
En combinatoria , los teoremas de tipo Hall para hipergrafías son varias generalizaciones del teorema del matrimonio de Hall de gráficas a hipergrafías . Tales teoremas fueron probados por Ofra Kessler, [1] [2] Ron Aharoni , [3] [4] Penny Haxell , [5] [6] Roy Meshulam , [7] y otros.
El teorema del matrimonio de Hall proporciona una condición que garantiza que un grafo bipartito ( X+Y, E ) admite una coincidencia perfecta o, más generalmente, una coincidencia que satura todos los vértices de Y. La condición implica el número de vecinos de subconjuntos de Y . La generalización del teorema de Hall a las hipergrafías requiere una generalización de los conceptos de bipartididad, coincidencia perfecta y vecinos.
1. Bipartididad : la noción de bipartididad se puede extender a las hipergrafías de muchas maneras (ver hipergrafía bipartita ). Aquí definimos un hipergráfico como bipartito si es exactamente bicolor , es decir, sus vértices pueden ser bicolores, de modo que cada hiperborde contenga exactamente un vértice amarillo. En otras palabras, V se puede dividir en dos conjuntos X e Y , de modo que cada hiperarista contenga exactamente un vértice de Y. [1] Un grafo bipartito es un caso especial en el que cada arista contiene exactamente un vértice de Y y también exactamente un vértice de X; en un hipergráfico bipartito, cada hiperborde contiene exactamente un vértice de Y , pero puede contener cero o más vértices de X. Por ejemplo, la hipergrafía ( V , E ) con V = {1,2,3,4,5,6} y E = { {1,2,3} , {1,2,4} , {1,3 ,4}, {5,2}, {5,3,4,6} } es bipartito con Y = {1,5} y X = {2,3,4,6}.
2. Coincidencia perfecta : una coincidencia en una hipergrafía H = (V,E) es un subconjunto F de E , tal que cada dos hiperaristas de F son disjuntas. Si H es bipartito con partes X e Y , entonces el tamaño de cada emparejamiento es obviamente como máximo | Y |. Una coincidencia se llama Y-perfecta (o Y-saturante ) si su tamaño es exactamente | Y |. En otras palabras: cada vértice de Y aparece exactamente en un hiperborde de M . Esta definición se reduce a la definición estándar de un Y-coincidencia perfecta en un grafo bipartito.
3. Vecinos : Dada una hipergrafía bipartita H = ( X+Y, E ) y un subconjunto Y 0 de Y, los vecinos de Y 0 son los subconjuntos de X que comparten hiperaristas con vértices de Y 0 . Formalmente: . Por ejemplo, en la hipergrafía del punto 1 tenemos: N H ({1}) = { {2,3}, {2,4}, {3,4} } y N H ({5}) = { {2}, {3,4,6} } y NH ({1,5}) = { {2,3}, {2,4}, {3,4}, {2}, {3,4 ,6} }. Tenga en cuenta que, en un gráfico bipartito, cada vecino es un singleton: los vecinos son solo los vértices de X que son adyacentes a uno o más vértices de Y0 _ En una hipergrafía bipartita, cada vecino es un conjunto; los vecinos son los subconjuntos de X que son "adyacentes" a uno o más vértices de Y 0 .
