Proof of Stanley's Acyclic-Orientation Formula

The Identity and Its Ingredients

Stanley’s formula turns an orientation-counting problem into an evaluation of a polynomial. The sign in the formula is determined by the number of vertices, not the number of edges. To prove it, we will connect three facts: the characteristic polynomial of a graphic hyperplane arrangement is the chromatic polynomial; the number of regions satisfies a deletion–restriction recurrence; and each region determines exactly one acyclic orientation.

Throughout, graphs are finite and simple. An orientation chooses a direction for each edge. It is acyclic if it has no directed cycle. For a graph \(G\), write \(a(G)\) for its number of acyclic orientations and \(P_G(q)\) for its chromatic polynomial, which counts proper vertex colorings when \(q\) is a positive integer.

For a finite arrangement \(\mathcal{A}\) in an \(n\)-dimensional real vector space, its characteristic polynomial is \(\chi_{\mathcal{A}}(q)=\sum_{\mathcal{B}\subseteq\mathcal{A}}(-1)^{|\mathcal{B}|}q^{\dim(\bigcap_{H\in\mathcal{B}}H)}\). The intersection for \(\mathcal{B}=\varnothing\) is the whole space, of dimension \(n\). In the graphic arrangement, the hyperplanes indexed by an edge set \(F\) impose equality of coordinates along every edge of \(F\). Coordinates are therefore constant on each component of \((V(G),F)\), so the intersection has dimension equal to the number of those components.

The Graphic Characteristic Polynomial

Proof. Fix a positive integer \(q\), and assign each vertex one of \(q\) colors. For an edge \(uv\), let the bad event be that \(u\) and \(v\) receive the same color. Inclusion–exclusion over the edge events gives the number of assignments avoiding all bad events. For a selected edge set \(F\), requiring equality at the endpoints of every edge in \(F\) forces one color per component of \((V(G),F)\), including its isolated vertices. Thus there are \(q^{c(F)}\) assignments satisfying those requirements, where \(c(F)\) is the number of components. As noted above, \(c(F)\) is also the dimension of the corresponding hyperplane intersection. Inclusion–exclusion therefore gives \(P_G(q)=\sum_{F\subseteq E(G)}(-1)^{|F|}q^{c(F)}=\chi_{\mathcal{A}_G}(q)\). This holds for every positive integer \(q\). Both sides are polynomials, and two polynomials agreeing at infinitely many values are identical. If \(V(G)=\varnothing\), the sum has one term, equal to \(1\), and the same identity holds. \(\square\)

Why Regions Satisfy a Recurrence

For an arrangement \(\mathcal{A}\), let \(r(\mathcal{A})\) be its number of regions. Choose one hyperplane \(H\in\mathcal{A}\). The deletion is \(\mathcal{A}\setminus\{H\}\); the restriction is the arrangement in \(H\) formed by the intersections \(H\cap K\) for \(K\in\mathcal{A}\setminus\{H\}\), with repeated hyperplanes counted only once.

Proof. A region of the deletion is an intersection of open half-spaces, hence is open and convex. If it does not meet \(H\), it remains one region when \(H\) is restored. If it meets \(H\), openness means it has points on both sides of \(H\), and adding \(H\) splits it into two regions. The regions that are split correspond one-to-one to the regions of the restriction: intersect a split deletion region with \(H\) to obtain one restriction region. Conversely, each restriction region lies in a unique deletion region, since it avoids every hyperplane of the deletion. These operations are inverse, so the number of newly created regions is \(r(\mathcal{A}^{H})\). Adding that to the number of deletion regions proves the recurrence. \(\square\)

Apply the lemma to \(\mathcal{A}_G\) and the hyperplane \(H_{uv}\) for an edge \(e=uv\). Deleting this hyperplane gives \(\mathcal{A}_{G-e}\). In the restriction to \(H_{uv}\), the coordinates \(x_u\) and \(x_v\) are identified. Every other edge hyperplane becomes the hyperplane associated with the corresponding edge after \(u\) and \(v\) are identified. If two such edges give the same hyperplane, the duplicate is discarded. This is precisely the graphic arrangement of the simple graph \(G/e\), obtained by contracting \(e\) and replacing any parallel edges by one edge. Therefore \(r(\mathcal{A}_G)=r(\mathcal{A}_{G-e})+r(\mathcal{A}_{G/e})\).

