2017/02/17 by Mubayi, Dhruv, Suk, Andrew · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1702.05509
The Ramsey number rk(s,n) is the minimum N such that for every red-blue coloring of the k-tuples of \1,…, N\, there are s integers such that every k-tuple among them is red, or n integers such that every k-tuple among them is blue. We prove the following new lower bounds for 4-uniform hypergraph Ramsey numbers: r4(5,n) gt; 2^nclog n \hbox and r4(6,n) gt; 2^2^cn1/5, where c is an absolute positive constant. This substantially improves the previous best bounds of 2^ncloglog n and 2^nclog n, respectively. Using previously known upper bounds, our result implies that the growth rate of r4(6,n) is double exponential in a power of n. As a consequence, we obtain similar bounds for the k-uniform Ramsey numbers rk(k+1, n) and rk(k+2, n) where the exponent is replaced by an appropriate tower function. This almost solves the question of determining the tower growth rate for \emph all classical off-diagonal hypergraph Ramsey numbers, a question first posed by Erd\H os and Hajnal in 1972. The only problem that remains is to prove that r4(5,n) is double exponential in a power of n.