On Ramsey numbers of hedgehogs. (18th January 2020) - Fox, Jacob; Li, Ray
Abstract: The hedgehog H t is a 3-uniform hypergraph on vertices $1, …, 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 ).