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.
Respuestas:
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.
fuente
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.
fuente
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.
fuente
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. :-)
fuente