The chromatic polynomial has the matching deletion–contraction identity \(P_G(q)=P_{G-e}(q)-P_{G/e}(q)\). Indeed, a proper coloring of \(G-e\) either gives different colors to \(u,v\), in which case it is a coloring of \(G\), or gives them the same color, in which case it corresponds to a coloring of \(G/e\). Thus \(P_{G-e}(q)=P_G(q)+P_{G/e}(q)\) for positive integer \(q\), and hence as a polynomial.

Regions and Acyclic Orientations

Proof. Take a point \(x=(x_v)_{v\in V(G)}\) outside every hyperplane. For each edge \(uv\), its endpoint coordinates are unequal, so orient the edge from the smaller coordinate to the larger. Along any directed cycle the coordinates would strictly increase at every edge and return to their starting value, which is impossible. The orientation is therefore acyclic. Throughout any one region, each comparison \(x_u<x_v\) or \(x_v<x_u\) has a fixed sign, so the orientation is constant there.

For the converse, let an acyclic orientation be given. Every finite directed acyclic graph has an ordering of its vertices in which every directed edge points forward. To see this, there must be a vertex with no incoming edge: otherwise, repeatedly following an incoming edge would eventually revisit a vertex and produce a directed cycle. Remove such a vertex and repeat on the remaining acyclic digraph. Listing the removed vertices in order gives the required ordering. Assign distinct increasing real coordinates in that order. Every edge then points from its smaller coordinate to its larger coordinate, so the resulting point lies outside the arrangement and induces the given orientation. Finally, the set of points inducing a fixed orientation is described by strict linear inequalities, one for each edge. It is convex and hence connected, so it lies in exactly one region. This proves the bijection. If the graph has no vertices, there is one empty orientation and the complement in the zero-dimensional space has one region, so the statement holds in that case as well. \(\square\)

Stanley’s Formula

Proof. We use induction on the number of edges. For an edgeless graph with \(n\) vertices, there is exactly one orientation, and it is acyclic. Its chromatic polynomial is \(P_G(q)=q^n\), so \((-1)^nP_G(-1)=(-1)^n(-1)^n=1\). This also covers the graph with no vertices, since then \(n=0\) and \(q^0=1\).

Now suppose \(G\) has an edge \(e\), and assume the formula holds for graphs with fewer edges. The region–orientation bijection and the region recurrence give \(a(G)=a(G-e)+a(G/e)\). The contracted graph has fewer edges than \(G\): contracting \(e\) removes \(e\), and any duplicated edges are discarded. Write \(n=|V(G)|\); then \(G-e\) has \(n\) vertices, while \(G/e\) has \(n-1\). By the induction hypothesis and the chromatic deletion–contraction identity, \[ \begin{aligned} a(G) &=(-1)^nP_{G-e}(-1)+(-1)^{n-1}P_{G/e}(-1)\\ &=(-1)^n\bigl(P_{G-e}(-1)-P_{G/e}(-1)\bigr)\\ &=(-1)^nP_G(-1). \end{aligned} \] The second equality uses \((-1)^{n-1}=-(-1)^n\), and the last uses deletion–contraction. This proves the formula. \(\square\)

A Common Sign Error

The exponent in Stanley’s formula is the number of vertices, because the graphic arrangement lives in a space with one coordinate per vertex. It is not the number of edges. For the three-vertex path above, using the edge count \(m=2\) would give \((-1)^mP_G(-1)=(-1)^2(-4)=-4\), which cannot count orientations. The correct exponent is \(n=3\), giving \((-1)^3(-4)=4\). A useful check is that the answer must be a nonnegative integer; the sign correction comes from the vertex count.

The proof also explains why the evaluation at \(-1\) appears: deletion–restriction adds region counts, while chromatic deletion–contraction subtracts polynomial values. Changing the sign when the vertex count drops by one converts that subtraction into the required addition. The geometric bijection then identifies those regions with acyclic orientations.