A Blow-up Construction And Graph Coloring

Paolo Aluffi

Given a graph G (or more generally a matroid embedded in a projective space), we construct a sequence of algebraic varieties whose geometry encodes combinatorial information about G. For example, the chromatic polynomial of G can be computed as an intersection product of certain classes on these varieties, or recovered in terms of the Segre classes of related subschemes of a projective space; other information such as Crapo's invariant also finds a very natural geometric counterpart. The note presents this construction, and gives `geometric' proofs of a number of standard combinatorial results on the chromatic polynomial and Crapo's invariant.