An update on multicolor Ramsey lower bounds

Marcelo Campos, Cosmin Pohoata · 2026

Read An update on multicolor Ramsey lower bounds by Marcelo Campos, Cosmin Pohoata (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-2601-15183.txt.

Introduction

Marcelo Campos and Cosmin Pohoata update lower bounds for multicolor Ramsey numbers. Their 2026 arXiv paper deals with a classic question in graph theory. A Ramsey number marks the size at which a pattern must appear, no matter how edges are colored.

The work builds on results by Conlon, Ferber, and Wigderson, and on a step by Sawin. The key tool is an upper bound on how sparse the independent sets of a certain graph must be. From that bound, the authors draw fresh lower bounds for the multicolor Ramsey numbers.

Catalog record

CREATORMarcelo Campos, Cosmin Pohoata
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15183

Browse the full library · About the Tower of Babel

Full text

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

An update on multicolor Ramsey lower bounds Marcelo Campos, Cosmin Pohoata Abstract Building upon previous works by Conlon-Ferber and Wigderson, Sawin showed a few years ago that upper bounds on the minimum density of independent sets in a K t K_{t} -free G G can be used to provide lower bounds for multicolor Ramsey numbers. In this note, we observe how a further improved upper bound on this parameter directly follows from a recent spherical random geometric graph construction of Ma-Shen-Xie. As a consequence, we derive a small exponential improvement over the best known lower bounds for multicolor Ramsey numbers. 1 Introduction For integers \ell,t\geq 2 , let r(t;\ell) denote the least N such that every \ell -coloring of the edges of K_{N} contains a monochromatic copy of K_{t} . The most well-studied case is that of \ell=2 , where the bounds 2^{t/2}\leq r(t;2)\leq 2^{2t} were originally proved by Erdős [ 6 ] and Erdős-Szekeres [ 7 ] in 1947 and 1935, respectively. The lower bound is a particularly celebrated probabilistic construction, which in fact initiated the development of the probabilistic method in combinatorics and related areas. Despite decades of effort, this lower bound has only been improved so far by a multiplicative constant (see [ 12 ] ). For the upper bound, the first exponential improvement was established only a couple of years ago by the first author, together with Griffiths, Morris and Sahasrabudhe [ 4 ] . For \ell\geq 3 , a straightforward modification of the Erdős–Szekeres “neighbourhood chasing” argument yields the general upper bound r(t;\ell)\leq\ell^{\ell t} . Using a new geometric approach and ideas related to the work from [ 4 ] , a recent paper [ 3 ] provided an exponential improvement over this bound for all \ell\geq 2 . In the other direction, the usual random colouring argument gives r(t;\ell)\geq\ell^{t/2} . This was originally improved by Abott [ 1 ] , who used an iterated product coloring to show that r(t;\ell)\geq 2^{\ell t/4} . This was more recently improved in a remarkable short paper by Conlon and Ferber [ 5 ] , who introduced a randomized algebraic construction to improve on this bound for \ell=3 , and then leveraged Abott’s product coloring trick to get an improvement for all \ell\geq 3 . Their lower bound was subsequently improved for \ell\geq 4 by Wigderson [ 13 ] , who replaced the Abott’s trick with a random homomorphism argument. Finally, Sawin [ 11 ] improved on the bounds of Conlon-Ferber and Wigderson for all \ell\geq 3 , by replacing the algebraic part of the Conlon-Ferber construction with an appropriate copy of the Erdős-Renyi random graph. In this note, we show that one can further improve the lower bound of Sawin for all \ell\geq 3 , by replacing the copy of the Erdős-Renyi random graph with the random geometric graph, used recently by Ma, Shen and Xie in [ 10 ] . Before we say more about this graph and where it comes in, let us first describe this story in a bit more detail. Following Sawin [ 11 ] , given integers s,t\geq 1 , let us start by defining c_{s,t} to be the infimum over all graphs G with no K_{t} of the probability that s i.i.d. uniform random vertices v_{1},\dots,v_{s}\in V(G) form an independent set (allowing repetitions). It turns out that upper bounds for this parameter translate very naturally into lower bounds for multicolor Ramsey numbers. Theorem 1 (Sawin) . For all \ell,t\geq 2 , r(t;\ell)\ \geq\ c_{t,t}^{-(\ell-2)/t}\,2^{(t-1)/2}. Indeed, fix a K_{t} -free graph G for which a random t -tuple of vertices forms an independent set with probability \approx c_{t,t} . The idea of Wigderson [ 13 ] , which goes back in some sense to the work of Alon and Rödl [ 2 ] , is that one can build a coloring of K_{N} by “trying” \ell-2 random homomorphisms f_{1},\dots,f_{\ell-2}:V(K_{N})\to V(G) in order: we give an edge xy the first color i for which f_{i}(x)f_{i}(y) lands on an edge of G , and if none of the \ell-2 tests succeeds we assign xy one of the two remaining colors uniformly at random. By construction, the first \ell-2 colors cannot contain a K_{t} (since G itself is K_{t} -free). So the only possible monochromatic K_{t} would have to use one of the last two colors. For a fixed t -set S , this requires two independent-looking conditions: for every i\leq\ell-2 , the image f_{i}(S) must be an independent set in G (costing about c_{t,t}^{\ell-2} ), and then the final random two-coloring must make all \binom{t}{2} edges of S agree (costing about 2^{1-\binom{t}{2}} ). A union bound over the \binom{N}{t} choices of S shows that if \binom{N}{t}\,c_{t,t}^{\ell-2}\,2^{1-\binom{t}{2}}<1, then with positive probability the resulting \ell -coloring contains no monochromatic K_{t} . It is not difficult to see that N\asymp c_{t,t}^{-(\ell-2)/t}2^{(t-1)/2} satisfies this inequality, therefore it follows that r(t;\ell)\ \geq\ c_{t,t}^{-(\ell-2)/t}\,2^{(t-1)/2} . Upper bounds for c_{t,t} . In turn, obtaining upper bounds on c_{t,t} amounts to exhibiting graphs G with no K_{t} for which a random t -tuple of vertices is unlikely to form an independent set. Indeed, by definition, c_{t,t} is the infimum of this probability over all K_{t} -free graphs, so any such example immediately yields an upper bound. The problem therefore becomes one of constructing graphs that simultaneously avoid large cliques and yet contain very few large independent sets, at least in the probabilistic sense captured by c_{t,t} . In [ 11 ] , Sawin approached this problem by taking G to be an Erdős–Rényi random graph on M vertices, with edge density slightly below 1/2 , and then conditioning on the event that G contains no K_{t} . For every t\geq 2 and every p\in(0,1) , this led to the following estimate: c_{t,t}\ \leq\ \exp\left(\,\frac{\,(4\log(1-p)-\log p)\,\log p}{8\log(1-p)}t^{2}\;+\;o(t^{2})\right). (1) In particular, optimizing over p the optimum is attained numerically at p\approx 0.454997 . Combinining this with Theorem 1 , Sawin then obtained the multicolor Ramsey lower bound r(t;\ell)\ \geq\ 2^{\,0.383796(\ell-2)t\;+\;\frac{t}{2}\;+\;o(t)}, (2) for every fixed \ell\geq 3 . Our main observation is that one can get an exponential improvement over ( 2 ) by instead taking G to be the complement of a dense random geometric graph in high dimension. This graph was recently used by Ma, Shen and Xie [ 10 ] in a new exciting lower bound for (two-color) off-diagonal Ramsey numbers. Even more recently, a variant of the model which is much simpler to analyze was introduced by Hunter, Milojević and Sudakov [ 8 ] in order to give a shorter proof of the main result of [ 10 ] . The key feature in these models is that edges are no longer independent: geometric constraints induce negative correlations among non-edges and positive correlations among edges. As an important consequence, large independent sets are suppressed compared to the Erdős–Rényi model, while large cliques become more likely. By choosing the dimension appropriately and slightly adjusting the edge density, the suppression of independent sets outweighs the increased likelihood of cliques, leading to a modest but genuine improvement over the Erdős–Rényi construction in the bounds for c_{t,t} , and hence for multicolor Ramsey numbers r(t;\ell) for all l\geq 3 . Our construction balances two geometric

Read the complete text