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

5more comments