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

Dániel Dobák, Eion Mulrenin · 2026

Read Recursive upper bounds for the vertex online Ramsey game with applications to hypergraph Ramsey numbers by Dániel Dobák, Eion Mulrenin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16607.txt.

Introduction

Dobák and Mulrenin sharpen a classic bound for hypergraph Ramsey numbers, which concern how large a structure must grow before a set pattern is forced to appear. They extend the vertex online Ramsey game from graphs to hypergraphs and prove a tighter recurrence for it. The result improves the long-standing Erdős–Rado bound by a lower-order term and yields better quantitative limits for hypergraph Ramsey numbers.

Catalog record

CREATORDániel Dobák, Eion Mulrenin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24211
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.16607

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Recursive upper bounds for the vertex online Ramsey game with applications to hypergraph Ramsey numbers Thanks: Keywords . Ramsey theory, hypergraph Ramsey numbers, online Ramsey numbers. Dániel Dobák, Eion Mulrenin Abstract . The classical recursive upper bound on hypergraph Ramsey numbers due to Erdős and Rado states that for 2 ≤ k < s ≤ t 2\leq k<s\leq t , r k ​ ( s , t ) ≤ 2 ( r k − 1 ​ ( s − 1 , t − 1 ) k − 1 ) . 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 r ~ ​ ( s , t ) \tilde{r}(s,t) for graphs to obtain a quantitative improvement over this bound when k = 3 k=3 . In this note, we show that the natural hypergraph generalization r ~ k ​ ( s , t ) \tilde{r}_{k}(s,t) of the vertex online Ramsey numbers satisfy an improved recurrence r ~ k ​ ( s , t ) ≤ 2 ( 1 + o ⁡ ( 1 ) ) ​ r ~ k − 1 ​ ( s − 1 , t − 1 ) . \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ős and Rado. 1. Introduction For positive integers k<t_{1},\dots,t_{q} , we denote by r_{k}(t_{1},\dots,t_{q}) the k -uniform q -color Ramsey number of t_{1},\dots,t_{q} , that is, the least integer n so that every q -coloring of E(K_{n}^{(k)}) contains a copy of K_{t_{c}}^{(k)} the edges of which all receive color c , for some c\in[q] . The study of these numbers goes back to the seminal paper of Ramsey [ 13 ] , but the problem of finding effective bounds for Ramsey numbers was first studied by Erdős and Rado [ 7 ] , who implicitly proved a recursive bound of the form r_{k}(t_{1},\ldots,t_{q})\leq 2^{\binom{r_{k-1}(t_{1}-1,\ldots,t_{q}-1)}{k-1}}. (1) As a corollary, they gave a tower-type upper bound for such hypergraph Ramsey numbers, greatly improving over the bound from Ramsey’s proof, which was not even primitive recursive. More precisely, we recursively define the tower function T_{i}(x) by setting T_{0}(x)=x and T_{i+1}(x)=2^{T_{i}(x)} (thus the subscript is the number of 2’s in the tower); the recurrence in ( 1 ) for two colors, e.g., then gives that r_{k}(s,t)\leq T_{k-1}((2+o(1))(s+t)) . In this note, we investigate upper bounds for another hypergraph Ramsey problem, namely the k -uniform vertex online Ramsey game . This was introduced by Conlon, Fox, and Sudakov in 2010 [ 6 ] for graphs (i.e., k=2 ) in order to give a quantitative improvement over the bound given by ( 1 ) for three-uniform hypergraphs. A hypergraph analogue of the game was first described by Fox, Pach, Sudakov, and Suk [ 8 ] , who studied it for monotone paths, and by Gasarch, Parrish, and Sinai [ 9 ] , who studied it for cliques. Mubayi and Suk [ 12 ] also introduced another variant in their work on the Erdős–Hajnal hypergraph Ramsey problem. The q -color k -uniform game is played by two players, builder and painter, starting on the ordered vertex set V=\{v_{i}:i\in\mathbb{N}\} of an empty k -uniform hypergraph, and proceeds in rounds as follows. • At the beginning of round i , the i th vertex v_{i} in the ordering of V is revealed; • During round i , builder can choose to build any number of edges of the form \{v_{i_{1}},...,v_{i_{k-1}},v_{i}\} for i_{1}<\dots<i_{k-1}<i , in any order; • Whenever builder decides to build an edge, painter must immediately assign it a color from [q] ; • In each round i\geq k , builder must build at least one new edge 1 1 1 Some versions of the game do not include this last rule, though to our knowledge, every known strategy which gives good bounds adheres to it. ; • Builder’s goal is to force painter to create a monochromatic K_{t_{c}}^{(k)} in some color c\in[q] , whereas painter’s objective is to delay this as much as possible. Since builder always has a winning strategy, namely, to build a clique on r_{k}(t_{1},\dots,t_{q}) vertices, the k -uniform vertex online Ramsey number \tilde{r}_{k}(s,t) is then defined to be the minimum number of edges builder must draw to force painter to create a monochromatic K_{t_{c}}^{(k)} in color c for some c\in[q] . It is worth mentioning that the more general online Ramsey game , introduced independently by Beck [ 2 ] and Kurek and Ruciński [ 11 ] , differs from the one studied here in that vertices are not revealed one at a time, and instead builder can draw whichever edges she wants at each step. For more information on this version, we refer the interested reader to the papers [ 4 , 5 ] and the references therein. Conlon, Fox, and Sudakov [ 6 , Lemma 2.2] proved that for the graph vertex online Ramsey game, builder always has a strategy which uses at most \binom{s+t-2}{s-1} vertices and at most (s+t-4)\binom{s+t-2}{s-1} edges to force painter to draw a red K_{s} or a blue K_{t} . In particular, \tilde{r}_{2}(s,t)\leq(s+t-4)\cdot\binom{s+t-2}{s-1}, (2) and they subsequently use this to give an upper bound 2 2 2 For off-diagonal Ramsey numbers where s is fixed and t\to\infty , they get a further improved bound with a slight alteration to their builder strategy. r_{3}(s,t)\leq 2^{\tilde{r}_{2}(s-1,t-1)}+1\leq 2^{(s+t-4)\cdot\binom{s+t-2}{s-1}}+1. (3) After finishing the first draft of our paper, we became aware of an exposition by Gasarch, Parrish, and Sinai [ 9 ] . In this work, they describe a generalization of the Conlon-Fox-Sudakov method for hypergraphs of higher uniformity, but did not obtain an improvement for hypergraph Ramsey numbers. They subsequently raised the question of whether the vertex online Ramsey game for hypergraphs could be used to obtain a further improvement for r_{k}(t,t) . Our main result and its first corollary below address this question, giving a recursive bound for \tilde{r}_{k}(s,t) which yields much sharper recurrence than ( 1 ) for hypergraph vertex online Ramsey numbers. Theorem 1 . Let 2\leq k<s,t and let m=\tilde{r}_{k-1}(s-1,t-1) . Then builder has a strategy in the k -uniform vertex online Ramsey game for cliques of size s and t using at most 2^{m}+k-2 vertices and at most m\cdot 2^{m} edges. In particular, r_{k}(s,t)\leq 2^{\tilde{r}_{k-1}(s-1,t-1)}+k-2 (4) and \begin{split}\tilde{r}_{k}(s,t)&\leq\tilde{r}_{k-1}(s-1,t-1)\cdot 2^{\tilde{r}_{k-1}(s-1,t-1)}\\[4.30554pt] &=2^{(1+o(1))\tilde{r}_{k-1}(s-1,t-1)},\end{split} (5) where the o(1) term goes to 0 as \max\left\{s,t\right\}\to\infty . It is worth pointing out that bounds of the form ( 4 ) were previously observed in several of the aforementioned papers [ 6 , 8 , 9 ] . We decided to include it in the statement of the theorem because it is an immediate consequence of our proof, which takes a slightly different route from this prior work (wherein it was proved by a modification of the Erdős–Rado argument), and it will be used in the proofs of our corollaries. On the other hand, ( 5 ) is, to our knowledge, the first nontrivial recursive-type bound for the hypergraph vertex online Ramsey game, and as such might be considered our main contribution. This sharper recurrence for hypergraph vertex online Ramsey numbers quickly yields

Read the complete text