Pith. sign in

REVIEW 2 major objections 3 minor 125 references

Recent progress in graph theory using expansion

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

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

Pith's one-line read This survey argues that a weak form of expansion, in which neighbourhoods grow only logarithmically slowly, has become a central tool in extremal graph theory and lies behind a decade of breakthroughs from exact cycle lengths to Latin-squar

desk verdict A genuinely useful survey of sublinear expansion's recent impact, but two headline 'resolutions' still rest on unpublished or forthcoming work; worth refereeing with a request for caveats. read the letter →

arxiv 2607.26049 v1 pith:VEJ3J7OU submitted 2026-07-28 math.CO

Richard Montgomery This is my paper · ORCID
classification math.CO MSC 05C3505C3805C4805C75
keywords sublinearexpansionexpandergraphsextremalgraphtheorysubdivisionsminorscyclelengthsdecompositionLatinsquaretransversals
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

Sublinear expansion is a deliberately weak connectivity property: in an n-vertex graph, every set of vertices of size up to n/2 has a neighbourhood at least proportional to |U|/log^2(3|U|/k). The survey's thesis is that this weak property, not the strong expansion of classical expander theory, has been the effective engine behind a wide range of recent results in extremal graph theory. The enabling fact is that any graph with large average degree contains a subgraph that is a sublinear expander and still has almost the same average degree, so a sparse graph can be replaced by an expander without losing the density that matters. Around this 'pass to an expander' step, the survey organises proofs of old conjectures about clique subdivisions, complete minors, cycle lengths and the odd cycle problem, cycle decompositions down to O(n log* n), rainbow cycles, Ramsey numbers, and even the existence of almost-full transversals in Latin squares. A sympathetic reader comes away with a single picture: weak expansion is a broadly applicable skeleton for constructing structure in sparse graphs.

What carries the argument

The central object is the (ε,k)-expander, a sublinear expander in which every vertex set U with k ≤ |U| ≤ n/2 has neighbourhood size at least (ε/log^2(3|U|/k))|U|. Its partner is a mid-1990s theorem: every graph of average degree d contains such a subgraph with average degree within (1−δ)d. The mechanism does the work by converting an arbitrary sparse graph into a graph whose iterated neighbourhoods grow, however slowly, in a controlled way; this gives paths between arbitrary vertices in poly-logarithmic length and, after careful construction, paths and cycles of exact or near-exact prescribed lengths.

What would settle it

Go to the proofs cited in Sections 5 and 10: the harmonic-sum cycle-length result announced as forthcoming, and the large-even Latin-square transversal proof. If either proof contains a gap that cannot be repaired—or if a counterexample appears, such as a sufficiently large even-order Latin square with no partial transversal of size n−1—the survey's central claim that sublinear expansion has resolved these problems would be false.

Watch

Extended reading notes

Core claim

The paper's central claim is that sublinear expansion should be regarded as a unifying technique: many hard extremal problems become tractable once the graph is replaced by a sublinear expander. The load-bearing result is a theorem from the mid-1990s: every graph of average degree d contains a subgraph that is an (ε,k)-expander with average degree at least (1−δ)d, so the reduction costs almost nothing in density. The survey compiles the high-water marks of this approach: tight quadratic bounds for topological cliques, logarithmic-size complete minors in dense graphs, the resolution of the C4-free subdivision conjecture, the odd cycle problem and the sharp (1/2−o(1)) log n harmonic sum over c

Load-bearing premise

The survey's narrative depends on the correctness of several very recent and still-unpublished results it cites—especially the proof of the n−1 partial transversal conjecture for all sufficiently large even-order Latin squares and the forthcoming resolution of the harmonic-sum cycle-length conjecture; if either is flawed, the survey's flagship examples of sublinear expansion at work would be unwarranted.

Editorial extensions

If this is right

  • Any graph with sufficiently large average degree contains a sublinear expander of almost the same degree, so the expander-replacement step is applicable to a broad class of extremal problems, not only those surveyed.
  • The cycle-length machinery implies that graphs of large chromatic number have odd cycles whose reciprocal lengths sum to at least (1/2−o(1)) log χ(G), which is optimal up to the o(1).
  • The cycle-decomposition results imply every n-vertex graph can be decomposed into O(n log* n) cycles and edges, and that improving this to O(n) likely requires a non-iterative or non-memoryless argument.
  • The Latin-square result implies every sufficiently large even-order Latin square has a partial transversal of size n−1, one short of a full transversal.
  • Conjectures stated in the survey, if true, would extend the same structural picture: every regular sublinear expander would be Hamiltonian, and every properly edge-coloured graph with no rainbow cycle would have O(n log n) edges.

