A new upper bound for diagonal Ramsey numbers

Abstract

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) \leq k^{- C {\log k}/{\log \log k}} \textstyle \binom{2k}{k}.\]

  • [CGW89] F. R. K. Chung, R. L. Graham, and R. M. Wilson, "Quasi-random graphs," Combinatorica, vol. 9, iss. 4, pp. 345-362, 1989.
    @article{CGW89, MRKEY = {1054011},
      AUTHOR = {Chung, F. R. K. and Graham, R. L. and Wilson, R. M.},
      TITLE = {Quasi-random graphs},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {9},
      YEAR = {1989},
      NUMBER = {4},
      PAGES = {345--362},
      ISSN = {0209-9683},
      CODEN = {COMBDI},
      MRCLASS = {05C80},
      MRNUMBER = {91e:05074},
      ZBLNUMBER = {0715.05057},
      MRREVIEWER = {Zbigniew Palka},
      }
  • [ES35] P. ErdHos and G. Szekeres, "A combinatorial problem in geometry," Compositio Math., vol. 2, pp. 463-470, 1935.
    @article{ES35, MRKEY = {1556929},
      AUTHOR = {Erdős, P. and Szekeres, G.},
      TITLE = {A combinatorial problem in geometry},
      JOURNAL = {Compositio Math.},
      FJOURNAL = {Compositio Mathematica},
      VOLUME = {2},
      YEAR = {1935},
      PAGES = {463--470},
      ISSN = {0010-437X},
      CODEN = {CMPMAF},
      MRCLASS = {Contributed Item},
      MRNUMBER = {1556929},
      ZBLNUMBER = {0012.27010},
      JFMNUMBER = {61.0651.04},
      }
  • [GR87] R. L. Graham and V. Rödl, "Numbers in Ramsey theory," in Surveys in Combinatorics 1987, Whitehead, C., Ed., Cambridge: Cambridge Univ. Press, 1987, pp. 111-153.
    @incollection{GR87, MRKEY = {905278},
      AUTHOR = {Graham, R. L. and R{ö}dl, V.},
      EDITOR = {Whitehead, C.},
      TITLE = {Numbers in {R}amsey theory},
      BOOKTITLE = {Surveys in Combinatorics 1987},
      VENUE = {New Cross, 1987},
      SERIES = {London Math. Soc. Lecture Note Ser.},
      NUMBER = {123},
      PAGES = {111--153},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1987},
      MRCLASS = {05C55},
      MRNUMBER = {89b:05125},
      ZBLNUMBER = {0633.05049},
      MRREVIEWER = {Walter A. Deuber},
      }
  • [R30] F. P. Ramsey, "On a problem of formal logic," Proc. London Math. Soc., vol. 30, pp. 264-286, 1929.
    @article{R30,
      author = {Ramsey, F. P.},
      TITLE = {On a problem of formal logic},
      JOURNAL = {Proc. London Math. Soc.},
      FJOURNAL = {},
      VOLUME = {30},
      YEAR = {1929},
      NUMBER = {},
      PAGES = {264--286},
      ISSN = {},
      JFMNUMBER = {55.0032.04},
      }
  • [T87] A. Thomason, "Pseudorandom graphs," in Random Graphs ’85, Karoński Michałand Palka, Z., Ed., Amsterdam: North-Holland, 1987, pp. 307-331.
    @incollection{T87, MRKEY = {930498},
      AUTHOR = {Thomason, Andrew},
      EDITOR = {Karo{ń}ski, Micha{\l}and Palka, Zbigniew},
      TITLE = {Pseudorandom graphs},
      BOOKTITLE = {Random Graphs {\rm'85}},
      VENUE = {Poznań, Poland, 1985},
      SERIES = {North-Holland Math. Stud.},
      NUMBER = {144},
      PAGES = {307--331},
      PUBLISHER = {North-Holland},
      ADDRESS = {Amsterdam},
      YEAR = {1987},
      MRCLASS = {05C80},
      MRNUMBER = {89d:05158},
      MRREVIEWER = {Edward R. Scheinerman},
      ZBLNUMBER = {0632.05045},
      }
  • [T88] A. Thomason, "An upper bound for some Ramsey numbers," J. Graph Theory, vol. 12, iss. 4, pp. 509-517, 1988.
    @article{T88, MRKEY = {968746},
      AUTHOR = {Thomason, Andrew},
      TITLE = {An upper bound for some {R}amsey numbers},
      JOURNAL = {J. Graph Theory},
      FJOURNAL = {Journal of Graph Theory},
      VOLUME = {12},
      YEAR = {1988},
      NUMBER = {4},
      PAGES = {509--517},
      ISSN = {0364-9024},
      CODEN = {JGTHDO},
      MRCLASS = {05C55},
      MRNUMBER = {90c:05152},
      ZBLNUMBER = {0661.05043},
      MRREVIEWER = {R. H. Schelp},
      }

Authors

David Conlon

Department of Pure Mathematics and Mathematical Statistics
Centre for Mathematical Sciences
University of Cambridge
Wilberforce Road
Cambridge
CB3 0WB
United Kingdom