pith. sign in

arxiv: 2605.15043 · v1 · pith:GJYSDDLVnew · submitted 2026-05-14 · 🧮 math.CO

Hamiltonicity of regular sublinear expanders

Domagoj Brada\v{c} , Oliver Janzer This is my paper

Pith reviewed 2026-06-30 19:59 UTC · model grok-4.3

classification 🧮 math.CO
keywords Hamiltonicityexpandersregular graphsbipartite graphsCayley graphsKneser graphsconnecting lemma
0
0 comments X

The pith

There exists an absolute constant K such that any n-vertex d-regular γ-expander with d ≥ (γ^{-1} log n)^K is Hamiltonian if bipartite or γ-far from bipartite.

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

The paper establishes a degree threshold guaranteeing that regular expander graphs contain a cycle through every vertex. For graphs meeting the expansion condition and either bipartite or sufficiently far from bipartite, a degree polynomial in the inverse of the expansion parameter and the logarithm of n suffices. The proof introduces a random connecting lemma for sublinear expanders to construct the necessary paths. This yields a general criterion that applies uniformly rather than to isolated families of graphs.

Core claim

We prove that there exists an absolute constant K such that any n-vertex d-regular γ-expander with d ≥ (γ^{-1} log n)^K is Hamiltonian, provided that it is bipartite or γ-far from bipartite. As part of the proof we establish a random connecting lemma for sublinear expanders.

What carries the argument

The random connecting lemma for sublinear expanders, which produces paths between prescribed vertices while preserving the expansion properties needed to complete a Hamiltonian cycle.

If this is right

  • Highly robust versions of recent Hamiltonicity results for Cayley graphs follow directly from the degree threshold.
  • Highly robust versions of recent Hamiltonicity results for Kneser graphs follow directly from the degree threshold.
  • The random connecting lemma supplies a tool for constructing paths in other sparse expander settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same degree threshold supplies a uniform test that can be applied to additional families of regular graphs once their expansion parameters are known.
  • The connecting lemma may extend to questions of long paths or cycles in sublinear expanders that are not necessarily regular.

Load-bearing premise

The random connecting lemma for sublinear expanders holds and can be applied to produce the required paths and cycles under the stated degree threshold.

What would settle it

An n-vertex d-regular γ-expander with d just below (γ^{-1} log n)^K that is bipartite yet contains no Hamiltonian cycle would falsify the claim.

Figures

Figures reproduced from arXiv: 2605.15043 by Domagoj Brada\v{c}, Oliver Janzer.

Figure 1
Figure 1. Figure 1: The construction of an (x, a, b, y)-absorber with ℓ = 7. The blue segments and curves represent single edges, where the a − b path with arcs below corresponds to Q1 and the a − b path with arcs above corresponds to Q2. The red segments represent paths P1, . . . , Pℓ. The first path is an x−y path with vertex set V (H) while the second is an x−y path with vertex set V (H)\ {a, b}. Finally, we use the follow… view at source ↗
Figure 2
Figure 2. Figure 2: The construction of an (x, a, y)-absorber with ℓ = 7. The blue segments and arcs represent single edges, where the a − y path with arcs below corresponds to Q1 and the a − u6 path with arcs above to Q2. The red segments represent paths P1, . . . , Pℓ−1. Construction of an (x, a, y)-absorber. Suppose we are given distinct vertices x, a, y in a graph G and an odd integer ℓ. Let Q1 = u0, . . . , uℓ be an a − … view at source ↗
Figure 3
Figure 3. Figure 3: An example with m = 3. The red, blue and green paths are constructed using the connecting properties of R. The orange lens-shaped objects represent (x, a, b, y)-absorbers. 29 [PITH_FULL_IMAGE:figures/full_fig_p029_3.png] view at source ↗
read the original abstract

