A large hole in pseudo-random graphs

Itay Markbreit; Maksim Zhukovskii; Michael Krivelevich; Sahar Diskin

REVIEW 2 major objections 5 minor 25 references

A large hole in pseudo-random graphs

T0 review · 2 major / 5 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 any graph whose second eigenvalue is far below its degree, there is an induced cycle of length Ω(n/d), a bound that is tight up to a constant factor.

desk verdict Tight holes in pseudo-random graphs: a solid new result with a patchable gap in the main proof. read the letter →

arxiv 2505.23384 v1 pith:A2W4YTKW submitted 2025-05-29 math.CO math.PR

Sahar Diskin , Michael Krivelevich , Itay Markbreit , Maksim Zhukovskii This is my paper

classification math.COmath.PR MSC 05C8005C4805C38

keywords pseudo-randomgraphsinducedcyclesholesspectralratiositepercolationdepth-firstsearchnon-isomorphicsubgraphsexpandermixinglemma

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

This paper proves that every graph whose edge distribution is uniformly spread, in the spectral sense that its nontrivial eigenvalues are tiny compared with its degree, contains a long induced cycle (hole). Concretely, for any (n,d,λ)-graph with λ/d below a fixed small constant and d at most a constant fraction of n, there is a hole of length at least δ2 n/d. The bound is linear in n/d and is best possible up to a constant factor. The same technique gives a lower bound exp(Ω(n log d / d)) on the number of non-isomorphic induced subgraphs, also tight up to the exponent's constant.

What carries the argument

The engine is site percolation combined with a tailored Depth-First-Search (DFS) algorithm. A vertex subset V_p is kept with probability p=(1+ε)/d; the DFS algorithm grows an induced path in G_p, maintaining a stack U that always spans an induced path, and the analysis shows that after εn steps the stack has size Ω(n/d) with high probability, while percolation results control the excess (edges minus vertices plus components) and the vertex expansion of explored sets. The second ingredient is the expander mixing lemma, which guarantees an edge between the two large external neighbourhoods used to close the path into a cycle. The upper-bound constructions use the lexicographic product of a random d0-regular graph with either an independent set or a clique, so that the spectral ratio is inherited from the base graph while the induced-path length or the number of induced subgraphs is forced to be small.

What would settle it

Exhibit a sequence of (n,d,λ)-graphs with λ/d → 0 and d = o(n) whose largest induced cycle has length o(n/d); that would refute Theorem 1.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: there are absolute constants δ1, δ2, δ3 > 0 such that every (n,d,λ)-graph with d ≤ δ3 n and λ/d ≤ δ1 contains an induced cycle of length at least δ2 n/d. The proof percolates the graph with probability p = (1+ε)/d and runs a Depth-First-Search algorithm whose stack always spans an induced path; percolation estimates control the explored sets and force the stack to grow to length Ω(n/d), giving a long induced path in the original graph. The path is then closed into a cycle: its first and last thirds have large external neighbourhoods, the middle third has a small neighbourhood, and an edge between the two external neighbourhoods outside the middle closes an induced cycle of length at least δ2 n/d. The paper further constructs, via lexicographic products with cliques or independent sets, graphs with the same spectral ratio whose longest induced path is O(n/d), showing the bound is tight, and adapts the path construction to show that the number of non-isomorphic induced subgraphs is exp(Ω(n log d/d)), matching an upper bound up to the constant in the exponent.

Load-bearing premise

The proof's final chord-avoidance step assumes that the edge chosen between the two external neighbourhoods has endpoints with no neighbours on the far end or the middle of the long path, so the closed cycle is induced, but the definitions of those neighbourhood sets do not by themselves guarantee this.

Editorial extensions

If this is right

