¿Cuáles son las dificultades fundamentales para pasar de gráficos a hipergrafías?

10

Hay muchos ejemplos en combinatoria y ciencias de la computación en los que podemos analizar un problema de teoría de grafos, pero para el análogo de hipergrafía del problema, faltan nuestras herramientas. ¿Por qué crees que los problemas a menudo se vuelven mucho más difíciles con las hipergrafías de 3 uniformes que con las gráficas de 2 uniformes? ¿Cuáles son las dificultades raíz?

Un problema es que, hasta el momento, no tenemos una comprensión satisfactoria de la teoría de la hipergrafía espectral. Por favor, siéntase libre de arrojar más luz sobre este tema. Pero también estoy buscando otras razones que hacen que las hipergrafías sean objetos más difíciles.

arnab
fuente
Me pregunto en qué medida esto está relacionado con la discusión reciente sobre el cambio en la complejidad de los problemas geométricos que van de 2D a 3D ( cstheory.stackexchange.com/questions/5251/… ). La razón por la que digo esto es que puede asociar aristas en un gráfico de 2 uniformes con ubicaciones en una red reticular 2D, mientras que una hipergrafía de 3 uniformes tendría hiperelaciones correspondientes a ubicaciones en una red reticular 3d.
Joe Fitzsimons
@ Joe Fitzsimons: buen punto. Pero los conceptos y técnicas que son naturales en la configuración del (hiper) gráfico, como subgrafos, coloraciones, particiones, etc., pueden no ser tan naturales en la configuración geométrica. Además, estoy de acuerdo con usted en que hay una transición de "dos a tres" en muchas áreas.
arnab
2
Su pregunta es difícil ya que una respuesta satisfactoria resolvería el problema P vs NP. Tenga en cuenta que la coincidencia perfecta es fácil para gráficos de 2 uniformes mientras que es difícil para hipergrafías de 3 uniformes.
Mohammad Al-Turkistany
¿Es la hipergrafía un concepto bien definido? (Por un lado, este corrector ortográfico del sitio no lo sabe :-) ¿Es una relación de aridad fija o variable?
Tegiri Nenashi
Ok, después de visitar Wikipedia, veo que en realidad no es una relación, sino una familia de conjuntos. ¿Las matemáticas convencionales toman en serio este concepto de "hipergrafía"?
Tegiri Nenashi

Respuestas:

8

En esta pregunta entiendo que "dificultad" se refiere no a "difícil de calcular", sino a "difícil de estudiar".

Los problemas de gráficos son más fáciles de estudiar (al menos para mí) ya que algunos conceptos son equivalentes. En otras palabras, si desea generalizar las preguntas de gráficos a las de hipergrafías, debe prestar atención a la generalización "correcta" para que se pueda obtener la consecuencia deseada.

Por ejemplo, considere un árbol. Para los gráficos, un gráfico es un árbol si está conectado y no contiene ningún ciclo. Esto es equivalente a estar conectado y tener n-1 aristas (donde n es el número de vértices), y también equivalente a no contener ningún ciclo y tener n-1 aristas. Sin embargo, para las hipergrafías de 3 uniformes, digamos que una hipergrafía de 3 uniformes es un árbol si está conectada y no contiene ningún ciclo. Pero, esto no es equivalente a estar conectado y tener hiperexage n-1, ni contener ningún ciclo y tener hiperexage n-1.

Escuché que una dificultad principal para probar que el lema de regularidad para las hipergrafías uniformes era encontrar las definiciones correctas de regularidad y conceptos relacionados.

Cuando desee considerar la "teoría de la hipergrafía espectral", puede intentar examinar los tensores o la homología si ve una hipergrafía k uniforme como un complejo simplicial dimensional (k-1), del cual surge naturalmente el álgebra lineal. No sé cuál es la generalización "correcta" para su propósito, o es posible que ninguna sea correcta.

Yoshio Okamoto
fuente
7

Creo que esto se debe en gran parte al "poder místico de la duplicidad" de Lawler (la observación de que muchos problemas parametrizados están en P para param = 2 y NP-completo para param≥3). Un gráfico es una cosa que conecta 2-tuplas de vértices, y una hipergrafía es una cosa que conecta k-tuplas de vértices para k≥3.

Entonces, por ejemplo, 2-SAT está en P, y es esencialmente un problema gráfico, mientras que 3-SAT es un problema en hipergrafías de 3 uniformes y es NP-completo.