Reading between the lines

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

  • If the pass-to-an-expander thesis generalizes as the survey suggests, hypergraph or directed-graph analogues of these problems may become tractable with a suitable notion of sublinear expansion; the survey does not make this claim.
  • The O(n log* n) barrier for cycle decomposition is implicitly presented as an artefact of iterative methods; a testable prediction is that a one-shot decomposition, if it exists, will need a structural characterisation of graphs that resist few-cycle decompositions.
  • The use of sublinear expansion in auxiliary graphs, for cycles with all diagonals and for Latin squares, suggests the technique may be most powerful when the problem's real difficulty has been hidden in a derived graph, and similar transfers could illuminate other Turán or colouring problems.
  • If random regular sublinear expanders turn out to be Hamiltonian, the survey's conjecture that every regular sublinear expander is Hamiltonian would place weak expanders on the same footing as the spectral expanders for which Hamiltonicity was recently proved.
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

2 major / 3 minor

Summary. The paper is a survey of recent progress in extremal graph theory obtained through sublinear expansion. It introduces the relevant definitions (α-expanders, (ε,k)-expanders), describes the Komlós–Szemerédi framework, and then surveys applications to clique subdivisions and minors, cycle lengths, cycle decomposition and packing, nested and chorded cycles, rainbow Turán problems, Ramsey numbers of cycles, and two applications involving auxiliary graphs (cycles with all diagonals and Latin-square transversals). It closes with several open problems, including Mader's constant for subdivisions, Erdős–Gallai cycle decomposition, nested cycles without geometric crossings, rainbow-cycle bounds, and Hamiltonicity of regular sublinear expanders.

Significance. If the surveyed results are correct, the paper provides a valuable and readable synthesis of a technique that has become central to sparse extremal graph theory in the last decade. The survey is careful in its attributions, correctly separates published results from open problems, and repeatedly points to the companion technical survey of Letzter [78] for details. It also explicitly highlights several important open questions, which is a useful service. The author's own work appears prominently, but the presentation is generally measured. The main weakness is that two of the headline 'resolutions' advertised in the abstract rest on a preprint and a forthcoming paper, respectively; these need clearer epistemic status flags. With that local revision, the survey would be a reliable entry point to the field.

major comments (2)
  1. [Section 5 (Erdős harmonic-sum conjecture)] The sentence 'That this is true when d is sufficiently large is shown in forthcoming work of Milojević, Montgomery, Pokrovskiy and Sudakov' is presented as an established resolution of a long-standing conjecture, yet no reference, preprint identifier, or proof sketch is given. This result is explicitly used in the abstract's narrative of 'resolution of many long-standing and notable problems'. Please either supply a citable source (arXiv ID or accepted paper) or explicitly mark it as a recent announcement whose details are not yet public.
  2. [Section 10 (Ryser–Brualdi–Stein conjecture)] The text states that 'Montgomery [92] showed that, when n is sufficiently large, every Latin square of order n contains a partial transversal with n−1 cells.' Although [92] is given an arXiv identifier, the surrounding wording ('showed', 'lengthy proof') presents it as a settled result. Since [92] is an unreviewed preprint (arXiv:2310.19779), the survey should qualify it as a preprint/announced result, e.g., 'announced in a preprint [92]' or 'proved in a recent preprint [92]', so that the reader can distinguish it from the refereed literature.
minor comments (3)
  1. [Section 2 (paragraph before Theorem 2.1)] The phrase 'showing d(t)=t^2+o(1)' appears to be a typo. The known bounds are d(t)=Θ(t^2), with lower bound (9/64+o(1))t^2 and upper bound (10/23+o(1))t^2 discussed later in the same section; an asymptotic equality with t^2 contradicts the lower bound. The intended statement is likely 'd(t)=O(t^2)' or 'd(t) ≤ (1+o(1))t^2'.
  2. [Section 5 (Erdős harmonic-sum conjecture)] The 'forthcoming work' of Milojević–Montgomery–Pokrovskiy–Sudakov is not listed in the references. If no preprint is yet available, at least add a reference entry with '(in preparation)' and the expected authors, so that the citation format is consistent with the rest of the survey.
  3. [Section 10 (Ryser–Brualdi–Stein)] Consider adding a sentence in the introduction or in Section 10 clarifying that the survey reviews both published and unpublished (preprint/announced) results, and that the latter should be read with appropriate caution. This would preempt the ambiguity highlighted for the two capstone results.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the survey is descriptive and its claims rest on cited external theorems, including preprints whose verification status is a correctness caveat rather than a circularity issue.

full rationale

