pith. sign in

arxiv: 2606.02389 · v1 · pith:SFMZFF5Snew · submitted 2026-06-01 · 🧮 math.CO

A degree version of the Burr-ErdH{o}s conjecture on trees

Jasmin Katz , Mat\'ias Pavez-Sign\'e , Jozef Skokan This is my paper

Pith reviewed 2026-06-28 13:50 UTC · model grok-4.3

classification 🧮 math.CO
keywords Burr-Erdős conjecturetreesminimum degreeRamsey numbersmonochromatic copiesedge coloringsbounded degree
0
0 comments X

The pith

Any graph on 2n vertices with minimum degree at least three-quarters of its order forces a monochromatic copy of every bounded-degree n-vertex tree in any 2-edge-coloring.

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

The paper proves Schelp's degree version of the Burr-Erdős conjecture on trees in a strong form. It establishes that the minimum-degree condition of floor(3N/4) suffices to guarantee monochromatic copies of all n-vertex trees with maximum degree at most any fixed Delta, even when the host graph has exactly N = 2n vertices and no extra epsilon n slack is present. A sympathetic reader would care because this removes the size buffer in the host graph, showing the degree condition alone works at the boundary size tied to the original conjecture's 2n-2 Ramsey bound.

Core claim

The central claim is that for every Delta greater than or equal to 2, every graph G on N greater than or equal to 2n vertices with minimum degree at least floor(3N/4) has the property that every 2-edge-coloring of G contains a monochromatic copy of every n-vertex tree with maximum degree at most Delta.

What carries the argument

The floor(3N/4) minimum-degree threshold on a host graph of order at least 2n, which carries the argument by enabling monochromatic embeddings of all bounded-degree trees.

If this is right

  • The extra epsilon n term in the host-graph size is unnecessary.
  • The monochromatic-tree guarantee holds at the exact conjectured size N = 2n.
  • The result applies uniformly for every fixed maximum degree bound Delta greater than or equal to 2.

Where Pith is reading between the lines

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

  • The same degree threshold may suffice for other sparse host graphs in related Ramsey settings.
  • Techniques developed here could be tested on trees whose maximum degree grows with n.
  • The boundary case N = 2n might allow removal of the bounded-degree restriction in some extensions.

Load-bearing premise

An embedding technique succeeds exactly at the three-quarters minimum-degree threshold without requiring extra slack vertices.

What would settle it

A single graph on exactly 2n vertices with minimum degree floor(3N/4) and a 2-edge-coloring that avoids a monochromatic copy of some n-vertex tree with maximum degree at most Delta would disprove the claim.

Figures

Figures reproduced from arXiv: 2606.02389 by Jasmin Katz, Jozef Skokan, Mat\'ias Pavez-Sign\'e.

