# When can a graph be oriented to form a Hasse diagram of a finite poset?

For any finite poset $$P=(X,\leq)$$ there is an undirected graph $$G$$ underlying the Hasse diagram of $$P$$ such 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?

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 one 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 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) it would still make sense to look for some other type of forbidden subgraph characterization (not necessarily involving minors) of this class. In fact one can prove if we call any digraph a psuedocycle when it is either a directed cycle or if it can be formed by flipping one arc in a directed cycle, then there exists a family of pairwise non-isomorphic graphs $$\mathcal{F}$$ where $$G\in\mathcal{F}$$ iff the following holds:

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

Such that any graph can be oriented to form a Hasse diagram of a finite poset iff it has no subgraph isomorphic to an element in $$\mathcal{F}$$. But how can this class of forbiden subgraphs be further simplified? Now I can prove if $$G$$ is one of these forbiden subgraphs then $$G$$ must be $$2$$-vertex connected and satisfy $$\chi(G)\geq \text{girth}(G)$$ though this alone still hardly narrows down what exactly these forbidden subgraphs look like. Is it possible to simplify the above criteria for these forbiden subgraphs? I know the smallest two by order are the triangle graph and the Grötzsch graph, but what are some others?

• Do you have examples of obstructions other than triangles? I.e. an example of a triangle-free graph that is not orientable into a Hasse diagram? – Yoav Kallus Oct 2 at 12:59
• @YoavKallus The Grötzsch graph – Ethan Oct 2 at 13:02
• I would guess it is not possible to characterize them. – Sam Hopkins Oct 2 at 13:09
• When Richard Stanley proved that the chromatic polynomial evaluated at -1 counts acyclic orientations of a graph, his motivation was in questions like this about the relationship between a Hasse diagram as a graph and its associated partial order. So maybe he would have more to say about this. – Sam Hopkins Oct 2 at 13:47
• @Fedor While the short answer is yes, there's a huge gap between the best upper and lower bounds for an $n$-element poset, like $n^{0.3}$ and $\log n$. Similar gaps for the largest independent set, even for bounded dimensional posets. Apart from the papers in my answer, see also J. Matousek, A. Privetivy: The Minimum Independence Number of a Hasse Diagram, Comb. Probab. Comput. 15, 3, 473-475, 2006. – domotorp Oct 3 at 6:48

## 3 Answers

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.

• How could it be NP complete in light of the comment about the graph minor theorem? – Sam Hopkins Oct 2 at 20:32
• @Sam Which comment? – domotorp Oct 2 at 21:00
• The OP mentioned that the property was hereditary, but I see that that was meant in the induced subgraph sense, not the graph minor sense, so the Robertson–Seymour theorem may not apply. – Sam Hopkins Oct 2 at 21:22

This paper, "Weakly transitive orientations, Hasse diagrams and string graphs " by Middendorf and Pfeiffer, gives some kind of characterization of Hasse diagrams, but it's not immediately clear to me how useful it is: https://www.sciencedirect.com/science/article/pii/0012365X9390176T

This is not an answer, but some context.

A somewhat related notion is that of comparability graphs: these are the graphs for which there is a poset $$P$$ on the vertex set such that $$\{x,y\}$$ is an edge $$\Leftrightarrow$$ $$x$$ and $$y$$ are comparable in $$P$$. A forbidden subgraph characterization was given by Gallai in 1967. See the Wikipedia article.

You can find the list of forbidden graphs in these slides on Tom Trotter's page. I think at one point he also had some course notes posted on it; it's also in his book on dimension theory of posets. See also this post on CSTheory stackexchange.

• These are not comparability graphs. Those refer to the undirected edges of the poset itself not the undirected edges of its Hasse diagram. For the poset $\small P=(X,\leq)$ the comparability graph would be $\small H=(X,\{\{u,v\}:u<v\})$ however I am interested in the graph $\small G=(X,\{\{u,v\}:u\lessdot v\})$. – Ethan Oct 2 at 15:40
• Indeed, comparability graphs are characterizable in a simple way, whereas Hasse diagrams seem much more complicated. – Sam Hopkins Oct 2 at 15:42
• Ok, right. Perhaps one of you wants to edit the post to reflect? (and I'd delete the answer) Or I could edit the answer... It seems like something someone else might get caught by. – Russ Woodroofe Oct 2 at 15:45