A note on the multicolor size-Ramsey numbers of connected graphs

Louis DeBiasio

arxiv: 2404.05856 · v3 · submitted 2024-04-08 · 🧮 math.CO

A note on the multicolor size-Ramsey numbers of connected graphs

Louis DeBiasio This is my paper

Pith reviewed 2026-05-24 02:02 UTC · model grok-4.3

classification 🧮 math.CO

keywords size-Ramsey numbersmulticolor Ramseyconnected graphsstarstreesvertex coverbeta parameter

0 comments

The pith

The star is the only connected graph whose multicolor size-Ramsey number grows linearly rather than quadratically in the number of edges.

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

The paper proves that the r-color size-Ramsey number of any connected graph H with m edges is at least order r squared m, except when H is a star. Krivelevich had already obtained the quadratic lower bound for graphs whose vertex cover exceeds sqrt(m), so the new work completes the picture by handling all remaining non-star connected graphs through an adaptation of the same counting method. A parallel statement holds for trees, replacing m with the parameter beta(T) that encodes the maximum degrees on each side of the bipartition, and the bound is shown to be tight up to constants for large families of trees. If the claim holds, it isolates the star as the unique exception among connected graphs in this Ramsey setting.

Core claim

We prove that hat R_r(H) equals Omega(r squared m) for every non-star connected graph H with m edges. We also prove that hat R_r(T) equals Omega(r squared beta(T)) for every tree T except the star, and that for the family of non-star trees with beta(T) equals Omega(n1 n2) the bound is tight, yielding Theta(r squared beta(T)).

What carries the argument

The r-color size-Ramsey number hat R_r(H), defined as the minimum number of edges in a host graph that forces a monochromatic copy of H in every r-edge-coloring, together with a counting argument adapted from Krivelevich to graphs with small vertex cover.

If this is right

hat R_r(H) is Omega(r squared m) for every connected non-star H with m edges.
For every tree T except the star, hat R_r(T) is Omega(r squared beta(T)).
For non-star trees satisfying beta(T) equals Omega(n1 n2), including all with linear maximum degree, the size-Ramsey number is Theta(r squared beta(T)).
The two-color case recovers the known Theta results of Beck and Dellamonica for the relevant trees.

Where Pith is reading between the lines

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

The star's linear behavior appears tied to its having vertex cover number 1, suggesting that any further exceptions would also need unusually small covers.
The same counting technique might extend to other sparse host graphs or to directed or hypergraph versions of size-Ramsey numbers.
Determining the leading constant in the Omega(r squared m) bound for specific families such as paths or cycles remains open.

Load-bearing premise

The counting argument used for large vertex cover can be adapted without change to connected graphs whose vertex cover is at most sqrt(m) provided they are not stars.

What would settle it

A concrete non-star connected graph H with m edges such that some host graph with o(r squared m) edges admits an r-edge-coloring with no monochromatic copy of H would falsify the lower bound.

read the original abstract

The $r$-color size-Ramsey number of a graph $H$, denoted by $\widehat{R}_r(H)$, is the minimum number of edges in a graph $G$ having the property that every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H$. Krivelevich proved that $\widehat{R}_r(P_{m+1})=\Omega(r^2m)$ where $P_{m+1}$ is the path on $m$ edges. He explains that his proof actually applies to any connected graph $H$ with $m$ edges and vertex cover number larger than $\sqrt{m}$. He also notes that some restriction on the vertex cover number is necessary since the star with $m$ edges, $K_{1,m}$, has vertex cover number 1 and satisfies $\widehat{R}_r(K_{1,m})=r(m-1)+1$. We prove that the star is actually the only exception; that is, $\widehat{R}_r(H)=\Omega(r^2m)$ for every non-star connected graph $H$ with $m$ edges. We also prove a strengthening of this result for trees. It follows from results of Beck and Dellamonica that $\widehat{R}_2(T)=\Theta(\beta(T))$ for every tree $T$ with bipartition $\{V_1, V_2\}$ and $\beta(T)=|V_1|\max\{d(v):v\in V_1\}+|V_2|\max\{d(v):v\in V_2\}$. We prove that $\widehat{R}_r(T)=\Omega(r^2\beta(T))$ for every tree $T$, again with the exception of the star. Additionally, we prove that for the family of non-star trees $T$ with $\beta(T)=\Omega(n_1n_2)$ (which includes all non-star trees of linear maximum degree and all trees of radius 2 for example) we have $\widehat{R}_r(T)=\Theta(r^2\beta(T))$.

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.

Desk Editor's Note private letter to a colleague

