Coincidencia en hipergrafos

En teoría de grafos , un emparejamiento en un hipergrafo es un conjunto de hiperaristas , en el que cada dos hiperaristas son disjuntas . Es una extensión de la noción de emparejamiento en un grafo . ^[1]^{: 466–470} ^[2]

Definición

Recordemos que un hipergrafo $H$ es un par $(V, E)$ , donde $V$ es un conjunto de vértices y $E$ es un conjunto de subconjuntos de $V$ llamados hiperaristas . Cada hiperarista puede contener uno o más vértices.

Una coincidencia en $H$ es un subconjunto $M$ de $E$ , tal que cada dos hiperaristas $e 1$ y $e 2$ en $M$ tienen una intersección vacía (no tienen ningún vértice en común).

El número de coincidencia de un hipergrafo $H$ es el tamaño más grande de una coincidencia en $H$ . A menudo se denota por $ν(H)$ . ^[1]^{: 466} ^[3]

Como ejemplo, sea $V$ el conjunto ${1,2,3,4,5,6,7}.$ Consideremos un hipergrafo 3-uniforme en $V$ (un hipergrafo en el que cada hiperarista contiene exactamente 3 vértices). Sea $H$ un hipergrafo 3-uniforme con 4 hiperaristas:

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

Luego $H$ admite varios emparejamientos de tamaño 2, por ejemplo:

{ {1,2,3}, {4,5,6} }

{ {1,4,5}, {2,3,6} }

Sin embargo, en cualquier subconjunto de 3 hiperaristas, al menos dos de ellas se intersecan, por lo que no hay coincidencia de tamaño 3. Por lo tanto, el número de coincidencia de $H$ es 2.

Hipergrafo intersecante

Un hipergrafo $H = (V, E)$ se denomina intersecante si cada dos hiperaristas en $E$ tienen un vértice en común. Un hipergrafo $H$ es intersecante si y solo si no tiene correspondencia con dos o más hiperaristas, si y solo si $ν(H) = 1$ . ^[4]

La correspondencia en un gráfico como caso especial

Un grafo sin bucles propios es simplemente un hipergrafo 2-uniforme: cada arista puede considerarse como un conjunto de los dos vértices que conecta. Por ejemplo, este hipergrafo 2-uniforme representa un grafo con 4 vértices ${1,2,3,4}$ y 3 aristas:

{ {1,3}, {1,4}, {2,4} }

Según la definición anterior, una coincidencia en un grafo es un conjunto $M$ de aristas, de modo que cada dos aristas en $M$ tienen una intersección vacía. Esto es equivalente a decir que no hay dos aristas en $M$ adyacentes al mismo vértice; esta es exactamente la definición de una coincidencia en un grafo .

Coincidencia fraccionaria

Una coincidencia fraccionaria en un hipergrafo es una función que asigna una fracción en $[0,1]$ a cada hiperarista, de modo que para cada vértice $v$ en $V$ , la suma de las fracciones de las hiperaristas que contienen $a v$ es como máximo 1. Una coincidencia es un caso especial de una coincidencia fraccionaria en el que todas las fracciones son 0 o 1. El tamaño de una coincidencia fraccionaria es la suma de las fracciones de todas las hiperaristas.

El número de coincidencia fraccionaria de un hipergrafo $H$ es el tamaño más grande de una coincidencia fraccionaria en $H$ . A menudo se denota por $ν *(H)$ . ^[3]

Dado que una coincidencia es un caso especial de una coincidencia fraccionaria, para cada hipergrafo $H$ :

Número coincidente ( $H$ ) ≤ número coincidente fraccionario ( $H$ )

Simbólicamente este principio está escrito:

\nu (H)\leq \nu ^{*}(H)

En general, el número de coincidencia fraccionaria puede ser mayor que el número de coincidencia. Un teorema de Zoltán Füredi ^[4] proporciona límites superiores para la relación entre el número de coincidencia fraccionaria ( $H$ ) y el número de coincidencia ( $H$ ):

Si cada hiperarista en $H$ contiene como máximo $r$ vértices, entonces

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.$

En particular, en un gráfico simple: ^[5]

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.$

