An improved bound on the minimum size of Turán $(r+1,r)$-systems

Abstract

For positive integers $n\ge s>r$, let $T(n,s,r)$ denote the minimum number of edges in an $r$-uniform hypergraph on $n$ vertices such that every $s$-set of vertices contains at least one edge. A simple averaging argument shows that the ratio $T(n,s,r)/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ is non-decreasing in $n$ and we denote its limit as $n\to \infty$ by $t(s,r)$. The case $s=r+1$ has a rich history, with the previously best known asymptotic bounds for $r\to \infty$ being $1\le r\cdot t(r+1,r)\le \mathrm{4.91...}$ . In this paper, we present a simple probabilistic construction which shows that $(r+2)\cdot t(r+1,r)\le 4$ for every $r\ge 1$. We also derandomise it and discuss applications to covering codes.