When is the poset of acyclic orientations of a graph a lattice?

Question

$\def\inv{\mathrm{inv}}\def\Acyc{\mathrm{Acyc}}$Let $G$ be a graph whose vertices are numbered $\{ 1,2, \ldots, n \}$. Given an orientation $\omega$ of $G$, define the inversions of $\omega$, written $\inv(\omega)$, to be the set of edges $(i,j)$ with $i<j$, which are oriented $i \leftarrow j$. Define one orientation $\omega_1$ to be $\leq$ another orienation $\omega_2$ iff $\inv(\omega_1) \subseteq \inv(\omega_2)$. Obviously, the set of all orientations of $G$ form a boolean lattice in this way.

Let $\Acyc(G)$ be the set of acyclic orientations of $G$. Restricting the above partial order to $\Acyc(G)$ makes $\Acyc(G)$ into a poset.

What is known about when $\Acyc(G)$ is a lattice?

Some thoughts below:

---

$\bullet$ If $G$ is the complete graph $K_n$, this is the weak order on $S_n$, known to be a lattice.

$\bullet$ We could ask more strongly when the obvious surjection $\Acyc(K_n) \to \Acyc(G)$ is a map of lattices or, in other words, if $\Acyc(G)$ is a quotient of $\Acyc(K_n)$. This can be studied using Nathan Reading's classification of quotients of weak orders (see Reading, Section 4). The answer is that, if $i<j<k$, and $(i,k)$ is an edge of $G$, then $(i,j)$ and $(j,k)$ must also be edges of $G$. However, this strong condition is not necessary to make $\Acyc(G)$ into a lattice. Note that $\Acyc(F)$ will be a lattice for any forest $F$, and a tree with $\geq 3$ edges will not obey the above condition.

$\bullet$ $\Acyc(G)$ is the regions of the graphical hyperplane arrangement coming from $G$, see Björner, Edelman and Ziegler, "Hyperplane arrangements with a lattice of regions" and Reading's Chapter 9, "Lattice Theory of the Poset of Regions" in Lattice Theory: Special Topics and Applications for relevant background. So we can phrase this questions as "when do the regions of a graphical hyperplane arrangement form a lattice"?

$\bullet$ An example of a graph where this does NOT hold is the one with edge set $\{ (1,2), (2,4), (1,3), (3,4) \}$. The elements $1 \to 2 \to 4 \to 3 \leftarrow 1$ and $1 \to 2 \to 4 \leftarrow 3 \to 1$ have no join.

Answer 1

Vincent Pilaud's recent paper "Acyclic reorientation graphs and their lattice quotients" is a thorough answer to this question and every question like it. In particular, here is the answer to the particular question which is asked:

Given a directed acyclic graph $G$, the transitive reduction of $G$ is defined to be the subgraph $G'$ obtained from $G$ by deleting those edges $i \to j$ for which there is a directed path $i \to \cdots \to j$ of length $\geq 2$. The directed acyclic graph $G$ is called vertebrate iff the transitive reduction of every induced subgraph is a forest.

Theorem (Pilaud) $A(G)$ is a lattice iff and only if $G$ is vertebrate.

Pilaud also characterizes when $A(G)$ is distributive, semidistributive, congruence uniform, and many other properties. Check out the paper!

Answer 2

$\def\Acyc{\mathrm{Acyc}}$Here are some things I have figured out since asking the question. Thanks to John Machacek for pointing out that I should look at the literature on supersolvability and chordality. First of all, rather than numbering the vertices of $G$, it is better to start with an acyclic directed graph $\vec{G}$, because we only care about the relative order of the labels on vertices which are joined by edges. So I'll refer to $\Acyc(\vec{G})$ from now on. I'll write $G$ for the underlying undirected graph of $\vec{G}$. I'll write $A(G)$ for the graphical hyperplane arrangement of $G$.

Let $\vec{G}$ be an acyclic digraph. Let $K$ be a clique of $G$. Define $c_K(G)$ to be the graph where we add a vertex $v$ with edges to the vertices of $K$ (and no other neighbors). Let $\sigma_K(\vec{G})$ and $\tau_K(\vec{G})$ be the orientations of $c_K(G)$ which match $\vec{G}$ on the edges of $G$ and make the new vertex $v$ into a source or a target respectively.

There are obvious maps $\Acyc(\sigma_K(\vec{G})) \to \Acyc(G)$ and $\Acyc(\tau_K(\vec{G})) \to \Acyc(G)$. The fibers of this map are total orders.

(1) Adapting the proof of Theorem 4.6 in Bjorner, Edelman and Ziegler shows that, if $\Acyc(\vec{G})$ is a lattice, then $\Acyc(\sigma_K(\vec{G}))$ and $\Acyc(\tau_K(\vec{G}))$ are as well.

In particular, if $\vec{G}$ can be built from the empty digraph by repeatedly applying the $\sigma$ and $\tau$ operators, then $\Acyc(\vec{G})$ is a lattice.

(2) Stanley (lecture 4) shows that the following are equivalent:

• $G$ can be built from the empty graph by repeatedly applying the $c_K$ operators.

• $G$ is chordal, meaning that $G$ does not have a $k$-cycle as induced subgraph for $k \geq 4$.

• $A(G)$ is supersolvable.

(3) If $\Acyc(\vec{G})$ is a lattice, and $\vec{H}$ is an induced diagraph of $\vec{G}$, then $\Acyc(\vec{H})$ is a lattice. Proof: Let $G/H$ be the graph obtained by shrinking $H$ to a point. Choose an acyclic orientation $\omega$ of $G/H$. Let $\omega_-$ be the orientation of $G$ which agree with $\omega$ on the edges not in $H$ and agree with $\vec{G}$ on $H$; let $\omega_+$ be the orientation where we reverse the edges in $H$ and keep the others the same. Then the interval $[\omega_-, \omega_+]$ in $\Acyc(\vec{G})$ is isomorphic to $\Acyc(\vec{H})$. Every interval in a lattice is likewise a lattice.

(4) Let $\vec{G}_1$ and $\vec{G}_2$ be two acyclic digraphs, and let $\vec{G}$ be the graph obtained by gluing $\vec{G}_1$ to $\vec{G}_2$ at a single vertex. Then $\Acyc(\vec{G}) \cong \Acyc(\vec{G}_1) \times \Acyc(\vec{G}_2)$, so $\Acyc(\vec{G})$ is a lattice if and only if $\Acyc(\vec{G}_1)$ and $\Acyc(\vec{G}_2)$ are. So we can reduce to considering $2$-connected graphs.

I still suspect there is a nice answer I am missing.