A Note on the Minimum Size of Turán Systems

Abstract

For positive integers $n \ge s > r$, a Turán $(n,s,r)$-system is an $n$-vertex $r$-graph in which every set of $s$ vertices contains at least one edge. Let $T(n,s,r)$ denote the the minimum size of a Turán $(n,s,r)$-system.

Upper bounds on $T(n,s,r)$ were established by Sidorenko for the case $s-r = \Omega(r/\ln r)$, based on a construction of Frankl-Rödl, and by a number of authors in the case $s-r = O(1)$. Motivated by these results and recent work of the second author, we investigate in this note the intermediate regime where $s = s(r)$ satisfies both $s - r = \Omega(1)$ and $s - r = O(r/\ln r)$, and establish upper bounds for $T(n,s,r)$ in this range as $r \to \infty$.