Coincidencia en hipergrafías

Conjunto de hiperbordes donde cada par es disjunto

En teoría de grafos , una coincidencia en un hipergrafo es un conjunto de hiperbordes , en el que cada dos hiperbordes son disjuntos . Es una extensión de la noción de coincidencia en un gráfico . ^{[1] : 466–470  [2]}

Definición

Recuerde 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 hiperborde 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 coincidente 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}. Considere un hipergrafo de 3 uniformes en V (un hipergrafo en el que cada hiperborde contiene exactamente 3 vértices). Sea H un hipergrafo de 3 uniformes con 4 hiperfilos:

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

Entonces H admite varias coincidencias 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 hiperbordes, al menos dos de ellos se cruzan, por lo que no hay coincidencia de tamaño 3. Por lo tanto, el número coincidente de H es 2.

Hipergrafo que se cruza

Un hipergrafo H = ( V , E ) se llama intersección si cada dos hiperflecos en E tienen un vértice en común. Un hipergrafo H se cruza si y solo si no coincide con dos o más hiperbordes, si y solo si ν( H ) = 1 . ^[4]

Coincidencia en un gráfico como caso especial

Un gráfico sin bucles propios es simplemente un hipergráfico de 2 uniformes: cada arista puede considerarse como un conjunto de los dos vértices que conecta. Por ejemplo, este hipergráfico de 2 uniformes representa un gráfico 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 gráfico es un conjunto M de aristas, de modo que cada dos aristas en M tienen una intersección vacía. Esto equivale a decir que no hay dos aristas en M que sean adyacentes al mismo vértice; ésta es exactamente la definición de coincidencia en un gráfico .

Emparejamiento fraccional

Una coincidencia fraccionaria en un hipergrafo es una función que asigna una fracción en [0,1] a cada hiperborde, de modo que para cada vértice v en V , la suma de fracciones de hiperbordes que contienen v es como máximo 1. Una coincidencia es una combinación especial caso 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 todos los hiperbordes.

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 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 coincidente fraccionario puede ser mayor que el número coincidente. Un teorema de Zoltán Füredi ^[4] proporciona límites superiores a la relación de números coincidentes fraccionarios ( H ) / números coincidentes ( 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 marcada: Sea H _r el plano proyectivo finito uniforme r . Entonces ν ( H _r ) = 1 ya que cada dos hiperbordes se cruzan, y ν *( H _r ) = r – 1 +1/rpor el emparejamiento fraccionario que asigna un peso de1/ra cada hiperborde (es una coincidencia ya que cada vértice está contenido en r hiperbordes y su tamaño es r – 1 +1/rya que hay r ² – r + 1 hiperbordes). Por lo tanto la relación es exactamente r – 1 +1/r.
• Si r es tal que el plano proyectivo finito uniforme r 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 se dividen en r partes y cada hiperborde contiene un vértice de cada parte), entonces:

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

En particular, en un gráfico bipartito, ν *( H ) = ν ( H ) . Así lo demostró András Gyárfás . ^[4]

• • La desigualdad es marcada: Sea H _r- el plano proyectivo truncado de orden r – 1 . Entonces ν ( H _{r -} ) = 1 ya que cada dos hiperbordes se cruzan, y ν *( H _{r -} ) = r – 1 por el emparejamiento fraccionario que asigna un peso de1/ra cada hiperborde (hay r ² – r hiperbordes).

Combinación perfecta

Una coincidencia M se llama perfecta si cada vértice v en V está contenido exactamente en un hiperborde de M. Ésta es la extensión natural de la noción de coincidencia perfecta en un gráfico.

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

Considere un hipergrafo H en el que cada hiperarista contiene como máximo n vértices. Si H admite una coincidencia fraccionaria perfecta, entonces su número de coincidencia fraccionaria es al menos | V | ⁄ norte . Si cada hiperarista en H contiene exactamente n vértices, entonces su número coincidente fraccionario está exactamente en | V | ⁄ norte . ^{[6] : sec.2} Esta es una generalización del hecho de que, en un gráfico, el tamaño de una coincidencia perfecta 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 coincidencia 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á balanceado, con la coincidencia fraccionaria perfecta { 1/2, 1/2, 1/2, 1/2, 1 }.

