A Blow-up Construction And Graph Coloring<P>

Paolo Aluffi<P>

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.