Graph constructions, graph decompositions, and random graphs

Graph constructions, graph decompositions, and random graphs

-
Amanda Redlich , Rutgers University
Fine Hall 224

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.