***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 7th March, 4:30 in Fine Hall 224.
 
Speaker: Amanda Redlich (Rutgers)

Title: Graph constructions, graph decompositions, and random graphs

Abstract: Recent work of Kolaitis and Kopparty relates the number of copies 
of a subgraph in the random graph G(n; p) to questions about logic and 
circuit complexity. Motivated by this relationship, they show that for
certain subgraphs H and values of p, the number of copies of H in G(n; p) 
is uniformly distributed modulo q for any q. This talk extends their result 
to a broader range of subgraphs H. The proof uses the construction of 
"uniquely decomposable" graphs, which are interesting in their own right, 
as well as an analysis of a particular partial ordering on graphs.  
Joint work with Bobby DeMarco and Jeff Kahn.

                       -----------

Next week: Tom Hales (Pittsburg)

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)