Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

Non-isomorphic subgraphs in random graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For almost all p, the number of non-isomorphic induced subgraphs of G(n,p) is determined asymptotically, with a sharp threshold at 1/n and full 2^n behavior after 2 ln n/n.

desk verdict Sharp threshold at p=1/n for exponentially many induced subgraphs, with a load-bearing but likely repairable gap in the contiguity extension used for part 5. read the letter →

arxiv 2505.14623 v1 pith:IF76O3RM submitted 2025-05-20 math.CO

Michael Krivelevich , Maksim Zhukovskii This is my paper · ORCID
classification math.CO
keywords randomsubgraphswhenasymptoticgraphsnumberorderpasses
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Random graphs have many subsets of vertices, and each subset induces a smaller graph. The paper counts how many of these induced subgraphs are different up to isomorphism, ignoring the names of the vertices. This number is called μ(G), and it measures how diverse a graph is. For an empty graph or a clique, μ is small, only n+1. For a random graph, the paper shows that μ is tiny (subexponential) when p is below about 1/n, becomes exponential as soon as p exceeds 1/n, and reaches the absolute maximum, essentially 2^n, once p is bigger than about 2 ln n/n. In fact, for p well above ln n/n, they give the precise number: almost every one of the 2^n subsets induces its own isomorphism type, and the rare duplicates are captured by an explicit formula involving the largest common neighbourhoods of pairs of vertices.

The proof combines standard tools of random graph theory with a new ingredient: they estimate how many non-isomorphic rooted subtrees a Galton-Watson tree contains on average. This estimate feeds into a model of the giant component near the critical probability. The authors also prove that random d-regular graphs, for every fixed d≥3, have exponentially many non-isomorphic induced subgraphs.

The main thresholds are sharp: at p around 1/n, the number of subgraphs jumps from subexponential to exponential; at p around 2 ln n/n, it jumps from some exponential base to the full 2^n. The paper leaves open only very narrow windows of p exactly at these transitions. The result improves earlier work by Bonnet, Duron, Sylvester, Zamaraev and the second author, and it answers a natural question left open since Bollobás and Müller's work on graph reconstruction.

Extended reading notes

Core claim

Theorem 1 gives asymptotic formulas for μ(G(n,p)) over almost the whole range of p: for ln n/n ≪ p ≤ 1/2, whp μ(G) = 2^n - 2^{n(1-2p(1-p)) + sqrt(8np(1-p)(1-2p(1-p)) ln n)(1+o(1))} (as clarified by the proof); μ(G) jumps from subexponential to exponential as p crosses 1/n; and for p≥(2+ε)ln n/n it reaches (1-o(1))2^n, while for p≤(2-ε)ln n/n it is o(2^n).

Load-bearing premise

Part 5 of Theorem 1 relies on Claim 7.4, which extends the Ding-Lubetzky-Peres contiguous model from constant np to the case np = λ+o(1) with λ varying. The paper states 'literally the same proof allows to get the following' and cites a local limit theorem, but does not give the full argument. If this extension fails, the sharp linear-in-ε lower bound near p=(1+ε)/n could be invalid, weakening the claimed 1/n threshold.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. This paper studies μ(G), the number of unlabelled induced subgraphs of a graph. For the binomial random graph G(n,p), Theorem 1 gives a near-complete asymptotic description: the authors determine the second-order term of μ(G) for p ≫ ln n / n, prove μ(G) = (1-o(1))2^n above (2+ε) ln n / n and o(2^n) below (2-ε) ln n / n, establish that exponential growth with exponent linear in ε begins once np exceeds 1+ε, and provide matching bounds around 1/n and 1-1/n. Theorems 2-4 give analogous results for random d-regular graphs and show tightness of the linear exponent for bounded-degree graphs. The proofs combine counting of isomorphic induced subgraphs, estimates for common neighbourhoods, Galton-Watson subtree entropy, and the anatomy of the supercritical giant component.