We say that a $d$-regular graph is a $\gamma$-expander if for every not too large set of vertices $S$, there are at least $\gamma d |S|$ edges leaving $S$, and we say that a graph $G$ is $\gamma$-far from bipartite if at least $\gamma e(G)$ edges need to be removed to make it bipartite. We prove that there exists an absolute constant $K$ such that any $n$-vertex $d$-regular $\gamma$-expander with $d \ge (\gamma^{-1} \log n)^K$ is Hamiltonian, provided that it is bipartite or $\gamma$-far from bipartite. As applications, we obtain highly robust versions of recent important results on the Hamiltonicity of Cayley graphs and Kneser graphs. As part of our proof, we prove a random connecting lemma for sublinear expanders which might be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that there exists an absolute constant K such that any n-vertex d-regular γ-expander with d ≥ (γ^{-1} log n)^K is Hamiltonian, provided the graph is bipartite or γ-far from bipartite. The proof introduces a random connecting lemma for sublinear expanders, which is used to construct the required paths and cycles, and applies the main theorem to obtain robust Hamiltonicity results for Cayley graphs and Kneser graphs.

Significance. If the random connecting lemma and its application to the degree threshold hold, the result substantially strengthens the known Hamiltonicity thresholds for regular expanders, moving from linear to polylogarithmic degree in the expansion parameter. The applications yield highly robust versions of recent results on Cayley and Kneser graphs, and the connecting lemma may have independent value for other connectivity problems in sparse expanders.

major comments (2)
  1. [§3] §3 (Random Connecting Lemma): the quantitative bound on the number of random walks needed to connect two sets appears to rely on a Chernoff-type tail bound whose failure probability must be union-bounded over all pairs of sets; it is not immediately clear from the statement whether the resulting degree threshold (γ^{-1} log n)^K absorbs all logarithmic factors arising from this union bound.
  2. [Theorem 1.1] Theorem 1.1 and the bipartite case: the argument that the lemma produces a Hamilton cycle when the graph is bipartite uses a perfect matching between the two parts; the proof sketch does not explicitly verify that the expansion parameter γ remains sufficient after removing the matching edges, which could affect the sublinear regime.
minor comments (2)
  1. [Abstract / Theorem 1.1] The definition of 'γ-far from bipartite' (at least γ e(G) edges to remove) is used in the non-bipartite case but is not restated in the statement of the main theorem; adding a parenthetical reminder would improve readability.
  2. [Introduction] Notation for the expansion parameter γ is overloaded between the expander definition and the far-from-bipartite condition; a brief remark distinguishing the two uses would prevent confusion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and constructive comments. Below we respond point-by-point to the major comments; all clarifications will be incorporated in the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (Random Connecting Lemma): the quantitative bound on the number of random walks needed to connect two sets appears to rely on a Chernoff-type tail bound whose failure probability must be union-bounded over all pairs of sets; it is not immediately clear from the statement whether the resulting degree threshold (γ^{-1} log n)^K absorbs all logarithmic factors arising from this union bound.

    Authors: In the proof of the Random Connecting Lemma, the number of walks per pair is chosen on the order of (log n / γ)^C for a sufficiently large C so that the Chernoff tail is exp(−Ω((log n / γ)^c)) for some c>0. The union bound is over at most n^2 pairs of sets and contributes an additional O(log n) to the exponent. The absolute constant K in the degree hypothesis d ≥ (γ^{-1} log n)^K is chosen larger than all constants appearing in these calculations (including those from the Chernoff and union-bound exponents), so that the failure probability is o(1/n^2) and the threshold absorbs every logarithmic factor. We will add an explicit remark after the statement of the lemma recording the dependence of K on these quantities. revision: yes

  2. Referee: [Theorem 1.1] Theorem 1.1 and the bipartite case: the argument that the lemma produces a Hamilton cycle when the graph is bipartite uses a perfect matching between the two parts; the proof sketch does not explicitly verify that the expansion parameter γ remains sufficient after removing the matching edges, which could affect the sublinear regime.

    Authors: In the bipartite case we delete a perfect matching M and work in G−M, which is (d−1)-regular. For any set S the number of edges leaving S in G−M is at least γ d |S| − |S|, hence the new expansion parameter satisfies γ′ ≥ (γ d − 1)/(d − 1). Whenever d ≥ 2/γ we have γ′ ≥ γ/2. Our degree lower bound already guarantees d ≫ 1/γ (since K ≥ 1), so the halved parameter γ/2 only multiplies the threshold by a constant factor 2^K, which is absorbed into the choice of the absolute constant K. We will insert this short calculation immediately after the invocation of the connecting lemma in the bipartite case of Theorem 1.1. revision: yes

