DEM 004
Counting Graphs
S. R. Srinivasa Varadhan from New York University's Courant Institute
Let \({H_i}, i=1,2,...,k\) be a finite collection of finite graphs. Let \(v_i\) be the number of vertices in \(H_i\). We want to count the number of graphs G with N vertices in which \(H_i\) appears roughly \(c_i N_i^v\) times. The tools are a combination of large deviations in probability theory and Szemeredi's regularity theorem for dense graphs.