Gaussian random graphs and Ramsey numbers

2025/12/19 by Hunter, Zach, Milojević, Aleksa, Sudakov, Benny
#05C80 #05D10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2512.17718

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.

Citations

• An exponential improvement for Ramsey lower bounds
• A new lower bound for the Ramsey numbers R(3,k)
• Upper bounds for multicolour Ramsey numbers
• Optimizing the CGMS upper bound on Ramsey numbers
• Optimal sub-Gaussian variance proxy for truncated Gaussian and exponential random variables
• The asymptotics of r(4,t)
• An exponential improvement for diagonal Ramsey
• Diagonal Ramsey via effective quasirandomness
• A note on pseudorandom Ramsey graphs
• Testing for high-dimensional geometry in random graphs
• A New Upper Bound for Diagonal Ramsey Numbers
• Values of Mills' Ratio of Area to Bounding Ordinate and of the Normal Probability Integral for Large Values of the Argument
• On a Problem of Formal Logic

Related

• An algorithmic framework for obtaining lower bounds for random Ramsey problems
• Reinforced Generation of Combinatorial Structures: Ramsey Numbers
• Computational lower limits on small Ramsey numbers
• Improving R(3,k) in just two bites
• An exponential improvement for Ramsey lower bounds