- La desigualdad es aguda: Sea $H r$ el plano proyectivo finito $r$ -uniforme . Entonces $ν$ $($ $H$ $r$ $) = 1$ ya que cada dos hiperaristas se intersecan, y $ν$ $*($ $H$ $r$ $) =$ $r$ $- 1 +$ $⁠$ $1 / a ⁠$ por la correspondencia fraccionaria que asigna un peso de $⁠$ $1 / a ⁠$ a cada hiperarista (es una coincidencia ya que cada vértice está contenido en $r$ hiperaristas, y su tamaño es $r - 1 + ⁠ 1 / a ⁠$ ya que hay $r 2 - r + 1$ hiperaristas). Por lo tanto, la relación es exactamente $r - 1 + ⁠ 1 / a ⁠$ .
Si $r$ es tal que el plano proyectivo finito $r$ -uniforme no existe (por ejemplo, $r$ $= 7$ ), entonces se cumple una desigualdad más fuerte:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

Si $H$ es $r$ -partito (los vértices están divididos en $r$ partes y cada hiperarista contiene un vértice de cada parte), entonces:

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$

En particular, en un grafo bipartito, $ν *(H) = ν (H)$ . Esto fue demostrado por András Gyárfás . ^[4]

- La desigualdad es aguda: Sea $H r-$ el plano proyectivo truncado de orden $r - 1$ . Entonces $ν (H r -) = 1$ ya que cada dos hiperaristas se intersecan, y $ν *(H r -) = r - 1$ por la correspondencia fraccionaria que asigna un peso de $⁠$ $1 / a ⁠$ a cada hiperarista (hay $r 2 - r$ hiperaristas).

Combinación perfecta

Se dice que una coincidencia $M$ es perfecta si cada vértice $v$ en $V$ está contenido en exactamente una hiperarista de $M.$ Esta es la extensión natural de la noción de coincidencia perfecta en un grafo.

Una coincidencia fraccionaria $M$ se llama perfecta si para cada vértice $v$ en $V$ , la suma de las fracciones de hiperaristas en $M$ que contienen $a v$ es exactamente 1.

Considérese un hipergrafo $H$ en el que cada hiperarista contiene como máximo $n$ vértices. Si $H$ admite un emparejamiento fraccionario perfecto, entonces su número de emparejamiento fraccionario es al menos $| V | ⁄ n$ . Si cada hiperarista en $H$ contiene exactamente $n$ vértices, entonces su número de emparejamiento fraccionario es exactamente $|$ $V$ $|$ $⁄$ $n$ . ^[6]^{: sec.2} Esta es una generalización del hecho de que, en un grafo, el tamaño de un emparejamiento perfecto es $|$ $V$ $|$ $⁄$ $2$ .

Dado un conjunto $V$ de vértices, una colección $E$ de subconjuntos de $V$ se llama equilibrada si el hipergrafo $(V, E)$ admite una correspondencia fraccionaria perfecta.

Por ejemplo, si $V = {1,2,3,a,b,c}$ y $E = { {1,a}, {2,a}, {1,b}, {2,b}, {3,c} },$ entonces $E$ está equilibrado, con la correspondencia fraccionaria perfecta ${1/2, 1/2, 1/2, 1/2, 1}.$

Existen varias condiciones suficientes para la existencia de un emparejamiento perfecto en un hipergrafo:

Teoremas de tipo Hall para hipergrafos : presenta condiciones suficientes análogas al teorema del matrimonio de Hall, basado en conjuntos de vecinos.
Coincidencia perfecta en hipergrafos de alto grado : presenta condiciones suficientes análogas al teorema de Dirac sobre ciclos hamiltonianos , basado en el grado de los vértices.
Keevash y Mycroft desarrollaron una teoría geométrica para la correspondencia de hipergrafos. ^[7]

Familia de conjuntos equilibrados

Una familia de conjuntos $E$ sobre un conjunto base $V$ se denomina equilibrada (con respecto a $V$ ) si el hipergrafo $H = (V, E)$ admite una correspondencia fraccionaria perfecta. ^[6] ^{: sec.2}

Por ejemplo, considere el conjunto de vértices $V = {1,2,3,a,b,c}$ y el conjunto de aristas $E = {1-a, 2-a, 1-b, 2-b, 3-c}.$ $E$ está equilibrado, ya que existe una correspondencia fraccionaria perfecta con pesos ${1/2, 1/2, 1/2, 1/2, 1}.$

Calcular una coincidencia máxima

