Skip to main content
1 of 2
David E Speyer
  • 156.4k
  • 14
  • 422
  • 763

$\def\Acyc{\mathrm{Acyc}}$Here are some things I have figured out since asking the question. Thanks to John Machachek 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.

David E Speyer
  • 156.4k
  • 14
  • 422
  • 763