Figure 1
Figure 1. Figure 1: In this picture is depicted the extremal colouring, where, for [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
read the original abstract

An old conjecture of Burr and Erd\H os states that the Ramsey number of any $n$-vertex tree $T$ is at most $2n-2$. In 2012, Schelp asked whether a degree version of the Burr--Erd\H{o}s conjecture holds. More precisely, Schelp asked if is it true that for any $\varepsilon>0$ and $\Delta\ge 2$, if $G$ is a graph on $N\ge (2+\varepsilon)n$ vertices and minimum degree $\delta(G)\ge \lfloor 3N/4\rfloor$, then every blue/red colouring of the edges of $G$ yields a monochromatic copy of each $n$-vertex tree with maximum degree at most $\Delta$. We prove this conjecture in a strong form, showing that it is true even if one removes the extra $\varepsilon n$ term in the size of the host graph.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 1 minor

Summary. The manuscript proves a strong form of Schelp's degree version of the Burr-Erdős conjecture: for every Δ ≥ 2, every n-vertex tree T with maximum degree at most Δ, and every 2-edge-coloring of an N-vertex graph G with N = 2n and δ(G) ≥ ⌊3N/4⌋, G contains a monochromatic copy of T.

Significance. If correct, the result is significant: it resolves the degree analogue of the Burr-Erdős conjecture at the exact numerical threshold N = 2n without an εn slack term, yielding a sharp, parameter-free statement for bounded-degree trees in 2-colored graphs under a minimum-degree condition.

major comments (1)
  1. [Main embedding argument (post-abstract proof section)] The central claim requires an embedding argument that succeeds with zero slack precisely at δ(G) = ⌊3N/4⌋ and N = 2n. Standard tree-embedding or regularity lemmas in this area typically produce o(N) error terms that are absorbed only by taking N ≥ (2 + ε)n or δ > (3/4 + ε)N; the manuscript must demonstrate explicitly how all such error terms are cancelled or avoided while remaining inside the exact threshold (see the main embedding lemma after the abstract).
minor comments (1)
  1. Clarify the precise statement of the result for even/odd n in the definition of ⌊3N/4⌋ to avoid ambiguity in the threshold.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of the result's significance and for the detailed comment on the embedding argument. We address the major comment point by point below.

read point-by-point responses

  1. Referee: [Main embedding argument (post-abstract proof section)] The central claim requires an embedding argument that succeeds with zero slack precisely at δ(G) = ⌊3N/4⌋ and N = 2n. Standard tree-embedding or regularity lemmas in this area typically produce o(N) error terms that are absorbed only by taking N ≥ (2 + ε)n or δ > (3/4 + ε)N; the manuscript must demonstrate explicitly how all such error terms are cancelled or avoided while remaining inside the exact threshold (see the main embedding lemma after the abstract).

    Authors: Our proof of the main embedding result (Lemma 3.2) deliberately avoids regularity lemmas and standard blow-up arguments that introduce o(N) slack. Instead, it proceeds by induction on the number of vertices in the target tree T, combined with a direct greedy embedding that tracks the exact number of available blue and red neighbors under the minimum-degree hypothesis δ(G) ≥ ⌊3N/4⌋. At each step the degree condition guarantees that the number of candidate vertices in the appropriate color class is at least the number required by the remaining tree, with equality cases handled by a separate potential-function argument that uses the global relation N = 2n to cancel any local deficit. Because the host graph size is exactly twice the tree order, the total number of vertices removed in previous steps is accounted for exactly rather than asymptotically. We acknowledge that the current write-up of this cancellation could be expanded for clarity and will add a short dedicated paragraph (or subsection) immediately after the statement of Lemma 3.2 that isolates the zero-slack bookkeeping. revision: yes

Circularity Check

0 steps flagged

No circularity: independent proof of external conjecture

full rationale

The paper states a proof of Schelp's 2012 conjecture (an external claim) in strengthened form, removing the εn slack from the host graph size. No self-citations, fitted parameters, or ansatzes are invoked as load-bearing steps in the provided abstract or description. The central claim is a direct embedding result at the exact threshold δ(G) ≥ ⌊3N/4⌋ for N=2n, presented without reduction to prior author work or redefinition of inputs. This matches the default expectation of a non-circular derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no free parameters, invented entities, or non-standard axioms are mentioned. Relies on standard graph-theoretic background.

axioms (1)
  • standard math Standard axioms and definitions of graph theory, edge colorings, and Ramsey numbers for trees.
    The statement is phrased entirely in classical combinatorial terms.

pith-pipeline@v0.9.1-grok · 5695 in / 1202 out tokens · 37050 ms · 2026-06-28T13:50:26.218292+00:00 · methodology

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

38 extracted references · 31 canonical work pages · 1 internal anchor

  1. [1]

    Arag˜ ao, J

    L. Arag˜ ao, J. P. Marciano, and W. Mendon¸ ca. Degree conditions for Ramsey goodness of paths. European J. Combin., 124:Paper No. 104082, 2025. doi:10.1016/j.ejc.2024.104082

    work page doi:10.1016/j.ejc.2024.104082 2025

  2. [2]

    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, 2024, arxiv:2410.17197. doi:10.48550/arXiv.2410.17197

    work page doi:10.48550/arxiv.2410.17197 2024

  3. [3]

    Balogh, A

    J. Balogh, A. Freschi, and A. Treglown. Ramsey-type problems for tilings in dense graphs.European J. Combin., 131:Paper No. 104228, 2026. doi:10.1016/j.ejc.2025.104228

    work page doi:10.1016/j.ejc.2025.104228 2026

  4. [4]

    Balogh, A

    J. Balogh, A. Kostochka, M. Lavrov, and X. Liu. Monochromatic paths and cycles in 2-edge- coloured graphs with large minimum degree.Combin. Probab. Comput., 31(1):109–122, 2022. doi:10.1017/s0963548321000201

    work page doi:10.1017/s0963548321000201 2022

  5. [5]

    F. S. Benevides, T. Luczak, A. Scott, J. Skokan, and M. White. Monochromatic cycles in 2-coloured graphs.Combin. Probab. Comput., 21(1-2):57–87, 2012. doi:10.1017/S0963548312000090

    work page doi:10.1017/s0963548312000090 2012

  6. [6]

    Besomi, M

    G. Besomi, M. Pavez-Sign´ e, and M. Stein. Degree conditions for embedding trees.SIAM J. Discrete Math., 33(3):1521–1555, 2019. doi:10.1137/18M1210861

    work page doi:10.1137/18m1210861 2019

  7. [7]

    Bondy and P

    J. Bondy and P. Erd˝ os. Ramsey numbers for cycles in graphs.J. Combin. Theory Ser. B, 14:46–54,

  8. [8]

    doi:10.1016/s0095-8956(73)80005-x

    work page doi:10.1016/s0095-8956(73)80005-x

  9. [9]

    J. A. Bondy. Pancyclic graphs. I.J. Combin. Theory Ser. B, 11:80–84, 1971. doi:10.1016/0095- 8956(71)90016-5

    work page doi:10.1016/0095- 1971

  10. [10]

    B¨ ottcher, J

    J. B¨ ottcher, J. Hladk` y, and D. Piguet. The tripartite Ramsey number for trees.J. Graph Theory, 69(3):264–300, 2012. doi:10.1002/jgt.20582

    work page doi:10.1002/jgt.20582 2012

  11. [11]

    B¨ ottcher, R

    J. B¨ ottcher, R. Montgomery, O. Parczyk, and Y. Person. Embedding spanning bounded degree graphs in randomly perturbed graphs.Mathematika, 66(2):422–447, 2020. doi:10.1112/mtk.12005

    work page doi:10.1112/mtk.12005 2020

  12. [12]

    Buci´ c and B

    M. Buci´ c and B. Sudakov. Tight Ramsey bounds for multiple copies of a graph.Adv. Comb., 1:22pp., 3 Feb 2023. doi:10.19086/aic.2023.1

    work page doi:10.19086/aic.2023.1 2023

  13. [13]

    S. A. Burr. Generalized Ramsey theory for graphs—a survey. InGraphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), volume Vol. 406 ofLecture Notes in Math., pages 52–75. Springer, Berlin-New York, 1974

    1973

  14. [14]

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

    1976

  15. [15]

    Campos, S

    M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe. An exponential improvement for diagonal Ramsey.Ann. of Math. (2), 2025. doi:10.48550/arXiv.2303.09521. to appear

    work page doi:10.48550/arxiv.2303.09521 2025

  16. [16]

    Chen and A

    Y. Chen and A. Lo. Embedding loose trees ink-uniform hypergraphs, 2025, arXiv:2502.04783. doi:10.48550/arXiv.2502.04783

    work page doi:10.48550/arxiv.2502.04783 2025

  17. [17]

    G. A. Dirac. Some theorems on abstract graphs.Proc. London Math. Soc. (3), 2:69–81, 1952. doi:10.1112/plms/s3-2.1.69

    work page doi:10.1112/plms/s3-2.1.69 1952

  18. [18]

    F. F. Dub´ o and M. Stein. On the Ramsey number of the double star.Discrete Math., 348(1):Paper No. 114227, 4, 2025. doi:10.1016/j.disc.2024.114227

    work page doi:10.1016/j.disc.2024.114227 2025

  19. [19]

    R. J. Faudree and R. H. Schelp. All Ramsey numbers for cycles in graphs.Discrete Math., 8(4):313– 329, 1974. doi:10.1016/0012-365X(74)90151-4

    work page doi:10.1016/0012-365x(74)90151-4 1974

  20. [20]

    Gerencs´ er and A

    L. Gerencs´ er and A. Gy´ arf´ as. On Ramsey-type problems.Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math., 10:167–170, 1967

    1967

  21. [21]

    Gupta, N

    P. Gupta, N. Ndiaye, S. Norin, and L. Wei. Optimizing the CGMS upper bound on Ramsey numbers, 2024, arxiv:2407.19026. doi:10.48550/arXiv.2407.19026. 28

    work page doi:10.48550/arxiv.2407.19026 2024

  22. [22]

    Gy´ arf´ as and G

    A. Gy´ arf´ as and G. N. S´ ark¨ ozy. Star versus two stripes Ramsey numbers and a conjecture of Schelp. Combin. Probab. Comput., 21(1-2):179–186, 2012. doi:10.1017/S0963548311000599

    work page doi:10.1017/s0963548311000599 2012

  23. [23]

    F. Harary. Recent results on generalized Ramsey theory for graphs. InGraph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), volume Vol. 303 ofLecture Notes in Math., pages 125–138. Springer, Berlin-New York, 1972

    1972

  24. [24]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski.Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. doi:10.1002/9781118032718

    work page doi:10.1002/9781118032718 2000

  25. [25]

    Kathapurkar and R

    A. Kathapurkar and R. Montgomery. Spanning trees in dense directed graphs.J. Combin. Theory Ser. B, 156:223–249, 2022. doi:10.1016/j.jctb.2022.04.007

    work page doi:10.1016/j.jctb.2022.04.007 2022

  26. [26]

    Koml´ os, G

    J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi. Spanning trees in dense graphs.Combin. Probab. Comput., 10(5):397–416, 2001. doi:10.1017/S0963548301004849

    work page doi:10.1017/s0963548301004849 2001

  27. [27]

    H. Li, V. Nikiforov, and R. H. Schelp. A new class of Ramsey-Tur´ an problems.Discrete Math., 310(24):3579–3583, 2010. doi:10.1016/j.disc.2010.09.009

    work page doi:10.1016/j.disc.2010.09.009 2010

  28. [28]

    Luczak.R(C n, Cn, Cn)≤(4 +o(1))n.J

    T. Luczak.R(C n, Cn, Cn)≤(4 +o(1))n.J. Combin. Theory Ser. B, 75(2):174–187, 1999. doi:10.1006/jctb.1998.1874

    work page doi:10.1006/jctb.1998.1874 1999

  29. [29]

    McDiarmid

    C. McDiarmid. On the method of bounded differences. InSurveys in combinatorics, 1989 (Norwich, 1989), volume 141 ofLondon Math. Soc. Lecture Note Ser., pages 148–188. Cambridge Univ. Press, Cambridge, 1989

    1989

  30. [30]

    Montgomery, M

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

    work page doi:10.48550/arxiv.2509.07934 2025

  31. [31]

    Nikiforov and R

    V. Nikiforov and R. Schelp. Cycles and stability.J. Combin. Theory Ser. B, 98(1):69–84, 2008. doi:10.1016/j.jctb.2007.05.001

    work page doi:10.1016/j.jctb.2007.05.001 2008

  32. [32]

    Asymptotics of Ramsey numbers of double stars

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

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1605.03612 2016

  33. [33]

    Pokrovskiy, L

    A. Pokrovskiy, L. Versteegen, and E. Williams. Embedding trees using minimum and maximum degree conditions, 2025, arXiv:2512.16799. doi:10.48550/arXiv.2512.16799

    work page doi:10.48550/arxiv.2512.16799 2025

  34. [34]

    F. P. Ramsey. On a Problem of Formal Logic.Proc. London Math. Soc. (2), 30(4):264–286, 1929. doi:10.1112/plms/s2-30.1.264

    work page doi:10.1112/plms/s2-30.1.264 1929

  35. [35]

    V. Rosta. On a Ramsey-type problem of J. A. Bondy and P. Erd˝ os. I, II.J. Combinatorial Theory Ser. B, 15(1):94–104; ibid. 15 (1973), 105–120, 1973. doi:10.1016/0095-8956(73)90035-x

    work page doi:10.1016/0095-8956(73)90035-x 1973

  36. [36]

    R. H. Schelp. Some Ramsey-Tur´ an type problems and related questions.Discrete Math., 312(14):2158–2161, 2012. doi:10.1016/j.disc.2011.09.015

    work page doi:10.1016/j.disc.2011.09.015 2012

  37. [37]

    N. C. Wormald. The differential equation method for random graph processes and greedy algorithms. In M. Karo´ nski and H. J. Pr¨ omel, editors,Lectures on approximation and randomized algorithms, pages 73–155. Wydawnictwo Naukowe Pwn, 1999

    1999

  38. [38]

    Y. Zhao. Proof of the (n/2−n/2−n/2) conjecture for largen.Electron. J. Combin., 18(1):Paper 27, 61pp., 2011. doi:10.37236/514. 29

    work page doi:10.37236/514 2011