2019/06/01 by Liu, S. Cliff
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1906.00132
The Ramsey number rk(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 rk(k+1, k+1). In particular, our algorithm is able to prove r5(6,6) ≥ 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 rk(p, q) on arbitrary p, q, and k ≥ 4.