pith. sign in

arxiv: 2606.11410 · v1 · pith:7ZDPIRFNnew · submitted 2026-06-09 · 🧮 math.CO

On Balance, To What Degree is Burr's Conjecture True?

Shagnik Das , Bruce Reed , Jozef Skokan This is my paper

Pith reviewed 2026-06-27 12:15 UTC · model grok-4.3

classification 🧮 math.CO
keywords Ramsey numberstreesBurr conjecturebipartitionmaximum degreecounterexamplesasymptotic gaps
0
0 comments X

The pith

Burr's conjecture fails for lopsided trees once the larger bipartition class reaches twice the smaller one.

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

Burr conjectured that the Ramsey number of any tree equals the maximum of 2t2-1 and 2t1+t2-1 when the tree's unique bipartition has parts t1 and t2. The paper proves this equality does not hold for every tree once t2 is at least twice t1. In that regime the largest Ramsey numbers exceed the conjectured value by a quantity whose order is max(t1 squared over t2, square root of t1). When the ratio t2 over t1 is at least 500 the bound becomes exact provided the tree's maximum degree stays at most t2 minus t1, yet the same bound underestimates by at least a constant times the logarithm of t2 whenever the maximum degree approaches t2 minus t1.

Core claim

We show that there are counterexamples to Burr's conjecture whenever t2 >= 2 t1, with the difference between the largest Ramsey numbers and Burr's bound being of order max(t1^2 / t2, sqrt(t1)). Moreover, for t2 >= 500 t1, Burr's bound is tight when Delta(T) <= t2 - t1, but is off by at least C log t2 (even when t2 >= 2 t1) when Delta(T) is approximately t2 - t1.

What carries the argument

Ramsey number R(T) of a tree T whose unique bipartition has class sizes t1 <= t2, compared against Burr's candidate value max(2t2-1, 2t1+t2-1) under varying constraints on the maximum degree Delta(T).

If this is right

  • Burr's bound is never tight for any tree once t2 >= 2 t1.
  • The size of the gap scales as max(t1^2 / t2, sqrt(t1)).
  • When t2 / t1 >= 500 the bound holds exactly if and only if Delta(T) <= t2 - t1.
  • When Delta(T) is close to t2 - t1 the bound underestimates by at least C log t2, even for t2 >= 2 t1.
  • Burr's bound therefore does not hold for every t-vertex tree whose maximum degree is roughly t/3.

Where Pith is reading between the lines

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

  • The obstructions appear to be created by high-degree vertices placed near the larger part of the bipartition.
  • Similar degree thresholds relative to part sizes may govern tightness in other bounded-degree Ramsey problems.
  • Direct computation of R(T) for moderate-size lopsided trees could confirm the logarithmic gap.
  • The same degree-partition analysis might extend to certain non-tree graphs with comparable bipartitions.

Load-bearing premise

The trees admit a unique bipartition into classes of the stated sizes t1 and t2 and can be realized with the maximum-degree constraints used in the constructions.

What would settle it

An explicit tree T with t2 >= 500 t1 and Delta(T) <= t2 - t1 whose Ramsey number R(T) strictly exceeds max(2t2-1, 2t1 + t2 - 1).

read the original abstract

For many trees $T$, the Ramsey number of $T$, denoted by ${\mathcal R}(T)$, is determined by the sizes of the partition classes in its unique bipartition. In 1976, Burr proved that when $T$ has partition classes of size $t_1$ and $t_2$ with $t_1 \le t_2$, the Ramsey number is at least $\max(2t_2-1,2t_1+t_2-1)$, and conjectured that this is tight. While counterexamples have been found for some pairs $(t_1, t_2)$, a main focus of research on this problem has been determining ratios $t_2/t_1$ or bounds on the maximum degree of $T$ for which Burr's bound is either exactly or asymptotically tight. We essentially resolve these questions for lopsided trees. Specifically, we show that (a) there are counterexamples whenever $t_2 \ge 2t_1$, with the order of magnitude of the difference between the largest Ramsey numbers and Burr's bound being $\max \left( t_1^2/t_2, \sqrt{t_1} \right)$, and (b) for $t_2 \ge 500 t_1$, Burr's bound is tight when $\Delta(T) \le t_2 - t_1$, but is off by at least $C \log t_2$ (even when $t_2 \ge 2 t_1$) when $\Delta(T) \gtrsim t_2 - t_1$. In particular, this shows that Burr's bound need not hold for $t$-vertex trees $T$ with $\Delta(T) \approx t/3$.

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

0 major / 1 minor

