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

$$\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, 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, 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.

• Could chordality be a right notion to look at? A chordal graph has a supersolvable arrangement which the BEZ reference says should make the poset of regions a lattice. Also, the chordality determines whether we have a lattice or not in the examples given in the question. But I am not familiar with these posets, and I don't have more time to think right now. Commented Jul 17, 2019 at 17:41
• After a bit more literature search: Stanley, "An introduction to hyperplane arrangements", in the proceedings of the PCMI course on geometric combinatorics, shows that "chordal" is equivalent to "supersovlable" is equivalent to "free". None of these conditions are effected by the ordering. BEZ show that "supersolvable" implies "lattice with respect to some ordering". Commented Jul 17, 2019 at 18:55
• @SamHopkins I don't know, and can't find a reference quickly. Letting $G_1$, $G_2$, ..., $G_r$ be the $2$-connected components of $G$, the $G$-arrangement is the product of the $G_i$ arrangements, so we can reduce to the $2$-connected case. I don't know an example of a $2$-connected graph with simplicial arrangement other than $K_n$. Commented Jul 17, 2019 at 20:25
• @SamHopkins I can now show that the only $2$-connected graph with $A(G)$ simplicial is $K_n$. Step 1: In any simplicial arrangment, the link of any flat is again simplicial. Therefore, if $H$ is an induced subgraph of $G$ and $A(G)$ is simplicial, then $A(H)$ is not simplicial. Step 2: Observe that $A(G)$ is not simplicial if $G$ is an $n$-cycle for $n \geq 3$, and also not if $G$ is a $4$-cycle with a single diagonal. So, let $G$ be a graph which does not have any of the graphs in Step 2 as an induced subgraph (continued) Commented Jul 17, 2019 at 23:01
• @SamHopkins I have recently stumbled across a reference for this result on when $A(G)$ is simplicial -- it appears as Prop 5.2 in Postnikov, Reiner, Williams arxiv.org/abs/math/0609184 . They cite it to a paper of Kim, but I don't have easy access to that right now. Commented Oct 12, 2019 at 0:40

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!

$$\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.