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

  • 2
    $\begingroup$ 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. $\endgroup$ Jul 17, 2019 at 17:41
  • 1
    $\begingroup$ 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". $\endgroup$ Jul 17, 2019 at 18:55
  • 1
    $\begingroup$ @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$. $\endgroup$ Jul 17, 2019 at 20:25
  • 3
    $\begingroup$ @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) $\endgroup$ Jul 17, 2019 at 23:01
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 12, 2019 at 0:40

1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .