For any finite poset $P=(X,\leq)$ there is a graph $G$ underlying its Hasse diagram $H=(X,\lessdot)$, so that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to characterize all these graphs? That is, those graphs which underlie the Hasse diagram of some finite poset?
It's easy to see any digraph $D$ is a Hasse diagram of a finite poset iff every directed path in $D$ is an induced path in $D$, so I'm trying to describe graphs that have an orientation with this property.
Clearly they must all be triangle free since any orientation of a triangle will result in either a cycle which isn't acyclic or an arc between two vertices and a path of length two between those vertices which isn't transitively reduced.
Moreover its easy to see any bipartite graph will fall into this class since if the vertices in an arbitrary graph $G$ can be partitioned into two independent sets $X$ and $Y$ then if we define $R=\bigcup_{e\in E(G)}(e\cap X)\times (e\cap Y)$ we see $P=(X\cup Y,R)$ is a poset with a height of two and that $G$ underlies the Hasse diagram of $P$. In fact if for any poset $P$ we let $h(P)$ denote the height of $P$ then whenever a graph $G$ underlies the Hasse diagram of $P$ we must have that $\chi(G)\leq h(P)+1$ as a consequence of the Gallai–Hasse–Roy–Vitaver theorem though note despite this class of graphs being closed under edge subdivisions, graphs in this class are not closed under edge contractions which rules out using the graph minor theorem. However because this class of graphs is closed under the removal of edges and vertices (since removing arcs from the Hasse diagram of any finite poset yields another Hasse diagram which is a subposet of its parent) we know there is a unique inclusion minimal family of forbidden subgraphs $F$ (unique up to isomorphisms of the graphs in $F$) which completely characterizes all graphs that can be oriented to form the Hasse diagram of a finite poset i.e. $F$ is such that a graph $G$ does not contain a subgraph isomorphic to a graph in $F$ if and only if $G$ has an orientation which is a Hasse diagram of a finite poset. Thus to characterize graphs underlying any finite Hasse diagram, it suffices to only characterize the forbiden subgraph family $F$. Further one can prove if we call any digraph a pseudocycle when it is either a directed cycle or if it can be formed by flipping one arc in a directed cycle, then since the transitive closure of any relation containing a path $(v_0,v_1,\ldots v_n)$ must have the arc $(v_0,v_n)$ this means no transitively reduced digraph has the pseudocycle consisting of all the arcs in that path and $(v_0,v_n)$ likewise all digraphs which are Hasse diagrams must be acyclic thus we see $G\in F$ iff we have:
$$(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}$$
In fact every graph $G\in F$ is both $2$-vertex connected and satisfies $\chi(G)\geq \text{girth}(G)$, because if graphs $A$ and $B$ underlie Hasse diagrams of finite posets and satisfy $\small |V(A)\cap V(B)|\leq 1$ then their union $A\cup B$ must further underlie a Hasse diagram of a finite poset, likewise by the first property above if $G\in F$ then we know every orientation of $G$ must contain a pseudocycle digraph $D$, while since the underlying graph of $D$ is a cycle graph in $G$ with $|V(D)|$ edges, we see $\small |V(D)|\geq\text{grth}(R)$ yet by definition the pseudocycle $D$ must contain a directed path of length $\small |V(D)|-1$ or equivalently a directed path with $\small |V(D)|$ vertices, which means $D$ contains a directed path with $\text{grth}(G)$ vertices, thus proving every orientation of $G$ contains a directed path with $\text{grth}(G)$ vertices, therefore we see as a corollary of the Gallai–Hasse–Roy–Vitaver theorem, that we get $\chi(G)\geq\text{grth}(G)$ as required. Though these few properties alone still provide no where near enough information on graphs in $F$ to give any kind of general characterization of them. So what sort of information has been proven about the graphs in $F$? I know that the smallest two graphs in $F$ by order are the triangle graph and the Grötzsch graph, but what are some others? Are there others? I would imagine there are, in fact if I had to guess I would say $|F|=\aleph_0$, for if $F$ was finite then let $m=\max(\text{cir}(G):G\in F)$ be the maximum circumference of any graph in $F$ then this means every graph $G$ with $\text{grth}(G)>m$ must underlie a Hasse diagram of a finite poset, since if a graph $G$ has girth greater then $m$ we know that by definition no graph in $F$ can be isomorphic to a subgraph of $G$ as otherwise it would then contain a cycle whose length was $m$ or smaller contradicting the assumption $G$ had girth larger then $m$. Yet this seems like far too "nice" of a property… So to reiterate how can this set of forbiden subgraphs $F$ characterizing all graphs underlying finite Hasse diagrams, be more simply expressed then this? Can someone just list a few other graphs in $F$ for me, apart from either the triangle or Grötzsch graph?
Best Answer
This problem was proved to be NP-complete in https://link.springer.com/article/10.1007/BF00340774, but a mistake was discovered, and later corrected, for a simple proof and brief history, see https://link.springer.com/article/10.1007%2FBF01108825.
I've asked the same question myself earlier this year from some people working in the field, the above links were given to me by Piotr Micek. Some papers to read are also given in https://arxiv.org/pdf/1908.08250.pdf on page 2, before Theorem 1. Also see https://link.springer.com/article/10.1007/BF00400288.