On Ramsey numbers of hedgehogs. (18th January 2020)

• Record Type: Journal Article
• Authors: Fox, Jacob; Li, Ray
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 1(2020)
• Page Start: 101
• Page End: 112
• Publication Date: 2020-01-18
• Subjects: Primary 05C55, -- Secondary 05C65; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548319000312
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: The hedgehog H t is a 3-uniform hypergraph on vertices $1, \ldots, t + \left({\matrix{t \cr 2}}\right)$ such that, for any pair ( i, j ) with 1 ≤ i < j ≤ t, there exists a unique vertex k > t such that { i, j, k } is an edge. Conlon, Fox and Rödl proved that the two-colour Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-colour Ramsey number grows exponentially in the square root of the number of vertices. They asked whether the two-colour Ramsey number of the hedgehog H t is nearly linear in the number of its vertices. We answer this question affirmatively, proving that r ( H t ) = O ( t 2 ln t ).