Stability for Helly-type and triangle-free families

Abstract

We consider $k$-graphs, $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$, $k\ge 3$. A $k$-graph is called intersecting if any two of its edges have non-empty intersection. It is called a star if all its edges share a common vertex. The $k$-graph $\mathcal{F}$ is called Helly if all its intersecting subfamilies are stars. If the same is required only for subfamilies consisting of three edges, it is called triangle-free. It is well known that for $n\ge 3k/2$, the full star is the unique largest triangle-free family whence the largest Helly family as well. In 1984 Tuza proved the best possible bound $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n-k-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)+1$ for Helly families that are not stars, albeit only for some unspecified $n>n_0(k)$. The aim of this paper is twofold. First we establish the same bound for $n>2k$. Second we show that for $n>12k^2$ the same upper bound holds for triangle-free families. It is shown as well that it is not true for $2k<n\le 3k-4$.