Diagonal Ramsey via effective quasirandomness

By A. Sah. Duke mathematical journal, 2020

50 citations recorded by the source corpus.

We improve the upper bound for diagonal Ramsey numbers to \[R(k+1,k+1)\le\exp(-c(\log k)^2)\binom{2k}{k}\] for $k\ge 3$. To do so, we build on a quasirandomness and induction framework for Ramsey numbers introduced by Thomason and extended by Conlon, demonstrating optimal "effective quasirandomness" results about convergence of graphs. This optimality represents a natural barrier to improvement.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/4225c755f1be93b08d90bc090f03cdf41eb8d8bc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Marcelo Campos
2. Simon Griffiths
3. Julian Sahasrabudhe
4. Robert Morris
5. Jacques Verstraëte

In Discrete Mathematics and Combinatorics

1. Marcelo Campos
2. Simon Griffiths
3. Julian Sahasrabudhe
4. Robert Morris
5. Jacques Verstraëte

In Geometry and Topology

1. Marcelo Campos
2. Simon Griffiths
3. Julian Sahasrabudhe
4. Robert Morris
5. Jacques Verstraëte

Citations in the corpus

• An exponential improvement for diagonal Ramsey (2023, methodology): “Erdős and Szekeres [11] proved that R(k, `) 6 ( k + ` ` ) (1) for all k, ` ∈ N, and this bound was improved by Thomason [21], Conlon [5] and Sah [18] when ` = Θ(k), the best known bound in this case1 being of the form R(k, `) 6 e−c(log k) 2 ( k + ` ` ) for some c > 0.”