2012/11/09 by Bobby DeMarco, Amanda Redlich, DeMarco, Bobby +1
Mathematics · #05C30 #05C76 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #math.CO #msc:05C30 #msc:05C76
paper · pdf · doi:10.48550/arxiv.1211.2243
13 pages
openalex publication_date 2012/11/09 · arxiv created 2015/01/31 · arxiv updated 2015/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Motivated by a recent extension of the zero-one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph G(n,p). We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo q. We determine the asymptotic distribution of all fixed two-component graphs in G(n,p) for all q, and we give infinite families of many-component graphs with a uniform asymptotic distribution for all q. We also prove a negative result, that no simple proof of uniform asymptotic distribution for arbitrary graphs exists.