Circularity Check

0 steps flagged

Derivation is self-contained; no circular reductions identified

full rationale

The paper establishes its Hamiltonicity result by proving a new random connecting lemma for sublinear expanders, presented as an independent contribution. The abstract and description contain no self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations that reduce the central claim to its own inputs by construction. The bipartite and γ-far-from-bipartite cases are handled directly within the proof structure, and applications to Cayley/Kneser graphs are straightforward consequences once the lemma holds. No equations or lemmas are quoted that exhibit the forbidden patterns of circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Central claim rests on the standard definitions of γ-expander and γ-far from bipartite plus the new random connecting lemma; no free parameters or invented entities are visible in the abstract.

axioms (2)
  • domain assumption Definition of γ-expander: for every not too large S there are at least γ d |S| edges leaving S.
    Standard definition invoked in the statement of the main theorem.
  • domain assumption Definition of γ-far from bipartite: at least γ e(G) edges must be removed to make G bipartite.
    Standard definition invoked in the statement of the main theorem.

pith-pipeline@v0.9.1-grok · 5684 in / 1227 out tokens · 29621 ms · 2026-06-30T19:59:26.785340+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. Towards the Lov\'{a}sz conjecture via sublinear expanders

    math.CO 2026-06 unverdicted novelty 7.0

    Every connected vertex-transitive graph of order n contains a cycle of length at least n^{2/3-o(1)}.

Reference graph

Works this paper leans on

