¿Cuándo un gráfico subyace al diagrama de Hasse de un poset?

Question

Para cualquier poset finito $P=(X,\leq)$ hay un gráfico $G$ subyacente a su diagrama de Hasse $H=(X,\lessdot)$ para que $V(G)=X$ y $E(G)=\{\{u,v\}:u\lessdot v\}$ . Dicho esto, ¿es posible caracterizar todos estos grafos? Es decir, ¿los gráficos que subyacen en el diagrama de Hasse de algún poset finito?

Es fácil ver cualquier dígrafo $D$ es un diagrama de Hasse de un subconjunto finito si cada camino dirigido en $D$ es un camino inducido en $D$ Por lo tanto, estoy tratando de describir los gráficos que tienen una orientación con esta propiedad.

Está claro que todos deben ser libres de triángulos, ya que cualquier orientación de un triángulo dará lugar a un ciclo que no es acíclico o a un arco entre dos vértices y un camino de longitud dos entre esos vértices que no se reduce transitivamente. Además, es fácil ver que cualquier grafo bipartito entra en esta clase, ya que si los vértices de un grafo arbitrario $G$ puede dividirse en dos conjuntos independientes $X$ y $Y$ entonces si definimos $R=\bigcup_{e\in E(G)}(e\cap X)\times (e\cap Y)$ vemos $P=(X\cup Y,R)$ es un poset con una altura de dos y que $G$ subyace en el diagrama de Hasse de $P$ . De hecho, si para cualquier poset $P$ dejamos que $h(P)$ denotan la altura de $P$ entonces siempre que un gráfico $G$ subyace en el diagrama de Hasse de $P$ debemos tener eso $\chi(G)\leq h(P)+1$ como consecuencia de la Teorema de Gallai-Hasse-Roy-Vitaver Sin embargo, a pesar de que esta clase de grafos es cerrada bajo subdivisiones de aristas, los grafos de esta clase no son cerrados bajo contracciones de aristas, lo que descarta el uso del teorema del menor de los grafos. Sin embargo, debido a que esta clase de grafos es cerrada bajo la eliminación de aristas y vértices (ya que la eliminación de arcos del diagrama de Hasse de cualquier conjunto de posiciones finito produce otro diagrama de Hasse que es un subconjunto de su padre) sabemos que hay una única familia mínima de inclusión de subgrafos prohibidos $F$ (único hasta los isomorfismos de los grafos en $F$ ) que caracteriza completamente todos los grafos que pueden ser orientados para formar el diagrama de Hasse de un poset finito, es decir $F$ es tal que un gráfico $G$ no contiene un subgrafo isomorfo a un gráfico en $F$ si y sólo si $G$ tiene una orientación que es un diagrama de Hasse de un poseto finito. Por lo tanto, para caracterizar los grafos subyacentes a cualquier diagrama de Hasse finito, basta con caracterizar únicamente la familia de subgrafos prohibidos $F$ . Además, se puede demostrar que si llamamos a cualquier dígrafo un pseudociclo cuando es un ciclo dirigido o si se puede formar volteando un arco en un ciclo dirigido, entonces como el cierre transitivo de cualquier relación que contenga un camino $(v_0,v_1,\ldots v_n)$ debe tener el arco $(v_0,v_n)$ esto significa que ningún dígrafo reducido transitivamente tiene el pseudociclo formado por todos los arcos de ese camino y $(v_0,v_n)$ Asimismo, todos los dígrafos que son diagramas de Hasse deben ser acíclicos, por lo que vemos $G\in F$ si tenemos:

$$(1)\text{ Every orientation of }G\text{ contains at least one pseudocycle}$$ $$(2)\text{ Every proper subgraph of $ G $ has an orientation containing no pseudocycles}$$

