Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Ramsey numbers of trees

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read Low-degree trees have exact Ramsey numbers

desk verdict Exact Ramsey numbers for small-linear-degree trees: real advance, coherent proof, but load-bearing Theorem 5.1 is asserted from HLT rather than proved; conditional as written. read the letter →

arxiv 2509.07934 v1 pith:6SVQSR7F submitted 2025-09-09 math.CO

Richard Montgomery , Matías Pavez-Signé , Jun Yan This is my paper · ORCID
classification math.CO MSC 05C5505C05
keywords Ramseynumberstrees1974conjectureregularitymethodstabilityanalysistreeembeddingsextremalcolouringsbipartiteclasses
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that the Ramsey number of any n-vertex tree T with maximum degree at most c n is determined exactly by its bipartition class sizes: if t1 ≥ t2, then R(T) = max{2t1, t1+2t2} − 1. That formula had been conjectured in 1974 and was known to fail for some trees with very large maximum degree, so the theorem pins down the small-degree regime and answers a question posed explicitly in 2020. A 2002 result gave the formula only up to a (1+ε) factor; the improvement is to exact equality, for a small but fixed c. The proof splits into a stability part, which uses regularity to embed the tree unless the colouring closely matches one of two extremal constructions, and an extremal part, which handles those near-extremal colourings by delicate randomized embeddings.

What carries the argument

The proof's load-bearing mechanism is a four-stage stability analysis on the reduced graph of a regularity partition. It starts from a scaled-down copy of the structure produced by the 2002 asymptotic proof (an 'A-situation': a vertex joined to one side of a nearly complete bipartite matching, with cluster sizes in ratio t1:t2), then passes through B-, C- and D-situations, at each stage either embedding T or concluding the reduced graph is extremal. The embedding workhorse is Lemma 4.2, which cuts T into tiny components through a homomorphism into a fixed auxiliary graph S, randomly assigns components to regular pairs, and uses concentration to keep cluster loads below capacity; specialised

What would settle it

Apply the 2002 proof to an explicit red/blue colouring of K_{t1+2t2-1} with t1≈2t2 and check whether the asserted starting structure appears: clusters of sizes m and (t1/t2)m, three equal parts each covering about (1−2ε)t2 vertices, a perfect matching, and a vertex joined to one side. Any colouring whose reduced graph cannot be partitioned this way while leaving the leftover clusters regular would invalidate the stability start. Alternatively, one counterexample tree with Δ(T)≤cn and R(T) > max{2t1, t1+2t2}−1 would directly falsify Theorem 1.1.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: there is an absolute c>0 such that every n-vertex tree T with Δ(T)≤cn and bipartition classes of sizes t1≥t2 has Ramsey number R(T)=max{2t1, t1+2t2}−1. The two extremal colourings from 1974 show R(T) is at least this; the paper proves the matching upper bound by showing every red/blue colouring of K_{max{2t1,t1+2t2}-1} contains a monochromatic copy of T. The proof works by a stability dichotomy: if the colouring is not close to either of those extremal colourings, a regularity-based argument embeds T; if it is close, separate extremal theorems still embed T using structure of the tree and sparse random choices. Since the theorem holds for every tree meeting

Load-bearing premise

The stability part starts from a version of the 2002 asymptotic proof that is asserted, not derived here, to produce the scaled-down structure while remembering the unused regularity clusters; if that extraction fails, the whole four-stage argument has no foundation.

Editorial extensions

If this is right

  • For every tree with maximum degree at most cn, the Ramsey number is read off from two integers t1,t2 rather than from the tree's shape.
  • The 1974 formula is exact for all small-linear-degree trees, so any counterexample to the conjecture must have maximum degree exceeding the fixed constant c.
  • The stability theorem gives a usable dichotomy: non-extremal colourings on exactly the conjectured number of vertices force a monochromatic copy of the tree.
  • The extremal lemmas show that colourings approximating the two extremal constructions still contain the tree, despite a known obstruction that makes naive embedding fail.