Existen varias condiciones suficientes para la existencia de una coincidencia perfecta 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 los ciclos hamiltonianos , basado en el grado de los vértices.
• Keevash y Mycroft desarrollaron una teoría geométrica para la coincidencia de hipergrafos. ^[7]

Familia de conjuntos equilibrada

Una familia de conjuntos E sobre un conjunto básico V se llama equilibrado (con respecto a V ) si el hipergrafo H = ( V , E ) admite una coincidencia fraccionaria perfecta. ^{[6] : sección 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 coincidencia fraccionaria perfecta con pesos {1/2, 1/2, 1/2, 1/2, 1}.

Calcular una coincidencia máxima

El problema de encontrar una coincidencia de cardinalidad máxima en un hipergráfico, calculando así , es NP-difícil incluso para hipergráficos de 3 uniformes (ver coincidencia tridimensional ). Esto contrasta con el caso de gráficos simples (2 uniformes) en los que el cálculo de una coincidencia de cardinalidad máxima se puede realizar en tiempo polinomial. ${\displaystyle \nu (H)}$

Emparejar y cubrir

Una cubierta de vértice en un hipergrafo H = ( V , E ) es un subconjunto T de V , tal que cada hiperborde en E contiene al menos un vértice de T (también se llama conjunto transversal o de impacto , y es equivalente a un juego de fundas ). Es una generalización de la noción de cobertura de vértices en un gráfico.

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értice 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 fracciones de vértices en e es al menos 1. Una cobertura de vértice es un caso especial de vértice fraccionario cubierta en la que todos los pesos son 0 o 1. El tamaño de una cubierta de vértice fraccionaria es la suma de fracciones de todos los vértices.

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

Dado que una cobertura de vértice es un caso especial de una cobertura de vértice 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 tanto, para cada hipergrafo H : ^[4]

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

Si el tamaño de cada hiperborde en H es como máximo r, entonces la unión de todos los hiperbordes en una coincidencia máxima es una cobertura de vértice (si hubiera un hiperborde descubierto, podríamos haberlo agregado a la coincidencia). Por lo tanto:

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

Esta desigualdad es estrecha: 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 ) ; consulte Coincidencia fraccionaria arriba.

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

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

Se han demostrado algunos casos especiales de la conjetura; ver la conjetura de Ryser .

Propiedad de Kőnig

Un hipergrafo tiene la propiedad de Kőnig si su número máximo coincidente es igual a su número mínimo de cobertura de vértice, 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 bipartición a los hipergrafos. ^{[1] : 468}

Una generalización natural es la siguiente. Un hipergrafo se llama bicolor si sus vértices pueden ser bicolores de modo que cada hiperborde (de tamaño al menos 2) contenga al menos un vértice de cada color. Un término alternativo es Propiedad B . Un gráfico simple es bipartito si tiene 2 colores. Sin embargo, hay hipergráficos de 2 colores 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 bicolor, por ejemplo, podemos colorear {1,2} azul y {3,4} blanco. Sin embargo, su número coincidente es 1 y su número de cobertura de vértice 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 por cada hiperborde e en E que intersecta a V' , tiene un hipergrafo e ' esa es la intersección de e y V' . Un hipergráfico se llama equilibrado si todas sus restricciones son esencialmente de 2 colores , lo que significa que ignoramos los hiperflecos únicos en la restricción. ^[8] Un gráfico simple es bipartito si está equilibrado.

Un gráfico simple es bipartito si no tiene ciclos de longitud impar. De manera similar, un hipergrafo está equilibrado si no tiene circuitos de longitud impar . Un circuito de longitud k en un hipergrafo es una secuencia alterna ( v ₁ , e ₁ , v ₂ , e ₂ ,…, v _k , e _k , v _{k +1} = v ₁ ) , donde los v _i son vértices distintos y los e _i son hiperbordes distintos, y cada hiperborde contiene el vértice a su izquierda y el vértice a su derecha. El circuito se llama desequilibrado si cada hiperborde no contiene otros vértices en el circuito. Claude Berge demostró que un hipergrafo está equilibrado si y sólo si no contiene un circuito de longitud impar desequilibrado. Todo hipergrafo equilibrado 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 algunos hiperfilos) tiene la propiedad de Kőnig.
• Cada hipergrafía parcial de H tiene la propiedad de que su grado máximo es igual a su número mínimo de coloración de borde .
• H tiene la propiedad de Helly , y la gráfica de intersección de H (la gráfica simple en la que los vértices son E y dos elementos de E están unidos si y sólo si se cruzan) es una gráfica perfecta .

