TOPICS
Search

Graphical Arrangement


Let G be a simple graph on the vertex set [l]={1,...,l}. The graphical arrangement of G is the collection of hyperplanes in R^l given by

 A_G={{x_i-x_j=0}:{i,j} in E(G)}.
(1)

Thus every subarrangement of the braid arrangement is graphical. The complete graph K_l gives the full braid arrangement, while the empty graph gives the empty arrangement.

The arrangement characteristic polynomial equals the chromatic polynomial of the graph,

 chi(A_G,t)=chi(G,t).
(2)

For example, a tree T on l vertices has chi(A_T,t)=t(t-1)^(l-1).

Nian et al. (2026) associate a finite-field arrangement A_G^q with G. Let q be a prime power, let F_q be the finite field of order q, and let K(G) be the collection of nonempty cliques of G. Then

 A_G^q= union _(C in K(G)){{sum_(i in C)a_ix_i=0}:(a_i)_(i in C) in F_q^C\{0}}.
(3)

Coefficient vectors differing by a nonzero scalar define the same hyperplane. For every nonnegative integer k, its characteristic polynomial satisfies

 (chi(A_G^q,q^k))/((q-1)^l)=chi(G,k)  (modq-1).
(4)

Consequently, if q>l^l, the characteristic polynomial of A_G^q determines the chromatic polynomial of G.

An arrangement is called free when its module of logarithmic polynomial vector fields is a free module. The graph G is chordal graph iff both A_G and A_G^q are free arrangements. Suppose (v_1,...,v_l) is a perfect elimination ordering, meaning that the earlier neighbors of each v_i form a clique, and let d_i be the number of those neighbors. Then

 chi(A_G^q,t)=product_(i=1)^l(t-q^(d_i)).
(5)

In particular, for a path graph P_l, this is (t-1)(t-q)^(l-1).


See also

Chordal Graph, Chromatic Polynomial, Clique, Finite Field, Hyperplane

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Nian, T.; Tsujie, S.; Uchiumi, R.; and Yoshinaga, M. "q-Deformation of Chromatic Polynomials and Graphical Arrangements." Electron. J. Combin. 33, P3.63, 2026. https://doi.org/10.37236/14149.Orlik, P. and Terao, H. Arrangements of Hyperplanes. Berlin, Germany: Springer-Verlag, 1992.

Cite this as:

Weisstein, Eric W. "Graphical Arrangement." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphicalArrangement.html

Subject classifications