Pictures of graphs

Jeremy Martin

University of Minnesota

March 7,
refreshments at 3:45pm


Let $G=(V,E)$ be a graph. A {\em picture} of $G$ consists of a point for each vertex in $V$ and a line for each edge in $E$, subject to containment conditions given by incidence in $G$. The space of all pictures has some very interesting combinatorial properties. Using elementary techniques, we can show that the polynomial equations constraining the possible slopes of the lines are generating functions for certain kinds of trees in $G$. In the case that $G$ is the complete graph of $K_n$, we can translate the algebraic problem into a combinatorial one using the theory of Stanley-Reisner simplicial complexes (which we will explain). Our results include some unexpected connections between the geometry of pictures of $K_n$ and the combinatorics of matchings and rooted trees.

The talk will be as combinatorial as possible and accessible to graduate students

Speaker's Contact Info: martin(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on February 26, 2003 at 02:22 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.