pith. sign in

arxiv: 2604.15643 · v2 · submitted 2026-04-17 · 🧮 math.CO · cs.DM

On the asymptotic behavior of online Ramsey numbers for stars, paths and cycles

Sam Beilis , Israel R. Curbelo This is my paper

Pith reviewed 2026-05-10 09:12 UTC · model grok-4.3

classification 🧮 math.CO cs.DM MSC 05C5505C38
keywords online Ramsey numbersasymptoticspathscyclesstarsBuilder-Painter gamesRamsey theory
0
0 comments X

The pith

Online Ramsey numbers for fixed paths or stars against growing paths or cycles are asymptotically a constant times n.

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

The paper studies the online Ramsey game on the infinite complete graph in which Builder picks an edge each round and Painter colors it red or blue. It proves that when one graph is a fixed path P_k or star K_{1,k}, the number of rounds Builder needs to force a monochromatic copy of that graph or a growing path or cycle of size n is linear in n. Specifically, the ratios of these online Ramsey numbers to n converge to one constant λ1 when the fixed graph is a path and to a different constant λ2 when it is a star. This linearity shows that Builder can succeed with controlled, proportional effort rather than needing superlinear moves against an adversarial Painter.

Core claim

For every fixed k there exist constants λ1 and λ2 such that the limits as n tends to infinity of r̃(P_k, P_n)/n and r̃(P_k, C_n)/n both equal λ1, while the limits of r̃(K_{1,k}, P_n)/n and r̃(K_{1,k}, C_n)/n both equal λ2.

What carries the argument

The online Ramsey number r̃(G,H) counting the smallest number of Builder moves that guarantee a red G or blue H against Painter's arbitrary coloring.

If this is right

  • Builder can force the desired monochromatic copy in at most roughly λ n moves for large n.
  • The constant for fixed paths differs from the constant for fixed stars, so the two families require distinct forcing rates.
  • Paths and cycles as the growing target produce the same limiting ratio when paired with the same fixed graph.
  • The linearity holds uniformly for every fixed k.

Where Pith is reading between the lines

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

  • The same linear asymptotics may hold for other bounded-degree trees or forests.
  • Explicit numerical values of λ1 and λ2 might be found by analyzing optimal Builder strategies for small k.
  • Simulations of the game for moderate n could yield practical approximations of the constants.
  • The result suggests that the online adversarial setting inflates the Ramsey cost only by a constant factor for these sparse graphs.

Load-bearing premise

Builder possesses strategies that force the monochromatic subgraphs in a number of moves linear in n by exploiting the incremental build-up possible with paths, cycles and stars.

What would settle it

An explicit computation for some fixed k showing that the lim sup and lim inf of r̃(P_k, P_n)/n as n grows differ or that the ratio exceeds any fixed multiple of n.

Figures

Figures reproduced from arXiv: 2604.15643 by Israel R. Curbelo, Sam Beilis.

