pith. sign in

arxiv: 2605.16607 · v1 · pith:ZZY2K4EYnew · submitted 2026-05-15 · 🧮 math.CO

Recursive upper bounds for the vertex online Ramsey game with applications to hypergraph Ramsey numbers

D\'aniel Dob\'ak , Eion Mulrenin This is my paper

Pith reviewed 2026-05-20 16:01 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypergraph Ramsey numbersvertex online Ramsey numbersrecursive upper boundsErdős-Rado theoremRamsey theoryonline gamesk-uniform hypergraphs
0
0 comments X

The pith

Hypergraph vertex online Ramsey numbers satisfy a recurrence with a (1+o(1)) factor in the exponent.

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

The paper generalizes vertex online Ramsey numbers from graphs to k-uniform hypergraphs. It proves that these numbers, written tilde r_k(s,t), obey the upper bound two raised to the power of one plus little-o of one times the previous level tilde r_{k-1}(s-1,t-1). This replaces the much larger binomial exponent in the classical Erdős-Rado recurrence for hypergraph Ramsey numbers. A sympathetic reader would care because the change produces modestly tighter upper estimates on the smallest size that forces a monochromatic clique in any two-coloring of the edges.

Core claim

The natural hypergraph generalization tilde r_k(s,t) of the vertex online Ramsey numbers satisfies tilde r_k(s,t) ≤ 2^{(1+o(1)) tilde r_{k-1}(s-1,t-1)} for 2 ≤ k < s ≤ t. The bound is obtained by exhibiting a recursive strategy in the vertex online Ramsey game on hypergraphs whose analysis incurs only a (1+o(1)) factor in the exponent, extending the earlier graph-case argument of Conlon, Fox, and Sudakov without extra losses from higher uniformity.

What carries the argument

The recursive strategy in the vertex online Ramsey game played on k-uniform hypergraphs, which controls the growth of the Ramsey number level by level and produces the linear factor in the exponent.

Load-bearing premise

That the vertex online Ramsey game on hypergraphs admits a recursive strategy whose analysis produces only a (1+o(1)) factor in the exponent, extending the graph-case argument without additional losses.

What would settle it

An explicit computation or tighter upper bound for tilde r_3(s,t) with small s and t that forces the ratio of log base two of the number to tilde r_2(s-1,t-1) to exceed any fixed constant greater than one.

read the original abstract

The classical recursive upper bound on hypergraph Ramsey numbers due to Erd\H{o}s and Rado states that for $2 \leq k < s \leq t$, \[ r_k(s,t) \leq 2^{\binom{r_{k-1}(s-1,t-1)}{k-1}}. \] In 2010, Conlon, Fox, and Sudakov introduced the so-called vertex online Ramsey numbers $\tilde{r}(s,t)$ for graphs to obtain a quantitative improvement over this bound when $k=3$. In this note, we show that the natural hypergraph generalization $\tilde{r}_k(s,t)$ of the vertex online Ramsey numbers satisfy an improved recurrence \[ \tilde{r}_k(s,t) \leq 2^{(1+o(1))\tilde{r}_{k-1}(s-1,t-1)}. \] We obtain several corollaries from this, including a lower-order improvement to the best known quantitative upper bounds for hypergraph Ramsey numbers and an improvement to the above recursive bound of Erd\H{o}s and Rado.

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

Summary. The manuscript defines the hypergraph vertex online Ramsey numbers tilde r_k(s,t) and proves the improved recurrence tilde r_k(s,t) ≤ 2^{(1+o(1)) tilde r_{k-1}(s-1,t-1)} for 2 ≤ k < s ≤ t. This is obtained by adapting the Conlon-Fox-Sudakov vertex-online strategy to hypergraphs: a potential is maintained over the (k-1)-uniform links of each newly presented vertex, and a probabilistic deletion argument is used to show that the exponent incurs only a (1+o(1)) factor with no additional multiplicative loss. Corollaries include a modest quantitative improvement to the best known upper bounds on hypergraph Ramsey numbers r_k(s,t) and a refinement of the classical Erdős-Rado recursive bound.

Significance. If the result holds, the paper supplies a concrete quantitative improvement to the recursive structure of hypergraph Ramsey numbers by reducing the exponent from a binomial coefficient to a linear term times (1+o(1)). The explicit tracking of the o(1) term through the induction and the use of probabilistic deletion to control losses constitute a technical strength that directly extends the graph-case precedent without introducing extra factors. This yields lower-order gains when the recurrence is iterated and strengthens the toolkit for bounding hypergraph Ramsey numbers.

