Lower bounds for Ramsey numbers of bounded degree hypergraphs

Abstract

We prove that, for all $k\ge 3,$ and any integers $\hat{I}”,n$ with $n\ge \hat{I}”,$ there exists a $k$-uniform hypergraph on $n$ vertices with maximum degree at most $\hat{I}”$ whose $4$-color Ramsey number is at least ${\mathrm{tw}}_k(c_k\hat{I}”)\cdot n$, for some constant $c_k>0$, where ${\mathrm{tw}}_k$ denotes the tower function. For $k\ge 4,$ this is tight up to the constant $c_k$ and for $k=3$ it is known to be tight up to a factor of $\log \hat{I}”$ on top of the tower. It extends a well-known result of Graham, Rödl and Ruciński for graphs and answers a question of Conlon, Fox and Sudakov from 2008.

Improved result to a tight linear dependence on $\hat{I}”$ on top of the tower