Lower Bounds for Small Ramsey Numbers on Hypergraphs

Abstract

The Ramsey number $r_k(p,q)$ is the smallest integer $N$ that satisfies for every red-blue coloring on $k$-subsets of $[N]$, there exist $p$ integers such that any $k$-subset of them is red, or $q$ integers such that any $k$-subset of them is blue. In this paper, we study the lower bounds for small Ramsey numbers on hypergraphs by constructing counter-examples and recurrence relations. We present a new algorithm to prove lower bounds for $r_k(k+1,k+1)$. In particular, our algorithm is able to prove $r_5(6,6)\ge 72$, where there is only trivial lower bound on $5$-hypergraphs before this work. We also provide several recurrence relations to calculate lower bounds based on lower bound values on smaller $p$ and $q$. Combining both of them, we achieve new lower bounds for $r_k(p,q)$ on arbitrary $p$, $q$, and $k\ge 4$.

A preliminary version of this paper appeared in the proceedings of COCOON 2019