Reading between the lines

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

  • The constant c is produced by hierarchy arguments and is almost certainly not optimal; a natural next step is to determine the largest c for which the formula survives, with known double-star examples bounding any possible c by 7/11+o(1).
  • The unstated starting lemma of the stability part, if true, is a reusable 'remembered clusters' version of the 2002 proof; formalising it could simplify future exact Ramsey results that work with a one-vertex deficit.
  • The sparse-cut and random leaf-embedding techniques in the extremal part may apply to other spanning tree problems in graphs that are almost complete or almost complete bipartite under a few forbidden edges.
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 / 4 minor

Summary. The paper proves an exact Ramsey-number formula for every n-vertex tree whose maximum degree is at most a small constant times n: R(T) = max{2t_1, t_1+2t_2}-1, where t_1≥t_2 are the bipartition class sizes. This sharpens the asymptotic result of Haxell, Luczak, and Tingley and resolves, in the small-linear-degree regime, a question of Stein and a positive part of Burr's 1974 conjecture. The proof is divided into a stability part, which shows that a red/blue colouring either contains T or is close to one of Burr's two extremal constructions, and an extremal part, which handles both near-extremal cases by a substantial set of new embedding lemmas.

Significance. If the main theorem is correct, it is a significant exact result in Ramsey theory for trees, converting a previously asymptotic statement into an exact one under a natural bounded-degree hypothesis. The paper is also structurally ambitious: it develops a large toolbox of regularity-based embedding methods (EM1a-c, EM2a-d, HLT), and the extremal part contains delicate new arguments needed because small linear maximum degree still permits trees of small diameter. The proof is not circular: the upper bound is compared against Burr's external lower-bound constructions, and the paper explicitly notes the known 7/11+o(1) ceiling from Norin–Sun–Zhao, so the small constant c is not being optimized. However, the entire stability argument rests on an unproved extraction from earlier work, which is a load-bearing gap in the current version.

major comments (2)
  1. [Section 5, Theorem 5.1] Theorem 5.1 is the starting point of the stability proof, but it is not proved in this manuscript and is not a stated theorem of [21]. The preceding paragraph says it 'easily follows from the proof of [21, Theorem 3]' applied with alpha=t1/t2 and n=(1-epsilon)(t1+2t2), while 'remembering' regularity clusters outside the HLT structure. This is exactly the kind of modification that needs a proof: one must show that the clusters outside the HLT structure can be retained with the required two sizes m and t1m/t2, that the partition into I_A,I_B,I_C with |I_A|=|I_B|=|I_C|=k and km≥(1-2ε)t2 can be produced, and that the perfect matching and star adjacency survive. No derivation or precise external reference is supplied. Since Lemma 5.9 consumes this structure and the chain Lemmas 5.9 -> 5.8 -> 5.5 -> 5.4 depends on it, the central claim is conditional on an unverified external proof obligation.
  2. [Section 5, Theorem 5.1, bullets] As stated, Theorem 5.1 is internally inconsistent in the colour of the structure: it says 'In R*, 0 is adjacent to every a∈I_A' but then 'R_red[I_A,I_B] contains a perfect matching'. If * is blue, these two properties are in different colours and do not form the monochromatic HLT- structure required by Lemma 5.9, whose assumptions Q3 and Q4 are both red. The statement should presumably have R*[I_A,I_B] in the matching bullet. This is not a mere presentation issue, because the colour consistency of the structure is essential for every subsequent stage.
minor comments (4)
  1. [Section 2.1 vs Section 5.7] The reduction to t1≤2t2+1 in Section 2.1 uses t'_2=floor(t1/2), while the analogous reduction in the proof of Theorem 2.2 (Section 5.7) uses t'_2=ceil(t1/2). The two claims are not the same and the notation should be harmonized, with the relevant inequalities checked for both parity cases.
  2. [Throughout] There are several typographical slips: 'Let Let I_A,3' at the start of the proof of Lemma 5.9; 'with with a partition' in Lemmas 4.6, 4.8, 4.9, 4.12, 4.13; 'F or' in Section 3; 'simiply' in Section 6.1. These do not affect the mathematics but should be corrected.
  3. [Section 3, Stage 2] The summary of the cascading argument is brief. The formal Lemma 5.10 is clear, but Stage 2 also uses a refinement into clusters of two different sizes (gamma m and gamma t1m/t2) and then requires an application of Lemma 5.5 after 'removing clusters with low degrees'. It would help the reader to state explicitly which hierarchy of constants makes this cluster-size conversion legitimate, since the B-situation in Lemma 5.8 has equal-sized clusters and the C-situation in Lemma 5.5 also assumes equal-sized clusters after refinement.
  4. [Section 5.1, Definition 5.2 and Lemma 5.3] In the Type II case of Lemma 5.3, the proof is omitted as 'similar'. Since Type II extremality is used in the final theorem, a few sentences indicating the counting and vertex-removal argument would make the dependency explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof derives new embedding lemmas and combines them with an external HLT theorem; there is no reduction of the claimed result to its own inputs.