66 extracted references · 4 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Aharoni and P

    R. Aharoni and P. Haxell. Hall’s theorem for hypergraphs.J. Graph Theory, 35(2):83–88, 2000

    2000

  2. [2]

    N. Alon, M. Bucić, L. Sauermann, D. Zakharov, and O. Zamir. Essentially tight bounds for rainbow cycles in proper edge-colourings.Proc. Lond. Math. Soc. (3), 130(4):Paper No. e70044, 37, 2025

    2025

  3. [3]

    Alon and V

    N. Alon and V. D. Milman.λ 1,isoperimetric inequalities for graphs, and superconcentrators.J. Combin. Theory Ser. B, 38(1):73–88, 1985

    1985

  4. [4]

    Bedert, M

    B. Bedert, M. Bucić, N. Kravitz, R. Montgomery, and A. Müyesser. On Graham’s rearrangement conjecture overF n 2.arXiv preprint arXiv, 2508, 2025

    2025

  5. [5]

    The Lov\'asz conjecture holds for moderately dense Cayley graphs

    B. Bedert, N. Draganić, A. Müyesser, and M. Pavez-Signé. The Lovász conjecture holds for moderately dense Cayley graphs.arXiv preprint arXiv:2603.08675, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  6. [6]

    N. Biggs. Some odd graph theory. InSecond International Conference on Combinatorial Mathematics (New York, 1978), volume 319 ofAnn. New York Acad. Sci., pages 71–81. New York Acad. Sci., New York, 1979

    1978

  7. [7]

    Bollobás

    B. Bollobás. The evolution of sparse graphs. InGraph theory and combinatorics (Cambridge, 1983), pages 35–57. Academic Press, London, 1984

    1983

  8. [8]

    Brandt, H

    S. Brandt, H. Broersma, R. Diestel, and M. Kriesell. Global connectivity and expansion: long cycles and factors inf-connected graphs.Combinatorica, 26(1):17–36, 2006

    2006

  9. [9]

    Bucić and R

    M. Bucić and R. Montgomery. Towards the Erdős-Gallai Cycle Decomposition Conjecture.Advances in Mathematics, 437:Paper No. 109434, 40, 2024

    2024

  10. [10]

    Chakraborti, O

    D. Chakraborti, O. Janzer, A. Methuku, and R. Montgomery. Edge-disjoint cycles with the same vertex set. Advances in Mathematics, 469:110228, 2025

    2025

  11. [11]

    C. C. Chen and N. F. Quimpo. On strongly Hamiltonian abelian group graphs. InCombinatorial mathematics, VIII (Geelong, 1980), volume 884 ofLecture Notes in Math., pages 23–34. Springer, Berlin, 1981

    1980

  12. [12]

    Y.-C. Chen. Triangle-free Hamiltonian Kneser graphs.Journal of Combinatorial Theory, Series B, 89(1):1–16, 2003. 38

    2003

  13. [13]

    Christofides, J

    D. Christofides, J. Hladký, and A. Máthé. Hamilton cycles in dense vertex-transitive graphs.J. Combin. Theory Ser. B, 109:34–72, 2014

    2014

  14. [14]

    V. Chvátal. On Hamilton’s ideals.J. Combinatorial Theory Ser. B, 12:163–168, 1972

    1972

  15. [15]

    Chvátal and P

    V. Chvátal and P. Erdős. A note on Hamiltonian circuits.Discrete Math., 2:111–113, 1972

    1972

  16. [16]

    Cooper, A

    C. Cooper, A. Frieze, and B. Reed. Random regular graphs of non-constant degree: Connectivity and Hamil- tonicity.Combinatorics, Probability and Computing, 11(3):249–261, 2002

    2002

  17. [17]

    G. A. Dirac. Some theorems on abstract graphs.Proc. London Math. Soc. (3), 2:69–81, 1952

    1952

  18. [18]

    Draganić, R

    N. Draganić, R. Montgomery, D. M. Correia, A. Pokrovskiy, and B. Sudakov. Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

    work page arXiv 2024

  19. [19]

    Draganić, A

    N. Draganić, A. Methuku, D. Munhá Correia, and B. Sudakov. Cycles with many chords.Random Structures & Algorithms, 65(1):3–16, 2024

    2024

  20. [20]

    Ferber, J

    A. Ferber, J. Han, D. Mao, and R. Vershynin. Hamiltonicity of sparse pseudorandom graphs.Combin. Probab. Comput., 34(4):596–620, 2025

    2025

  21. [21]

    I. G. Fernández, J. Kim, Y. Kim, and H. Liu. Nested cycles with no geometric crossings.Proc. Amer. Math. Soc. Ser. B, 9:22–32, 2022

    2022

  22. [22]

    Hamiltoncyclesinpseudorandomgraphs.Adv

    S.Glock, D.MunháCorreia, andB.Sudakov. Hamiltoncyclesinpseudorandomgraphs.Adv. Math., 458:Paper No. 109984, 45, 2024

    2024

  23. [23]

    Godsil and K

    C. Godsil and K. Meagher.Erdős-Ko-Rado theorems: algebraic approaches, volume 149 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2016

    2016

  24. [24]

    Godsil and G

    C. Godsil and G. Royle.Algebraic graph theory, volume 207 ofGraduate Texts in Mathematics. Springer- Verlag, New York, 2001

    2001

  25. [25]

    B. Green. A Szemerédi-type regularity lemma in abelian groups, with applications.Geom. Funct. Anal., 15(2):340–376, 2005

    2005

  26. [26]

    Harutyunyan, K.-i

    A. Harutyunyan, K.-i. Kawarabayashi, L. Picasarri-Arrieta, and G. Puig i Surroca. (∆−1)-dicolouring of digraphs.arXiv preprint arXiv:2507.10266, 2025

    work page arXiv 2025

  27. [27]

    Haslegrave, J

    J. Haslegrave, J. Kim, and H. Liu. Extremal density for sparse minors and subdivisions.Int. Math. Res. Not. IMRN, 2022(20):15505–15548, 2022

    2022

  28. [28]

    B. Jackson. Hamilton cycles in regular two-connected graphs. InGraph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), pages 261–265. Academic Press, New York-London, 1979

    1977

  29. [29]

    Janson, T

    S. Janson, T. Łuczak, and A. Rucinski.Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000

    2000

  30. [30]

    Jiang, S

    T. Jiang, S. Letzter, A. Methuku, and L. Yepremyan. Rainbow subdivisions of cliques.Random Structures Algorithms, 64(3):625–644, 2024

    2024

  31. [31]

    J. R. Johnson. An inductive construction for Hamilton cycles in Kneser graphs.Electron. J. Combin., 18(1):Paper 189, 12, 2011

    2011

  32. [32]

    D. R. Karger. Random sampling in cut, flow, and network design problems.Math. Oper. Res., 24(2):383–413, 1999

    1999

  33. [33]

    R. M. Karp. Reducibility among combinatorial problems. InComplexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), The IBM Research Symposia Series, pages 85–103. Plenum, New York-London, 1972

    1972

  34. [34]

    Kelmans, D

    A. Kelmans, D. Mubayi, and B. Sudakov. Asymptotically optimal tree-packings in regular graphs.Electron. J. Combin., 8(1):Research Paper 38, 8, 2001

    2001

  35. [35]

    J. Kim, H. Liu, M. Sharifzadeh, and K. Staden. Proof of Komlós’s conjecture on Hamiltonian subsets.Proc. Lond. Math. Soc. (3), 115(5):974–1013, 2017

    2017

  36. [36]

    Komlós and E

    J. Komlós and E. Szemerédi. Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Math., 43(1):55–63, 1983

    1983

  37. [37]

    Komlós and E

    J. Komlós and E. Szemerédi. Topological cliques in graphs.Combin. Probab. Comput., 3(2):247–256, 1994

    1994

  38. [38]

    Komlós and E

    J. Komlós and E. Szemerédi. Topological cliques in graphs. II.Combin. Probab. Comput., 5(1):79–90, 1996

    1996

  39. [39]

    A. D. Koršunov. Solution of a problem of P. Erdős and A. Rényi on Hamiltonian cycles in nonoriented graphs. Diskret. Analiz, 228(31):17–56, 90, 1977. 39

    1977

  40. [40]

    Krivelevich and B

    M. Krivelevich and B. Sudakov. Sparse pseudo-random graphs are Hamiltonian.J. Graph Theory, 42(1):17–33, 2003

    2003

  41. [41]

    Krivelevich and B

    M. Krivelevich and B. Sudakov. Pseudo-random graphs. In E. Győri, G. O. H. Katona, L. Lovász, and T. Fleiner, editors,More Sets, Graphs and Numbers: A Salute to Vera Sós and András Hajnal, pages 199–

  42. [42]

    Springer Berlin Heidelberg, Berlin, Heidelberg, 2006

    2006

  43. [43]

    Krivelevich, B

    M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald. Random regular graphs of high degree.Random Structures Algorithms, 18(4):346–363, 2001

    2001

  44. [44]

    H. Lee, M. Pavez-Signé, and T. Petrov. Spanning clique subdivisions in pseudorandom graphs.arXiv preprint arXiv:2504.01642, 2025

    work page arXiv 2025

  45. [45]

    S. Letzter. Sublinear expanders and their applications. InSurveys in combinatorics 2024, volume 493 of London Math. Soc. Lecture Note Ser., pages 89–130. Cambridge Univ. Press, Cambridge, 2024

    2024

  46. [46]

    Letzter, A

    S. Letzter, A. Methuku, and B. Sudakov. Nearly Hamilton cycles in sublinear expanders and applications.J. Lond. Math. Soc. (2), 113(2):Paper No. e70452, 42, 2026

    2026

  47. [47]

    Liu and R

    H. Liu and R. Montgomery. A proof of Mader’s conjecture on large clique subdivisions inC4-free graphs.J. Lond. Math. Soc. (2), 95(1):203–222, 2017

    2017

  48. [48]

    Liu and R

    H. Liu and R. Montgomery. A solution to Erdős and Hajnal’s odd cycle problem.J. Amer. Math. Soc., 36(4):1191–1234, 2023

    2023

  49. [49]

    L. Lovász. Problem 11. InCombinatorial Structures and Their Applications, page 497. Gordon and Breach, New York, 1970. Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications, 1969

    1970

  50. [50]

    L. Lovász. Random walks on graphs.Combinatorics, Paul Erdős is eighty, 2(1-46):4, 1993

    1993

  51. [51]

    W. Mader. Minimalen-fach kantenzusammenhängende Graphen.Math. Ann., 191:21–28, 1971

    1971

  52. [52]

    McDiarmid

    C. McDiarmid. On the method of bounded differences.Surveys in combinatorics, 141(1):148–188, 1989

    1989

  53. [53]

    G. H. J. Meredith and E. K. Lloyd. The footballers of Croam.J. Combinatorial Theory Ser. B, 15:161–166, 1973

    1973

  54. [54]

    Merino, T

    A. Merino, T. Mütze, and Namrata. Kneser graphs are Hamiltonian.Advances in Mathematics, 468:110189, 2025

    2025

  55. [55]

    Montgomery

    R. Montgomery. Spanning trees in random graphs.Adv. Math., 356:106793, 92, 2019

    2019

  56. [56]

    Montgomery, A

    R. Montgomery, A. Müyesser, A. Pokrovskiy, and B. Sudakov. Approximate path decompositions of regular graphs.J. Lond. Math. Soc. (2), 112(2):Paper No. e70269, 40, 2025

    2025

  57. [57]

    T. Mütze. On Hamilton cycles in graphs defined by intersecting set systems.Notices Amer. Math. Soc., 71(5):583–592, 2024

    2024

  58. [58]

    Mütze, J

    T. Mütze, J. Nummenpalo, and B. Walczak. Sparse Kneser graphs are Hamiltonian.J. Lond. Math. Soc. (2), 103(4):1253–1275, 2021

    2021

  59. [59]

    C. S. J. A. Nash-Williams. Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency. In Studies in Pure Mathematics (Presented to Richard Rado), pages 157–183. Academic Press, London-New York, 1971

    1971

  60. [60]

    O. Ore. Note on Hamilton circuits.Amer. Math. Monthly, 67:55, 1960

    1960

  61. [61]

    L. Pósa. Hamiltonian circuits in random graphs.Discrete Math., 14(4):359–364, 1976

    1976

  62. [62]

    Rapaport-Strasser

    E. Rapaport-Strasser. Cayley color groups and Hamilton lines.Scripta Math., 24:51–58, 1959

    1959

  63. [63]

    V. Rödl, A. Ruciński, and E. Szemerédi. A Dirac-type theorem for 3-uniform hypergraphs.Combin. Probab. Comput., 15(1-2):229–251, 2006

    2006

  64. [64]

    Sudakov and I

    B. Sudakov and I. Tomon. The extremal number of tight cycles.Int. Math. Res. Not. IMRN, 2022(13):9663– 9684, 2022

    2022

  65. [65]

    Trevisan

    L. Trevisan. Max cut and the smallest eigenvalue. InProceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 263–272, New York, NY, USA, 2009. Association for Computing Machinery

    2009

  66. [66]

    M. E. Watkins. Connectivity of transitive graphs.J. Combinatorial Theory, 8:23–29, 1970. 40 A Connecting pairs of vertices by vertex-disjoint paths through a ran- dom vertex set In this appendix, we prove Lemma 5.2, which we now restate for the reader’s convenience. Lemma 5.2.LetGbe ann-vertex(d±d ′)-nearly-regularγ-expander, whered ′ ≤d/4andγ < 1 (logn) ...

    1970