Gaussian random graphs and Ramsey numbers

2025/12/19 by Zach Hunter, Aleksa Milojević, Hunter, Zach +3
Computer Science · Mathematics · #05C80 #05D10 #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods

paper · doi:10.48550/arxiv.2512.17718

openalex publication_date 2025/12/19 · openalex created_date 2025/12/23 · openalex updated_date 2026/07/28

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