Random d-regular graphs, which typically have λ ≤ 2√d, have holes of length Ω(n/d) with high probability, improving the earlier Ω(n/d²) bound for sparse random graphs.
The n/d bound cannot be improved in general: some (n,d,λ)-graphs with arbitrarily small spectral ratio have longest induced path only O(n/d), so the hole length is Θ(n/d) up to constants.
The number of non-isomorphic induced subgraphs of any such pseudo-random graph is at least exp(c·n log d / d), and this is the right order of magnitude in the exponent.
The proof yields a randomised algorithm that finds such a hole in linear time with high probability.
The new result upgrades the earlier induced-path theorem of Draganić and Keevash to an induced cycle while significantly relaxing the required spectral-ratio condition.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The n/d scaling hints at a stronger optimal bound Θ(n log(d/λ)/d) for the largest hole, matching the independence-number scale; the paper raises this question and leaves it open.
The percolate-then-DFS method is likely transferable to other induced structures — long induced trees, induced even cycles, or induced subgraphs with prescribed degrees — under the same spectral hypothesis.
The counting argument obtains the exponent of μ(G) only up to a constant; pinning down the constant for specific families, such as random d-regular graphs, is a natural next step.

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.

Desk Editor's Note

read the letter

Colleague — quick take: the paper has a real, nontrivial result and a real, fixable gap in the proof of Theorem 1. The central claim — induced cycles of length Ω(n/d) under λ/d ≤ δ, tight up to a constant — is important and, based on the overall machinery, likely correct. The percolation-plus-DFS strategy is a nice way to get holes, not just paths, and the upper-bound constructions via lexicographic products look sound. The counting application (exp(Ω(n log d / d)) non-isomorphic induced subgraphs) is a good bonus and tight up to the exponent.

