Two problems in graph Ramsey theory

Abstract

We study two problems in graph Ramsey theory. In the early 1970's, Erdős and O'Neil considered a generalization of Ramsey numbers. Given integers $n,k,s$ and $t$ with $n\ge k\ge s,t\ge 2$, they asked for the least integer $N=f_k(n,s,t)$ such that in any red-blue coloring of the $k$-subsets of $\{1,2,\dots ,N\}$, there is a set of size $n$ such that either each of its $s$-subsets is contained in some red $k$-subset, or each of its $t$-subsets is contained in some blue $k$-subset. Erdős and O'Neil found an exact formula for $f_k(n,s,t)$ when $k\ge s+t-1$. In the arguably more interesting case where $k=s+t-2$, they showed $2^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}n<\log f_k(n,s,t)<2n$ for sufficiently large $n$. Our main result closes the gap between these lower and upper bounds, determining the logarithm of $f_{s+t-2}(n,s,t)$ up to a multiplicative factor. Recently, Damásdi, Keszegh, Malec, Tompkins, Wang and Zamora initiated the investigation of saturation problems in Ramsey theory, wherein one seeks to minimize $n$ such that there exists an $r$-edge-coloring of $K_n$ for which any extension of this to an $r$-edge-coloring of $K_{n+1}$ would create a new monochromatic copy of $K_k$. We obtain essentially sharp bounds for this problem.

10 pages