ABSTRACT OF THE DISSERTATION Graph Varieties by Jeremy Leander Martin Abstract Goes Here We study configuration varieties parametrizing plane pictures P of a given graph G, with vertices v and edges e represented respectively by points P(v) \in P^2 and lines P(e) connecting them in pairs. Three such varieties naturally arise: the picture space X(G) of all pictures of G; the picture variety V(G), an irreducible component of X(G); and the slope variety S(G), essentially the projection of V(G) on coordinates m_e giving the slopes of the lines P(e). In practice, we most often work with affine open subvarieties \tilde{X}(G), \tilde{V}(G), \tilde{S}(G), in which the points P(v) lie in an affine plane and the lines P(e) are nonvertical. We prove that the algebraic dependence matroid of the slopes is in fact the generic rigidity matroid M(G) studied by Laman et. al. [12], [8]. For each set of edges forming a circuit in M(G), we give an explicit determinantal formula for the polynomial relation among the corresponding slopes m_e. This polynomial enumerates decompositions of the given circuit into complementary spanning trees. We prove that precisely these "tree polynomials" cut out V(G) in X(G) set-theoretically. We also show how the full component structure of X(G) can be economically described in terms of the rigidity matroid, and show that when X(G) = V(G), this variety has Cohen-Macaulay singularities. We study intensively the case that G is the complete graph K_n. Describing S(K_n) corresponds to the classical problem of determining all relations among the slopes of the \binom{n}{2} lines connecting n general points in the plane. We prove that the tree polynomials form a Grobner basis for the affine variety \tilde{S}(K_n) (with respect to a particular term order). Moreover, the facets of the associated Stanley-Reisner simplicial complex \Delta(n) can be described explicitly in terms of the combinatorics of decreasing planar trees. Using this description, we prove that \Delta(n) is shellable, implying that S(K_n) is Cohen-Macaulay for all n. Moreover, the Hilbert series of \tilde{S}(K_n) appears to have a combinatorial interpretation in terms of perfect matchings.

Home | Personnel | Programs |Jobs | Computing | Organization | Department | Research