The soft spot is exactly where the reader put it. In Theorem 1, after defining N1 = N(P1) \ (P ∪ N(P')), the text asserts that a vertex u1 ∈ N1 has no neighbors in P' ∪ P2. The P' part is fine, because N1 excludes N(P'); the P2 part doesn't follow from the definition. Membership in N(P1) says nothing about edges to P2. If a cross-edge to P2 exists inside the relevant subpath, the cycle u1u2 plus the subpath has a chord, so the proof as written doesn't certify an induced cycle. The stress-test note's patch is plausible: if some u1 has a P2-neighbor, use its closest P1- and P2-neighbors to close a shorter cycle; otherwise the original argument goes through, symmetrically for u2. But that case split isn't in the manuscript. This is a genuine referee item, not a cosmetic one.

The other soft spot is Theorem 4's isomorphism argument. It's compressed in a way that hides real details: the degree-one vertices in H, the handling of possible edges inside N_W', and the spacing argument for the degree-≥3 vertices all require filling in. I believe they can be filled, but a referee will need to do the work.

None of this is load-bearing in the sense of circularity — the imported percolation theorems have independent proofs and the constants aren't fitted. The constructions in Section 5 are standard lexicographic products and check out.

Bottom line: this deserves a serious referee. I'd send it out with a request to fix the Theorem 1 gap and expand Theorem 4. If the patch works, it's a strong paper.

Referee Report

2 major / 5 minor

Summary. The paper proves that for any (n,d,lambda)-graph with lambda/d sufficiently small and d at most a constant fraction of n, there is an induced cycle of length at least a constant times n/d, and it shows this is tight up to a constant factor. It also proves a lower bound of exp(Omega(n log d / d)) on the number of non-isomorphic induced subgraphs of such graphs, together with a matching upper bound up to the constant in the exponent. The proofs combine site percolation, a DFS-based exploration algorithm, and lexicographic product constructions.

Significance. If the gaps identified below are repaired, this is a strong contribution: it transfers the known induced-cycle bounds from the binomial random graph to all (n,d,lambda)-graphs with small spectral ratio, improves the induced-path result of Draganic and Keevash, and provides matching tightness constructions. The percolation-based technique is elegant and the counting application is new for pseudo-random graphs. The constants are universal and the paper is generally clearly written.

major comments (2)

[Section 3, proof of Theorem 1] The assertion that u1 has no neighbours in Pmid union P2 does not follow from the definition of N1 = N_G(P1) minus (P union N_G(Pmid)). Membership in N1 guarantees at least one neighbour in P1 and no neighbours in P or Pmid, but it imposes no restriction on edges from u1 to P2. If u1 has a neighbour in the portion of P2 that lies on the subpath from w1 to w2, the cycle formed by u1u2 plus that subpath has a chord. The gap is repairable with a case split: if some u1 in N1 has a P2-neighbour, then u1 together with the subpath between its closest neighbours in P1 and P2 is an induced cycle; otherwise all u1 have no P2-neighbours and the original construction works, with a symmetric argument for u2. Since this case split is absent, Theorem 1 is not proved as written.
[Section 4, proof of Theorem 4] The isomorphism argument is too compressed and appears to rely on an unjustified distance claim. The sentence 'by construction of H, the two closest vertices to u which have degree at least 3 ... are at distance at least four from each other' is not valid as a statement about graph distance in H. Edges inside N_Wprime can create shortcuts between vertices of W: for example, if a and b in N_Wprime have unique P-neighbours w1 and w2 respectively and ab is an edge of G, then w1-a-b-w2 is a path of length 3 between two W-vertices that may be far apart on P. Thus the distance in H between the nearest degree-3 vertices can be less than the distance along P. The proof needs either to control the number of edges inside N_Wprime using the expander mixing lemma or to replace the distance-in-H argument with a different invariant that rules out psi(u) in Aprime for degree-2 vertices u in V(P). Since the counting lower bound depends on the claim that psi preserves V(P), this gap is load-bearing.

minor comments (5)

[Section 3, proof of Theorem 1] The reference 'By Theorem 2.3' should read 'By Lemma 2.3'.
[Section 2] The notation delta = epsilon^{24}/epsilon^{12} is confusing; it equals epsilon^{12} and should be written as a single power.
[Introduction] The phrase 'one might expecto to find' contains a typo; it should be 'one might expect to find'.
[Section 3, proof of Theorem 1] The phrase 'let w2 be the neighbourhood of u closest to P prime' should say 'neighbour' instead of 'neighbourhood'.
[Section 2, DFS observations] The observation that G_p[U] spans an induced path should state explicitly that G[U] is an induced path, since this is what the proof of Theorem 2 uses.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: self-cited percolation lemmas are independent inputs; central path/cycle result is not assumed. A non-circular proof gap in Theorem 1 is noted.

full rationale

The paper's central result, Theorem 1, is derived from Theorem 2, which asserts an induced path in the p-site-percolated graph G_p. Theorem 2 is proved with a DFS algorithm plus Lemma 2.3 and Theorems 2.4-2.6, quoted from the authors' earlier work [8]. These are self-citations and are load-bearing: Lemma 2.7 and the final contradiction in Theorem 2 use the expansion and excess estimates from [8]. However, the cited results concern the vertex expansion of subsets of V_p, the order and edge count of the giant component of G_p, and the number of edges outside the giant component and isolated trees; none of these statements is the target 'long induced path/cycle' result, and they are parameter-free statements with explicit assumptions (small lambda/d and p=(1+epsilon)/d). Thus the derivation is not circular: Theorem 1 and Theorem 2 are not assumed, and the universal constants epsilon, alpha, and delta are not fitted to the quantity being predicted. Theorems 3 and 5 provide matching upper-bound examples via lexicographic products and random regular graphs, so the lower bounds are tested against independent constructions rather than defined into existence. I also flag a non-circular proof concern in the proof of Theorem 1 (Section 3): after defining N1 as N_G(P1) minus (P union N_G(P')) and N2 as N_G(P2) minus (P union N_G(P')), the text states that u1 has no neighbours in P' union P2 and symmetrically for u2. The 'no neighbours in P'' part follows from the exclusion of N_G(P'), but the 'no neighbours in P2' part is not implied by u1 in N1: u1 not in P only means u1 is not itself a path vertex, and it does not forbid edges from u1 to P2, a subset of P. If such an edge exists, the displayed cycle u1u2 plus the w1-w2 subpath may have chords. This is a correctness gap, not a circularity, because it does not identify any claim that is being assumed as its own input. Overall, the claimed derivation is not circular; the score of 2 reflects the substantial but non-circular reliance on self-cited percolation results from [8].

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The central lower-bound proof has no fitted constants in the sense of data fitting: epsilon and alpha are universal small constants, and the asymptotic constants delta1, delta2, delta3 are existential. The proof leans on four external results from a self-cited paper, but those results are established theorems. The invented-entities ledger is empty because no new combinatorial objects are postulated.

free parameters (3)

epsilon = any sufficiently small constant, e.g. <=1/4
Ad hoc small constant used throughout; percolation probability p=(1+epsilon)/d and all error bounds scale with it.
alpha = epsilon^12
Chosen to apply the expansion and percolation lemmas; must satisfy alpha in (0, epsilon/8).
d0 = smallest integer >=3 with sqrt(d0) >= 4/delta
Used in the tightness constructions; controls the spectral ratio of the lexicographic product.

assumptions (6)

standard math Expander mixing lemma (Alon-Chung)
Lemma 2.2, used in Theorems 1 and 4 to lower bound edge counts between large sets.
domain assumption Site percolation lemmas from Diskin-Krivelevich 2023
Lemma 2.3 and Theorems 2.4-2.6, imported from [8], give expansion and giant component estimates for G_p; the entire proof of Theorem 2 rests on them.
standard math Chernoff bound
Used in Theorem 2 to control the number of surviving vertices in the DFS process.
standard math Spectral properties of lexicographic products
Lemmas 5.1-5.2, used in the constructions for Theorems 3 and 5.
domain assumption Existence of (n0,d0,lambda0)-graphs with lambda0 <= 3*sqrt(d0)
Random regular graphs typically satisfy this; used in both tightness constructions.
domain assumption d=o(n) assumption in Theorem 2
The percolation theorems from [8] are stated for d=o(n); Theorem 1 extends to d<=delta3 n via the same lemmas.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A large hole in pseudo-random graphs." pith.science (2026). https://pith.science/paper/A2W4YTKW

@misc{pith2026250523384,
  author       = {Pith},
  title        = {Pith review of: A large hole in pseudo-random graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A2W4YTKW}},
  note         = {Machine review of arXiv:2505.23384}
}

abstract

We show that there exist constants $\delta_1,\delta_2>0$ such that if $G$ is an $(n,d,\lambda)$-graph with $\lambda/d\le\delta_1$, then $G$ contains an induced cycle of length at least $\delta_2n/d$. We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such $G$ is at least exponential in $n\log d/d$, and further demonstrate that this is tight up to a constant factor in the exponent.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 23 canonical work pages

[1]

H. L. Abbott and M. Katchalski. On the snake in the box problem.J. Comb. Theory, Ser. B, 45(1):13–24, 1988

work page 1988
[2]

Alon and B

N. Alon and B. Bollob´ as. Graphs with a small number of distinct induced subgraphs.Discrete Math., 75(1-3):23–30, 1989. Graph theory and combinatorics (Cambridge, 1988)

work page 1989
[3]

Alon and F

N. Alon and F. R. K. Chung. Explicit construction of linear sized tolerant networks.Discrete Math., 72(1-3):15–19, 1988

work page 1988
[4]

Alon and A

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

work page 1991
[5]

Alon and J

N. Alon and J. H. Spencer.The probabilistic method. Wiley-Intersci. Ser. Discrete Math. Optim. Hoboken, NJ: John Wiley & Sons, 4th edition edition, 2016

work page 2016
[6]

Barik, D

S. Barik, D. Kalita, S. Pati, and G. Sahoo. Spectra of graphs resulting from various graph operations and products: a survey.Spec. Matrices, 6:323–342, 2018

2018
[7]

D. M. Cvetkovi´ c, M. Doob, and H. Sachs.Spectra of graphs. Theory and application, volume 87 ofPure Appl. Math., Academic Press. New York, NY; Academic Press, 1980

work page 1980
[8]

Diskin and M

S. Diskin and M. Krivelevich. Site percolation on pseudo-random graphs.Random Struct. Algorithms, 63(2):406–441, 2023

work page 2023

Show all 25 references

[9]

Dragani´ c, S

N. Dragani´ c, S. Glock, and M. Krivelevich. The largest hole in sparse random graphs.Random Struct. Algorithms, 61(4):666–677, 2022

2022
[10]

Dragani´ c and P

N. Dragani´ c and P. Keevash. Long induced paths in expanders.Comb. Probab. Comput., 34(2):276–282, 2025

2025
[11]

Dutta and C

K. Dutta and C. R. Subramanian. On induced paths, holes, and trees in random graphs.SIAM J. Discrete Math., 37(1):279–303, 2023

2023
[12]

Enriquez, G

N. Enriquez, G. Faraud, L. M´ enard, and N. Noiry. Long induced paths in a configuration model. Preprint, arXiv:2106.11130 [math.PR] (2021), 2021. 10

2021 arXiv
[13]

Friedman

J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems.Mem. Amer. Math. Soc., 195(910):viii+100, 2008

2008
[14]

A. Frieze. Hamilton Cycles in Random Graphs: a bibliography. Preprint, arXiv:1901.07139 [math.CO] (2019), 2019

2019 arXiv
[15]

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

1987
[16]

Hoory, N

S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications.Bull. Am. Math. Soc., New Ser., 43(4):439–561, 2006

2006
[17]

Krivelevich

M. Krivelevich. The phase transition in site percolation on pseudo-random graphs.Electron. J. Comb., 23(1):research paper p1.12, 11, 2016

2016
[18]

Krivelevich

M. Krivelevich. Expanders – how to find them, and what to find in them. InSurveys in combinatorics 2019. Papers based on the 27th British combinatorial conference, University of Birmingham, Birmingham, UK, July 29 – August 2, 2019, pages 115–142. Cambridge: Cambridge Universit...

2019
[19]

Krivelevich and B

M. Krivelevich and B. Sudakov. Pseudo-random graphs. InMore sets, graphs and numbers. A salute to Vera S´ os and Andr´ as Hajnal, pages 199–262. Berlin: Springer. Budapest: J´ anos Bolyai Mathematical Society, 2006

2006
[20]

Krivelevich and B

M. Krivelevich and B. Sudakov. The phase transition in random graphs: A simple proof. Random Structures Algorithms, 43(2):131–138, 2013

2013
[21]

Krivelevich and M

M. Krivelevich and M. Zhukovskii. Non-isomorphic subgraphs in random graphs. Preprint, arXiv:2505.14623 [math.CO] (2025), 2025

2025 arXiv
[22]

T. Luczak. The size of the largest hole in a random graph.Discrete Math., 112(1-3):151–163, 1993

1993
[23]

M¨ uller

V. M¨ uller. Probabilistic reconstruction from subgraphs.Commentat. Math. Univ. Carol., 17:709–719, 1976

1976
[24]

W. C. S. Suen. On large induced trees and long induced paths in sparse random graphs.J. Comb. Theory, Ser. B, 56(2):250–262, 1992

1992
[25]

G. Z´ emor. An upper bound on the size of the snake-in-the-box.Combinatorica, 17(2):287–298, 1997. 11

1997

Pith tools

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

[1] [1]

H. L. Abbott and M. Katchalski. On the snake in the box problem.J. Comb. Theory, Ser. B, 45(1):13–24, 1988

work page 1988

[2] [2]

Alon and B

N. Alon and B. Bollob´ as. Graphs with a small number of distinct induced subgraphs.Discrete Math., 75(1-3):23–30, 1989. Graph theory and combinatorics (Cambridge, 1988)

work page 1989

[3] [3]

Alon and F

N. Alon and F. R. K. Chung. Explicit construction of linear sized tolerant networks.Discrete Math., 72(1-3):15–19, 1988

work page 1988

[4] [4]

Alon and A

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

work page 1991

[5] [5]

Alon and J

N. Alon and J. H. Spencer.The probabilistic method. Wiley-Intersci. Ser. Discrete Math. Optim. Hoboken, NJ: John Wiley & Sons, 4th edition edition, 2016

work page 2016

[6] [6]

Barik, D

S. Barik, D. Kalita, S. Pati, and G. Sahoo. Spectra of graphs resulting from various graph operations and products: a survey.Spec. Matrices, 6:323–342, 2018

2018

[7] [7]

D. M. Cvetkovi´ c, M. Doob, and H. Sachs.Spectra of graphs. Theory and application, volume 87 ofPure Appl. Math., Academic Press. New York, NY; Academic Press, 1980

work page 1980

[8] [8]

Diskin and M

S. Diskin and M. Krivelevich. Site percolation on pseudo-random graphs.Random Struct. Algorithms, 63(2):406–441, 2023

work page 2023