2025/04/01 by Robert Morris, Morris, Robert, Oliver Riordan +1
Computer Science · Mathematics · Physics and Astronomy · #05C65 #05C70 #05C80 #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2504.00964
openalex publication_date 2025/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the distribution of the set of copies of some given graph H in the random graph G(n,p), focusing on the case when H = Kr. Our main results capture the 'leading term' in the difference between this distribution and the 'independent hypergraph model', where (in the case H = Kr) each copy is present independently with probability π= p^\binomr2. As a concrete application, we derive a new upper bound on the number of Kr-factors in G(n,p) above the threshold for such factors to appear. We will prove our main results in a much more general setting, so that they also apply to random hypergraphs, and also (for example) to the case when p is constant and r = r(n) ∼ 2log1/p(n).