David Eppstein
fuente
1
Para ser más preciso, quise preguntar si uno puede identificar algunas razones fundamentales por las cuales las técnicas de teoría de grafos se descomponen. Por ejemplo, realmente no tenemos métodos lineal-algebraicos para hipergrafías porque el rango del tensor no se entiende bien (por ejemplo, es NP-difícil de calcular).
arnab
1
La intención de mi respuesta no fue tanto "estos problemas son difíciles de resolver para las computadoras", sino más bien que existe una fuerte correlación entre P / NPC y tener / no tener buenas caracterizaciones matemáticas. Entonces, los problemas se vuelven más difíciles de estudiar en conjunto con su NPC.
David Eppstein
77
En este contexto, la pregunta cstheory.stackexchange.com/questions/14950/… publicada recientemente es bastante interesante: el reconocimiento de gráficos de líneas de 2 hipergrafías, es decir, gráficos de líneas de (múltiples) gráficos, está en P, mientras que el reconocimiento de gráficos de líneas de Las 3 hipergrafías parecen ser un problema abierto. Tenga en cuenta también que el problema de caracterización para las 3 hipergrafías (por subgrafías inducidas prohibidas) todavía está abierto, mientras que los gráficos de líneas de (múltiples) gráficos admiten varias de tales caracterizaciones.
vb le
5

Otra razón sería que tenemos mucho más conocimiento en relaciones binarias que cualquier otra relación n-aria para n mayor que 2.

Naturalmente, consideramos las relaciones binarias entre objetos, como adyacencia, intersección no vacía, equivalencia, etc. Por lo tanto, podemos definir gráficos en términos de relaciones binarias e incluso definir un gráfico basado en alguna relación binaria en otro gráfico. (Por ejemplo, gráficos de líneas, árboles de camarillas, descomposiciones de árboles ...)

Pero en cuanto a otras relaciones n-arias, no tenemos mucha comprensión. Por ejemplo, lleva algún tiempo encontrar una relación ternaria interesante; (Bien, en parte debido a mi ignorancia) las propiedades son más débiles y las herramientas son mucho menores en el estudio de las relaciones ternarias. (¿Cómo definimos relaciones ternarias simétricas o transitivas ? Ambas están entre las relaciones más importantes que uno puede estudiar).

Pero aún no sé por qué sucede esto entre las relaciones binarias y ternarias. Tal vez, como dijo Turquía, esta pregunta es difícil y puede estar relacionada con la comprensión del problema P / NP.

Hsien-Chih Chang 張顯 之
fuente
[A pesar de las álgebras cilíndricas y poliádicas] no existe un álgebra convincente para las relaciones n-arias. El debate puede incluso reducirse al nivel cuando uno discute la perspectiva posicional frente a la nombrada para relacionar atributos.
Tegiri Nenashi
2

Primero iba a responder la pregunta incorrecta: "qué ejemplo de problemas es mucho más difícil en las hipergrafías que en los gráficos". Me impresionó especialmente la diferencia en el tratamiento del problema de coincidencia máxima en gráficos, y lo mismo con las hipergrafías (un conjunto de bordes separados por pares), que pueden modelar muy fácilmente el color, el conjunto máximo independiente, la camarilla máxima ...

Entonces me di cuenta de que no era tu pregunta: "¿Cuáles son las principales dificultades entre los dos?".

Bueno, a eso respondería que hasta ahora no he visto muchos puntos comunes entre gráficos e hipergrafías. Excepto el nombre en sí. Y el hecho de que mucha gente está tratando de "extender" los resultados del primero al otro.

Tuve la oportunidad de pasar las páginas de "Hypergraphs" de Berge y "Set sets" de Bollobas: contienen muchos resultados sabrosos, y los que encontré más interesantes tenían poco que decir sobre los gráficos. Por ejemplo, el teorema de Baranyai (hay una buena prueba en el libro de Jukna).

No sé mucho de ellos, pero estoy pensando en un problema de hipergrafía en este momento y todo lo que puedo decir al respecto es que no siento ningún gráfico acechando en ningún lado. Quizás los consideremos "difíciles" porque solo estamos tratando de estudiarlos con las herramientas equivocadas. No espero que los problemas gráficos en los que estoy trabajando desaparezcan de inmediato mediante el uso de la teoría de números (aunque a veces sucede).

Ah, y algo mas. Quizás sean más difíciles de estudiar porque son combinatoriamente mucho ... ¿más?

"probarlos todos y ver cuándo funciona" a veces es una buena idea para los gráficos, pero con los hipergráficos uno se humilla rápidamente por los números. :-)

Nathann Cohen
fuente