minor comments (2)
  1. [§2] §2, Definition of tilde r_k(s,t): the precise rules of the vertex online game on k-uniform hypergraphs (in particular, how the adversary presents vertices and the colorer responds) should be stated with an explicit small example for k=3 to make the generalization from the graph case fully transparent.
  2. [Corollary 1.4] Corollary 1.4: the claimed improvement to the Erdős-Rado bound is stated asymptotically; a short remark on the precise range of s,t for which the (1+o(1)) factor yields a visible numerical gain would help readers assess the practical scope.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, accurate summary of our results, and recommendation of minor revision. The assessment correctly identifies the technical contribution in adapting the Conlon-Fox-Sudakov vertex-online strategy to hypergraphs via potential functions and probabilistic deletion, yielding the (1+o(1)) factor in the exponent without extra multiplicative losses.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation proceeds directly from the definition of the vertex online Ramsey game on hypergraphs by maintaining a potential over the (k-1)-uniform links of each new vertex and applying a probabilistic deletion argument to control the exponent. This yields the claimed recurrence with only a (1+o(1)) factor without any fitted parameters, self-referential quantities, or load-bearing self-citations; the argument is an explicit inductive extension of the external Conlon-Fox-Sudakov strategy and remains self-contained against the combinatorial inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claim rests on the inductive definition of the online Ramsey game and standard combinatorial counting arguments; no free parameters or invented physical entities appear.

axioms (1)
  • standard math Standard inductive argument on uniformity k using the definition of the vertex online game
    Invoked to obtain the (1+o(1)) factor from the graph-case analysis.
invented entities (1)
  • Hypergraph vertex online Ramsey number tilde r_k(s,t) no independent evidence
    purpose: Generalization of the graph online Ramsey number to k-uniform hypergraphs
    Defined in the paper as the natural extension that enables the improved recurrence.

pith-pipeline@v0.9.0 · 5735 in / 1238 out tokens · 73308 ms · 2026-05-20T16:01:52.250146+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

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

13 extracted references · 13 canonical work pages · 1 internal anchor

  1. [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, J. Amer. Math. Soc., to appear. 4

    work page

  2. [2]

    Beck,Achievement games and the probabilistic method, in Combinatorics, Paul Erd˝ os is Eighty, Bolyai Soc

    J. Beck,Achievement games and the probabilistic method, in Combinatorics, Paul Erd˝ os is Eighty, Bolyai Soc. Math. Stud.1(1993), 51–78. 2

    work page 1993

  3. [3]

    Campos, S

    M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe,An exponential improvement for diagonal Ramsey, Ann. of Math., to appear. 4

    work page

  4. [4]

    Conlon,On-line Ramsey numbers, SIAM J

    D. Conlon,On-line Ramsey numbers, SIAM J. Discrete Math.23(2009), 1954–1963. 2, 9

    work page 2009

  5. [5]

    Conlon, J

    D. Conlon, J. Fox, A. Grinshpun, and X. He,Online Ramsey numbers and the Subgraph Query Problem, in Building Bridges II, 159–194, Springer, 2019. 2

    work page 2019

  6. [6]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov,Hypergraph Ramsey numbers, J. Amer. Math. Soc.23(2010), 247–

    work page 2010

  7. [7]

    Erd˝ os and R

    P. Erd˝ os and R. Rado,Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc.3(1952), 417–439. 1

    work page 1952

  8. [8]

    J. Fox, J. Pach, B. Sudakov, and A. Suk,Erd˝ os–Szekeres-type theorems for monotone paths and convex bodies, Proc. Lond. Math. Soc. (3)105(2012), 953–982. 2, 3

    work page 2012

  9. [9]

    Three Proofs of the Hypergraph Ramsey Theorem (An exposition)

    W. Gasarch, A. Parrish, and S. Sinai,Three proofs of the hypergraph Ramsey theorem (An exposition), preprint available athttps://arxiv.org/abs/1206.4257. 2, 3

    work page internal anchor Pith review Pith/arXiv arXiv

  10. [10]

    R. L. Graham, B. L. Rothschild, and J. H. Spencer,Ramsey theory, 2nd edition, John Wiley & Sons (1980)

    work page 1980

  11. [11]

    Kurek and A

    A. Kurek and A. Ruci´ nski,Two variants of the size Ramsey number, Discuss. Math. Graph Theory25 (2005), 141–149 2

    work page 2005

  12. [12]

    Mubayi and A

    D. Mubayi and A. Suk,The Erd˝ os–Hajnal hypergraph Ramsey problem, J. Eur. Math. Soc. (JEMS)22 (2020), 1247–1259. 2

    work page 2020

  13. [13]

    F. P. Ramsey,On a problem of formal logic, Proc. London Math. Soc. (2)30(1929), 264–286. 1 Department of Mathematics, Emory University, Atlanta, GA, 30322, USA Email address:daniel.dobak@emory.edu Department of Mathematics, Emory University, Atlanta, GA, 30322, USA Email address:eion.mulrenin@emory.edu 10

    work page 1929