El problema de encontrar una correspondencia de máxima cardinalidad en un hipergrafo, y por lo tanto calcular , es NP-difícil incluso para hipergrafos 3-uniformes (ver correspondencia tridimensional ). Esto contrasta con el caso de los grafos simples (2-uniformes) en los que el cálculo de una correspondencia de máxima cardinalidad se puede realizar en tiempo polinomial. $\nu (H)$

Combinación y cobertura

Una cobertura de vértices en un hipergrafo $H = (V, E)$ es un subconjunto $T$ de $V$ , tal que cada hiperarista en $E$ contiene al menos un vértice de $T$ (también se denomina transversal o conjunto de impacto , y es equivalente a una cobertura de conjuntos ). Es una generalización de la noción de cobertura de vértices en un grafo.

El número de cobertura de vértice de un hipergrafo $H$ es el tamaño más pequeño de una cobertura de vértice en $H$ . A menudo se denota por $τ (H)$ , ^[1]^{: 466} para transversal.

Una cobertura de vértices fraccionaria es una función que asigna un peso a cada vértice en $V$ , de modo que para cada hiperarista $e$ en $E$ , la suma de las fracciones de vértices en $e$ es al menos 1. Una cobertura de vértices es un caso especial de una cobertura de vértices fraccionaria en el que todos los pesos son 0 o 1. El tamaño de una cobertura de vértices fraccionaria es la suma de las fracciones de todos los vértices.

El número de cobertura de vértices fraccionarios de un hipergrafo $H$ es el tamaño más pequeño de una cobertura de vértices fraccionarios en $H$ . A menudo se denota por $τ *(H)$ .

Dado que una cobertura de vértices es un caso especial de una cobertura de vértices fraccionaria, para cada hipergrafo $H$ :

número de cobertura de vértice fraccional ( $H$ ) ≤ número de cobertura de vértice ( $H$ ).

La dualidad de programación lineal implica que, para cada hipergrafo $H$ :

número-coincidente-fraccional ( $H$ ) = número-de-cobertura-de-vértice-fraccional ( $H$ ).

Por lo tanto, para cada hipergrafo $H$ : ^[4]

\nu (H)\leq \nu ^{*}(H)=\tau ^{*}(H)\leq \tau (H)

Si el tamaño de cada hiperarista en $H$ es como máximo $r$ , entonces la unión de todas las hiperaristas en una correspondencia máxima es una cobertura de vértices (si hubiera una hiperarista descubierta, podríamos haberla agregado a la correspondencia). Por lo tanto:

\tau(H)\leq r\cdot \nu(H).

Esta desigualdad es estricta: la igualdad se cumple, por ejemplo, cuando $V$ contiene $r \cdot ν (H) + r - 1$ vértices y $E$ contiene todos los subconjuntos de $r$ vértices.

Sin embargo, en general $τ *(H) < r \cdot ν (H)$ , ya que $ν *(H) < r \cdot ν (H)$ ; ver correspondencia fraccional más arriba.

La conjetura de Ryser dice que, en cada $hipergrafo r$ -partito $y r$ -uniforme:

\tau (H)\leq (r-1)\nu (H).

Se han demostrado algunos casos especiales de la conjetura; véase la conjetura de Ryser .

La propiedad del rey

Un hipergrafo tiene la propiedad de Kőnig si su número máximo de coincidencias es igual a su número mínimo de cobertura de vértices, es decir, si $ν (H) = τ (H)$ . El teorema de Kőnig-Egerváry muestra que todo grafo bipartito tiene la propiedad de Kőnig. Para extender este teorema a los hipergrafos, necesitamos extender la noción de bipartididad a los hipergrafos. ^[1]^{: 468}

Una generalización natural es la siguiente. Un hipergrafo se llama 2-coloreable si sus vértices pueden ser 2-coloreados de modo que cada hiperarista (de tamaño al menos 2) contenga al menos un vértice de cada color. Un término alternativo es Propiedad B . Un grafo simple es bipartito si es 2-coloreable. Sin embargo, hay hipergrafos 2-coloreables sin la propiedad de König. Por ejemplo, considere el hipergrafo con $V = {1,2,3,4}$ con todos los tripletes $E = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }.$ Es 2-coloreable, por ejemplo, podemos colorear ${1,2}$ de azul y ${3,4}$ de blanco. Sin embargo, su número coincidente es 1 y su número de cobertura de vértices es 2.

