Coincidencia en hipergrafos

Conjunto de hiperaristas donde cada par es disjunto

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 ₁ y e ₂ 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:

${\displaystyle \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

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

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

${\displaystyle {\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 ² – 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:

${\displaystyle {\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:

${\displaystyle {\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 ² – 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. ${\displaystyle \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]

${\displaystyle \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:

${\displaystyle \tau (H)\leq r\cdot \nu (H).}$

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

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

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

${\displaystyle \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 ₁ , e ₁ , v ₂ , e ₂ , …, v _k , e _k , v _{k +1} = v ₁ ) , 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 ₁ , e ₂ ) tales que e ₁ , e ₂ 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

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.
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.
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.
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.