This paper is a survey, not a derivation: it reports results achieved using sublinear expansion and does not derive predictions from fitted parameters or definitions. The central claim in the abstract is historical and descriptive. Each technical statement is attributed to external work with proofs in the cited papers. The definition of an (ε,k)-expander (Definition 3.1) and the existence theorem for such expanders (Theorem 3.2) are presented as prior results, not as outputs generated by the survey. The self-citations (e.g., [15], [80], [81], [92]) are standard in a research survey and are not load-bearing in a circular sense: [80] and [81] are published peer-reviewed results, and [92] is an arXiv preprint whose status is a verification concern, not a definitional dependency. Similarly, the 'forthcoming work' on Erdős's harmonic-sum conjecture in Section 5 is reported as external forthcoming research; its unavailability is a caveat about evidential support, not circularity. No equation in the paper is equal to another by construction, and no fitted parameter is renamed as a prediction. Under the proportionality rule, the appropriate finding is no significant circularity, score 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The survey introduces no free parameters or new entities. It relies on the standard definitions of expansion and on the correctness of the primary literature, including several very recent preprints.

assumptions (4)
  • standard math Correctness of cited peer-reviewed theorems (e.g., Komlós–Szemerédi Theorem 3.2 and the Bollobás–Thomason subdivision theorem).
    The survey's usefulness depends on the validity of the results it cites; these are standard published results widely accepted by the community.
  • domain assumption Correctness of cited unpublished or preprint results ([92], [29], [19], and the forthcoming Milojević et al. result).
    Several highlighted advances are cited as established though they remain in preprint or are described as forthcoming; the survey does not provide proofs.
  • standard math Erdős–Stone theorem and standard Turán-theory background.
    Invoked in Sections 2 and 8 to frame extremal numbers and motivate the sparse regime.
  • domain assumption The (ε,k)-expander formalism of Definition 3.1 faithfully represents the 'sublinear expansion' used in the cited proofs.
    The survey treats Definition 3.1 as representative and glosses over variations ('Many variations... have by now been used'), assuming the reader accepts the unifying description.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Recent progress in graph theory using expansion." pith.science (2026). https://pith.science/paper/VEJ3J7OU

@misc{pith2026260726049,
  author       = {Pith},
  title        = {Pith review of: Recent progress in graph theory using expansion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VEJ3J7OU}},
  note         = {Machine review of arXiv:2607.26049}
}
read the original abstract