Figure 1
Figure 1. Figure 1: A Builder strategy to extend the total length of disjoint red and blue paths by 1, every 2 rounds. Builder joins the paths by choosing edge vaub, and depending on the color c1 assigned by Painter, Builder either chooses edge vaw or ubw. Proof. The proof is trivial since for any fixed graph H and any positive integer n, Builder can force either a red H or a blue Cn in at most ˜r(H, Cn) rounds, and a blue Pn… view at source ↗
Figure 2
Figure 2. Figure 2: The Builder strategy in Lemma 3.3 forces Painter to either join the two long blue paths or create a short red path. so that Bi is a blue Pa and Ri is a red Pb. In round N + 2i + 1, Builder chooses the edge vaub. Let w be an isolated vertex. If Painter colors the edge vaub blue, then in round N + 2i + 2, Builder chooses the edge ubw. If Painter colors vaub red, then in round N + 2i + 2, Builder chooses the … view at source ↗
Figure 3
Figure 3. Figure 3: A Builder strategy forcing Painter to create a blue Cn−k or a red Pk, starting with a blue CN where n − k < N ≤ n. In this example, n = 30, k = 5 and N = 28. Finally, Builder chooses the edges forming the path P = v1u1v2u2v3u3 . . . until Painter colors an edge blue. If Painter colors the first k − 1 edges red, then Builder has forced a red Pk and we are done. Hence, we may assume that Painter colors one o… view at source ↗
Figure 4
Figure 4. Figure 4: The Builder strategy in Lemma 3.5 forces Painter to either create a red star or extend a blue path by 1. be the blue Pn. Next, Builder chooses the edges forming the path P ′ = v1vnv2vn−1v3vn−2 . . . until Painter colors an edge blue. If Painter colors the first k − 1 edges red, then Builder has forced a red Pk, and we are done. So we may assume that Painter colors one of the first k −1 edges blue. Hence, w… view at source ↗
Figure 5
Figure 5. Figure 5: The Builder strategy in Lemma 3.7 forces Painter to either join two long blue paths or create a small red star. Proof. Let k and n be positive integers. We show that Builder has a strategy that forces a red K1,k or a blue Cn−2k in at most ˜r(K1,k, Pn) + 3k rounds. Builder first plays the strategy that forces a red K1,k or a blue Pn in at most r˜(K1,k, Pn) rounds. If Painter creates a red K1,k, then Builder… view at source ↗
Figure 6
Figure 6. Figure 6: The Builder strategy in Lemma 3.8 forces Painter to create a blue Cn−2k or a red K1,k, starting with a blue CN where n − k < N ≤ n. In this example, n = 20, k = 5 and N = 16. In order to prove Theorem 1.2, we show that ˜r(Pk, Cn) is eventually almost subadditive. Lemma 4.2. For any positive integers k, m and n satisfying m + n > k2 − k and n > k/2, r˜(Pk, Cm+n) ≤ r˜(Pk, Cm) + ˜r(Pk, Cn) + 9k. Proof. Let k … view at source ↗
read the original abstract

The online Ramsey game for graphs $G$ and $H$ is played on the infinite complete graph $K_\mathbb{N}$. Each round, Builder chooses an edge, and Painter colors it red or blue. The online Ramsey number $\tilde{r}(G,H)$ is the smallest integer $t$ for which Builder has a strategy that guarantees a red copy of $G$ or a blue copy of $H$ in at most $t$ rounds. We show that for every fixed $k$, there are constants $\lambda_1$ and $\lambda_2$ such that $\tilde{r}(P_k,P_n)/n$ and $\tilde{r}(P_k,C_n)/n$ converge to $\lambda_1$, and $\tilde{r}(K_{1,k},P_n)/n$ and $\tilde{r}(K_{1,k},C_n)/n$ converge to $\lambda_2$.

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 / 3 minor

Summary. The paper studies online Ramsey numbers in the Builder-Painter game on the infinite complete graph, where Builder aims to force a red copy of a fixed graph G (P_k or K_{1,k}) or a blue copy of a growing graph H_n (P_n or C_n). The central result is that for each fixed k there exist constants λ1(k) and λ2(k) such that the ratios r̃(P_k, P_n)/n, r̃(P_k, C_n)/n converge to λ1 and r̃(K_{1,k}, P_n)/n, r̃(K_{1,k}, C_n)/n converge to λ2 as n tends to infinity.

Significance. If the result holds, it establishes the linear growth rate and the existence of limiting densities for these online Ramsey numbers, which is a notable contribution to online Ramsey theory. The proof relies on explicit strategies for Builder that exploit the bounded-degree, path-like structure of the target graphs to force the monochromatic subgraphs in Θ(n) moves; the existence of the limits follows from a combination of upper-bound strategies and lower-bound Painter responses that prevent faster forcing. This supplies the first asymptotic resolution for this family of sparse versus linear targets and supplies a concrete, falsifiable prediction about the growth constants.

