[CSDM] Discrete math seminar

[Paul Seymour]

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


Date: TODAY, 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 at math.princeton.edu)