Acyclic Orientations and Graphic Hyperplane Arrangements

Orientations as Systems of Inequalities

An undirected graph records which pairs of vertices are adjacent, but it does not specify a direction of travel along an edge. One way to choose directions is to assign a real number to each vertex and direct every edge from the endpoint with the smaller number to the endpoint with the larger number. Such directions cannot form a directed cycle: following a directed edge always strictly increases the assigned number. The graphic hyperplane arrangement makes this idea precise and shows that it accounts for every possible acyclic orientation.

Throughout, graphs are finite and simple. A directed graph has directed edges, written \(u\to v\). An orientation of an undirected graph \(G=(V,E)\) is obtained by replacing each edge \(uv\in E\) with exactly one of \(u\to v\) or \(v\to u\). A directed cycle is a cycle whose edges all point in the direction of travel. An orientation is acyclic if it contains no directed cycle.

Only adjacent vertices are required to have different coordinates. Two nonadjacent vertices may have equal coordinates. For a point \(x=(x_v)_{v\in V}\) in the complement, direct each edge from its lower-coordinate endpoint to its higher-coordinate endpoint: \(u\to v\) when \(x_u<x_v\). These inequalities give an orientation of every edge.

Regions and Their Inequalities

Fix an orientation \(O\) of \(G\). The points that induce exactly \(O\) are those satisfying \(x_u<x_v\) for every directed edge \(u\to v\) of \(O\). This set is an intersection of open half-spaces. If it is nonempty, it is convex: for any two points satisfying all the inequalities, every point on the line segment between them satisfies them too. In particular, this set is connected.

Conversely, the orientation cannot change while a point moves continuously within one region. For an edge \(uv\), changing from \(x_u<x_v\) to \(x_v<x_u\) would require passing through a point with \(x_u=x_v\), which is on the removed hyperplane \(H_{uv}\). Thus each region has one fixed edge orientation. The question is which orientations occur. The following result gives the exact answer.

Proof. Suppose instead that every vertex has an incoming edge. Start at any vertex \(v_0\), choose an edge \(v_1\to v_0\), then an edge \(v_2\to v_1\), and continue. Since the graph has finitely many vertices, some vertex must repeat. Take the first repetition in this sequence. The directed edges along the segment between the two occurrences, read in their directed order, form a directed cycle. This contradicts the assumption that the graph has no directed cycle. Therefore at least one vertex has no incoming edge. \(\square\)

Proof. First, every point \(x\) in the complement induces an acyclic orientation. Along each directed edge \(u\to v\), the coordinates strictly increase, since \(x_u<x_v\). If there were a directed cycle \(v_1\to v_2\to\cdots\to v_k\to v_1\), these inequalities would give \(x_{v_1}<x_{v_2}<\cdots<x_{v_k}<x_{v_1}\), which is impossible. Also, as noted above, the orientation is constant throughout a region.

Now let \(O\) be any acyclic orientation of \(G\). We show that there is a point in the complement inducing \(O\). If \(V\) is nonempty, the lemma gives a vertex with no incoming edge. Place such a vertex first in a list, remove it and its incident edges, and repeat on the remaining directed graph. Removing vertices cannot create a directed cycle, so the lemma applies at every stage at which vertices remain. The process gives an ordering \(v_1,\ldots,v_n\). For every directed edge \(v_i\to v_j\), we have \(i<j\): when \(v_i\) was selected, it had no incoming edge from any vertex still present, so no edge could point from a later vertex to \(v_i\). Assign \(x_{v_i}=i\). Then every edge \(v_i\to v_j\) satisfies \(x_{v_i}<x_{v_j}\), so this point lies in the complement and induces \(O\).

It remains to verify the one-to-one assertion. If two points induce the same orientation, they both satisfy the same strict edge inequalities. The set of all points satisfying those inequalities is convex, hence connected, so the two points lie in the same region. If two points lie in the same region, the orientation is constant there, as proved above. Therefore each region induces exactly one acyclic orientation, and each acyclic orientation is induced by a point in exactly one region.

If \(V=\varnothing\), the coordinate space has one point, there are no hyperplanes, and there is one region and one orientation. If \(E=\varnothing\), the complement is all of \(\mathbb{R}^{V}\), which is connected, and the graph has exactly one orientation, the empty choice of edge directions. These cases also satisfy the correspondence. \(\square\)

Worked Examples

How to Use the Correspondence

The theorem converts a geometric question about regions into a graph-theoretic question about directions on edges. To test a proposed orientation for whether it has a corresponding region, write down one strict inequality for each directed edge. If the inequalities can be satisfied, any satisfying point lies in the region for that orientation. If they cannot be satisfied because they force a strict increase all the way back to the starting coordinate, the orientation contains a directed cycle.

This viewpoint also explains why different edge sets give different arrangements in the same coordinate space. A hyperplane is included only for an edge of \(G\). Equality between coordinates of nonadjacent vertices is permitted, so adding inequalities for nonedges would change the arrangement and would answer a different question.

The main pitfall is to assume that every direction choice on the edges must come from some point. In the triangle example, the attempted assignment \(x_1=0\), \(x_2=1\), \(x_3=2\) satisfies \(1\to2\) and \(2\to3\), but it gives \(x_1<x_3\), not \(x_3<x_1\). The correction is to test all edge inequalities together: the directed cycle requires \(x_1<x_2<x_3<x_1\), which is impossible. Only acyclic orientations correspond to regions.