This note shows stars are the only connected exception to the Omega(r^2 m) lower bound for multicolor size-Ramsey numbers.

read the letter

The main thing to know is that the paper establishes stars as the unique connected exception in multicolor size-Ramsey theory. Specifically, for any connected graph H that is not a star with m edges, the r-color size-Ramsey number is at least on the order of r squared times m. This resolves the growth rate question left open after Krivelevich's work on paths and large vertex cover graphs. The star was already known to be linear, so the classification is the new piece. The tree strengthening using beta(T) is also new, giving Omega(r^2 beta(T)) for non-star trees and Theta bounds for families like radius-2 trees or those with linear maximum degree. This builds cleanly on Beck and Dellamonica without extra assumptions. The paper does well by extending the existing combinatorial counting arguments from the cited results. The lower bounds come directly from adaptations of Krivelevich, Beck, and Dellamonica, with no circularity or fitted parameters. The claims line up with what those earlier papers established. The only soft spot is the adaptation of the counting argument to connected non-star graphs with vertex cover at most sqrt(m). Krivelevich needed large cover, so this case requires a modified structural property tied to connectedness and non-star status. The abstract indicates the proof exists, and the manuscript presumably supplies the details, but that step is the one worth checking for any gaps in coverage. This paper is for researchers in extremal combinatorics who work on Ramsey-type problems and size-Ramsey numbers. A reader familiar with the background will find the classification and the tree bounds useful. It is important enough and the evidence is sharp enough to merit peer review, even if some revisions clarify the small-cover case. I would send it to referees.

Referee Report

2 major / 2 minor

Summary. The paper proves that the multicolor size-Ramsey number satisfies hat R_r(H) = Omega(r^2 m) for every connected non-star graph H with m edges, establishing that stars are the sole exception to the quadratic lower bound previously shown by Krivelevich only for graphs with vertex-cover number > sqrt(m). It further strengthens the result for trees by showing hat R_r(T) = Omega(r^2 beta(T)) except for stars, with matching Theta(r^2 beta(T)) bounds for the subfamily of non-star trees where beta(T) = Omega(n1 n2).

Significance. If the central lower-bound claims hold, the work completes the classification of connected graphs by their size-Ramsey growth rate, showing that only stars admit a linear-in-r construction while all other connected graphs require quadratic dependence on r. The extension of combinatorial counting arguments from Krivelevich, Beck, and Dellamonica supplies the technical core; the tree results give explicit tight bounds for natural families (linear maximum degree, radius-2 trees).

major comments (2)

[Abstract and proof of main theorem for small vertex cover] Abstract (paragraph beginning 'We prove that the star is actually the only exception') and the corresponding proof section for the tau(H) <= sqrt(m) case: the adaptation of Krivelevich's counting argument to connected non-star graphs with small vertex cover is the load-bearing step for the Omega(r^2 m) claim, yet the manuscript must explicitly identify the structural replacement (beyond connectedness and non-star) for the large-cover hypothesis; without this, it is unclear whether the argument covers all such graphs (e.g., certain radius-2 trees or double stars).
[Section on trees and beta(T)] Tree strengthening (the paragraph on hat R_r(T) = Omega(r^2 beta(T))): the lower-bound argument for non-star trees must be checked against the same small-cover issue, since many trees have tau(T) = 1 or small; the manuscript should state whether the beta(T)-based counting inherits the same adaptation or uses a separate counting.

minor comments (2)

[Abstract] Notation: ensure consistent use of hat R_r versus widehat{R}_r throughout; the abstract mixes both.
[Introduction] The citation to Krivelevich should include the precise theorem number being extended.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The two major comments both concern the clarity of how the counting argument is adapted for the small vertex-cover case; we agree that explicit identification of the replacement structure will strengthen the presentation. We address each point below and will incorporate the suggested clarifications.

read point-by-point responses

Referee: Abstract (paragraph beginning 'We prove that the star is actually the only exception') and the corresponding proof section for the tau(H) <= sqrt(m) case: the adaptation of Krivelevich's counting argument to connected non-star graphs with small vertex cover is the load-bearing step for the Omega(r^2 m) claim, yet the manuscript must explicitly identify the structural replacement (beyond connectedness and non-star) for the large-cover hypothesis; without this, it is unclear whether the argument covers all such graphs (e.g., certain radius-2 trees or double stars).