Summary. The paper studies Burr's 1976 conjecture on Ramsey numbers R(T) for trees T with unique bipartition into classes of sizes t1 ≤ t2. Burr proved the lower bound max(2t2−1, 2t1+t2−1) and conjectured it is tight. The authors show counterexamples exist for all t2 ≥ 2t1, with the gap to the largest R(T) of order max(t1²/t2, √t1). They further prove that when t2 ≥ 500 t1 the bound is tight for all such trees with Δ(T) ≤ t2−t1, but is off by Ω(log t2) whenever Δ(T) ≳ t2−t1 (even for t2 ≥ 2t1). This implies Burr's bound fails for some t-vertex trees with Δ(T) ≈ t/3.

Significance. If the stated constructions and bounds hold, the work essentially settles the asymptotic status of Burr's conjecture in the lopsided regime (t2/t1 bounded away from 1), giving matching upper and lower bounds on the gap in two regimes separated by the maximum degree. The explicit counterexample constructions and the degree-threshold result for tightness constitute a substantial contribution to the literature on Ramsey numbers of trees.

minor comments (1)
  1. [Abstract] The specific threshold 500 in the statement 't2 ≥ 500 t1' is not motivated in the abstract; a brief remark on whether this constant arises from the proof technique or can be improved would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation to accept. Their summary correctly reflects the paper's contributions on the asymptotic status of Burr's conjecture for lopsided trees.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes its claims via explicit constructions of counterexamples for t2 >= 2t1 (with explicit gap orders max(t1^2/t2, sqrt(t1))) and matching upper-bound arguments for tightness when t2 >= 500 t1 and Delta(T) <= t2 - t1. These rest on direct tracking of bipartition sizes t1,t2 and degree constraints in the tree families under consideration. No steps reduce by definition, by fitted inputs renamed as predictions, or by load-bearing self-citations; the derivation is self-contained against the stated parameters without hidden ansatzes or imported uniqueness theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters, invented entities, or non-standard axioms are indicated in the abstract; the work relies on the standard definitions of Ramsey numbers and bipartite trees.

axioms (1)
  • standard math Standard definitions and basic properties of Ramsey numbers for graphs and the bipartition of trees.
    The entire discussion presupposes the usual combinatorial definitions of R(T) and tree bipartitions.

pith-pipeline@v0.9.1-grok · 5865 in / 1261 out tokens · 27230 ms · 2026-06-27T12:15:02.145416+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

13 extracted references · 6 canonical work pages

  1. [1]

    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

  2. [2]

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

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

  3. [3]

    Erd˝ os, R

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

    1982

  4. [4]

    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

  5. [5]

    J. W. Grossman, F. Harary, and M. Klawe. Generalized Ramsey theory for graphs. X. Double stars.Discrete Math., 28(3):247–254, 1979. doi:10.1016/0012-365X(79)90132-8

    work page doi:10.1016/0012-365x(79)90132-8 1979

  6. [6]

    P. Hall. On Representatives of Subsets.J. London Math. Soc., 10(1):26–30, 1935. doi:10.1112/jlms/s1-10.37.26

    work page doi:10.1112/jlms/s1-10.37.26 1935

  7. [7]

    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 303 ofLecture Notes in Math., pages 125–138. Springer, Berlin-New York, 1972

    1972

  8. [8]

    P. E. Haxell, T. Luczak, and P. W. Tingley. Ramsey numbers for trees of small maximum degree.Combinatorica, 22(2):287–320, 2002. doi:10.1007/s004930200014. Special issue: Paul Erd˝ os and his mathematics. 14

    work page doi:10.1007/s004930200014 2002

  9. [9]

    Hoeffding

    W. Hoeffding. Probability inequalities for sums of bounded random variables.J. Amer. Statist. Assoc., 58:13–30, 1963. URLhttp://www.jstor.org/stable/2282952

    arXiv 1963

  10. [10]

    Overview of IKAROS Mission,

    C. McDiarmid. Concentration. InProbabilistic methods for algorithmic discrete mathematics, volume 16 ofAlgorithms Combin., pages 195–248. Springer, Berlin, 1998. doi:10.1007/978-3- 662-12788-9 6

    work page doi:10.1007/978-3- 1998

  11. [11]

    Montgomery, M

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

    arXiv 2025

  12. [12]

    Norin, Y

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

    Pith/arXiv arXiv 2016

  13. [13]

    M. Stein. Tree containment and degree conditions. InDiscrete mathematics and applications, volume 165 ofSpringer Optim. Appl., pages 459–486. Springer, Cham, 2020. doi:10.1007/978- 3-030-55857-4 19. 15

    work page doi:10.1007/978- 2020