Gaussian random graphs and Ramsey numbers
Zach Hunter, Aleksa Milojević, Benny Sudakov · 2025
Read Gaussian random graphs and Ramsey numbers by Zach Hunter, Aleksa Milojević, Benny Sudakov (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-2512-17718.txt.
Introduction
Zach Hunter, Aleksa Milojević, and Benny Sudakov give a simpler proof of a recent leap in Ramsey theory. That field studies how large a network must be before a tidy pattern is forced to appear. A team led by Ma, Shen, and Xie had just raised the known lower bounds by an exponential step, with heavy machinery. Hunter and co-authors reach the same heights with Gaussian random graphs, a cleaner random construction. Their simpler analysis even sharpens the numbers.
Catalog record
| CREATOR | Zach Hunter, Aleksa Milojević, Benny Sudakov |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-17718
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Gaussian random graphs and Ramsey numbers Thanks: Department of Mathematics, ETH Zürich, Switzerland. Email: {zach.hunter, aleksa.milojevic, benjamin.sudakov}@math.ethz.ch . Research supported in part by SNSF grant 200021-228014. Zach Hunter, Aleksa Milojević, Benny Sudakov Abstract . We give a simple proof of the recent remarkable exponential improvement for Ramsey lower bounds, obtained by Ma, Shen and Xie. Our key ingredient is an alternative construction based on Gaussian random graphs, which allows us to simplify their analysis significantly. As a consequence of this simpler analysis, we also obtain better quantitative bounds. 1. Introduction For positive integers k,\ell\geq 1 , the Ramsey number R(\ell,k) is the smallest integer n such that any edge-coloring of the complete graph K_{n} using the colors red and blue either contains a copy of K_{\ell} all of whose edges are red or a copy of K_{k} all of whose edges are blue. These numbers play a central role in Ramsey theory , which is itself an essential branch of combinatorics with a long and rich history, with hundreds of papers published each year. Arguably the most famous problem in Ramsey theory is to determine the growth of Ramsey numbers R(\ell,k) when k=\ell , also known as the diagonal Ramsey numbers , and more generally when k=C\ell . Without attempting to comprehensively survey all of the recent results, let us mention that the last couple of years have brought a series of exciting developments on many long-standing questions related to Ramsey numbers of cliques, see e.g. [ 1 , 4 , 5 , 7 , 13 , 15 , 16 , 17 ] and the references therein. The first quantitative upper bound on R(\ell,k) comes from a classical paper of Erdős and Szekeres [ 10 ] from 1935, and states that R(\ell,k)\leq\binom{\ell+k-2}{\ell-1} , thus showing that R(\ell,\ell)\leq 4^{\ell} . After several important improvements by Thomason [ 22 ] , Conlon [ 6 ] and Sah [ 20 ] , in a recent breakthrough paper Campos, Griffiths, Morris and Sahasrabudhe [ 4 ] showed that R(\ell,\ell)\leq 4^{(1-\varepsilon)\ell} for a positive constant \varepsilon>0 (see also [ 12 ] and [ 1 ] for further developments). The study of the lower bounds for the Ramsey numbers had at least equal, if not greater, influence on combinatorics. In the paper which introduced the probabilistic method to combinatorics, Erdős [ 9 ] in 1947 gave an argument using random graphs which shows R(\ell,\ell)\geq\frac{\ell}{e\sqrt{2}}2^{\ell/2} . Beyond a modest improvement [ 21 ] by a factor of 2 using the Lovász Local Lemma, the progress on this question was extremely slow and Erdős’ bound stays essentially unchanged to this day. Hence it was a great surprise when Ma, Shen and Xie [ 15 ] used a different random graph model to give an exponential improvement to Erdős’ lower bound for R(\ell,k) when k=C\ell for a constant C>1 . To obtain this improvement, they used a geometrically defined random graph, whose vertices are random points on a high-dimensional sphere and the colors of the edges are determined by the distances between the points. Because of the complicated geometry of high-dimensional spheres, the analysis of this random graph model is long and technical, spanning many pages. In this paper, we propose an alternative approach to this problem. Although we draw our inspiration from the work of Ma, Shen and Xie, we use random Gaussian vectors to define our graphs. Of course, in the regime of parameters considered here, the length of the Gaussian random vectors we choose is highly concentrated, so the resulting graph is very similar to the one obtained by placing random points on the sphere. However, the key advantage is that the Gaussian measure is a product measure, that is to say its coordinates are independent. This, along with a couple of further ideas, allows us to significantly simplify and shorten the analysis of such graphs, and to obtain tighter bounds. In order to state our main theorem, let us briefly recall the classical lower bound on R(\ell,k) coming from Erdős’ argument. If we color every edge of the graph red with probability p or blue with probability 1-p , independently of all other edges, then the probability that \ell vertices form a red clique is exactly p^{\binom{\ell}{2}} , and the probability that k vertices form a blue clique is (1-p)^{\binom{k}{2}} . Thus, the expected number of red \ell -cliques is \binom{n}{\ell}p^{\binom{\ell}{2}} , and the expected number of blue k -cliques is \binom{n}{k}(1-p)^{\binom{k}{2}} . If for some positive integer n we have that \binom{n}{\ell}p^{\binom{\ell}{2}}+\binom{n}{k}(1-p)^{\binom{k}{2}}<1 , then there exists a coloring in which both the number of red \ell -cliques and blue k -cliques is zero, and therefore we have R(\ell,k)\geq n . When k=C\ell , the probability p which gives the best lower bound is denoted by p_{C} , and it can be found as the unique solution of the equation C=\frac{\log p_{C}}{\log(1-p_{C})} . In this case, the corresponding lower bound is R(\ell,k)\gtrsim p_{C}^{-\ell/2} . In this paper we improve this bound as follows. Theorem 1.1 . For any C>1 , there exists a constant \varepsilon such that, for all sufficiently large \ell , we have R(\ell,C\ell)\geq(p_{C}^{-1/2}+\varepsilon)^{\ell}, where p_{C}\in(0,1/2) is the unique solution to the equation C=\frac{\log p_{C}}{\log(1-p_{C})} . Beyond its simplicity, another advantage of this analysis is that it allows us to obtain quantitative improvements over the work of Ma, Shen and Xie. Namely, as C\to\infty and p_{C}\to 0 , Ma, Shen and Xie obtain a gain of \varepsilon which goes to 0 with C\to\infty . On the other hand, the argument we present here can be extended to show one can take \varepsilon=(e^{1/24}-1)p_{C}^{-1/2} , thus showing R(\ell,C\ell)\geq(e^{1/24}p_{C}^{-1/2})^{\ell} for all sufficiently large C . Let us also remark that when C\to 1 , our proof gives the same quantitative behavior \varepsilon=\Omega((C-1)^{2}) as [ 15 ] . To focus on the simplest possible presentation, we present this proof only in a forthcoming appendix to this paper. 1.1. Gaussian random geometric graph G(n,d,p) . Let us now formally define the model of the Gaussian random geometric graph, before saying a couple of words about how to analyze it. Let n,d\geq 1 be positive integers, and let p\in(0,1/2) be a probability. Also, let c_{p}>0 be the unique real number for which \mathbb{P}[Z\leq-c_{p}]=p , where Z\sim\mathcal{N}(0,1) is the standard one-dimensional Gaussian. Definition 1.2 . The vertices of the Gaussian random geometric graph G(n,d,p) correspond to vectors \boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n} , independently sampled from the d -dimensional normal distribution \mathcal{N}(0,\frac{1}{d}I_{d}) . Further, the vertices i,j\in[n] are connected by an edge if \langle\boldsymbol{x}_{i},\boldsymbol{x}_{j}\rangle\geq-\frac{c_{p}}{\sqrt{d}} . Note that given a graph G\sim G(n,d,p) , we can define a red/blue edge-coloring of the complete graph K_{n} , by declaring the edges of G to be blue, and all other edges to be red. Our notion of random geometric graphs differs slightly from the one commonly used in the literature. There are two main reasons. Firstly, it would be common to define the threshold c_{p} such that \langle\boldsymbol{x}_{i},\boldsymbol{x}_{j}\rangle\geq-\frac{c_{p}}{\sqrt{d}} occurs exactly with probability 1-p , when \boldsymbol{x}_{i},\boldsymbol{x}_{j}\sim\mathcal{N}(0,\frac{1}{d}I_{d}) , since the graph G(n,d,p) would then have expected density exactly 1-p . However, we opt for a simpler definition of c_{p} , and observe that the graph we define has expected density very close to 1-p (in fact, the expected