Una generalización más fuerte es la siguiente. Dado un hipergrafo $H = (V, E)$ y un subconjunto $V'$ de $V$ , la restricción de $H$ a $V'$ es el hipergrafo cuyos vértices son $V$ , y para cada hiperarista $e$ en $E$ que interseca a $V'$ , tiene una hiperarista $e'$ que es la intersección de $e$ y $V'$ . Un hipergrafo se llama equilibrado si todas sus restricciones son esencialmente 2-coloreables , lo que significa que ignoramos las hiperaristas singleton en la restricción. ^[8] Un grafo simple es bipartito si y solo si está equilibrado.

Un grafo simple es bipartito si y solo si no tiene ciclos de longitud impar. De manera similar, un hipergrafo está balanceado si y solo si no tiene circuitos de longitud impar . Un circuito de longitud $k$ en un hipergrafo es una secuencia alternada $(v 1, e 1, v 2, e 2, \dots, v k, e k, v k +1 = v 1)$ , donde las $v i$ son vértices distintos y las $e i$ son hiperaristas distintas, y cada hiperarista contiene el vértice a su izquierda y el vértice a su derecha. El circuito se llama desbalanceado si cada hiperarista no contiene otros vértices en el circuito. Claude Berge demostró que un hipergrafo está balanceado si y solo si no contiene un circuito desbalanceado de longitud impar. Todo hipergrafo balanceado tiene la propiedad de König. ^[9]^[1]^{: 468–470}

Los siguientes son equivalentes: ^[1]^{: 470–471}

Cada hipergrafo parcial de $H$ (es decir, un hipergrafo derivado de $H$ eliminando algunas hiperaristas) tiene la propiedad de Kőnig.
Cada hipergrafo parcial de $H$ tiene la propiedad de que su grado máximo es igual a su número mínimo de coloración de aristas .
$H$ tiene la propiedad de Helly , y el gráfico de intersección de $H$ (el gráfico simple en el que los vértices son $E$ y dos elementos de $E$ están vinculados si y sólo si se intersecan) es un gráfico perfecto .

Combinación y embalaje

El problema del empaquetamiento de conjuntos es equivalente al de la correspondencia de hipergrafos.

Un empaquetamiento de vértices en un gráfico (simple) es un subconjunto $P$ de sus vértices, tal que no hay dos vértices en $P$ adyacentes.

El problema de encontrar un empaquetamiento máximo de vértices en un gráfico es equivalente al problema de encontrar una correspondencia máxima en un hipergráfico: ^[1]^{: 467}

Dado un hipergrafo $H = (V, E)$ , defina su grafo de intersección $Int(H)$ como el grafo simple cuyos vértices son $E$ y cuyas aristas son pares $(e 1, e 2)$ tales que $e 1$ , $e 2$ tienen un vértice en común. Entonces, cada coincidencia en $H$ es un empaquetamiento de vértices en $Int(H)$ y viceversa.
Dado un grafo $G = (V', E')$ , defina su hipergrafo estrella $St(G)$ como el hipergrafo cuyos vértices son $E'$ y cuyas hiperaristas son las estrellas de los vértices de $G$ (es decir, para cada vértice $v'$ en $V'$ , hay una hiperarista en $St(G)$ que contiene todas las aristas en $E'$ que son adyacentes a $v'$ ). Entonces, cada empaquetamiento de vértices en $G$ es una correspondencia en $St(G)$ y viceversa.
Alternativamente, dado un grafo $G = (V', E')$ , defina su hipergrafo de clique $Cl(G)$ como el hipergrafo cuyos vértices son los cliques de $G$ , y para cada vértice $v'$ en $V'$ , hay una hiperarista en $Cl(G)$ que contiene todos los cliques en $G$ que contienen $a v'$ . Entonces nuevamente, cada empaquetamiento de vértices en $G$ es una coincidencia en $Cl(G)$ y viceversa. Nótese que $Cl(G)$ no puede construirse a partir de $G$ en tiempo polinomial , por lo que no puede usarse como una reducción para probar NP-dureza. Pero tiene algunos usos teóricos.

Véase también

