Size-Ramsey numbers of tight paths

Shoham Letzter, Alexey Pokrovskiy, Liana Yepremyan · 2025

Read Size-Ramsey numbers of tight paths by Shoham Letzter, Alexey Pokrovskiy, Liana Yepremyan (2025) 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-2507-01498.txt.

Introduction

Shoham Letzter, Alexey Pokrovskiy, and Liana Yepremyan settle a question about Ramsey numbers, a classic topic in combinatorics. Their 2025 paper defines the size-Ramsey number of a hypergraph. It is the fewest edges a host structure needs so that any coloring, with a fixed number of colors, yields a one-color copy of the target. They study tight paths, chains where consecutive blocks overlap heavily.

The authors prove the multi-color size-Ramsey number of a tight path grows only linearly with the path's length. The result holds for every fixed uniformity and number of colors. It answers a question posed by Dudek and co-authors in 2017, closing a known gap in the area.

Catalog record

CREATORShoham Letzter, Alexey Pokrovskiy, Liana Yepremyan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-01498

Browse the full library · About the Tower of Babel

Full text

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

Size-Ramsey numbers of tight paths Shoham Letzter, Alexey Pokrovskiy, Liana Yepremyan Abstract The s s -colour size-Ramsey number of a hypergraph H H is the minimum number of edges in a hypergraph G G whose every s s -edge-colouring contains a monochromatic copy of H H . We show that the s s -colour size-Ramsey number of the r r -uniform tight path on n n vertices is linear in n n , for every fixed r r and s s , thereby answering a question of Dudek, La Fleur, Mubayi and Rödl (2017). 1 Introduction A central problem in extremal combinatorics is to find conditions under which a graph G is guaranteed to contain another graph H , and a more “robust” variant of this question asks for the existence of a monochromatic copy of H in an edge-coloured graph G . Ramsey [ 42 ] initiated an already century-long line of research around such problems, by considering the numbers R(k,\ell) , defined to be the minimum number n such that any red/blue edge-colouring of the complete graph K_{n} contains a red K_{k} or a blue K_{\ell} , and showing that they are finite. Early results of Erdős and Szekeres [ 26 ] and Erdős [ 25 ] give general upper and lower bounds on these numbers that remained the state-of-the-art for many years, especially for the interesting range k=\ell . Nevertheless, over the years several improved bounds on R(k,k) were proved [ 45 , 29 , 46 , 15 , 44 ] , culminating with the major breakthrough of Campos, Griffiths, Morris and Sahasrabudhe [ 10 ] , who obtained the first significant improvement on the aforementioned early bound for R(k,k) , showing that it is at most (4-c)^{k} for some constant c>0 , thereby solving the most famous open problem in the field. The study of off-diagonal Ramsey numbers, in particular, R(3,k) has been another central topic in the area, that has driven the development of new probabilistic tools and techniques, such as the triangle-free process. We refer the reader to the most recent preprint on this topic by Campos, Jenssen, Michelen and Sahasrabudhe [ 11 ] , who improved the best-known lower bound on R(3,k) , thus narrowing the gap between the upper and lower bounds to a factor 3+o(1) . More generally, for two graphs or hypergraphs \mathcal{G} and \mathcal{H} and an integer s\geq 2 write \mathcal{G}\stackrel{{\scriptstyle s}}{{\longrightarrow}}\mathcal{H} if in every s -edge-colouring of \mathcal{G} there is a monochromatic copy of \mathcal{H} . The Ramsey number of a graph/hypergraph \mathcal{H} is defined as r_{s}(\mathcal{H})=\min\{|\mathcal{G}|:\mathcal{G}\stackrel{{\scriptstyle s}}{{\longrightarrow}}\mathcal{H}\}. In this paper we study a variant of classical Ramsey numbers, introduced by Erdős, Faudree, Rousseau and Schelp [ 27 ] in 1978. The s -colour size-Ramsey number of a hypergraph \mathcal{H} , denoted \hat{r}_{s}(\mathcal{H}) , is the minimum number of edges in a hypergraph \mathcal{G} satisfying \mathcal{G}\stackrel{{\scriptstyle s}}{{\longrightarrow}}\mathcal{H} . Namely, \hat{r}_{s}(\mathcal{H})=\min\{e(\mathcal{G}):\mathcal{G}\stackrel{{\scriptstyle s}}{{\longrightarrow}}\mathcal{H}\}. When s=2 , we often omit the subscript 2 , and refer to the 2 -colour size-Ramsey number of \mathcal{H} as, simply, the size-Ramsey number of \mathcal{H} . It is easy to see that for any graph H , \hat{r}(H)\leq{r(H)\choose 2} , and it is known that for H=K_{n} , this inequality is tight [ 27 ] , the latter often attributed to Chvátal. One of the earliest results regarding size-Ramsey numbers of graphs, obtained by Beck [ 4 ] in 1983, asserts that, somewhat surprisingly, the size-Ramsey number of a path is linear in its length; more precisely, Beck showed that \hat{r}(P_{n})\leq 900n for large n . The problem of determining the size-Ramsey number of a path has been the subject of many papers [ 2 , 4 , 9 , 8 , 22 , 23 , 37 ] , and the currently best-known bounds are as follows: (3.75+o(1))n\leq\hat{r}(P_{n})\leq 74n, where the lower bound is due to Bal and DeBiasio [ 2 ] and the upper bound is by Dudek and Prałat [ 23 ] . One can easily generalise Beck’s arguments to the multicolour setting, showing that \hat{r}_{s}(P_{n})=O_{s}(P_{n}) . This multicolour variant has received its own fair share of attention [ 23 , 36 , 2 , 24 ] ; and currently the best-known bounds are as follows, where the lower bound is due to Dudek and Prałat [ 23 ] and the upper bound is by Krivelevich [ 36 ] . \hat{r}_{s}(P_{n})=\Omega(s^{2}n),\qquad\hat{r}_{s}(P_{n})=O(s^{2}\log s\cdot n). In subsequent work, inspired by previous results on paths and trees, Beck [ 5 ] asked whether every bounded degree graph has size-Ramsey number linear in its number of vertices. The conjecture was proven to be true for trees by Friedman and Pippenger [ 28 ] and for cycles by Haxell, Kohayakawa and Luczak [ 32 ] , but eventually turned out to be false in general, as proven by Rödl and Szeméredi [ 43 ] who constructed a sequence of graphs (G_{n}) with |G_{n}|=n , \Delta(G_{n})\leq 3 and such that \hat{r}(G_{n})\geq cn(\log{n})^{1/60} . More recently, by carefully modifying their construction, Tikhomirov [ 47 ] improved this lower bound to cn\exp(c\sqrt{\log{n}}) (optimal bound for the method). Arguably one of the most interesting questions in this area remains open; a conjecture by Rödl and Szeméredi [ 43 ] suggests that Beck’s conjecture is false in a strong way, namely that for every d\geq 3 there is \varepsilon=\varepsilon(d)>0 and a sequence of graphs (G_{n}) on n vertices and \Delta(G_{n})\leq d such that \hat{r}(G_{n})\geq n^{1+\varepsilon} . Regarding upper bounds, Kohayakawa, Rödl, Schacht, and Szemerédi [ 35 ] proved that any n -vertex graph H of maximum degree d satisfies \hat{r}(H)\leq n^{2-1/d+o(1)}. This was recently improved to \hat{r}(H)\leq n^{2-1/(d-1)+o(1)} for d\geq 4 by Allen and Böttcher [ 1 ] . Better bounds have been obtained for triangle-free graphs by Conlon and Nenadov (see [ 40 ] ) and for cubic graphs, first by Conlon, Nenadov and Trujić [ 16 ] , and later by Draganić and Petrova [ 20 ] . A recent work of Draganić, Kaufmann, Munh’a Correia, Petrova, and Steiner [ 18 ] improves the bounds coming from [ 35 ] in certain cases by considering treewidth as a parameter, along with maximum degree. In contrast, the study of size-Ramsey numbers of hypergraphs was initiated only recently (in 2017) by Dudek, La Fleur, Mubayi and Rödl [ 21 ] . One of the first problems proposed in their paper is the following generalisation of Beck’s result [ 4 ] regarding size-Ramsey numbers of paths. The r -uniform tight path on n vertices, denoted P_{n}^{(r)} , is the r -uniform hypergraph on vertex set [n] whose edges are all sets of r consecutive elements in [n] . Observe that P_{n}^{(2)} is the path P_{n} on n vertices. Dudek, La Fleur, Mubayi and Rödl [ 21 ] asked if, similarly to the graph case, \hat{r}\big(P_{n}^{(r)}\big)=O(n) for every r . This was answered affirmatively for r=3 by Han, Kohayakawa, Letzter, Mota and Parczyk [ 31 ] . For r\geq 4 , the best-known bound prior to our work was \hat{r}(P_{n}^{(r)})=O\big((n\log n)^{r/2}\big) , due to Lu and Wang [ 39 ] . In our main result we settle the problem, and, in fact, prove a stronger statement where the number of colours is arbitrary (rather than

Read the complete text