full rationale

The paper's derivation chain is: use Burr's lower bound (external, 1974) for R(T) >= max{t1+2t2,2t1}-1; prove stability Theorem 2.2 and extremal Theorems 2.3-2.4; then deduce Theorem 1.1. The upper-bound machinery is developed in Section 4 through self-contained regularity embedding lemmas (Lemmas 4.2, 4.5-4.13), none of which assume the target Ramsey number. The only imported structural input is Theorem 5.1, stated as 'easily follows from the proof of [21, Theorem 3]' and attributed to Haxell, Luczak, and Tingley. This is an independent external source, not a prior work of the present authors. No parameter is fitted to the target formula, no prediction is defined in terms of the quantity being predicted, and no known result is merely renamed. The one genuine concern about Theorem 5.1 is that its precise 'remembering' version is not proved in the manuscript and the justification is a one-sentence reference to the HLT proof; however, that is a proof gap or derivation dependency, not circularity: the cited HLT theorem and proof are independent of the present paper's conclusions. Similarly, the dependence of Stages 1-4 on Theorem 5.1 is a conditional chain, but conditionality is not equivalence. The lower bound and all upper-bound cases are checked against an external benchmark (Burr's construction), so the central claim has independent content. Score 0.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard tools (regularity lemma, concentration inequalities, matching theorems), Burr's external lower bound, and the modified HLT structure of Theorem 5.1, which is asserted without proof. The single hand-chosen object is the existential constant c. Nothing is fitted to data; the theorem is derived, not calibrated.

free parameters (1)
  • c (linear maximum-degree constant) = not specified (existential)
    Theorem 1.1 asserts the existence of c > 0; the proofs only require the hierarchy 1/n << c << epsilon, so no quantitative value is given. The statement does not depend on a particular fitted number.
assumptions (5)
  • domain assumption Coloured Szemeredi regularity lemma (Theorem 2.22, cited as [24, Theorem 1.18])
    Provides the epsilon-regular partition and reduced graph used throughout the stability part (Section 2.6).
  • domain assumption Theorem 5.1, a modified A-situation structure asserted to follow from the proof of [21, Theorem 3]
    The stability proof starts from this structure, but the required version, which remembers clusters outside the HLT structure, is not stated in [21] and no derivation is given here (Section 5, before Theorem 5.1).
  • standard math Standard probabilistic and matching tools: Chernoff, Azuma, McDiarmid, Hall's theorem, Dirac's theorem (Lemmas 2.5-2.9)
    Used throughout Sections 4-7 for randomized embeddings and degree conditions.
  • standard math Tree decomposition lemmas (Lemma 2.16 cited as [2, Proposition 4.1]; Lemma 2.11 cited as [25, Lemma 2.1]; Lemma 2.13 cited as [28, Proposition 3.19])
    Cut the tree into small pieces and into balanced subtrees; invoked in Lemma 4.1, Lemma 6.6, and Proposition 7.2.
  • standard math Burr's 1974 lower bound constructions (Figure 1) showing R(T) >= max{t1 + 2t2, 2t1} - 1
    Provides the matching lower bound; the paper only needs to prove the upper bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ramsey numbers of trees." pith.science (2026). https://pith.science/paper/6SVQSR7F

@misc{pith2026250907934,
  author       = {Pith},
  title        = {Pith review of: Ramsey numbers of trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6SVQSR7F}},
  note         = {Machine review of arXiv:2509.07934}
}
abstract

We show that there exists a constant $c>0$ such that every $n$-vertex tree $T$ with $\Delta(T)\le cn$ has Ramsey number $R(T)=\max\{t_1+2t_2,2t_1\}-1$, where $t_1\ge t_2$ are the sizes of the bipartition classes of $T$. This improves an asymptotic result of Haxell, {\L}uczak, and Tingley from 2002, and shows that, though Burr's 1974 conjecture on the Ramsey numbers of trees has long been known to be false for certain `double stars', it is true for trees with up to small linear maximum degree.