Significance. If the stated results are fully justified, this is a substantial contribution: it sharpens the earlier threshold result from [7] at a large constant to the natural 1/n threshold, gives the first asymptotics of the second-order term for a broad range of p, and extends the picture to random regular graphs. The paper is not curve-fitting; the constants are explicit and the statements are falsifiable. The Galton-Watson subtree-entropy bound in Claim 7.1 is elegant and likely to be useful elsewhere, and the appendix supplies a delicate lower bound for the maximum common-neighbourhood statistic. The main weakness is that one load-bearing contiguity statement, Claim 7.4, is only asserted as a direct extension of a constant-λ result rather than proved.

major comments (3)
  1. [7.2, Claim 7.4 and Section 7.3] Claim 7.4 extends the Ding-Lubetzky-Peres contiguous model from constant np to np = λ+o(1) with λ varying, and this extension is used to transfer the whp event from the model G'' to the actual complex components G' in the proof of part 5 of Theorem 1. The manuscript does not prove this transfer: the sentence 'literally the same proof' followed by a citation to a triangular-array local limit theorem [24] does not supply the required uniform error estimates when λ = λ(n) varies. The cited local limit theorem covers one ingredient, but the full contiguity statement also needs a verification that the exploration process leading to [9, Eq. (5.9)] is uniform in the varying parameter. Because the lower bound μ(G) ≥ 2^{εn/1000} for np ≥ 1+ε depends on this transfer, the sharp 1/n threshold is not established as written; a failure of Claim 7.4 would reduce that part to the weaker constant-C threshold from [7]. I request a full proof of the extension, or a precise statement and reference with explicitly stated uniform bounds.
  2. [7.4, final paragraph] The final sentence of Section 7.4, which handles the case np ≤ 1+o(1), is not correct as written: the property of containing at least 2^{εn} vertices in components of size at least ln ln n is never satisfied in an n-vertex graph, so the monotonicity argument is vacuous. Since the upper bound μ(G) ≤ 2^{3εn} for the critical window depends on this transfer, please replace the sentence with a precise argument, for example a direct bound on the number of isomorphism types of the components, or an explicit monotone event that is known to fail for G(n,(1+ε/2)/n).
  3. [Appendix A, proof of Claim A.1] In the proof of Claim A.1, after the definition of the pruned variable \tilde X, the displayed inequality E[\tilde X] ≥ E[X] − 2n^2 E[\tilde ξ_{x,x'}] is dimensionally wrong and cannot be true, because E[\tilde ξ_{x,x'}] is linear in n. The intended estimate is presumably a bound involving the o(n^{-2}) probabilities computed just above; as written it makes the proof of the lower bound in Claim 3.1, which is needed for Theorem 1(1), formally incorrect. Please correct this displayed line and the surrounding derivation.
minor comments (3)
  1. [Theorem 1(1)] The exponent in the statement is written as α_n + β_n(1-o(1)); since o(1) is two-sided this is formally defensible, but it is easily misread as only a lower bound for the subtracted term. The proof in Section 3 actually gives the subtracted term of the form 2^{α_n + β_n + o(β_n)}, so consider writing α_n + β_n + o(β_n) or α_n + β_n(1+o(1)) to match the upper and lower bounds simultaneously.
  2. [Throughout] The manuscript has no numbered equations or displayed claims, which makes it difficult to refer precisely to intermediate steps; adding equation numbers to the key displays in Sections 3, 7, and Appendix A would improve verifiability.
  3. [7.2, footnote] The footnote to Claim 7.4 acknowledges that the non-constant np case requires a triangular-array local limit theorem; this indicates the authors are aware of the issue, but the main text should state the precise theorem needed rather than relegating this essential qualification to a footnote.
Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fit to data; the paper's constants (ε, C, c1, c2) are auxiliary decisions, not outputs tuned to observations. It relies on several imported theorems, most notably the non-constant-np extension of the contiguous model, which is stated rather than proved.