Combinación y embalaje

El problema del empaquetado de conjuntos es equivalente a la coincidencia de hipergráficos.

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

El problema de encontrar un empaquetado máximo de vértices en un gráfico es equivalente al problema de encontrar una coincidencia 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 empaquetado 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 cuyos hiperbordes 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 empaquetado de vértices en G es una coincidencia en St( G ) y viceversa.
• Alternativamente, dado un gráfico G = ( V' , E' ) , defina su hipergrafo de camarilla Cl( G ) como el hipergrafo cuyos vértices son los camarillas de G , y para cada vértice v' en V' , hay un hiperborde en Cl ( G ) que contiene todas las camarillas en G que contienen v' . Por otra parte, cada empaquetado de vértices en G es una coincidencia en Cl( G ) y viceversa. Tenga en cuenta que Cl( G ) no se puede construir a partir de G en tiempo polinómico , por lo que no se puede utilizar como reducción para demostrar la dureza NP. Pero tiene algunos usos teóricos.

Ver también

• Coincidencia tridimensional : un caso especial de coincidencia de hipergrafos con hipergrafos de 3 uniformes.
• Cobertura de vértices en hipergrafías.
• Hipergrafo bipartito
• Coincidencia de arcoíris en hipergrafías
• Hipergrafo de intervalo D : un hipergrafo infinito en el que existe alguna relación entre el número coincidente y el que lo cubre.
• 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, señor  0859549
2. Bergé, Claude (1973). Gráficos e Hipergrafos . Ámsterdam: Holanda Septentrional.
3. Aharoni, Ron; Kessler, Ofra (15 de octubre de 1990). "Sobre una posible extensión del teorema de Hall a hipergrafías bipartitas". Matemáticas discretas . 84 (3): 309–313. doi : 10.1016/0012-365X(90)90136-6 . ISSN  0012-365X.
4. Füredi, Zoltán (1 de junio de 1981). "Coincidencias fraccionarias y de grado máximo en hipergrafías uniformes". Combinatoria . 1 (2): 155–162. doi :10.1007/BF02579271. ISSN  1439-6912. S2CID  10530732.
5. Lovász, L. (1974). "Teoremas de minimax para hipergrafos". En Bergé, Claude; Ray-Chaudhuri, Dijen (eds.). Seminario Hipergrafo . Apuntes de conferencias de matemáticas. vol. 411. Berlín, Heidelberg: Springer. págs. 111-126. doi :10.1007/BFb0066186. ISBN 978-3-540-37803-7.
6. Nyman, Kathryn; Su, Francisco Eduardo; Zerbib, Shira (2 de enero de 2020). "División justa con múltiples piezas". Matemática Aplicada Discreta . 283 : 115-122. arXiv : 1710.09477 . doi :10.1016/j.dam.2019.12.018. ISSN  0166-218X. S2CID  119602376.
7. Keevash, Pedro; Mycroft, Richard (1 de enero de 2015). Una teoría geométrica para la coincidencia de hipergrafos. Memorias de la Sociedad Matemática Estadounidense. vol. 233. Sociedad Matemática Estadounidense. 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", Un estudio de la teoría combinatoria , Holanda Septentrional, págs.15– 23, ISBN 978-0-7204-2262-7, recuperado el 19 de junio de 2020
9. Bergé, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Anales de la Academia de Ciencias de Nueva York . 175 (1): 32–40. Código bibliográfico : 1970NYASA.175...32B. doi :10.1111/j.1749-6632.1970.tb56451.x. ISSN  1749-6632. S2CID  84670737.