Gráfico lineal de una hipergrafía

Un gráfico lineal de un hipergráfico  es un gráfico cuyo conjunto de vértices es el conjunto de hiperaristas del hipergráfico y dos hiperaristas son adyacentes si tienen una intersección no vacía. En otras palabras, el gráfico lineal de un hipergráfico es el gráfico de intersección de una familia de conjuntos finitos. El concepto es una generalización de un gráfico lineal de un gráfico ordinario.

Las preguntas sobre gráficos lineales de hipergrafías suelen ser generalizaciones de preguntas sobre gráficos lineales de gráficos ordinarios. Por ejemplo, una hipergrafía cuyos bordes son todos de tamaño k se denomina k-uniforme' (una hipergrafía de 2 uniformes es una gráfica ordinaria). En la teoría de hipergrafías, a menudo es natural requerir k -uniformidad. Cualquier gráfico ordinario es un gráfico lineal de algún hipergráfico, pero si fijamos el tamaño del borde k (el número de puntos en el conjunto que pertenece al borde), no todo gráfico es un gráfico lineal de algún k - gráfico uniforme. La tarea principal es describir gráficos de líneas para cada uno .

Una hipergrafía se llama lineal si cualquier par de hiperaristas tiene como máximo un vértice en la intersección. Cualquier gráfico es un gráfico lineal no solo de algún hipergráfico, sino también de algún hipergráfico lineal [1] .

Gráficos lineales de hipergrafías k -uniformes,

Beinecke [2] describió los gráficos de líneas de gráficos regulares enumerando 9 subgráficos inducidos prohibidos (ver la entrada en gráficos de líneas ). No se conoce ninguna descripción por subgrafos inducidos prohibidos para los gráficos lineales de hipergrafos k-uniformes para cualquier , y Lovas [3] demostró que no existe tal descripción en forma de lista finita para k = 3.

Kraus [4] describió gráficos de líneas de gráficos ordinarios en términos de cobertura de camarilla ( ver gráfico de líneas ). Berge [1] proporciona una descripción global del tipo de Kraus para gráficos lineales de k - hipergrafías uniformes para cualquiera .

Gráficos de línea de hipergrafías de línea uniforme k para

Naik, Rao, Srikhande y Singhi [5] dan una descripción global del tipo de Kraus para gráficos lineales de hipergráficos lineales k uniformes para cualquiera . Al mismo tiempo, encontraron un número finito de subgrafos inducidos prohibidos para hipergrafos lineales de 3 uniformes con un grado de vértice mínimo de al menos 69. Metelsky y Tyshkevich [6] y Jakobson, Kezdi, Lekhel [7] mejoraron este límite a 19 , mientras que Skums, Suzdal y Tyszkiewicz [8] redujeron esto a 16. Metelsky y Tyszkiewicz [6] también probaron que para k > 3 no existe tal lista para hipergrafías uniformes k lineales, sin importar el grado de restricción que se imponga.

La complejidad de encontrar una descripción de hipergrafías uniformes k lineales es que hay infinitas subgrafías generadas prohibidas. Para dar un ejemplo, para m > 0, tome una cadena de m gráficos de diamantes para que los diamantes compartan vértices de segundo orden, y agregue algunos vértices colgantes, como se muestra en la figura, para obtener una de las familias de subgrafos prohibidos mínimos [5 ] [9] .

Hay una serie de descripciones interesantes para los gráficos lineales de hipergrafías k -uniformes lineales dadas por varios autores [10] , sujetas a restricciones sobre el grado mínimo de vértices o el grado mínimo de aristas. El grado de borde mínimo para describir gráficos de líneas de k - hipergrafías de líneas uniformes para cualquier , que no es menor en el trabajo de Naik, Rao, Srikhande y Sighi [5] , se reduce a en los trabajos de Jakobson, Kezdi, Lehel [7 ] y Zverovich [11] .

Se desconoce la complejidad de reconocer gráficos lineales de hipergrafías uniformes k lineales sin restricciones en el grado mínimo (o grado mínimo de bordes). Para k = 3 y un grado mínimo de al menos 19, el reconocimiento es posible en tiempo polinomial [7] [6] ). Skums, Suzdal y Tyszkiewicz [8] redujeron el grado mínimo a 10.

Hay muchos problemas e hipótesis sin resolver en los trabajos de Nike et al., Jacobson et al., Metelsky et al. y Zverovich.

Notas

  1. ↑ 12 Berge , 1989 .
  2. ↑ Beineke, 1968 .
  3. ↑ Lovasz, 1977 .
  4. ↑ Krausz, 1943 .
  5. ↑ 1 2 3 Naik, Rao, Shrikhande, Singhi, 1980 .
  6. ↑ 1 2 3 Metelsky y Tyshkevich, 1997 .
  7. ↑ 1 2 3 Jacobson, Kézdy, Lehel, 1997 .
  8. ↑ 1 2 Skums, Suzdal', Tyshkevich, 2009 .
  9. ↑ Naik, Rao, Shrikhande, Singhi, 1982 .
  10. ↑ Naik, Rao, Shrikhande, Singhi, 1980 ; Naik, Rao, Shrikhande, Singhi 1982 ; Jacobson, Kézdy, Lehel, 1997 ; Metelsky y Tyshkevich, 1997 ; Zverovich, 2004
  11. ↑ Zverovich, 2004 .

Literatura