Modular statistics for subgraph counts in sparse random graphs

2014/02/10 by Bobby DeMarco, Jeff Kahn, DeMarco, Bobby +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1402.2264

arxiv created 2015/01/27 · arxiv updated 2015/01/29

Abstract

Answering a question of Kolaitis and Kopparty, we show that, for given integer q>1 and pairwise nonisomorphic connected graphs G₁...G_k, if p=p(n) is such that Pr(G_n,p⊇ G_i)→ 1 ∀ i, then, with ξ_i the number of copies of G_i in G_n,p, (ξ₁...ξ_k) is asymptotically uniformly distributed on \bf Z_q^k.

Related

• The probability of nonexistence of a subgraph in a moderately sparse random graph
• Asymptotic Normality of Subgraph Counts in Sparse Inhomogeneous Random Graphs
• Subgraph distributions in dense random regular graphs
• Modularity and random graphs
• Graph decomposition and parity