assumptions (3)
  • domain assumption Contiguous model of the giant component (Ding-Lubetzky-Peres) remains valid when np = λ+o(1) with λ varying in [1+ε, C].
    Used in Section 7.3 to transfer a Galton-Watson subtree estimate to G(n,p); the paper states 'literally the same proof allows' and cites [9,24] but does not reproduce the argument.
  • domain assumption The automorphism group of the 2-core of the union of complex components of supercritical G(n,p) is O_P(1) (Verbitsky-Zhukovskii [26]).
    Used to bound overcounting of isomorphic subgraphs in Section 7.3.
  • domain assumption Whp G_{n,d} contains an induced path of length at least c(d)n (Frieze-Jackson [15]).
    Starting point for the exponential lower bound for random regular graphs in Theorem 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Non-isomorphic subgraphs in random graphs." pith.science (2026). https://pith.science/paper/IF76O3RM

@misc{pith2026250514623,
  author       = {Pith},
  title        = {Pith review of: Non-isomorphic subgraphs in random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IF76O3RM}},
  note         = {Machine review of arXiv:2505.14623}
}
abstract

We establish the asymptotic behaviour of $\mu(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)\in[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\gg 1/n$, and reaches the asymptotic value $2^n$ when $p$ passes $2\ln n/n$. For $p\gg \ln n/n$, we get the first order term and asymptotics of the second order term of $\mu(G(n,p))$. We also prove that random regular graphs $G_{n,d}$ typically have $\mu(G_{n,d})\geq 2^{c_d n}$ for all $d\geq 3$ and some positive constant $c_d$ such that $c_d\to 1$ as $d\to\infty$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A large hole in pseudo-random graphs

    math.CO 2025-05 conditional novelty 8.0 of 10

    Any (n,d,lambda)-graph with lambda/d small contains an induced cycle of length Omega(n/d), and this is tight up to constants.

Reference graph

Works this paper leans on

26 extracted references · 25 canonical work pages · cited by 1 Pith paper

  1. [7]

    Bonnet, J

    É. Bonnet, J. Duron, J. Sylvester, V. Zamaraev, M. Zhukovskii,Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes, SIAM Journal on Computing,53:5 (2024) 1578–1601

    work page 2024

  2. [9]

    J. Ding, E. Lubetzky, Y. Peres,Anatomy of the giant component: the strictly supercritical regime, European Journal of Combinatorics,35(2014) 155–168

    work page 2014

  3. [24]

    Yu. A. Rozanov,On a local limit theorem for lattice distributions, Theory of Probability & Its Applications,2:2 (1957) 260–265

    work page 1957

  4. [1]

    N. Alon, B. Bollobás,Graphs with a small number of distinct induced subgraphs, Discrete Mathematics,75(1989) 23–30. 20

    work page 1989

  5. [2]

    N. Alon, A. Hajnal,Ramsey graphs contain many distinct induced subgraphs, Graphs and Combinatorics,7(1991) 1–6

    work page 1991

  6. [3]

    N. Alon, J. H. Spencer,The Probabilistic method, 4th edition, Wiley Series in Discrete Mathematics and Optimization, 2016

    work page 2016

  7. [4]

    Bollobás,Almost every graph has reconstruction number three, J

    B. Bollobás,Almost every graph has reconstruction number three, J. Graph Theory,14 (1990) 1–4

    work page 1990

  8. [5]

    Bollobás,Random graphs, 2nd edition, Cambridge University Press, 2001

    B. Bollobás,Random graphs, 2nd edition, Cambridge University Press, 2001

    work page 2001

Show all 26 references
  1. [6]

    Bollobas, P

    B. Bollobas, P. Erdős,Cliques in random graphs, Mathematical Proceedings of the Cam- bridge Philosophical Society,80:3 (1976) 419–427

    1976

  2. [8]

    Bordenave,A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts, Annales Scientifiques de l’École Normale Supérieure53:6 (2020) 1393–1439

    C. Bordenave,A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts, Annales Scientifiques de l’École Normale Supérieure53:6 (2020) 1393–1439

    2020

  3. [10]

    Enriquez, G

    N. Enriquez, G. Faraud, L. Ménard, N. Noiry,Long induced paths in a configuration model, arXiv:2106.11130 (2021)

    2021 arXiv

  4. [11]

    Erdős, A

    P. Erdős, A. Hajnal,On the number of distinct induced subgraphs of a graph, Discrete Mathematics,75(1989) 145–154

    1989

  5. [12]

    Erdős, A

    P. Erdős, A. Rényi, On the evolution of random graphs,Publ. Math. Inst. Hungar. Acad. Sci, 5: 17–61, 1960

    1960

  6. [13]

    Friedman,A proof of Alon’s second eigenvalue conjecture and related problems, Memoirs of the American Mathematical Society,195:910 (2008) 100pp

    J. Friedman,A proof of Alon’s second eigenvalue conjecture and related problems, Memoirs of the American Mathematical Society,195:910 (2008) 100pp

    2008

  7. [14]

    A. M. Frieze,On the independence number of random graphs, Discrete Mathematics,81:2 (1990) 171–175

    1990

  8. [15]

    A. M. Frieze, B. Jackson,Large holes in sparse random graphs, Combinatorica,7:3 (1987) 265–274

    1987

  9. [16]

    Janson, T

    S. Janson, T. Łuczak, A. Ruciński,Random graphs, Wiley, 2000

    2000

  10. [17]

    B. D. McKay,Subgraphs of random graphs with specified degrees, Congr. Numer.,33(1981) 213–223

    1981

  11. [18]

    Müller,Probabilistic reconstruction from subgraphs, Commentationes Mathematicae Uni- versitatis Carolinae,17:4 (1976) 709–719

    V. Müller,Probabilistic reconstruction from subgraphs, Commentationes Mathematicae Uni- versitatis Carolinae,17:4 (1976) 709–719

    1976

  12. [19]

    Nadarajah, K

    S. Nadarajah, K. Mitov,Asymptotics of maxima of discrete random variables, Extremes, 5:3 (2002) 287–294

    2002

  13. [20]

    Otter,The number of trees, Annals of Mathematics,2:49 (1948) 583–599

    R. Otter,The number of trees, Annals of Mathematics,2:49 (1948) 583–599

    1948

  14. [21]

    Pittel,On trees census and the giant component in a sparse random graph, Random Structures & Algorithms,1(1990) 311–342

    B. Pittel,On trees census and the giant component in a sparse random graph, Random Structures & Algorithms,1(1990) 311–342. 21

    1990

  15. [22]

    Puder,Expansion of random graphs: New proofs, new results, Inventiones Mathematicae, 201:3 (2015) 845–908

    D. Puder,Expansion of random graphs: New proofs, new results, Inventiones Mathematicae, 201:3 (2015) 845–908

    2015

  16. [23]

    Rodionov, M

    I. Rodionov, M. Zhukovskii,The distribution of the maximum number of common neighbors in the random graph, European Journal of Combinatorics,107(2023) 103602

    2023

  17. [25]

    Shelah,Erdős and Rényi conjecture, Journal of Combinatorial Theory, Ser A,82(1998) 179–185

    S. Shelah,Erdős and Rényi conjecture, Journal of Combinatorial Theory, Ser A,82(1998) 179–185

    1998

  18. [26]

    Verbitsky, M

    O. Verbitsky, M. Zhukovskii,Canonical labeling of sparse random graphs, 42nd Interna- tional Symposium on Theoretical Aspects of Computer Science (STACS 2025), Leibniz International Proceedings in Informatics (LIPIcs),327(2025) 75:1–75:20. A Proof of the lower bound in Claim 3...

    2025

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.