Pith. sign in

REVIEW 2 major objections 3 minor 125 references

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

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 00:43 UTC pith:VEJ3J7OU

load-bearing objection 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. the 2 major comments →

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

Recent progress in graph theory using expansion

Richard Montgomery This is my paper
classification math.CO MSC 05C3505C3805C4805C75
keywords sublinear expansionexpander graphsextremal graph theorygraph subdivisionsgraph minorscycle lengthscycle decompositionLatin square transversals
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

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.

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

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.

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.

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 this falsifier. Get emailed when new claim-graph text bears on it.

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.

Where Pith is reading between the lines

These are 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, 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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 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.

axioms (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.

pith-pipeline@v1.3.0-alltime-deepseek · 21375 in / 11127 out tokens · 100134 ms · 2026-08-01T00:43:31.673473+00:00 · methodology

0 comments
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 Richard Montgomery.

Figure 1
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… view at source ↗
Figure 2
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… view at source ↗
Figure 3
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… view at source ↗
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] view at source ↗
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 that any n-vertex graph can be decomposed into at most ⌈n/2⌉ cycles and paths. This follows by an elegant inductive argument, and the lack of a… view at source ↗
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 problems asking whether cycles can be found with additional properties. In all of these problems the extremal number of edges required in a… view at source ↗
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 work only in regular, or nearly-regular, graphs. Finding a subgraph which is both regular and a sublinear expander is an interesting challenge… view at source ↗
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], it has been known for more than 50 years that ex(n, H) = O(n 1+1/k). Despite generally being expected to tight up to the value of the impl… view at source ↗
Figure 9
Figure 9. Figure 9: Burr’s colouring of a complete graph on ( [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
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 mathematical perspective since the work of Euler [43], who considered decompositions of Latin squares into transversals. A partial transversal of … view at source ↗

discussion (0)

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

Reference graph

Works this paper leans on

125 extracted references · 10 linked inside Pith

  1. [1]

    Allen, G

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

    2013

  2. [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

    Pith/arXiv arXiv 2023

  3. [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

  4. [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

  5. [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

  6. [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

  7. [7]

    Bollob´ as

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

    1977

  8. [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

  9. [9]

    Bollob´ as.Random graphs

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

    2011

  10. [10]

    Bollob´ as and A

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

    1996

  11. [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

  12. [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

  13. [13]

    Bradaˇ c, A

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

    Pith/arXiv arXiv 2023

  14. [14]

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

    1991

  15. [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

  16. [16]

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

    1981

  17. [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

  18. [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

  19. [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

    Pith/arXiv arXiv 2025

  20. [20]

    Chakraborti, O

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

    arXiv 2024

  21. [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

  22. [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

  23. [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

  24. [24]

    Conlon, J

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

    2014

  25. [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

  26. [26]

    Conlon and O

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

    Pith/arXiv arXiv 2022

  27. [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

  28. [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

  29. [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

    Pith/arXiv arXiv 2024

  30. [30]

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

    1975

  31. [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

  32. [32]

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

    1984

  33. [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

  34. [34]

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

    1975

  35. [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

  36. [36]

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

    1981

  37. [37]

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

    1994

  38. [38]

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

    1997

  39. [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

  40. [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

  41. [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

  42. [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

  43. [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

  44. [44]

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

    1974

  45. [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

  46. [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

  47. [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

  48. [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

  49. [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

  50. [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

  51. [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

  52. [52]

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

    1972

  53. [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

  54. [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

  55. [55]

    Hoory, N

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

    2006

  56. [56]

    Janson, T

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

    2011

  57. [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

  58. [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

  59. [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

  60. [60]

    Jiang, S

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

    2023

  61. [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

  62. [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

  63. [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

  64. [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

  65. [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

  66. [66]

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

    Pith/arXiv arXiv 2022

  67. [67]

    Koml´ os and E

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

    1994

  68. [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

  69. [69]

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

    1984

  70. [70]

    Krivelevich

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

    2019

  71. [71]

    Krivelevich and B

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

    2003

  72. [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

  73. [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

  74. [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

  75. [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

  76. [76]

    Kuratowski

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

    1930

  77. [77]

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

    2017

  78. [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

  79. [79]

    Letzter, A

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

    arXiv 2025

  80. [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

Showing first 80 references.