Graph expansion has long been recognised as an important and desirable property with applications in a wide range of areas in computer science and mathematics. A particular form of expansion known as `sublinear expansion' has recently been used particularly effectively in extremal graph theory, leading to the resolution of many long-standing and notable problems over the last decade and an improved understanding of the structure of sparse graphs. This survey will cover these advances.

Figures

Figures reproduced from arXiv: 2607.26049 by the authors.

Figure 1
Figure 1. a) The neighbourhood NG(U) of a vertex set U in a graph G and b) expanding neighbour￾hoods iteratively from x and y respectively to find a path from x to y. Various definitions of expanders have been used in different settings, and similar properties can be reached through different routes, e.g. by defining an expander from whether random walks on their edges rapidly mix, from their spectral properties, or from comb… view at source ↗
Figure 2
Figure 2. a) A K5-subdivision, b) a K3,3-subdivision, and c) a graph drawn in the plane with no edges crossing, which necessarily contains no K5- or K3,3-subdivision. a couple of recent results in which sublinear expansion plays a more unexpected role through its application in an auxiliary graph (Section 10). 2 Subdivisions. We subdivide an edge xy in a graph G by replacing xy with a new vertex whose neighbours are exactly x… view at source ↗
Figure 3
Figure 3. G contains H as a minor, for a copy of H can be formed by deleting an edge, then a vertex and then contracting the edge xy into the vertex z. with only O(log n) vertices. In the influential work of Shapira and Sudakov [110] mentioned above, it was shown using sublinear expansion that such a minor exists with only O(log n log log n) vertices. Subsequently, the conjecture was proved in full by Montgomery [91], who als… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: A long cycle passing through three short cycles which can be used to adjust the length of [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: a) An Eulerian graph decomposed into cycles and b) a graph decomposed into cycles and edges. open is in stark contrast to the corresponding case for decompositions into cycles and paths. Here, thanks to an old result of Lov´asz [82], we have the exactly tight bound tha…
Figure 6
Figure 6. Figure 6: a) Nested cycles, b) nested cycles with no geometric crossing, and c) two cycles nested with each other. 7 Cycles with additional properties. In Section 5, we discussed what we might be able to say about the length of the cycles in sparse graphs. We now discuss several…
Figure 7
Figure 7. Figure 7: a) A cycle with many chords, b) a cycle with all its diagonals, and c) the graph in b) redrawn as a ‘twisted cycle of 4-cycles’. subgraph without too unreasonable a loss in average degree. Having a regular subgraph then allows the applications of techniques known to wo…
Figure 8
Figure 8. Figure 8: a) A properly coloured graph, b) a non-properly coloured graph, and c) a rainbow cycle. have copies of H but have a proper colouring that ensures each of these copies is not rainbow. A good example is when H is a cycle with 2k vertices. Due to Bondy and Simonovits [12]…
Figure 9
Figure 9. Figure 9: Burr’s colouring of a complete graph on ( [PITH_FULL_IMAGE:figures/full_fig_p014_9.png]
Figure 10
Figure 10. Figure 10: a) A Latin square of order 6 with a partial transversal of order 5 highlighted and b) a Latin square of order 6 with a (full) transversal highlighted. table of any group G of order n, which forms a Latin square of order n. Latin squares have been studied from a mathem…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

125 extracted references · 10 linked inside Pith

  1. [78]

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

    2024

  2. [92]

    Montgomery

    R. Montgomery. A proof of the Ryser-Brualdi-Stein conjecture for large evenn. arXiv:2310.19779, 2023

    arXiv 2023

  3. [1]

    Allen, G

    P. Allen, G. Brightwell, and J. Skokan. Ramsey-goodness–and otherwise.Combinatorica, 33:125– 160, 2013

    2013

  4. [2]

    N. Alon, M. Buci´ c, L. Sauermann, D. Zakharov, and O. Zamir. Essentially tight bounds for rainbow cycles in proper edge-colourings.arXiv:2309.04460, 2023

    arXiv 2023

  5. [3]

    N. Alon, S. Friedland, and G. Kalai. Regular subgraphs of almost regular graphs.Journal of Combinatorial Theory, Series B, 37(1):79–91, 1984

    1984

  6. [4]

    N. Alon, M. Krivelevich, and B. Sudakov. Tur´ an numbers of bipartite graphs and related Ramsey-type questions.Combin. Probab. Comput., 12:477–494, 2003

    2003

  7. [5]

    Balogh, H

    J. Balogh, H. Liu, and M. Sharifzadeh. Subdivisions of a large clique inC 6-free graphs.J. Combin. Theory Ser. B, 112:18–35, 2015

    2015

  8. [6]

    L. A. Bassalygo and M. S. Pinsker. The complexity of an optimal non-blocking commutation scheme without reorganization.Problemy Peredaˇ ci Informacii, 9:84–87, 1973. Translated into English in Problems of Information Transmission, 9 (1974) 64-66

    1973

Show all 125 references
  1. [7]

    Bollob´ as

    B. Bollob´ as. Cycles modulok.Bulletin of the London Mathematical Society, 9(1):97–98, 1977

    1977

  2. [8]

    Bollob´ as

    B. Bollob´ as. Nested cycles in graphs. InProbl´ emes combinatoires et th´ eorie des graphes Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, pages 49–50. 1978

    1976

  3. [9]

    Bollob´ as.Random graphs

    B. Bollob´ as.Random graphs. Springer, 2011

    2011

  4. [10]

    Bollob´ as and A

    B. Bollob´ as and A. Thomason. Highly linked graphs.Combinatorica, 16:313–320, 1996

    1996

  5. [11]

    Bondy and P

    J. Bondy and P. Erd˝ os. Ramsey numbers for cycles in graphs.Journal of Combinatorial Theory, Series B, 14(1):46–54, 1973

    1973

  6. [12]

    J. A. Bondy and M. Simonovits. Cycles of even length in graphs.Journal of Combinatorial Theory, Series B, 16(2):97–105, 1974

    1974

  7. [13]

    Bradaˇ c, A

    D. Bradaˇ c, A. Methuku, and B. Sudakov. The extremal number of cycles with all diagonals. arXiv:2308.16163, 2023

    2023 arXiv

  8. [14]

    R. A. Brualdi and H. J. Ryser.Combinatorial matrix theory. Cambridge University Press, 1991

    1991

  9. [15]

    Buci´ c and R

    M. Buci´ c and R. Montgomery. Towards the Erd˝ os-Gallai cycle decomposition conjecture.Ad- vances in Mathematics, 437:109434, 2024

    2024

  10. [16]

    S. A. Burr. Ramsey numbers involving graphs with long suspended paths.J. London Math. Soc., 2:405–413, 1981

    1981

  11. [17]

    S. A. Burr and P. Erd˝ os. Generalizations of a Ramsey-theoretic result of Chv´ atal.Journal of Graph Theory, 7(1):39–51, 1983

    1983

  12. [18]

    Campos, S

    M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe. An exponential improvement for diagonal Ramsey.Annals of Mathematics, 2025, to appear

    2025

  13. [19]

    Campos, M

    M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe. A new lower bound for the Ramsey numbersR(3, k).arXiv preprint arXiv:2505.13371, 2025

    2025 arXiv

  14. [20]

    Chakraborti, O

    D. Chakraborti, O. Janzer, A. Methuku, and R. Montgomery. Regular subgraphs at every density.arXiv preprint arXiv:2411.11785, 2024

    2024

  15. [21]

    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. 16

    2025

  16. [22]

    G. Chen, P. Erd˝ os, and W. Staton. Proof of a conjecture of Bollob´ as on nested cycles.J. Combin. Theory Ser. B, 66:38–43, 1996

    1996

  17. [23]

    Chv´ atal, V

    V. Chv´ atal, V. R¨ odl, E. Szemer´ edi, and W. T. Trotter Jr. The Ramsey number of a graph with bounded maximum degree.Journal of Combinatorial Theory, Series B, 34(3):239–243, 1983

    1983

  18. [24]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov. Cycle packing.Random Structures Algorithms, 45:608–626, 2014

    2014

  19. [25]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov. Recent developments in graph ramsey theory.Surveys in combinatorics, 424(2015):49–118, 2015

    2015

  20. [26]

    Conlon and O

    D. Conlon and O. Janzer. Rational exponents near two.arXiv preprint arXiv:2203.03375, 2022

    2022 arXiv

  21. [27]

    S. Das, C. Lee, and B. Sudakov. Rainbow Tur´ an problem for even cycles.European Journal of Combinatorics, 34(5):905–915, 2013

    2013

  22. [28]

    Dragani´ c, A

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

    2024

  23. [29]

    Dragani´ c, R

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

    2024 arXiv

  24. [30]

    P. Erd˝ os. Some recent progress on extremal problems in graph theory.Congr. Numer., 14:3–14, 1975

    1975

  25. [31]

    P. Erd˝ os. Problems and results in graph theory.The theory and applications of graphs (Kala- mazoo, MI, 1980), pages 331–341, 1981

    1980

  26. [32]

    P. Erd˝ os. Some new and old problems on chromatic graphs. InCombinatorics and applications, pages 118–126. 1984

    1984

  27. [33]

    Erd˝ os, A

    P. Erd˝ os, A. W. Goodman, and L. P´ osa. The representation of a graph by set intersections. Canad. J. Math., 18:106–112, 1966

    1966

  28. [34]

    P. Erd˝ os. Problems and results in graph theory and combinatorial analysis.Proc. 5th British Combin. Conf., pages 169–192, 1975

    1975

  29. [35]

    P. Erdos. Some recent problems and results in graph theory, combinatorics, and number theory. InProc. Seventh SE Conf. Combinatorics, Graph Theory and Computing, Utilitas Math, pages 3–14, 1976

    1976

  30. [36]

    P. Erd˝ os. On the combinatorial problems which i would most like to see solved.Combinatorica, 1(1):25–42, 1981

    1981

  31. [37]

    P. Erd˝ os. Some problems in number theory, combinatorics and combinatorial geometry.Math- ematica Pannonica, 5:261–269, 1994

    1994

  32. [38]

    P. Erd˝ os. Some recent problems and results in graph theory.Discrete Mathematics, 164(1-3):81– 85, 1997

    1997

  33. [39]

    Erd˝ os, R

    P. Erd˝ os, R. J. Faudree, C. C. Rousseau, and R. H. Schelp. The size Ramsey number.Periodica Mathematica Hungarica, 9(1-2):145–161, 1978

    1978

  34. [40]

    Erd˝ os and A

    P. Erd˝ os and A. Hajnal. On chromatic number of graphs and set-systems.Acta Math. Acad. Sci. Hungar., 17:61–99, 1966

    1966

  35. [41]

    Erd˝ os and A

    P. Erd˝ os and A. Hajnal. On topological complete subgraphs of certain graphs. InAnnales Univ. Sci. Budapest, volume 7, pages 193–199, 1969. 17

    1969

  36. [42]

    Erd˝ os and A

    P. Erd˝ os and A. H. Stone. On the structure of linear graphs.Bull. Amer. Math. Soc., 52:1087– 1091, 1946

    1946

  37. [43]

    L. Euler. Recherches sur un nouvelle esp´ ece de quarr´ es magiques.Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, pages 85–239, 1782

  38. [44]

    R. J. Faudree and R. H. Schelp. All Ramsey numbers for cycles in graphs.Discrete Mathematics, 8(4):313–329, 1974

    1974

  39. [45]

    Fiorini, G

    S. Fiorini, G. Joret, D. O. Theis, and D. R. Wood. Small minors in dense graphs.Europ. J. Combin., 33:1226–1245, 2012

    2012

  40. [46]

    Gabber and Z

    O. Gabber and Z. Galil. Explicit constructions of linear size superconcentrators. In20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pages 364–370. IEEE Computer Society, 1979

    1979

  41. [47]

    Gallai et al

    T. Gallai et al. On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hungar, 10:337–356, 1959

    1959

  42. [48]

    Gerencs´ er and A

    L. Gerencs´ er and A. Gy´ arf´ as. On Ramsey-type problems.Annales Universitatis Scientiarium Budapestinensis de Rolando E¨ otv¨ os Nominatae, Sectio Mathematica, 10:167–170, 1967

    1967

  43. [49]

    Gil Fern´ andez, J

    I. Gil Fern´ andez, J. Kim, Y. Kim, and H. Liu. Nested cycles with no geometric crossings.Proc. Am. Math. Soc. Ser. B, 9:22–32, 2022

    2022

  44. [50]

    Glock, D

    S. Glock, D. K¨ uhn, and D. Osthus. Extremal aspects of graph and hypergraph decomposition problems.Surveys in Combinatorics 2021, page 235, 2021

    2021

  45. [51]

    Gy´ arf´ as, J

    A. Gy´ arf´ as, J. Koml´ os, and E. Szemer´ edi. On the distribution of cycle lengths in graphs.J. Graph Theory, 8:441–462, 1984

    1984

  46. [52]

    F. Harary. Recent results on generalized Ramsey theory for graphs. InGraph Theory and Applications, pages 125–138. Springer, 1972

    1972

  47. [53]

    Haslegrave, J

    J. Haslegrave, J. Hyde, J. Kim, and H. Liu. Ramsey numbers of cycles versus general graphs. Forum Math. Sigma, 11:e10, 2023

    2023

  48. [54]

    Hatami and P

    P. Hatami and P. W. Shor. A lower bound for the length of a partial transversal in a Latin square.Journal of Combinatorial Theory, Series A, 115(7):1103–1113, 2008

    2008

  49. [55]

    Hoory, N

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

    2006

  50. [56]

    Janson, T

    S. Janson, T. Luczak, and A. Rucinski.Random graphs. John Wiley & Sons, 2011

    2011

  51. [57]

    O. Janzer. Rainbow Tur´ an number of even cycles, repeated patterns and blow-ups of cycles. Israel J. Math., 253:813–840, 2023

    2023

  52. [58]

    Janzer and B

    O. Janzer and B. Sudakov. Resolution of the Erd˝ os–Sauer problem on regular subgraphs. In Forum of Mathematics, Pi, volume 11, page e19, 2023

    2023

  53. [59]

    Janzer and B

    O. Janzer and B. Sudakov. On the Tur´ an number of the hypercube. InForum of Mathematics, Sigma, volume 12, page e38. Cambridge University Press, 2024

    2024

  54. [60]

    Jiang, S

    T. Jiang, S. Letzter, A. Methuku, and L. Yepremyan. Rainbow clique subdivisions.Random Structures Algorithms, 64:625–644, 2023

    2023

  55. [61]

    Jiang, A

    T. Jiang, A. Methuku, and L. Yepremyan. Rainbow Tur´ an number of clique subdivisions.Europ. J. Combin., 110:103675, 2023. 18

    2023

  56. [62]

    Jiang and Y

    T. Jiang and Y. Qiu. Tur´ an numbers of bipartite subdivisions.SIAM Journal on Discrete Mathematics, 34(1):556–570, 2020

    2020

  57. [63]

    Keevash, E

    P. Keevash, E. Long, and J. Skokan. Cycle–complete ramsey numbers.International Mathemat- ics Research Notices, 2021(1):275–300, 2021

    2021

  58. [64]

    Keevash, D

    P. Keevash, D. Mubayi, B. Sudakov, and J. Verstra¨ ete. Rainbow Tur´ an problems.Combin. Probab. Comput., 16:109–126, 2007

    2007

  59. [65]

    Keevash, A

    P. Keevash, A. Pokrovskiy, B. Sudakov, and L. Yepremyan. New bounds for Ryser’s conjecture and related problems.Transactions of the American Mathematical Society, Series B, 9(8):288– 321, 2022

    2022

  60. [66]

    J. Kim, J. Lee, H. Liu, and T. Tran. Rainbow cycles in properly edge-colored graphs. 2022. arXiv:2211.03291

    2022 arXiv

  61. [67]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi. Topological cliques in graphs.Combin. Probab. Comput., 3:247– 256, 1994

    1994

  62. [68]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi. Topological cliques in graphs II.Combin. Probab. Comput., 5:79–90, 1996

    1996

  63. [69]

    A. V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4(4):307–316, 1984

    1984

  64. [70]

    Krivelevich

    M. Krivelevich. Expanders - how to find them, and what to find in them. InSurveys in Combinatorics 2019, pages 115–142, 2019

    2019

  65. [71]

    Krivelevich and B

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

    2003

  66. [72]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. Topological minors in graphs of large girth.Journal of Combinatorial Theory, Series B, 86(2):364–380, 2002

    2002

  67. [73]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. Large topological cliques in graphs without a 4-cycle.Combin. Probab. Comput., 13:93–102, 2004

    2004

  68. [74]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. Extremal connectivity for topological cliques in bipartite graphs.J. Combin. Theory Ser. B, 96:73–99, 2006

    2006

  69. [75]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. A survey on Hamilton cycles in directed graphs.European Journal of Combinatorics, 33(5):750–766, 2012

    2012

  70. [76]

    Kuratowski

    C. Kuratowski. Sur le probleme des courbes gauches en topologie.Fundamenta mathematicae, 15(1):271–283, 1930

    1930

  71. [77]

    C. Lee. Ramsey numbers of degenerate graphs.Annals of Mathematics, 185(3):791–829, 2017

    2017

  72. [79]

    Letzter, A

    S. Letzter, A. Methuku, and B. Sudakov. Nearly Hamilton cycles in sublinear expanders, and applications.arXiv preprint arXiv:2503.07147, 2025

    2025

  73. [80]

    Liu and R

    H. Liu and R. Montgomery. A proof of Mader’s conjecture on large clique subdivisions inC 4-free graphs.J. London Math. Soc., 95:203–222, 2017

    2017

  74. [81]

    Liu and R

    H. Liu and R. Montgomery. A solution to Erd˝ os and Hajnal’s odd cycle problem.J. Am. Math. Soc., 2023. 19

    2023

  75. [82]

    Lov´ asz

    L. Lov´ asz. On covering of graphs. InTheory of Graphs, pages 231–236. Academic Press New York, 1968

    1968

  76. [83]

    Lubotzky

    A. Lubotzky. Expander graphs in pure and applied mathematics.Bull. Am. Math. Soc., 49:113– 162, 2012

    2012

  77. [84]

    W. Mader. Homomorphieeigenschaften und mittlere kantendichte von graphen.Mathematische Annalen, 174(4):265–268, 1967

    1967

  78. [85]

    W. Mader. Homomorphies¨ atze f¨ ur graphen.Mathematische Annalen, 178(2):154–168, 1968

    1968

  79. [86]

    W. Mader. An extremal problem for subdivisions ofK − 5 .J. Graph Theory, 30:261–276, 1999

    1999

  80. [87]

    W. Mantel. Problem 28 (solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff).Wiskundige Opgaven, 10:60–61, 1907

    1907

  81. [88]

    G. A. Margulis. Explicit constructions of concentrators.Problemy Peredachi Informatsii, 9(4):71–80, 1973

    1973

  82. [89]

    Matouˇ sek

    J. Matouˇ sek. The number of unit distances is almost linear for most norms.Advances in Mathematics, 226(3):2618–2628, 2011

    2011

  83. [90]

    Mattheus and J

    S. Mattheus and J. Verstra¨ ete. The asymptotics ofr(4, t).Annals of Mathematics, 199(2):919– 941, 2024

    2024

  84. [91]

    Montgomery

    R. Montgomery. Logarithmically small minors and topological minors.J. London Math. Soc., 91:71–88, 2015

    2015

  85. [93]

    Montgomery

    R. Montgomery. Transversals in Latin squares.Surveys in Combinatorics, 2024

    2024

  86. [94]

    Montgomery, M

    R. Montgomery, M. Pavez-Sign´ e, and J. Yan. Ramsey numbers of bounded degree trees versus general graphs.Journal of Combinatorial Theory, Series B, 173:102–145, 2025

    2025

  87. [95]

    Montgomery, M

    R. Montgomery, M. Pavez-Sign´ e, and J. Yan. Ramsey numbers of trees.arXiv preprint arXiv:2509.07934, 2025

    2025 arXiv

  88. [96]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira. Decomposing a graph into expanding subgraphs.Random Structures Algorithms, 52:158–178, 2018

    2018

  89. [97]

    R. Nenadov. Improved bound on the number of cycle sets.arXiv preprint arXiv:2501.09904, 2025

    2025

  90. [98]

    Nikiforov

    V. Nikiforov. The cycle-complete graph Ramsey numbers.Combinatorics, Probability and Computing, 14(3):349–370, 2005

    2005

  91. [99]

    Nikiforov and C

    V. Nikiforov and C. C. Rousseau. Ramsey goodness and beyond.Combinatorica, 29(2):227–262, 2009

    2009

  92. [100]

    M. S. Pinsker. On the complexity of a concentrator. InProceedings of the Seventh International Teletraffic Congress (Stockholm, 1973), page 318/1–318/4. 1973

    1973

  93. [101]

    Pokrovskiy.Rainbow Subgraphs and their Applications, page 191–214

    A. Pokrovskiy.Rainbow Subgraphs and their Applications, page 191–214. London Mathematical Society Lecture Note Series. Cambridge University Press, 2022

    2022

  94. [102]

    Pokrovskiy and B

    A. Pokrovskiy and B. Sudakov. Ramsey goodness of paths.Journal of Combinatorial Theory, Series B, 122:384–390, 2017. 20

    2017

  95. [103]

    Pokrovskiy and B

    A. Pokrovskiy and B. Sudakov. Ramsey goodness of cycles.SIAM J. Discr. Math., 34:1884–1908, 2020

    1908

  96. [104]

    L. Pyber. Regular subgraphs of dense graphs.Combinatorica, 5(4):347–349, 1985

    1985

  97. [105]

    Pyber, V

    L. Pyber, V. Rodl, and E. Szemer´ edi. Dense graphs without 3-regular subgraphs.Journal of Combinatorial Theory, Series B, 63(1):41–54, 1995

    1995

  98. [106]

    F. P. Ramsey. On a problem of formal logic.Proceedings of The London Mathematical Society, s2-30(1):264–286, 1930

    1930

  99. [107]

    V. Rosta. On a Ramsey-type problem of J. A. Bondy and P. Erd˝ os. II.Journal of Combinatorial Theory, Series B, 15(1):105–120, 1973

    1973

  100. [108]

    H. J. Ryser. Neuere probleme der kombinatorik.Vortr¨ age ¨ uber Kombinatorik, Oberwolfach, 69:91, 1967

    1967

  101. [109]

    P. C. Sarnak. What is... an expander?Not. Am. Math. Soc., 51:762–763, 2004

    2004

  102. [110]

    Shapira and B

    A. Shapira and B. Sudakov. Small complete minors above the extremal edge density.Combina- torica, 35:75–94, 2015

    2015

  103. [111]

    P. W. Shor. A lower bound for the length of a partial transversal in a Latin square.Journal of Combinatorial Theory, Series A, 33(1):1–8, 1982

    1982

  104. [112]

    S. K. Stein. Transversals of Latin squares and their generalizations.Pacific J. Math., 59:567–575, 1975

    1975

  105. [113]

    B. Sudakov. Restricted subgraphs of edge-colored graphs and applications.arXiv preprint arXiv:2412.13945, 2024

    2024 arXiv

  106. [114]

    Sudakov and J

    B. Sudakov and J. Verstra¨ ete. Cycle lengths in sparse graphs.Combinatorica, 28(3):357–372, 2008

    2008

  107. [115]

    Sudakov and J

    B. Sudakov and J. Verstra¨ ete. Cycles in graphs with large independence ratio.Journal of Combinatorics, 2(1):83–102, 2011

    2011

  108. [116]

    Thomason

    A. Thomason. An extremal function for contractions of graphs. InMathematical Proceedings of the Cambridge Philosophical Society, volume 95, pages 261–265. Cambridge University Press, 1984

    1984

  109. [117]

    Thomason

    A. Thomason. The extremal function for complete minors.J. Combin. Theory Ser. B, 81:318– 338, 2001

    2001

  110. [118]

    I. Tomon. Robust (rainbow) subdivisions and simplicial cycles.arXiv:2201.12309, 2022

    2022 arXiv

  111. [119]

    P. Tur´ an. On an external problem in graph theory.Mat. Fiz. Lapok, 48:436–452, 1941

    1941

  112. [120]

    O. Veblen. An application of modular equations in analysis situs.Annals of Mathematics, 14(1/4):86–94, 1912

    1912

  113. [121]

    Verstra¨ ete

    J. Verstra¨ ete. On the number of sets of cycle lengths.Combinatorica, 24(4):719–730, 2004

    2004

  114. [122]

    Verstra¨ ete

    J. Verstra¨ ete. Unavoidable cycle lengths in graphs.J. Graph Theory, 49:151–167, 2005

    2005

  115. [123]

    Verstra¨ ete

    J. Verstra¨ ete. Extremal problems for cycles in graphs. InRecent trends in combinatorics, pages 83–116. Springer, 2016

    2016

  116. [124]

    Y. Wang. Rainbow clique subdivisions.European Journal of Combinatorics, 116:103868, 2024

    2024

  117. [125]

    I. M. Wanless. Transversals in Latin squares: A survey. pages 403–437, 2011. 21

    2011

Pith tools

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