Authors: We agree that the adaptation step would benefit from an explicit statement of the structural property that replaces the large vertex-cover hypothesis. In the proof, connectedness together with the non-star assumption guarantees the existence of a path of length three whose middle edge is not incident to a minimum vertex cover; this configuration supplies the necessary counting leverage in place of a large cover. The same property holds for all radius-2 trees and double stars that are non-stars. We will revise the proof section (and the abstract paragraph) to state this replacement explicitly and to verify coverage for the cited families. revision: yes
Referee: Tree strengthening (the paragraph on hat R_r(T) = Omega(r^2 beta(T))): the lower-bound argument for non-star trees must be checked against the same small-cover issue, since many trees have tau(T) = 1 or small; the manuscript should state whether the beta(T)-based counting inherits the same adaptation or uses a separate counting.

Authors: The Omega(r^2 beta(T)) lower bound is obtained by applying the same adapted counting argument developed for the main theorem, specialized to the bipartition and degree maxima that define beta(T). Because every non-star tree satisfies the hypotheses of the main result, the beta version inherits the identical structural replacement (the length-three path configuration). We will add a short clarifying sentence in the tree section stating that the argument is inherited rather than separate, thereby addressing the small-cover concern uniformly. revision: yes

Circularity Check

0 steps flagged

No circularity; proof extends independent external combinatorial arguments

full rationale

The claimed Omega(r^2 m) lower bound is obtained by adapting Krivelevich's counting argument (external citation) to the complementary structural case of connected non-star graphs with tau(H) <= sqrt(m). The tree strengthening likewise invokes Beck-Dellamonica results (external) for the upper bound and supplies a new lower-bound argument. No self-citations appear, no parameter is fitted then renamed as a prediction, and no equation reduces to its own input by definition. The derivation chain therefore remains non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definitions of size-Ramsey numbers, vertex cover, and the bipartition parameter beta together with the external theorems of Krivelevich, Beck, and Dellamonica; no free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (1)

standard math Standard axioms and definitions of finite graphs, edge colorings, and Ramsey numbers
Invoked throughout the abstract in the definitions of hat R_r(H) and beta(T).

pith-pipeline@v0.9.0 · 5912 in / 1301 out tokens · 34870 ms · 2026-05-24T02:02:04.281944+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that the star is actually the only exception; that is, hat R_r(H)=Omega(r^2 m) for every non-star connected graph H with m edges.
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Krivelevich proved that hat R_r(P_{m+1})=Omega(r^2 m) ... applies to any connected graph H with m edges and vertex cover number larger than sqrt(m)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Bal and L

D. Bal and L. DeBiasio. New lower bounds on the size-Ramsey number of a path. The Electronic Journal of Combinatorics , pages P1–18, 2022

work page 2022
[2]

D. Bal, L. DeBiasio, and E. Oren-Dahan. On the multicolor Ramsey numbers of balanced double stars. arXiv preprint arXiv:2403.05677 , 2024

work page arXiv 2024
[3]

J. Beck. On size Ramsey number of paths, trees and circuits. II. Mathematics of Ramsey theory, pages 34–45, 1990

work page 1990
[4]

Chernoff

H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics , pages 493–507, 1952

work page 1952
[5]

Dellamonica Jr

D. Dellamonica Jr. The size-Ramsey number of trees. Random Structures & Algo- rithms, 40(1):49–73, 2012

work page 2012
[6]

Dudek and P

A. Dudek and P. Pra lat. On some multicolor Ramsey properties of random graphs. SIAM Journal on Discrete Mathematics , 31(3):2079–2092, 2017

work page 2079
[7]

Dudek and P

A. Dudek and P. Pra lat. Note on the multicolour size-Ramsey number for paths. The Electronic Journal of Combinatorics , pages P3–35, 2018

work page 2018
[8]

Friedman and N

J. Friedman and N. Pippenger. Expanding graphs contain all small trees. Combina- torica, 7:71–76, 1987

work page 1987
[9]

Gy´ arf´ as

A. Gy´ arf´ as. Large monochromatic components in edge colorings of graphs: a survey. Ramsey Theory: Yesterday, Today, and Tomorrow , pages 77–96, 2011. 14

work page 2011
[10]

J. H. Hattingh and E. J. Joubert. Some bistar bipartite Ramsey numbers. Graphs and Combinatorics, 30(5):1175–1181, 2014

work page 2014
[11]

P. E. Haxell and Y. Kohayakawa. The size-Ramsey number of trees. Israel Journal of Mathematics, 89(1):261–274, 1995

work page 1995
[12]

X. Ke. The size Ramsey number of trees with bounded degree. Random Structures & Algorithms, 4(1):85–97, 1993

work page 1993
[13]

Krivelevich

M. Krivelevich. Expanders—how to find them, and what to find in them. In Surveys in Combinatorics 2019 , volume 456 of London Math. Soc. Lecture Note Ser. , pages 115–142. Cambridge Univ. Press, Cambridge, 2019