Figures

Figures reproduced from arXiv: 2509.07934 by the authors.

Figure 1
Figure 1. Burr’s extremal constructions for R(T) when T is a tree with bipartition classes of sizes t1 ≥ t2. I: Disjoint blue cliques on U1 and U2, with |U1| = t1 +t2 −1, |U2| = t2 −1, and every edge between U1 and U2 coloured red. Any connected blue subgraph has at most t1 + t2 − 1 < |T| vertices, and any connected red subgraph is bipartite with fewer than t2 vertices in one class. II: Disjoint blue cliques on U1 and U2, wit… view at source ↗
Figure 2
Figure 2. To give a rough idea of how these embedding lemmas are proved, we will discuss and sketch a [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 2
Figure 2. The different situations we find in the reduced graph, and the stages we use to work through [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figures from the paper (20 more)
Figure 3
Figure 3. Figure 3: The structure in the reduced graph required for embedding methods [PITH_FULL_IMAGE:figures/full_fig_p010_3.png]
Figure 4
Figure 4. Figure 4: The structure in the reduced graph required for [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: On the left, the main structure in Stage 1. On the right, the main structure in Stage 2. [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: The deductions for Claim A, before finally EM2c is applied to get a red copy of T. Claim A: If IA and IB cover t − 1 and t − 2 vertices respectively, and there are some red edges between IB and IC , then we can either find a monochromatic copy of T or reach a D-situati…
Figure 7
Figure 7. Figure 7: The deductions for Claim B, before finally either EM2d applies or we have a D-situation. Claim B: Suppose IA and IB cover at least t + 2 and t − 2 vertices respectively, and n − vertices in total. If there are some red edges between IA and IC , then we can either find …
Figure 8
Figure 8. Figure 8: Auxiliary graphs R and R′ used in the statement of Lemma 4.2 Let G be a graph on at most 2n vertices with a vertex partition V1 ∪ V2 ∪ · · · ∪ Vk, such that for each ij ∈ E(R), G[Vi , Vj ] is (ε, d)-regular, and for each I ∈ V (R′ ) \ {i1, i2, i3}, the sets Vi with i ∈…
Figure 9
Figure 9. Figure 9: On the left, the slight refinement of the initial reduced graph [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]
Figure 10
Figure 10. Figure 10: On the left, the initial reduced graph REM1a transformed into the subgraph used to embed the tree in Lemma 4.6. On the right, the auxiliary graph R′ EM1a used when applying Lemma 4.2. Lemma 4.6 (EM1a). Let 1/n ≪ 1/m ≪ c ≪ 1/k ≪ ε ≪ α ≪ d ≤ 1. Let T be an n-vertex tree…
Figure 11
Figure 11. Figure 11: The initial reduced graph REM1b in Lemma 4.8 on the left, and the three substructures within that we use to embed the tree in Cases I & II, Case III, and Case IV, respectively. Lemma 4.8 (EM1b). Let 1/n ≪ 1/m ≪ c ≪ 1/k ≪ ε ≪ γ ≪ α ≪ d ≤ 1. Let T be an n-vertex tree wi…
Figure 12
Figure 12. Figure 12: On the left, the transformation of the reduced graph structure used in [PITH_FULL_IMAGE:figures/full_fig_p022_12.png]
Figure 13
Figure 13. Figure 13: On the left, the transformation of the reduced graph structure used in [PITH_FULL_IMAGE:figures/full_fig_p023_13.png]
Figure 14
Figure 14. Figure 14: On the left, the transformation of the reduced graph structure used in [PITH_FULL_IMAGE:figures/full_fig_p024_14.png]
Figure 15
Figure 15. Figure 15: The initial reduced graph REM1c in Lemma 4.9 on the left, and the three substructures within used to embed the tree in Cases I & II, Case III, and Case IV, respectively. G4 In REM1c, there exist perfect matchings between each of the three pairs of sets (IA, IB), (IA,1…
Figure 16
Figure 16. Figure 16: On the left, the transformation of the reduced graph structure used in [PITH_FULL_IMAGE:figures/full_fig_p026_16.png]
Figure 17
Figure 17. Figure 17: On the left, the transformation of the reduced graph structure used in [PITH_FULL_IMAGE:figures/full_fig_p027_17.png]
Figure 18
Figure 18. Figure 18: On the left, the transformation of the reduced graph structure used in [PITH_FULL_IMAGE:figures/full_fig_p027_18.png]
Figure 19
Figure 19. Figure 19: On the left, the initial reduced graph REM2a transformed into the substructure used to embed the tree in Lemma 4.10. On the right, the auxiliary graph R′ EM2a used when applying Lemma 4.2. 2n vertices and a vertex partition V1 ∪ · · · ∪ Vk such that |V1| = |V2| = · · …
Figure 20
Figure 20. Figure 20: On the left, the initial reduced graph REM2b transformed into the substructure used to embed the tree in Lemma 4.11. On the right, the auxiliary graph R′ EM2b used when applying Lemma 4.2. Lemma 4.11 (EM2b). Let 1/n ≪ 1/m ≪ c ≪ 1/k ≪ ε ≪ η ≪ α ≪ d ≤ 1. Let T be an n-v…
Figure 21
Figure 21. Figure 21: On the left, the initial reduced graph REM2c transformed into the substructure used to embed the tree in Lemma 4.12. On the right, the auxiliary graph R′ EM2c used when applying Lemma 4.2. Lemma 4.12 (EM2c). Let 1/n ≪ 1/m ≪ c ≪ 1/k ≪ ε ≪ η ≪ α ≪ d ≤ 1. Let T be an n-v…
Figure 22
Figure 22. Figure 22: On the left, the initial reduced graph REM2d transformed into the substructure used to embed the tree in Lemma 4.13. On the right, the auxiliary graph R′ EM2d used when applying Lemma 4.2. Lemma 4.13 (EM2d). Let 1/n ≪ 1/m ≪ c ≪ 1/k ≪ ε ≪ η ≪ α ≪ d ≤ 1. Let T be an n-v…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. On the Ramsey number of a graph obtained by attaching a pendant to a path with length 1 modulo 4

    math.CO 2026-07 accept novelty 6.0 of 10

    For n ≡ 1 (mod 4), the two-colour Ramsey number of the path-with-middle-pendant tree T_n is exactly (3n+1)/2.

  2. Recent progress in graph theory using expansion

    math.CO 2026-07 accept novelty 3.0 of 10

    Sublinear expansion—weak neighbourhood growth in sparse graphs—has resolved many long-standing extremal graph theory conjectures, and this survey organizes that progress.

Reference graph

Works this paper leans on

36 extracted references · 29 canonical work pages · cited by 2 Pith papers

  1. [21]

    P. E. Haxell, T. Luczak, and P. W. Tingley. Ramsey numbers for trees of small maximum degree. Combinatorica, 22(2):287–320, 2002

    work page 2002

  2. [1]

    Balister, B

    P. Balister, B. Bollob´ as, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, and M. Tiba. Upper bounds for multicolour Ramsey numbers.arXiv:2410.17197, 2024

    arXiv 2024

  3. [2]

    Besomi, M

    G. Besomi, M. Pavez-Sign´ e, and M. Stein. Degree conditions for embedding trees.SIAM Journal on Discrete Mathematics, 33(3):1521–1555, 2019

    work page 2019

  4. [3]

    Bollob´ as.Modern Graph Theory

    B. Bollob´ as.Modern Graph Theory. Springer, 1998

    1998

  5. [4]

    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

    work page 1973

  6. [5]

    S. A. Burr. Generalized Ramsey theory for graphs - a survey. InGraphs and Combinatorics, pages 52–75. Springer, 1974

    work page 1974

  7. [6]

    S. A. Burr and P. Erd˝ os. On the magnitude of generalized Ramsey numbers for graphs. InInfinite and finite sets, pages 215–240. J´ anos Bolyai Mathematical Society, 1975

    work page 1975

  8. [7]

    S. A. Burr and P. Erd˝ os. Extremal Ramsey theory for graphs.Utilitas Mathematica, 9:247–258, 1976

    work page 1976

Show all 36 references
  1. [8]

    Campos, S

    M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe. An exponential improvement for diagonal Ramsey.arXiv:2303.09521, 2023

    2023 arXiv

  2. [9]

    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

  3. [10]

    F. F. Dub´ o and M. Stein. On the Ramsey number of the double star.Discrete Mathematics, 348(1):114227, 2025

    2025

  4. [11]

    P. Erd˝ os. Some remarks on the theory of graphs.Bulletin of the American Mathematical Society, 53(4):292–294, 1947

    1947

  5. [12]

    Erd˝ os, R

    P. Erd˝ os, R. J. Faudree, C. C. Rousseau, and R. H. Schelp. Ramsey numbers for brooms.Congressus Numerantium, 35:283–293, 1982

    1982

  6. [13]

    Erd˝ os, Z

    P. Erd˝ os, Z. F¨ uredi, M. Loebl, and V. T. S´ os. Discrepancy of trees.Studia Scientiarum Mathemati- carum Hungarica, 30(1-2):47–57, 1995

    1995

  7. [14]

    Erd˝ os and G

    P. Erd˝ os and G. Szekeres. A combinatorial problem in geometry.Compositio Mathematica, 2:463–470, 1935

    1935

  8. [15]

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

    1974

  9. [16]

    Gerencs´ er and A

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

    1967

  10. [17]

    J. W. Grossman, F. Harary, and M. Klawe. Generalized Ramsey theory for graphs, x: double stars. Discrete Mathematics, 28(3):247–254, 1979

    1979

  11. [18]

    Gupta, N

    P. Gupta, N. Ndiaye, S. Norin, and L. Wei. Optimizing the CGMS upper bound on Ramsey numbers. arXiv:2407.19026, 2024. 58

    2024 arXiv

  12. [19]

    P. Hall. On representatives of subsets.Journal of the London Mathematical Society, s1-10(1):26–30, 1935

    1935

  13. [20]

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

    1972

  14. [22]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski.Random graphs. Wiley-Interscience, 2000

    2000

  15. [23]

    Koml´ os, G

    J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi. Spanning trees in dense graphs.Combinatorics, Probability and Computing, 10(5):397–416, 2001

    2001

  16. [24]

    Koml´ os and M

    J. Koml´ os and M. Simonovits. Szemer´ edi’s Regularity Lemma and its applications in graph theory. In Combinatorics, Paul Erd˝ os is eighty, Volume 2, pages 295–352. J´ anos Bolyai Mathematical Society, 1996

    1996

  17. [25]

    Krivelevich

    M. Krivelevich. Embedding spanning trees in random graphs.SIAM Journal on Discrete Mathemat- ics, 24(4):1495–1500, 2010

    2010

  18. [26]

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

    2017

  19. [27]

    McDiarmid

    C. McDiarmid. On the method of bounded differences. InSurveys in Combinatorics, 1989, pages 148–188. Cambridge University Press, 1989

    1989

  20. [28]

    Montgomery

    R. Montgomery. Spanning trees in random graphs.Advances in Mathematics, 356:106793, 2019

    2019

  21. [29]

    Norin, Y

    S. Norin, Y. R. Sun, and Y. Zhao. Asymptotics of Ramsey numbers of double stars.arXiv:1605.03612, 2016

    2016 arXiv

  22. [30]

    Pokrovskiy

    A. Pokrovskiy. Hyperstability in the Erd˝ os-S´ os conjecture.arXiv:2409.15191, 2024

    2024 arXiv

  23. [31]

    Radziszowski

    S. Radziszowski. Small Ramsey numbers.The Electronic Journal of Combinatorics, DS1, 2024

    2024

  24. [32]

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

    1930

  25. [33]

    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

  26. [34]

    M. Stein. Tree containment and degree conditions. InDiscrete Mathematics and Applications, pages 459–486. Springer, 2020

    2020

  27. [35]

    N. C. Wormald. The differential equation method for random graph processes and greedy algorithms. InLectures on Approximation and Randomized Algorithms, pages 73–155. Polish Scientific Publishers, 1999

    1999

  28. [36]

    Y. Zhao. Proof of the (n/2−n/2−n/2) conjecture for largen.The Electronic Journal of Combina- torics, 18(1):P27, 2011. 59

    2011

Pith tools

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