Pictures of graphsJeremy MartinUniversity of Minnesota
March 7,

ABSTRACT


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 StanleyReisner 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 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

