$\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](https://arxiv.org/abs/1405.6904)). 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](https://mathscinet.ams.org/mathscinet-getitem?mr=1036875)" and Reading's Chapter 9, "Lattice Theory of the Poset of Regions" in [Lattice Theory: Special Topics and Applications](https://link.springer.com/book/10.1007%2F978-3-319-44236-5) 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.



When is the poset of acyclic orientations of a graph a lattice?
Vincent Pilaud's recent paper ["Acyclic reorientation graphs and their lattice quotients"](https://arxiv.org/abs/2111.12387) 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!