minor comments (3)
  1. [Introduction] The definition of the online Ramsey number r̃(G,H) in the introduction should explicitly state that t is the minimal number such that Builder has a winning strategy in at most t moves; the current wording is slightly ambiguous about whether it is the worst-case over Painter strategies.
  2. [Section 4] In the proof of the upper bound for r̃(K_{1,k},P_n), the potential function used to track the embedding of the star should be defined with an explicit formula (currently only described informally); this would make the calculation of the constant λ2 easier to verify.
  3. [Figure 1] Figure 1 (the illustration of a typical Builder strategy) has overlapping labels on the red and blue edges; increasing the font size or adding a legend would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our paper, the accurate summary of our results on the asymptotic limits of the online Ramsey numbers, and the recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No circularity: limits derived from explicit strategy bounds

full rationale

The paper proves existence of λ1 and λ2 by constructing Builder strategies that force the required monochromatic subgraphs in Θ(n) moves and establishing matching upper/lower bounds on the minimal t_n. These bounds rely on the linear structure and bounded degree of paths, cycles, and stars, without any parameter fitting, self-referential definitions, or load-bearing self-citations. The convergence statement follows directly from the strategy analysis and is not equivalent to the input assumptions by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions of online Ramsey games and graph theory without introducing new free parameters or entities; the constants λ1 and λ2 are proven to exist but not explicitly computed.

axioms (1)
  • standard math Standard axioms and definitions of graphs, paths, cycles, stars, and the online Ramsey game on the infinite complete graph.
    The result is built directly on these established concepts from combinatorial game theory.

pith-pipeline@v0.9.0 · 5456 in / 1275 out tokens · 53765 ms · 2026-05-10T09:12:59.320894+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

5 extracted references · 5 canonical work pages

  1. [1]

    [1]Adamski, G., and Bednarska-Bzde ¸ga, M.Online size Ramsey numbers: odd cycles vs connected graphs.Electron. J. Combin. 31, 3 (2024), Paper No. 3.16,

    work page 2024

  2. [2]

    Discrete Math

    [2]Adamski, G., Bednarska-Bzde ¸ga, M., and Bla ˇzej, V.Online Ramsey numbers: long versus short cycles.SIAM J. Discrete Math. 38, 4 (2024), 3150–3175. [3]Beck, J.On size Ramsey number of paths, trees, and circuits. I.J. Graph Theory 7, 1 (1983), 115–129. [4]Bednarska-Bzde ¸ga, M.Off-diagonal online size Ramsey numbers for paths.European J. Combin. 118(20...

    work page 2024

  3. [3]

    InComputer science—theory and applications, vol

    [5]Bla ˇzej, V., Dvo ˇr´ak, P., and Valla, T.On induced online Ramsey number of paths, cycles, and trees. InComputer science—theory and applications, vol. 11532 ofLecture Notes in Comput. Sci.Springer, Cham, 2019, pp. 60–69. [6]Cyman, J., Dzido, T., Lapinskas, J., and Lo, A.On-line Ramsey numbers of paths and cycles.Electron. J. Combin. 22, 1 (2015), Paper 1.15,

    work page 2019

  4. [4]

    G., and Erd ˝os, P.Some linear and some quadratic recursion formulas

    [7]De Bruijn, N. G., and Erd ˝os, P.Some linear and some quadratic recursion formulas. i. Proc. Koninklijke Nederlandse Akademie van Wetenschappen, Series A 55(1952), 374–382. [8]Erd ˝os, P., Faudree, R. J., Rousseau, C. C., and Schelp, R. H.The size Ramsey number. Period. Math. Hungar. 9, 1-2 (1978), 145–161. [9]Fekete, M. ¨Uber die verteilung der wurzel...

    work page 1952

  5. [5]

    Australas

    [13]Pra lat, P.A note on small on-line Ramsey numbers for paths and their generalization. Australas. J. Combin. 40(2008), 27–36. [14]Pra lat, P.A note on off-diagonal small on-line Ramsey numbers for paths.Ars Combin. 107(2012), 295–306. [15]Song, R., Wang, S., and Zhang, Y.Online Ramsey numbers ofK 1,3 versus paths.Discrete Appl. Math. 377(2025), 218–224...

    work page 2008