work page 2019
[14]

Krivelevich

M. Krivelevich. Long cycles in locally expanding graphs, with applications. Combi- natorica, 39(1):135–151, 2019

work page 2019
[15]

McDiarmid

C. McDiarmid. On the method of bounded differences. Surveys in Combinatorics , 141(1):148–188, 1989

work page 1989
[16]

McDiarmid

C. McDiarmid. Concentration. In Probabilistic methods for algorithmic discrete math- ematics, pages 195–248. Springer, 1998. 15 7 Appendix: An upper bound on the size-Ramsey numbers of bounded degree trees As mentioned in the introduction, Krivelevich [13] proved that bRr(Pn) = O(r2(log r)n). However, his method of proof is more general and (after an appr...

work page 1998
[17]

Thus by Theorem 7.1, G′ 1 contains a copy of T

with |X| ≤ 2n satisfies |NG′ 1 (X) \ X| ≥ ∆|X|. Thus by Theorem 7.1, G′ 1 contains a copy of T . 17

work page

[1] [1]

Bal and L

D. Bal and L. DeBiasio. New lower bounds on the size-Ramsey number of a path. The Electronic Journal of Combinatorics , pages P1–18, 2022

work page 2022

[2] [2]

D. Bal, L. DeBiasio, and E. Oren-Dahan. On the multicolor Ramsey numbers of balanced double stars. arXiv preprint arXiv:2403.05677 , 2024

work page arXiv 2024

[3] [3]

J. Beck. On size Ramsey number of paths, trees and circuits. II. Mathematics of Ramsey theory, pages 34–45, 1990

work page 1990

[4] [4]

Chernoff

H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics , pages 493–507, 1952

work page 1952

[5] [5]

Dellamonica Jr

D. Dellamonica Jr. The size-Ramsey number of trees. Random Structures & Algo- rithms, 40(1):49–73, 2012

work page 2012

[6] [6]

Dudek and P

A. Dudek and P. Pra lat. On some multicolor Ramsey properties of random graphs. SIAM Journal on Discrete Mathematics , 31(3):2079–2092, 2017

work page 2079

[7] [7]

Dudek and P

A. Dudek and P. Pra lat. Note on the multicolour size-Ramsey number for paths. The Electronic Journal of Combinatorics , pages P3–35, 2018

work page 2018

[8] [8]

Friedman and N

J. Friedman and N. Pippenger. Expanding graphs contain all small trees. Combina- torica, 7:71–76, 1987

work page 1987

[9] [9]

Gy´ arf´ as

A. Gy´ arf´ as. Large monochromatic components in edge colorings of graphs: a survey. Ramsey Theory: Yesterday, Today, and Tomorrow , pages 77–96, 2011. 14

work page 2011

[10] [10]

J. H. Hattingh and E. J. Joubert. Some bistar bipartite Ramsey numbers. Graphs and Combinatorics, 30(5):1175–1181, 2014

work page 2014

[11] [11]

P. E. Haxell and Y. Kohayakawa. The size-Ramsey number of trees. Israel Journal of Mathematics, 89(1):261–274, 1995

work page 1995

[12] [12]

X. Ke. The size Ramsey number of trees with bounded degree. Random Structures & Algorithms, 4(1):85–97, 1993

work page 1993

[13] [13]

Krivelevich

M. Krivelevich. Expanders—how to find them, and what to find in them. In Surveys in Combinatorics 2019 , volume 456 of London Math. Soc. Lecture Note Ser. , pages 115–142. Cambridge Univ. Press, Cambridge, 2019

work page 2019

[14] [14]

Krivelevich

M. Krivelevich. Long cycles in locally expanding graphs, with applications. Combi- natorica, 39(1):135–151, 2019

work page 2019

[15] [15]

McDiarmid

C. McDiarmid. On the method of bounded differences. Surveys in Combinatorics , 141(1):148–188, 1989

work page 1989

[16] [16]

McDiarmid

C. McDiarmid. Concentration. In Probabilistic methods for algorithmic discrete math- ematics, pages 195–248. Springer, 1998. 15 7 Appendix: An upper bound on the size-Ramsey numbers of bounded degree trees As mentioned in the introduction, Krivelevich [13] proved that bRr(Pn) = O(r2(log r)n). However, his method of proof is more general and (after an appr...

work page 1998

[17] [17]

Thus by Theorem 7.1, G′ 1 contains a copy of T

with |X| ≤ 2n satisfies |NG′ 1 (X) \ X| ≥ ∆|X|. Thus by Theorem 7.1, G′ 1 contains a copy of T . 17

work page