25
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yoav Kallus Oct 2 '19 at 12:59
  • 3
    $\begingroup$ @YoavKallus The Grötzsch graph $\endgroup$ – Ethan Oct 2 '19 at 13:02
  • 1
    $\begingroup$ I would guess it is not possible to characterize them. $\endgroup$ – Sam Hopkins Oct 2 '19 at 13:09
  • 2
    $\begingroup$ 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. $\endgroup$ – Sam Hopkins Oct 2 '19 at 13:47
  • 1
    $\begingroup$ @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. $\endgroup$ – domotorp Oct 3 '19 at 6:48
19
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How could it be NP complete in light of the comment about the graph minor theorem? $\endgroup$ – Sam Hopkins Oct 2 '19 at 20:32
  • $\begingroup$ @Sam Which comment? $\endgroup$ – domotorp Oct 2 '19 at 21:00
  • 2
    $\begingroup$ 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. $\endgroup$ – Sam Hopkins Oct 2 '19 at 21:22
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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\})$. $\endgroup$ – Ethan Oct 2 '19 at 15:40
  • $\begingroup$ Indeed, comparability graphs are characterizable in a simple way, whereas Hasse diagrams seem much more complicated. $\endgroup$ – Sam Hopkins Oct 2 '19 at 15:42
  • $\begingroup$ 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. $\endgroup$ – Russ Woodroofe Oct 2 '19 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.