$K_4^{-}$-free triple systems without large stars in the complement

Abstract

The $n$-star $S_n$ is the $n$-vertex triple system with $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ edges all of which contain a fixed vertex, and $K_4^{-}$ is the unique triple system with four vertices and three edges. We prove that the Ramsey number $r(K_4^{-},S_n)$ has order of magnitude $n^2/\log n$. This confirms a conjecture of Conlon, Fox, He, Suk, Verstraëte and the first author. It also generalizes the well-known bound of Kim for the graph Ramsey number $r(3,n)$, as the link of any vertex in a $K_4^{-}$-free triple system is a triangle-free graph. Our method builds on the approach of Guo and Warnke who adapted Kim's lower bound for $r(3,n)$ to the pseudorandom setting.

35 pages