Journal of Combinatorics

Volume 8 (2017)

Number 3

Guest Editor: Steve Butler (Iowa State University)

Hedgehogs are not colour blind

Pages: 475 – 485

DOI: https://dx.doi.org/10.4310/JOC.2017.v8.n3.a4

Authors

David Conlon (Mathematical Institute, University of Oxford, United Kingdom)

Jacob Fox (Department of Mathematics, Stanford University, Stanford, California, U.S.A.)

Vojtěch Rödl (Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia, U.S.A.)

Abstract

We exhibit a family of 3-uniform hypergraphs with the property that their 2-colour Ramsey numbers grow polynomially in the number of vertices, while their 4-colour Ramsey numbers grow exponentially. This is the first example of a class of hypergraphs whose Ramsey numbers show a strong dependence on the number of colours.

Keywords

Ramsey numbers, hypergraphs

Full Text (PDF format)

D. Conlon is supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632.

J. Fox is supported by a Packard Fellowship, by NSF Career Award DMS-1352121 and by an Alfred P. Sloan Fellowship.

V. Rödl is supported by NSF Grant DMS-1301698.

Received 31 October 2015

Published 21 June 2017