De hecho, todos los gráficos $G\in F$ es a la vez $2$ -vértice conectado y satisface $\chi(G)\geq \text{girth}(G)$ porque si los gráficos $A$ y $B$ subyacen a los diagramas de Hasse de los posets finitos y satisfacen $\small |V(A)\cap V(B)|\leq 1$ entonces su unión $A\cup B$ debe además subyacer a un diagrama de Hasse de un poset finito, igualmente por la primera propiedad anterior si $G\in F$ entonces sabemos que cada orientación de $G$ debe contener un dígrafo de pseudociclo $D$ mientras que el gráfico subyacente de $D$ es un gráfico de ciclo en $G$ con $|V(D)|$ bordes, vemos $\small |V(D)|\geq\text{grth}(R)$ pero por definición el pseudociclo $D$ debe contener un camino dirigido de longitud $\small |V(D)|-1$ o, de forma equivalente, un camino dirigido con $\small |V(D)|$ vértices, lo que significa $D$ contiene un camino dirigido con $\text{grth}(G)$ vértices, demostrando así cada orientación de $G$ contiene un camino dirigido con $\text{grth}(G)$ vértices, por lo que vemos como corolario del teorema de Gallai-Hasse-Roy-Vitaver, que obtenemos $\chi(G)\geq\text{grth}(G)$ según sea necesario. Aunque estas pocas propiedades por sí solas no proporcionan ni de lejos suficiente información sobre los gráficos en $F$ para dar algún tipo de caracterización general de ellos. Entonces, ¿qué tipo de información se ha demostrado sobre los gráficos en $F$ ? Sé que los dos gráficos más pequeños de $F$ por orden son el gráfico de triángulos y el de Grötzsch, pero ¿cuáles son otros? ¿Hay otros? Me imagino que sí, de hecho si tuviera que adivinar diría $|F|=\aleph_0$ ya que si $F$ era finito, entonces dejemos que $m=\max(\text{cir}(G):G\in F)$ sea la circunferencia máxima de cualquier gráfico en $F$ entonces esto significa que cada gráfico $G$ con $\text{grth}(G)>m$ debe subyacer a un diagrama de Hasse de un poset finito, ya que si un gráfico $G$ tiene una circunferencia mayor que $m$ sabemos que por definición ningún gráfico en $F$ puede ser isomorfo a un subgrafo de $G$ ya que, de lo contrario, contendría un ciclo cuya longitud sería $m$ o menor contradiciendo la suposición $G$ tenía una circunferencia mayor que $m$ . Sin embargo, esto parece una propiedad demasiado "bonita"... Así que para reiterar cómo puede este conjunto de subgrafos prohibidos $F$ caracterizar todos los grafos subyacentes a los diagramas de Hasse finitos, se exprese de forma más sencilla que ésta? ¿Puede alguien enumerar algunos otros gráficos en $F$ para mí, aparte del triángulo o el gráfico de Grötzsch?

Answer 1

Se ha demostrado que este problema es NP-completo en https://link.springer.com/article/10.1007/BF00340774 Pero se descubrió un error y se corrigió posteriormente; para una prueba sencilla y una breve historia, véase https://link.springer.com/article/10.1007%2FBF01108825 .

Yo mismo pregunté lo mismo a principios de este año a algunas personas que trabajan en este campo, los enlaces anteriores me los dio Piotr Micek. También se pueden leer algunos artículos en https://arxiv.org/pdf/1908.08250.pdf en la página 2, antes del Teorema 1. Véase también https://link.springer.com/article/10.1007/BF00400288 .

Answer 2

Este artículo, "Weakly transitive orientations, Hasse diagrams and string graphs "de Middendorf y Pfeiffer, da algún tipo de caracterización de los diagramas de Hasse, pero no me queda claro de inmediato su utilidad: https://www.sciencedirect.com/science/article/pii/0012365X9390176T

Answer 3

Esto no es una respuesta, sino un poco de contexto.

Una noción algo relacionada es la de gráficos de comparabilidad : son los gráficos para los que existe un poset $P$ en el conjunto de vértices tal que $\{x,y\}$ es un borde $\Leftrightarrow$ $x$ y $y$ son comparables en $P$ . Una caracterización del subgrafo prohibido fue dada por Gallai en 1967. Véase la Artículo de Wikipedia .

Puede encontrar la lista de gráficos prohibidos en estas diapositivas en la página de Tom Trotter. Creo que en un momento dado también tenía algunos apuntes del curso publicados sobre ello; también está en su libro sobre la teoría de las dimensiones de los posets. Ver también este puesto en CSTheory stackexchange.