Teoremas de tipo Hall para hipergrafos

En el campo matemático de la teoría de grafos , los teoremas de tipo Hall para hipergrafos son varias generalizaciones del teorema de matrimonio de Hall de grafos a hipergrafos . Dichos teoremas fueron demostrados por Ofra Kessler, ^{[ 1 ]}^{[ 2 ]} Ron Aharoni , ^{[ 3 ]}^{[ 4 ]} Penny Haxell , ^{[ 5 ]}^{[ 6 ]} Roy Meshulam , ^{[ 7 ]} y otros.

Preliminares

El teorema de Hall sobre el matrimonio proporciona una condición que garantiza que un grafo bipartito $(X + Y, E)$ admite un emparejamiento perfecto , o, más generalmente, un emparejamiento que satura todos los vértices de $Y.$ La condición involucra el número de vecinos de los subconjuntos de $Y.$ Generalizar el teorema de Hall a hipergrafos requiere una generalización de los conceptos de bipartición, emparejamiento perfecto y vecinos.

1. Bipartición : La noción de bipartición puede extenderse a los hipergrafos de muchas maneras (véase hipergrafo bipartito ). Aquí definimos un hipergrafo como bipartito si es exactamente 2- coloreable , es decir, sus vértices pueden ser 2-coloreados de tal manera que cada hiperarista contiene exactamente un vértice amarillo. En otras palabras, $V$ puede ser particionado en dos conjuntos $X$ e $Y$ , de tal manera que cada hiperarista contiene 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 hipergrafo bipartito, cada hiperarista contiene exactamente un vértice de $Y$ pero puede contener cero o más vértices de $X.$ Por ejemplo, el hipergrafo $(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. Emparejamiento perfecto : Un emparejamiento en un hipergrafo $H = (V, E)$ es un subconjunto $F$ de $E$ , tal que cada par de 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 |$ . Un emparejamiento se denomina $Y$ -perfecto (o $Y$ -saturador ) si su tamaño es exactamente $| Y |$ . En otras palabras: cada vértice de $Y$ aparece en exactamente una hiperarista de $M.$ Esta definición se reduce a la definición estándar de un emparejamiento $Y$ -perfecto en un grafo bipartito.

3. Vecinos : Dado un hipergrafo bipartito $H = (X + Y, E)$ y un subconjunto $Y₀$ de $Y$ , los vecinos de $Y₀$ $son$ $los$ subconjuntos de $X$ que comparten hiperaristas con vértices de $Y₀ .$ Formalmente:

N_{H}(Y_{0}):=\{X_{0}\subseteq X~~|~~\exists y_{0}\in Y_{0}:~\{y_{0}\}\cup X_{0}\in E\}.

Por ejemplo, en el hipergrafo del punto 1, tenemos: $N H ({1}) = { {2,3}, {2,4}, {3,4} }$ y $N H ({5}) = { {2}, {3,4,6} }$ y $N H ({1,5}) = { {2,3}, {2,4}, {3,4}, {2}, {3,4,6} }.$ Nótese que, en un grafo bipartito, cada vecino es un singleton: los vecinos son simplemente los vértices de $X$ que son adyacentes a uno o más vértices de $Y 0$ . En un hipergrafo bipartito, 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$ .

Dado que $N H (Y 0)$ contiene solo subconjuntos de $X$ , se puede definir un hipergrafo en el que el conjunto de vértices es $X$ y el conjunto de aristas es $N H (Y 0)$ . Lo llamamos hipergrafo de vecindad de $Y 0$ y lo denotamos:

H_{H}(Y_{0}):=(X,N_{H}(Y_{0})).

Tenga en cuenta que, si $H$ es un grafo bipartito simple, el hipergrafo de vecindad de cada $Y 0$ contiene solo los vecinos de $Y 0$ en $X$ , cada uno de los cuales tiene un bucle propio.

Insuficiencia de la condición de Hall

La condición de Hall requiere que, para cada subconjunto $Y 0$ de $Y$ , el conjunto de vecinos de $Y 0$ sea suficientemente grande. Con los hipergrafos, esta condición es insuficiente. Por ejemplo, consideremos el hipergrafo tripartito con aristas:

{ {1, a, A}, {2, a, B} }

Sea $Y = {1,2}.$ Cada vértice en $Y$ tiene un vecino, y $Y$ mismo tiene dos vecinos: $N H (Y) = { {a,A}, {a,B} }.$ Pero no hay un emparejamiento perfecto $en Y$ ya que ambas aristas se superponen. Se podría intentar solucionarlo exigiendo que $N H (Y 0)$ contenga al menos $| Y 0 |$ aristas disjuntas , en lugar de solo $| Y 0 |$ aristas. En otras palabras: $H H (Y 0)$ debería contener un emparejamiento de tamaño al menos $| Y 0 |$ . El tamaño máximo de un emparejamiento en un hipergrafo $H$ se llama su número de emparejamiento y se denota por $ν (H)$ (por lo tanto, $H$ admite un emparejamiento perfecto $en Y$ si y solo si $ν (H) = | Y |$ ). Sin embargo, esta solución es insuficiente, como lo demuestra el siguiente hipergrafo tripartito:

{ {1, a, A}, {1, b, B}, {2, a, B}, {2, b, A} }

Sea $Y = {1,2}.$ Nuevamente, cada vértice en $Y$ tiene un vecino, y $Y$ mismo tiene cuatro vecinos: $N H (Y) = { {a,A}, {a,B}, {b, A}, {b, B} }.$ Además, $ν (H H (Y)) = 2$ ya que $H H (Y)$ admite un emparejamiento de tamaño 2, por ejemplo ${ {a,A}, {b,B} } o { {a,B}, {b,A} }.$ Sin embargo, H no admite un emparejamiento $Y$ -perfecto, ya que cada hiperarista que contiene 1 se superpone a cada hiperarista que contiene 2.

Por lo tanto, para garantizar una compatibilidad perfecta, se necesita una condición más estricta. Se han sugerido varias condiciones de este tipo.

Condiciones de Aharoni: mayor coincidencia

Sea $H = (X + Y, E)$ un hipergrafo bipartito (como se define en el punto 1 anterior), en el que el tamaño de cada hiperarista es exactamente $r$ , para algún entero $r > 1$ . Supongamos que, para cada subconjunto $Y 0$ de $Y$ , se cumple la siguiente desigualdad:

\nu (N_{H}(Y_{0}))\geq (r-1)\cdot (|Y_{0}|-1)+1

En otras palabras: el hipergrafo de vecindad de $Y 0$ admite un emparejamiento mayor que $(r - 1) (| Y 0 | - 1)$ . Entonces $H$ admite un emparejamiento $Y$ -perfecto (como se define en el punto 2 anterior).

Esto fue conjeturado por primera vez por Aharoni. ^{[ 3 ]} Fue demostrado con Ofra Kessler para hipergrafos bipartitos en los que $| Y | \leq 4$ ^{[ 1 ]} y para $| Y | = 5$ . ^{[ 2 ]} Posteriormente fue demostrado para todos los hipergrafos $r$ -uniformes. ^{[ 6 ]}^{: Corolario 1.2}

En gráficos simples

Para un grafo simple bipartito $r = 2$ , la condición de Aharoni se convierte en:

\nu (H_{H}(Y_{0}))\geq |Y_{0}|.

Además, el hipergrafo de vecindad (como se define en el punto 3 anterior) contiene solo singletons: un singleton para cada vecino de $Y 0$ . Dado que los singletons no se intersecan, el conjunto completo de singletons es un emparejamiento. Por lo tanto, $ν (H H (Y 0)) = | N H (Y 0) | =$ el número de vecinos de $Y 0$ . Así, la condición de Aharoni se convierte en, para cada subconjunto $Y 0$ de $Y$ :

|N_{H}(Y_{0})|\geq |Y_{0}|.

Esta es precisamente la condición matrimonial de Hall.

Opresión

El siguiente ejemplo muestra que el factor $(r - 1)$ no se puede mejorar. Elija algún entero $m > 1.$ Sea $H = (X + Y, E)$ el siguiente hipergrafo bipartito $r -uniforme:$

$Y = {1, ..., m};$
E es la unión de E ₁ , … , E _m (donde E _i es el conjunto de hiperaristas que contienen el vértice i ), y:
- Para cada $i$ en ${1, \dots , m - 1},$ $E i$ contiene $r - 1$ hiperaristas disjuntas de tamaño $r$ : $\{i,x_{i,1,1},\ldots ,x_{i,1,r-1}\},\ldots ,\{i,x_{i,r-1,1},\ldots ,x_{i,r-1,r-1}\}.$
- $E m$ contiene $m - 1$ hiperaristas de tamaño $r$ : $\{m,x_{1,1,1},\ldots ,x_{1,r-1,r-1},\},\ldots ,\{m,x_{m-1,1,1},\ldots ,x_{m-1,r-1,1}\}$

Nótese que la arista $i$ en $E m$ se encuentra con todas las aristas en $E i$ .

Esta $H$ no admite un emparejamiento $Y$ -perfecto, ya que cada hiperarista que contiene $m$ interseca todas las hiperaristas en $E i$ para algún $i < m$ .

Sin embargo, todo subconjunto $Y 0$ de $Y$ satisface la siguiente desigualdad.

\nu (H_{H}(Y_{0}))\geq (r-1)\cdot (|Y_{0}|-1)

puesto que $H H ( Y 0 \ { m })$ contiene al menos $(r - 1) \cdot (| Y 0 | - 1)$ hiperaristas, y todas son disjuntas.

Emparejamientos fraccionarios

El tamaño máximo de un emparejamiento fraccional en $H$ se denota por $ν *(H)$ . Claramente $ν *(H) \geq ν (H)$ . Supongamos que, para cada subconjunto $Y 0$ de $Y$ , se cumple la siguiente desigualdad más débil:

\nu ^{*}(H_{H}(Y_{0}))\geq (r-1)\cdot (|Y_{0}|-1)+1

Se conjeturó que en este caso también $H$ admite un emparejamiento $Y$ -perfecto. Esta conjetura más fuerte se demostró para hipergrafos bipartitos en los que $| Y | = 2$ . ^{[ 4 ]}

Más tarde se demostró ^{[ 4 ]} que, si se cumple la condición anterior, entonces $H$ admite un emparejamiento fraccional $Y$ -perfecto , es decir, $ν$ $*($ $H$ $) =$ $|$ $Y$ $|$ . Esto es más débil que tener un emparejamiento $Y$ -perfecto, que es equivalente a $ν$ $($ $H$ $) =$ $|$ $Y$ $|$ .

Condición de Haxell: transversal más pequeña

Una transversal (también llamada cubierta de vértices o conjunto de colisión ) en un hipergrafo $H = (V, E)$ es un subconjunto $U$ de $V$ tal que cada hiperarista en $E$ contiene al menos un vértice de $U$ . El tamaño más pequeño de una transversal en $H$ se denota por $τ (H)$ .

Sea $H = (X + Y, E)$ un hipergrafo bipartito en el que el tamaño de cada hiperarista es como máximo $r$ , para algún entero $r > 1$ . Supongamos que, para cada subconjunto $Y 0$ de $Y$ , se cumple la siguiente desigualdad:

\tau (H_{H}(Y_{0}))\geq (2r-3)\cdot (|Y_{0}|-1)+1

En palabras: el hipergrafo de vecindad de $Y 0$ no tiene transversal de tamaño $(2 r - 3)(Y 0 - 1)$ o menor.

Entonces, $H$ admite un emparejamiento $Y$ -perfecto (como se define en el punto 2 anterior). ^{[ 5 ]}^{: Teorema 3}

En gráficos simples

Para un grafo simple bipartito $r = 2,$ entonces $2 r - 3 = 1$ , y la condición de Haxell se convierte en:

\tau (H_{H}(Y_{0}))\geq |Y_{0}|.

Además, el hipergrafo de vecindad (como se define en el punto 3 anterior) contiene solo singletons : un singleton para cada vecino de $Y 0$ . En un hipergrafo de singletons, una transversal debe contener todos los vértices. Por lo tanto, $τ (H H (Y 0)) = | N H (Y 0) | =$ el número de vecinos de $Y 0$ . Así, la condición de Haxell se convierte en, para cada subconjunto $Y 0$ de $Y$ :

|N_{H}(Y_{0})|\geq |Y_{0}|.

Esta es precisamente la condición de matrimonio de Hall. Por lo tanto, el teorema de Haxell implica el teorema de matrimonio de Hall para grafos simples bipartitos.

Opresión

El siguiente ejemplo muestra que el factor $(2 r - 3)$ no se puede mejorar. Sea $H = (X + Y, E)$ un hipergrafo bipartito $r -uniforme con:$

$Y=\{0,1\}$
$X=\{x_{ij}:1\leq i,j\leq r-1\}$ [por lo tanto $| X | = (r - 1) 2$ ].
$E=E_{0}\cup E_{1},$ $E=E_{0}\cup E_{1},$ dónde:
- $E_{0}=\{\{0,x_{i1},\ldots ,x_{i(r-1)}\}|1\leq i\leq r-1\}$ [por lo tanto, $E 0$ contiene $r - 1$ hiperaristas].
- $E_{1}=\{\{1,x_{1j[1]},\ldots ,x_{(r-1)j[r-1]}\}|1\leq j[k]\leq r-1$ para $1\leq k\leq r-1\}$ [por lo tanto, $E 1$ contiene $(r - 1) r -1$ hiperaristas].

Esta $H$ no admite un emparejamiento $Y$ -perfecto, ya que cada hiperarista que contiene 0 interseca cada hiperarista que contiene 1.

Sin embargo, todo subconjunto $Y 0$ de $Y$ satisface la siguiente desigualdad:

\tau (H_{H}(Y_{0}))\geq (2r-3)\cdot (|Y_{0}|-1)

Es solo ligeramente más débil (por 1) que lo requerido por el teorema de Haxell. Para verificar esto, basta con comprobar el subconjunto $Y 0 = Y$ , ya que es el único subconjunto para el cual el lado derecho es mayor que 0. El hipergrafo de vecindad de $Y$ es $(X, E 00 \cup E 11)$ donde:

E_{00}=\{\{x_{i1},\ldots ,x_{i(r-1)}\}|1\leq i\leq r-1\}

E_{11}=\{\{x_{1j[1]},\ldots ,x_{(r-1)j[r-1]}\}|1\leq j[k]\leq r-1

para

1\leq k\leq r-1\}

Se pueden visualizar los vértices de $X$ dispuestos en una cuadrícula de $(r - 1) \times (r - 1) . Las hiperaristas de$ $E 00$ son las $r - 1$ filas. Las hiperaristas de $E 11$ son las $(r - 1) r -1$ selecciones de un solo elemento en cada fila y cada columna. Para cubrir las hiperaristas de $E 10$ necesitamos $r - 1$ vértices, un vértice en cada fila. Dado que todas las columnas son simétricas en la construcción, podemos asumir que tomamos todos los vértices en la columna 1 (es decir, $v i 1$ para cada $i$ en ${1, \dots, r - 1})$ . Ahora, dado que $E 11$ contiene todas las columnas, necesitamos al menos $r - 2$ vértices adicionales, un vértice para cada columna ${2, \dots, r}.$ En total, cada transversal requiere al menos $2 r - 3$ vértices.

Algoritmos

La demostración de Haxell no es constructiva. Sin embargo, Chidambaram Annamalai demostró que se puede encontrar un emparejamiento perfecto de manera eficiente bajo una condición ligeramente más estricta. ^{[ 8 ]}

Para cada elección fija de $r \geq 2$ y $ε > 0$ , existe un algoritmo que encuentra un emparejamiento $Y$ -perfecto en cada hipergrafo bipartito $r -uniforme que satisface, para cada subconjunto$ $Y 0$ de $Y$ :

\tau (H_{H}(Y_{0}))\geq (2r-3+\epsilon )\cdot (|Y_{0}|-1)+1

De hecho, en cualquier hipergrafo $r$ -uniforme, el algoritmo encuentra un emparejamiento $Y$ -perfecto o un subconjunto $Y 0$ que viola la desigualdad anterior.

El algoritmo se ejecuta en un tiempo polinómico en el tamaño de $H$ , pero exponencial en $r$ y $1 / ε$ .

Queda por determinar si existe un algoritmo con un tiempo de ejecución polinomial en $r$ o en $1$ $/$ $ε$ (o en ambos).

Se han aplicado algoritmos similares para resolver problemas de asignación justa de artículos , en particular el problema de Santa Claus . ^{[ 9 ]}^{[ 10 ]}^{[ 11 ]}

Condiciones de Aharoni-Haxell: conjuntos de fijación más pequeños

Decimos que un conjunto $K$ de aristas fija otro conjunto $F$ de aristas si cada arista en $F$ interseca alguna arista en $K.$ ^{[ 6} ] El ancho de un hipergrafo $H = (V, E)$ , denotado $w (H)$ , es el tamaño más pequeño de un subconjunto de ^E $que$ fija $E$ . ^{[ 7 ]} El ancho de emparejamiento de un hipergrafo $H$ , denotado $mw (H)$ , es el máximo, sobre todos los emparejamientos $M$ en $H$ , del tamaño mínimo de un subconjunto de $E$ que fija $M$ . ^{[ 12 ]} Dado que $E$ contiene todos los emparejamientos en $E$ , el ancho de H es obviamente al menos tan grande como el ancho de emparejamiento de $H$ .

Aharoni y Haxell demostraron la siguiente condición:

Sea $H = (X + Y, E)$ un hipergrafo bipartito. Supongamos que, para cada subconjunto $Y 0$ de $Y$ , se cumple la siguiente desigualdad:
$mw(N_{H}(Y_{0}))\geq |Y_{0}|$
[En otras palabras: $N H (Y 0)$ contiene un emparejamiento $M(Y 0)$ tal que se requieren al menos $| Y 0 |$ aristas disjuntas de $N H (Y 0) para fijar$ $M(Y 0)$ ]. Entonces, $H$ admite un emparejamiento $Y$ -perfecto. ^{[ 6 ]}^{: Teorema 1.1}

Posteriormente, extendieron esta condición de varias maneras, que más tarde fueron ampliadas por Meshulam de la siguiente manera:

Sea $H = (X + Y, E)$ un hipergrafo bipartito. Supongamos que, para cada subconjunto $Y 0$ de $Y$ , se cumple al menos una de las siguientes condiciones:
$mw(N_{H}(Y_{0}))\geq |Y_{0}|$ o $w(N_{H}(Y_{0}))\geq 2|Y_{0}|-1$
Entonces, $H$ admite un emparejamiento $Y$ -perfecto. ^{[ 7 ]}^{: Teorema 1.4}

En gráficos simples

En un grafo simple bipartito, el hipergrafo de vecindad contiene solo singletons: un singleton para cada vecino de $Y 0$ . Dado que los singletons no se intersecan, el conjunto completo de vecinos $N H (Y 0)$ es un emparejamiento, y su único conjunto de fijación es el propio conjunto $N H (Y 0)$ , es decir, el ancho de emparejamiento de $N H (Y 0)$ es $| N H (Y 0) |$ , y su ancho es el mismo:

w(N_{H}(Y_{0}))=mw(N_{H}(Y_{0}))=|N_{H}(Y_{0})|.

Por lo tanto, ambas condiciones anteriores son equivalentes a la condición de matrimonio de Hall.

Ejemplos

Consideramos varios grafos bipartitos con $Y = {1, 2}$ y $X = {A, B; a, b, c}.$ La condición de Aharoni-Haxell se cumple trivialmente para el conjunto vacío . Se cumple para subconjuntos de tamaño 1 si y solo si cada vértice en $Y$ está contenido en al menos una arista, lo cual es fácil de comprobar. Resta comprobar el subconjunto $Y$ en sí.

$H = { {1,A,a}; {2,B,b}; {2,B,c} }.$ Aquí $N H (Y) = { {A,a}, {B,b}, {B,c} }.$ Su ancho de emparejamiento es al menos 2, ya que contiene un emparejamiento de tamaño 2, por ejemplo ${ {A,a}, {B,b} },$ que no puede ser fijado por ninguna arista individual de $N H (Y 0)$ . De hecho, H admite un $emparejamiento Y$ -perfecto, por ejemplo ${ {1,A,a}; {2,B,b} }.$
$H = { {1,A,a}; {1,B,b}; {2,A,b}, {2,B,a} }.$ Aquí $N H (Y) = { {A,a}, {B,b}, {A,b}, {B,a} }.$ Su ancho de emparejamiento es 1: contiene un emparejamiento de tamaño 2, por ejemplo ${ {A,a}, {B,b} },$ pero este emparejamiento puede ser fijado por una sola arista, por ejemplo ${A,b}.$ El otro emparejamiento de tamaño 2 es ${ {A,b},{B,a} },$ pero también puede ser fijado por la única arista ${A,a}.$ Si bien $N H (Y)$ es mayor que en el ejemplo 1, su ancho de emparejamiento es menor; en particular, es menor que $| Y |$ . Por lo tanto, la condición suficiente de Aharoni-Haxell no se satisface. De hecho, $H$ no admite un $emparejamiento Y$ -perfecto.
$H = { {1,A,a}, {1,A,b}; {1,B,a}, {1,B,b}; {2,A,a}, {2,A,b}; {2,B,a}, {2,B,b} }.$ Aquí, como en el ejemplo anterior, $N H (Y) = { {A,a}, {B,b}, {A,b}, {B,a} },$ por lo que se viola la condición suficiente de Aharoni-Haxell. El ancho de $N H (Y)$ es 2, ya que está fijado, por ejemplo, por el conjunto ${ {A,a}, {B,b} },$ por lo que también se viola la condición más débil de Meshulam. Sin embargo, este $H$ sí admite unemparejamiento $Y -perfecto, por ejemplo$ $, { {1,A,a}; {2,B,b} },$ lo que muestra que estas condiciones no son necesarias.

Formulación de familia de conjuntos

Consideremos un hipergrafo bipartito $H = (X + Y, E)$ donde $Y = {1, \dots, m}.$ Los teoremas de tipo Hall no se ocupan del conjunto $Y$ en sí mismo, sino solo de los vecinos de los elementos de $Y.$ Por lo tanto, $H$ puede representarse como una colección de familias de conjuntos ${H 1, \dots, H m},$ donde para cada $i$ en $[m]$ , $H i := N H ({i}) =$ la familia de conjuntos de vecinos de $i$ . Para cada subconjunto $Y 0$ de $Y$ , la familia de conjuntos $N H (Y 0)$ es la unión de las familias de conjuntos $H i$ para $i$ en $Y 0$ . Un emparejamiento perfecto en $H$ es una familia de conjuntos de tamaño $m$ , donde para cada $i$ en $[m]$ , la familia de conjuntos $H i$ está representada por un conjunto $R i$ en $H i$ , y los conjuntos representativos $R i$ son disjuntos dos a dos.

En esta terminología, el teorema de Aharoni-Haxell se puede enunciar de la siguiente manera.

Sea $A = {H 1, \dots, H m}$ una colección de familias de conjuntos. Para cada subcolección $B$ de $A$ , consideremos la familia de conjuntos $\cup B$ - la unión de todos los $H i$ en $B$ . Supongamos que, para cada subcolección $B$ de $A$ , esta $\cup B$ contiene un $M (B)$ correspondiente tal que se requieren al menos $| B |$ subconjuntos disjuntos de $\cup B$ para fijar $M (B)$ . Entonces $A$ admite un sistema de representantes disjuntos.

Condición necesaria y suficiente

Sea $H = (X + Y, E)$ un hipergrafo bipartito. Los siguientes son equivalentes: ^{[ 6 ]}^{: Teorema 4.1}

$H$ admite un emparejamiento $Y$ -perfecto.
Hay una asignación de un $M (Y 0)$ coincidente en $N H (Y 0)$ para cada subconjunto $Y 0$ de $Y$ , de tal manera que fijar $M (Y 0)$ requiere al menos $| 0 |$ aristas disjuntas de $\cup {M (Y 1): Y 1$ es un subconjunto de $Y 0}.$

En la formulación de familias de conjuntos: sea $A = {H 1, \dots, H m}$ una colección de familias de conjuntos. Las siguientes son equivalentes:

$A$ admite un sistema de representantes disjuntos;
Hay una asignación de un $M (B$ coincidente en $\cup B$ para cada subcolección $B$ de $A$ , de tal manera que, para fijar $M (B)$ , se requieren al menos $| B |$ aristas de $\cup {M (C): C$ es una subcolección de $B}$ .

Ejemplos

Consideremos el ejemplo n.° 3 anterior: $H = { {1,A,a}, {1,A,b};$ ${1,B,a}, {1,B,b};$ ${2,A,a}, {2,A,b};$ ${2,B,a}, {2,B,b} }.$ Dado que admite un emparejamiento $Y$ -perfecto, debe satisfacer la condición necesaria. En efecto, consideremos la siguiente asignación a subconjuntos de $Y$ :

$M({1}) = {A,a}$
$M({2}) = {B,b}$
$M({1,2}) = { {A, a}, {B, b} }$

En la condición suficiente, el anclaje de $M({1,2})$ requería al menos dos aristas de $N H (Y) = { {A,a}, {B,b}, {A,b}, {B,a} };$ no se cumplió.

Pero en la condición necesaria, fijar $M({1,2})$ requería al menos dos aristas de $M({1}) \cup M({2}) \cup M({1,2}) = { {A,a}, {B,b} };$ y se cumple.

Por lo tanto, se cumple la condición necesaria y suficiente.

Prueba

La demostración es topológica y utiliza el lema de Sperner . Curiosamente, implica una nueva demostración topológica para el teorema de Hall original. ^{[ 13 ]}

Primero, supongamos que no hay dos vértices en $Y$ que tengan exactamente el mismo vecino (esto no supone pérdida de generalidad , ya que para cada elemento $y$ de $Y$ , se puede añadir un vértice ficticio a todos los vecinos de $y$ ).

Sea $Y = {1, \dots, m}.$ Consideran un símplex $de m$ vértices y demuestran que admite una triangulación $T$ con algunas propiedades especiales que denominan triangulación jerárquica económica . Luego, etiquetan cada vértice de $T$ con una hiperarista de $N H (Y)$ de la siguiente manera:

(a) Para cada $i$ en $Y$ , el vértice principal $i$ del simplex se etiqueta con alguna hiperarista del $M({i})$ correspondiente .
(b) Cada vértice de $T$ en una cara generada por un subconjunto $Y 0$ de $Y$ , está etiquetado por alguna hiperarista del $M(Y 0)$ correspondiente .
(c) Para cada dos vértices adyacentes de $T$ , sus etiquetas son idénticas o disjuntas.

Su condición suficiente implica que existe tal etiquetado. Luego, colorean cada vértice $v$ de $T$ con un color $i$ tal que la hiperarista asignada a $v$ sea vecina de $i$ .

Las condiciones (a) y (b) garantizan que esta coloración satisface la condición de contorno de Sperner. Por lo tanto, existe un símplex completamente etiquetado. En este símplex hay $m$ hiperaristas, cada una de las cuales es vecina de un elemento distinto y único de $Y$ , por lo que deben ser disjuntas. Este es el emparejamiento perfecto $de Y deseado.$

Extensiones

El teorema de Aharoni-Haxell tiene una versión deficiente. Se utiliza para demostrar la conjetura de Ryser para $r =$ 3. ^{[ 12 ]}

Las condiciones de Meshulam: los teoremas topológicos de Hall

En complejos simpliciales abstractos

Sea $V$ un conjunto de vértices. Sea $C$ un complejo simplicial abstracto sobre $V.$ Sean $V y$ (para $y$ en $Y$ ) subconjuntos de $V.$ Una transversal $CV$ es un conjunto en $C$ (un elemento de $C$ ) cuya intersección con cada $V y$ contiene exactamente un vértice. Para cada subconjunto $Y 0$ de $Y$ , sea

V_{Y_{0}}:=\bigcup _{y\in Y_{0}}V_{y}.

Supongamos que, para cada subconjunto $Y 0$ de $Y$ , la conectividad homológica más 2 del subcomplejo inducido por $V_{Y_{0}}$ es al menos $| Y 0 |$ , es decir:

\eta _{H}(C[V_{Y_{0}}])\geq |Y_{0}|.

Entonces existe una transversal $CV$ . Es decir: existe un conjunto en $C$ que interseca cada $V y$ por exactamente un elemento. ^{[ 14 ]} Este teorema tiene una versión deficiente. ^{[ 15 ]} Si, para cada subconjunto $Y 0$ de $Y$ :

\eta _{H}(C[V_{Y_{0}}])\geq |Y_{0}|-d,

Entonces existe una $C$ -transversal parcial que interseca algunos conjuntos $| Y | - d$ por 1 elemento, y el resto por como máximo 1 elemento. De manera más general, si $g$ es una función sobre enteros positivos que satisface $g (z + 1) \leq g (z )$ $+$ $1$ , y para cada subconjunto $Y₀$ de $Y$ :

\eta _{H}(C[V_{Y_{0}}])\geq g(|Y_{0}|),

entonces hay un conjunto en $C$ que interseca al menos $g (| Y |)$ de $V y$ en un elemento, y los demás en como máximo un elemento.

El juego de Meshulam

El uso del teorema anterior requiere algunas cotas inferiores para la conectividad homológica. Una de estas cotas inferiores viene dada por el juego de Meshulam . Este es un juego jugado por dos jugadores en un grafo. Un jugador, CON, quiere demostrar que el grafo tiene una alta conectividad homológica . El otro jugador, NON, quiere demostrar lo contrario. CON ofrece aristas a NON una por una; NON puede desconectar una arista o hacerla explotar; una explosión elimina los extremos de la arista y todos sus vecinos. La puntuación de CON es el número de explosiones cuando todos los vértices han desaparecido, o infinito si quedan algunos vértices aislados. El valor del juego en un grafo $G$ dado (la puntuación de CON cuando ambos jugadores juegan de forma óptima) se denota por $Ψ(G)$ . Este número se puede utilizar para obtener una cota inferior para la conectividad homológica del complejo de independencia de $G$ , denotada por . ${\mathcal {I}}(G)$ :

\eta _{H}({\mathcal {I}}(G))\geq \Psi (G).

Por lo tanto, el teorema anterior implica lo siguiente. Sea $V$ un conjunto de vértices. Sea $G$ un grafo sobre $V.$ Supongamos que, para cada subconjunto $Y 0$ de $Y$ :

\Psi (G[V_{Y_{0}}])\geq |Y_{0}|.

Entonces hay un conjunto independiente en $G$ que interseca a cada $V y$ por exactamente un elemento.

En grafos bipartitos simples

Sea $H$ un grafo bipartito con partes $X$ e $Y.$ Sea $V$ el conjunto de aristas de $H.$ Sea $G = L(H) =$ el grafo de líneas de $H.$ Entonces, el complejo de independencia ${\mathcal {I}}(L(H))$ ⁠ es igual al complejo correspondiente de H, denotado ⁠ ${\mathcal {M}}(H)$ Es un complejo simplicial sobre las aristas de $H$ , cuyos elementos son todos los emparejamientos en $H.$ Para cada vértice $y$ en $Y$ , sea $V y$ el conjunto de aristas adyacentes a $y$ (nótese que $V y$ es un subconjunto de $V ).$ Entonces , para cada subconjunto $Y 0$ de $Y$ , el subgrafo inducido $G[V_{Y_{0}}]$ contiene una camarilla para cada vecino de $Y 0$ (todas las aristas adyacentes a $Y 0$ que se encuentran en el mismo vértice de $X$ forman una camarilla en el grafo de líneas). Por lo tanto, hay $| N H (Y 0) |$ camarillas disjuntas. En consecuencia, cuando se juega el juego de Meshulam, NON necesita $| N H (Y 0) |$ explosiones para destruir todo $L(N H (Y 0))$ , por lo que $Ψ(L(N H (Y 0)) = | N H (Y 0) |$ . Por lo tanto, la condición de Meshulam

\Psi (G[V_{Y_{0}}])\geq |Y_{0}|

es equivalente a la condición de matrimonio de Hall. Aquí, los conjuntos $V y$ son disjuntos por pares, por lo que una $C$ -transversal contiene un elemento único de cada $V y$ , lo que es equivalente a un emparejamiento $Y$ -saturado.

En complejos coincidentes

Sea $H$ un hipergrafo bipartito y supongamos que $C$ es su complejo de emparejamiento . ${\mathcal {M}}(H)$ ⁠ . Sea $H y$ (para $y$ en $Y$ ) un conjunto de aristas de $H$ . Para cada subconjunto $Y 0$ de $Y$ , ⁠ ${\mathcal {M}}(H_{Y_{0}})$ es el conjunto de emparejamientos en el subhipergrafo:

\bigcup _{y\in Y_{0}}H_{y}.

Si, para cada subconjunto $Y 0$ de $Y$ :

\eta _{H}({\mathcal {M}}(H_{Y_ {0}}))\geq |Y_ {0}|

Entonces existe un emparejamiento que interseca cada conjunto $H y$ exactamente una vez (también se le llama emparejamiento arcoíris , ya que cada $H y$ puede tratarse como un color).

Esto es cierto, en particular, si definimos $H y$ como el conjunto de aristas de $H$ que contienen el vértice $y$ de $Y.$ En este caso , ${\mathcal {M}}(H_{Y_{0}})$ ⁠ es equivalente a $N H (Y 0)$ - el hipergrafo múltiple de vecinos de $Y 0$ ("multi" - ya que cada vecino puede aparecer varias veces para varios $y$ diferentes ).

El complejo de correspondencia de un hipergrafo es exactamente el complejo de independencia de su grafo de líneas , denotado $L (H)$ . Este es un grafo en el que los vértices son las aristas de $H$ , y dos de estos vértices están conectados si y solo si sus aristas correspondientes se intersecan en $H.$ Por lo tanto, el teorema anterior implica:

\eta _{H}({\mathcal {M}}(H))\geq \Psi (L(H))

La combinación de las desigualdades anteriores conduce a la siguiente condición.

Sea

H = (X + Y, E)

un hipergrafo bipartito. Supongamos que, para cada subconjunto

Y 0

de

Y

, se cumple la siguiente condición:

\Psi (L(N_{H}(Y_{0})))\geq |Y_{0}|,

donde

N H (Y 0)

se considera un hipergrafo múltiple (es decir, puede contener la misma hiperarista varias veces, si es vecina de varios elementos diferentes de

Y 0

). Entonces,

H

admite un emparejamiento

Y

-perfecto. ^{[ 14 ]}

Ejemplos

Consideramos varios hipergrafos bipartitos con $Y = {1, 2}$ y $X = {A, B; a, b, c}.$ La condición de Meshulam se cumple trivialmente para el conjunto vacío. Se cumple para subconjuntos de tamaño 1 si y solo si el grafo de vecinos de cada vértice en $Y$ no está vacío (por lo que requiere al menos una explosión para destruirlo), lo cual es fácil de comprobar. Resta comprobar el subconjunto $Y$ en sí mismo.

$H = { {1,A,a}; {2,B,b}; {2,B,c} }.$ Aquí $N H (Y) = { {A,a}, {B,b}, {B,c} }.$ El grafo $L(N H (Y))$ tiene tres vértices: $Aa, Bb, Bc.$ Solo los dos últimos están conectados; el vértice Aa está aislado. Por lo tanto, $Ψ(L(N H (Y)) = \infty$ . En efecto, $H$ admite un $emparejamiento Y$ -perfecto, por ejemplo ${ {1,A,a}; {2,B,b} }.$
H = { {1,A,a}; {1,B,b}; {2,A,b}, {2,B,a} }. Aquí $L(N H (Y))$ tiene cuatro vértices: $Aa, Bb, Ab, Ba,$ y cuatro aristas: ${Aa,Ab}, {Aa,Ba}, {Bb,Ba}, {Bb,Ab}.$ Para cualquier arista que CON ofrece, NON puede explotarla y destruir todos los vértices. Por lo tanto, $Ψ(L(N H (Y)) = 1$ . De hecho, $H$ no admite un emparejamiento $Y$ -perfecto.
$H = { {1,A,a}, {1,A,b};$ ${1,B,a}, {1,B,b};$ ${2,A,a}, {2,A,b};$ ${2,B,a}, {2,B,b} }.$ Aquí $N H (Y)$ es el mismo que en el ejemplo anterior, por lo que se viola la condición suficiente de Meshulam. Sin embargo, este $H$ sí admite un $emparejamiento Y$ -perfecto, por ejemplo ${ {1,A,a}; {2,B,b} },$ lo que demuestra que esta condición no es necesaria.

No se conoce ninguna condición necesaria y suficiente que utilice $Ψ .$

Más condiciones de coincidencias arcoíris

Un emparejamiento arcoíris es un emparejamiento en un grafo simple, donde cada arista tiene un "color" diferente. Al considerar los colores como vértices del conjunto $Y$ , se observa que un emparejamiento arcoíris es, de hecho, un emparejamiento en un hipergrafo bipartito . Por lo tanto, varias condiciones suficientes para la existencia de un emparejamiento arcoíris grande pueden traducirse en condiciones para la existencia de un emparejamiento grande en un hipergrafo.

Los siguientes resultados se refieren a hipergrafos tripartitos en los que cada una de las 3 partes contiene exactamente $n$ vértices, el grado de cada vértice es exactamente $n$ , y el conjunto de vecinos de cada vértice es un emparejamiento (en adelante, " hipergrafo tripartito $n$ "):

Cada $n$ -hipergrafo tripartito tiene un emparejamiento de tamaño $2$ $n$ $⁄$ $3$ . ^[¹⁶^]
Cada $n$ -hipergrafo tripartito tiene un emparejamiento de tamaño $n - \sqrt n$ . ^{[ 17 ]}
Cada $n$ -hipergrafo tripartito tiene un emparejamiento de tamaño $n - 11 log 22 (n)$ . ^{[ 18 ]}
Cada $n$ -hipergrafo tripartito tiene un emparejamiento de tamaño $n - O(log n /log log n)$ . ^{[ 19 ]}
Cada $n$ -hipergrafo tripartito tiene un emparejamiento de tamaño $n - 1$ . ^{[ 20 ]} (Preimpresión)
HJ Ryser conjeturó que, cuando $n$ es impar , todo hipergrafo tripartito $n tiene un emparejamiento de tamaño$ $n$ . ^{[ 21 ]}
SK Stein y Brualdi conjeturaron que, cuando $n$ es par , cada $n$ -hipergrafo tripartito tiene un emparejamiento de tamaño $n - 1.$ [ ^{22 ] (} se sabe que un emparejamiento de tamaño $n$ podría no existir en este caso).
Una conjetura más general de Stein es que existe un emparejamiento de tamaño $n - 1$ incluso sin requerir que el conjunto de vecinos de cada vértice en $Y$ sea un emparejamiento. ^{[ 21 ]}

Los siguientes resultados se refieren a hipergrafos bipartitos más generales:

Cualquier hipergrafo tripartito $(X 1 + X 2 + Y, E)$ en el que $| Y | = 2 n - 1$ , el grado de cada vértice $y$ en $Y$ es $n$ , y el conjunto de vecinos de $y$ es un emparejamiento, tiene un emparejamiento de tamaño $n$ . ^{[ 23 ]} El $2 n - 1$ es el mejor posible: si $| Y | = 2 n - 2$ , entonces el emparejamiento máximo puede ser de tamaño $n$ -1.
Cualquier hipergrafo bipartito $(X + Y, E)$ en el que $| Y | = 3 n - 2$ , el grado de cada vértice y en $Y$ es $n$ , y el conjunto de vecinos de $y$ es un emparejamiento, tiene un emparejamiento de tamaño $n$ . ^{[ 23 ]} No se sabe si este es el mejor posible. Para $n$ par , solo se sabe que se requiere $2 n$ ; para $n$ impar , solo se sabe que se requiere $2 n - 1 .$

Condición de Conforti-Cornuejols-Kapoor-Vuskovic: Hipergrafos equilibrados

Un hipergrafo equilibrado es una generalización alternativa de un grafo bipartito: es un hipergrafo en el que cada ciclo impar $C$ de $H$ tiene una arista que contiene al menos tres vértices de $C.$

Sea $H = (V, E)$ un hipergrafo balanceado. Las siguientes son equivalentes: ^{[ 24 ]}^{[ 25 ]}

$H$ admite un emparejamiento perfecto (es decir, un emparejamiento en el que cada vértice está emparejado).
Para todos los conjuntos de vértices disjuntos $V 1$ , $V 2$ , si $| V 1 | > | V 2 |$ , entonces existe una arista $e$ en $E$ tal que $| e \cap V 1 | > | e \cap V 2 |$ (equivalentemente: si $| e \cap V 2 | \geq | e \cap V 1 |$ para todas las aristas $e$ en $E$ , entonces $| V 2 | \geq | V 1 |$ ).

En gráficos simples

Un grafo simple es bipartito si y solo si está equilibrado (no contiene ciclos impares ni aristas con tres vértices).

Sea $G = (X + Y, E) un grafo bipartito. Sea X 0 un subconjunto de X e Y 0 un subconjunto de Y . La condición " e \cap X 0 \geq | e \cap Y 0 |$ para todas las aristas $e$ en $E$ " significa que $X 0$ contiene todos los vecinos de los vértices de $Y 0.$ Por lo tanto, la condición CCKV se convierte en:

"Si un subconjunto $X 0$ de $X$ contiene el conjunto $N H (Y 0)$ , entonces $| X 0 | \geq | Y 0 |$ ".

Esto equivale a la condición de Hall.

Véase también

Emparejamiento perfecto en hipergrafos de alto grado : presenta otras condiciones suficientes para la existencia de emparejamientos perfectos, que se basan únicamente en el grado de los vértices.

Referencias

1 2 3 Aharoni, Ron; Kessler, Ofra (1990-10-15). "Sobre una posible extensión del teorema de Hall a hipergrafos bipartitos" . Matemáticas Discretas . 84 (3): 309– 313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
1 2 Kessler, Ofra (1989). Emparejamientos en hipergrafos (tesis doctoral) . Haifa, Israel: Technion, instituto tecnológico de Israel.
1 2 Aharoni, Ron (1985-12-01). "Matchings inn-partiten-graphs". Graphs and Combinatorics . 1 (1): 303– 304. doi : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .
1 2 3 Aharoni, Ron (1993-06-01). "Sobre un criterio de emparejamiento en hipergrafos". Graphs and Combinatorics . 9 (2): 209– 212. doi : 10.1007/BF02988309 . ISSN 1435-5914 . S2CID 29126477 .
1 2 Haxell, PE (1995-09-01). "Una condición para la emparejabilidad en hipergrafos". Graphs and Combinatorics . 11 (3): 245– 248. doi : 10.1007/bf01793010 . S2CID 28459229 .
1 2 3 4 5 Aharoni, Ron; Haxell, Penny (2000). "Teorema de Hall para hipergrafos" . Journal of Graph Theory . 35 (2): 83– 88. doi : 10.1002/1097-0118(200010)35:2 < 83::AID-JGT2 > 3.0.CO ; 2-V . ISSN 1097-0118 .
1 2 3 Meshulam, Roy (2001-01-01). "El complejo de cliques y el emparejamiento de hipergrafos". Combinatorica . 21 (1): 89– 94. doi : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .
↑ Annamalai, Chidambaram (21-12-2015), "Finding Perfect Matchings in Bipartite Hypergraphs", Actas del Simposio Anual ACM-SIAM de 2016 sobre Algoritmos Discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 1814–1823 , arXiv : 1509.07007 , doi : 10.1137/1.9781611974331.ch126 , ISBN 978-1-61197-433-1
↑ Asadpour Arash; Feige Uriel; Saberi Amin (24 de julio de 2012). "Santa Claus conoce a los emparejamientos de hipergrafos". ACM Transactions on Algorithms . 8 (3): 1– 9. doi : 10.1145/2229163.2229168 . S2CID 10281304 .
↑ Annamalai Chidambaram; Kalaitzis Christos; Svensson Ola (26 de mayo de 2017). "Algoritmo combinatorio para asignación justa max-min restringida". ACM Transactions on Algorithms . 13 (3): 1– 28. arXiv : 1409.0607 . doi : 10.1145/3070694 . S2CID 14749011 .
↑ Davies, Sami; Rothvoss, Thomas; Zhang, Yihao (23 de diciembre de 2019), "Un cuento de Papá Noel, hipergrafos y matroides", Actas del Simposio ACM-SIAM de 2020 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 2748–2757 , arXiv : 1807.07189 , doi : 10.1137/1.9781611975994.167 , ISBN 978-1-61197-599-4, S2CID 49880727
^ Aharoni, Ron (1 de enero de 2001) . "Conjetura de Ryser para 3 gráficos tripartitos". Combinatoria . 21 (1): 1– 4. doi : 10.1007/s004930170001 . ISSN 1439-6912 . S2CID 13307018 .
↑ Kalai, Gil (25 de noviembre de 2012). "¡Feliz cumpleaños, Ron Aharoni!" . Combinatoria y más . Recuperado el 30 de junio de 2020 .
1 2 Meshulam, Roy (2003-05-01). "Números de dominación y homología" . Journal of Combinatorial Theory . Serie A. 102 (2): 321– 330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 .
^ Aharoni, Ron; Berger, Eli; Briggs, José; Segal-Halevi, Erel; Zerbib, Shira (2 de noviembre de 2020). "Hipergrafos fraccionariamente equilibrados y teoremas de KKM arcoíris". arXiv : 2011.01053 [ matemáticas.CO ].
↑ Koksma, Klaas K. (1969-07-01). "Una cota inferior para el orden de una transversal parcial en un cuadrado latino" . Journal of Combinatorial Theory . 7 (1): 94– 95. doi : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800 .
↑ Woolbright, David E (1978-03-01). "Un cuadrado latino n × n tiene una transversal con al menos n−n símbolos distintos" . Journal of Combinatorial Theory . Serie A. 24 (2): 235– 237. doi : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165 .
↑ Hatami, Pooya; Shor, Peter W. (1 de octubre de 2008). "Una cota inferior para la longitud de una transversal parcial en un cuadrado latino" . Journal of Combinatorial Theory . Serie A. 115 (7): 1103–1113 . doi : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165 .
↑ Keevash, Peter; Pokrovskiy, Alexey; Sudakov, Benny; Yepremyan, Liana (15 de abril de 2022). "Nuevos límites para la conjetura de Ryser y problemas relacionados" . Transactions of the American Mathematical Society, Series B. 9 ( 8): 288–321 . arXiv : 2005.00526 . doi : 10.1090/btran/92 . ISSN 2330-0000 .
↑ Montgomery, Richard (2023). "Una demostración de la conjetura de Ryser-Brualdi-Stein para n par grande ". arXiv : 2310.19779 [ math.CO ].
1 2 Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (4 de enero de 2017). "Sobre una conjetura de Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211 . arXiv : 1605.01982 . doi : 10.1007/s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .
↑ Stein, Sherman (1975-08-01). "Transversales de cuadrados latinos y sus generalizaciones" . Pacific Journal of Mathematics . 59 (2): 567– 575. doi : 10.2140/pjm.1975.59.567 . ISSN 0030-8730 .
1 2 Aharoni, Ron; Berger, Eli (2009-09-25). "Emparejamientos arcoíris en $r$-grafos $r$-partitos" . The Electronic Journal of Combinatorics . 16 (1) R119. doi : 10.37236/208 . ISSN 1077-8926 .
↑ Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (1996-09-01). "Emparejamientos perfectos en hipergrafos equilibrados". Combinatorica . 16 (3): 325– 329. doi : 10.1007/BF01261318 . ISSN 1439-6912 . S2CID 206792822 .
↑ Huck, Andreas; Triesch, Eberhard (2002-07-01). "Emparejamientos perfectos en hipergrafos balanceados: un enfoque combinatorio". Combinatorica . 22 (3): 409– 416. doi : 10.1007/s004930200020 . ISSN 1439-6912 . S2CID 34490040 .

[:1-1] 1 2 3 Aharoni, Ron; Kessler, Ofra (1990-10-15). "Sobre una posible extensión del teorema de Hall a hipergrafos bipartitos" . Matemáticas Discretas . 84 (3): 309– 313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .

[:2-2] 1 2 Kessler, Ofra (1989). Emparejamientos en hipergrafos (tesis doctoral) . Haifa, Israel: Technion, instituto tecnológico de Israel.

[:5-3] 1 2 Aharoni, Ron (1985-12-01). "Matchings inn-partiten-graphs". Graphs and Combinatorics . 1 (1): 303– 304. doi : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .

[:3-4] 1 2 3 Aharoni, Ron (1993-06-01). "Sobre un criterio de emparejamiento en hipergrafos". Graphs and Combinatorics . 9 (2): 209– 212. doi : 10.1007/BF02988309 . ISSN 1435-5914 . S2CID 29126477 .

[:0-5] 1 2 Haxell, PE (1995-09-01). "Una condición para la emparejabilidad en hipergrafos". Graphs and Combinatorics . 11 (3): 245– 248. doi : 10.1007/bf01793010 . S2CID 28459229 .

[:4-6] 1 2 3 4 5 Aharoni, Ron; Haxell, Penny (2000). "Teorema de Hall para hipergrafos" . Journal of Graph Theory . 35 (2): 83– 88. doi : 10.1002/1097-0118(200010)35:2 < 83::AID-JGT2 > 3.0.CO ; 2-V . ISSN 1097-0118 .

[:7-7] 1 2 3 Meshulam, Roy (2001-01-01). "El complejo de cliques y el emparejamiento de hipergrafos". Combinatorica . 21 (1): 89– 94. doi : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

[8] Annamalai, Chidambaram (21-12-2015), "Finding Perfect Matchings in Bipartite Hypergraphs", Actas del Simposio Anual ACM-SIAM de 2016 sobre Algoritmos Discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 1814–1823 , arXiv : 1509.07007 , doi : 10.1137/1.9781611974331.ch126 , ISBN 978-1-61197-433-1

[9] Asadpour Arash; Feige Uriel; Saberi Amin (24 de julio de 2012). "Santa Claus conoce a los emparejamientos de hipergrafos". ACM Transactions on Algorithms . 8 (3): 1– 9. doi : 10.1145/2229163.2229168 . S2CID 10281304 .

[10] Annamalai Chidambaram; Kalaitzis Christos; Svensson Ola (26 de mayo de 2017). "Algoritmo combinatorio para asignación justa max-min restringida". ACM Transactions on Algorithms . 13 (3): 1– 28. arXiv : 1409.0607 . doi : 10.1145/3070694 . S2CID 14749011 .

[11] Davies, Sami; Rothvoss, Thomas; Zhang, Yihao (23 de diciembre de 2019), "Un cuento de Papá Noel, hipergrafos y matroides", Actas del Simposio ACM-SIAM de 2020 sobre algoritmos discretos , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 2748–2757 , arXiv : 1807.07189 , doi : 10.1137/1.9781611975994.167 , ISBN 978-1-61197-599-4, S2CID 49880727

[:6-12] Aharoni, Ron (1 de enero de 2001) . "Conjetura de Ryser para 3 gráficos tripartitos". Combinatoria . 21 (1): 1– 4. doi : 10.1007/s004930170001 . ISSN 1439-6912 . S2CID 13307018 .

[13] Kalai, Gil (25 de noviembre de 2012). "¡Feliz cumpleaños, Ron Aharoni!" . Combinatoria y más . Recuperado el 30 de junio de 2020 .

[:03-14] 1 2 Meshulam, Roy (2003-05-01). "Números de dominación y homología" . Journal of Combinatorial Theory . Serie A. 102 (2): 321– 330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 .

[15] Aharoni, Ron; Berger, Eli; Briggs, José; Segal-Halevi, Erel; Zerbib, Shira (2 de noviembre de 2020). "Hipergrafos fraccionariamente equilibrados y teoremas de KKM arcoíris". arXiv : 2011.01053 [ matemáticas.CO ].

[16] Koksma, Klaas K. (1969-07-01). "Una cota inferior para el orden de una transversal parcial en un cuadrado latino" . Journal of Combinatorial Theory . 7 (1): 94– 95. doi : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800 .

[17] Woolbright, David E (1978-03-01). "Un cuadrado latino n × n tiene una transversal con al menos n−n símbolos distintos" . Journal of Combinatorial Theory . Serie A. 24 (2): 235– 237. doi : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165 .

[18] Hatami, Pooya; Shor, Peter W. (1 de octubre de 2008). "Una cota inferior para la longitud de una transversal parcial en un cuadrado latino" . Journal of Combinatorial Theory . Serie A. 115 (7): 1103–1113 . doi : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165 .

[19] Keevash, Peter; Pokrovskiy, Alexey; Sudakov, Benny; Yepremyan, Liana (15 de abril de 2022). "Nuevos límites para la conjetura de Ryser y problemas relacionados" . Transactions of the American Mathematical Society, Series B. 9 ( 8): 288–321 . arXiv : 2005.00526 . doi : 10.1090/btran/92 . ISSN 2330-0000 .

[20] Montgomery, Richard (2023). "Una demostración de la conjetura de Ryser-Brualdi-Stein para n par grande ". arXiv : 2310.19779 [ math.CO ].

[:022-21] 1 2 Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (4 de enero de 2017). "Sobre una conjetura de Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211 . arXiv : 1605.01982 . doi : 10.1007/s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .

[22] Stein, Sherman (1975-08-01). "Transversales de cuadrados latinos y sus generalizaciones" . Pacific Journal of Mathematics . 59 (2): 567– 575. doi : 10.2140/pjm.1975.59.567 . ISSN 0030-8730 .

[:02-23] 1 2 Aharoni, Ron; Berger, Eli (2009-09-25). "Emparejamientos arcoíris en $r$-grafos $r$-partitos" . The Electronic Journal of Combinatorics . 16 (1) R119. doi : 10.37236/208 . ISSN 1077-8926 .

[24] Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (1996-09-01). "Emparejamientos perfectos en hipergrafos equilibrados". Combinatorica . 16 (3): 325– 329. doi : 10.1007/BF01261318 . ISSN 1439-6912 . S2CID 206792822 .

[25] Huck, Andreas; Triesch, Eberhard (2002-07-01). "Emparejamientos perfectos en hipergrafos balanceados: un enfoque combinatorio". Combinatorica . 22 (3): 409– 416. doi : 10.1007/s004930200020 . ISSN 1439-6912 . S2CID 34490040 .

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 13 ]

[ 15 ]

[

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

22 ] (

[ 24 ]

[ 25 ]