A new upper bound for diagonal Ramsey numbers

By David Conlon. 2006

199 citations recorded by the source corpus.

We prove a new upper bound for diagonal two-colour Ramsey numbers, showing that there exists a constant C such that r(k + 1,k+1) ≤ k -Clog k/log log k ( 2k k ).

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

View Paper: https://www.semanticscholar.org/paper/700debad13bddfb08efb7fd41024227854563c2e

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

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Erdős-Hajnal-type Results on Intersection Patterns of Geometric Objects (2008, background): “This bound, which has been slightly improved by Conlon [15], is tight up to a constant factor: Erd˝os [20] showed that there exists a graph on n vertices, for every integer n > 1, with no clique or independent of more than 2 log n vertices.”
Open problems in additive combinatorics (2007, unknown): “Just to give one example, within the ﬁeld of combinatorics, but not speciﬁcally additive combinatorics, Conlon [22] has used some of Gowers’s methods to produce a new upper bound on the diagonal Ramsey number r ( n, n ) (which is the smallest r such that if the edges of a complete graph on r…”
Diagonal Ramsey via effective quasirandomness (2020, methodology): “The following lemma is similar to bounds appearing in [4].”
An exponential improvement for diagonal Ramsey (2023, methodology): “Erdő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.”
The triangle-free process and R(3,k) (2013, unknown): “n particular that R (k ) := R (k;k ) 6 4k , and that R (3 ;k) = O (k 2 ). Despite an enormous amount of eort, the former bound has only recently been improved by a super-polynomial factor, by Conlon [24], who rened the earlier method of Thomason [52]. A constructive super-polynomial lower bound was ”
Ramsey numbers of degenerate graphs (2015, background): “There have been some interesting improvements on these bounds [8], [32], but despite a great amount of eﬀort, the constants in the exponents remain unchanged.”
An Approximate Version of Sidorenko’s Conjecture (2010, background): “Furthermore, for a large class of bipartite graphs, we prove a stronger stability result which answers a question of Chung, Graham, and Wilson on quasirandomness for these graphs.”