Coincidencia tridimensional : un caso especial de coincidencia de hipergrafos con hipergrafos tridimensionales uniformes.
Cobertura de vértices en hipergrafos
Hipergrafo bipartito
Coincidencia de arcoíris en hipergrafos
Hipergrafo de intervalo D : un hipergrafo infinito en el que existe alguna relación entre el número coincidente y el número de cobertura.
Teorema de Erdős–Ko–Rado sobre aristas no disjuntas por pares en hipergrafos

Referencias

^ abcdefg Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr. 0859549
^ Berge, Claude (1973). Gráficos e hipergráficos . Ámsterdam: Holanda Septentrional.
^ ab Aharoni, Ron; Kessler, Ofra (15 de octubre de 1990). "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.
^ abcd Füredi, Zoltán (1981-06-01). "Correspondencias de grado máximo y fraccionarias en hipergrafos uniformes". Combinatorica . 1 (2): 155–162. doi :10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.
^ Lovász, L. (1974). "Teoremas de minimax para hipergrafos". En Berge, Claude; Ray-Chaudhuri, Dijen (eds.). Hypergraph Seminar . Lecture Notes in Mathematics. Vol. 411. Berlín, Heidelberg: Springer. págs. 111–126. doi :10.1007/BFb0066186. ISBN 978-3-540-37803-7.
^ ab Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "División justa con múltiples piezas". Matemáticas Aplicadas Discretas . 283 : 115–122. arXiv : 1710.09477 . doi :10.1016/j.dam.2019.12.018. ISSN 0166-218X. S2CID 119602376.
^ Keevash, Peter; Mycroft, Richard (1 de enero de 2015). Una teoría geométrica para la correspondencia de hipergrafos. Memorias de la American Mathematical Society. Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4.
^ Berge, CLAUDE (1 de enero de 1973), Srivastava, JAGDISH N. (ed.), "CAPÍTULO 2 – Hipergrafos equilibrados y algunas aplicaciones a la teoría de grafos", A Survey of Combinatorial Theory , North-Holland, págs. 15-23, ISBN 978-0-7204-2262-7, consultado el 19 de junio de 2020
^ Berge, Claude; Vergnas, Michel LAS (1970). "Sobre un teorema del tipo rey para hipergrafías". Anales de la Academia de Ciencias de Nueva York . 175 (1): 32–40. Bibcode :1970NYASA.175...32B. doi :10.1111/j.1749-6632.1970.tb56451.x. ISSN 1749-6632. S2CID 84670737.

[lp-1] Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr. 0859549

[2] Berge, Claude (1973). Gráficos e hipergráficos . Ámsterdam: Holanda Septentrional.

[:1-3] Aharoni, Ron; Kessler, Ofra (15 de octubre de 1990). "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-4] Füredi, Zoltán (1981-06-01). "Correspondencias de grado máximo y fraccionarias en hipergrafos uniformes". Combinatorica . 1 (2): 155–162. doi :10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.

[5] Lovász, L. (1974). "Teoremas de minimax para hipergrafos". En Berge, Claude; Ray-Chaudhuri, Dijen (eds.). Hypergraph Seminar . Lecture Notes in Mathematics. Vol. 411. Berlín, Heidelberg: Springer. págs. 111–126. doi :10.1007/BFb0066186. ISBN 978-3-540-37803-7.

[:0-6] Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "División justa con múltiples piezas". Matemáticas Aplicadas Discretas . 283 : 115–122. arXiv : 1710.09477 . doi :10.1016/j.dam.2019.12.018. ISSN 0166-218X. S2CID 119602376.

[7] Keevash, Peter; Mycroft, Richard (1 de enero de 2015). Una teoría geométrica para la correspondencia de hipergrafos. Memorias de la American Mathematical Society. Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4.

[8] Berge, CLAUDE (1 de enero de 1973), Srivastava, JAGDISH N. (ed.), "CAPÍTULO 2 – Hipergrafos equilibrados y algunas aplicaciones a la teoría de grafos", A Survey of Combinatorial Theory , North-Holland, págs. 15-23, ISBN 978-0-7204-2262-7, consultado el 19 de junio de 2020

[9] Berge, Claude; Vergnas, Michel LAS (1970). "Sobre un teorema del tipo rey para hipergrafías". Anales de la Academia de Ciencias de Nueva York . 175 (1): 32–40. Bibcode :1970NYASA.175...32B. doi :10.1111/j.1749-6632.1970.tb56451.x. ISSN 1749-6632. S2CID 84670737.