Non-isomorphic subgraphs in random graphs

2025/05/20 by Michael Krivelevich, Krivelevich, Michael, Maksim Zhukovskii +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2505.14623

openalex publication_date 2025/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We establish the asymptotic behaviour of μ(G(n,p)), the number of unlabelled induced subgraphs in the binomial random graph G(n,p), for almost the entire range of the probability parameter p=p(n)∈[0,1]. In particular, we show that typically the number of subgraphs becomes exponential when p passes 1/n, reaches maximum possible base of exponent (asymptotically) when p≫ 1/n, and reaches the asymptotic value 2ⁿ when p passes 2ln n/n. For p≫ ln n/n, we get the first order term and asymptotics of the second order term of μ(G(n,p)). We also prove that random regular graphs G_n,d typically have μ(G_n,d)≥ 2^{c_d n} for all d≥ 3 and some positive constant c_d such that c_d→ 1 as d→∞.

Citations

• Long induced paths in a configuration model
• The distribution of the maximum number of common neighbors in the random graph
• A new proof of Friedman's second eigenvalue Theorem and its extension to random lifts
• Anatomy of the giant component: The strictly supercritical regime
• A proof of Alon's second eigenvalue conjecture and related problems

Cited by

• A large hole in pseudo-random graphs

Related

• Isomorphisms between dense random graphs
• The probability of nonexistence of a subgraph in a moderately sparse\n random graph
• Large induced matchings in random graphs
• Regular induced subgraphs of a random graph
• Random cliques in random graphs revisited