On the maximum number of points in a maximal intersecting family of finite sets

Abstract

Paul Erdős and László Lovász proved in a landmark article that, for any positive integer $k$, up to isomorphism there are only finitely many maximal intersecting families of $k-$sets (maximal $k-$cliques). So they posed the problem of determining or estimating the largest number $N(k)$ of the points in such a family. They also proved by means of an example that $N(k)\ge 2k-2+\frac{1}{2}\left(\genfrac{}{}{0ex}{}{2k-2}{k-1}\right)$. Much later, Zsolt Tuza proved that the bound is best possible up to a multiplicative constant by showing that asymptotically $N(k)$ is at most $4$ times this lower bound. In this paper we reduce the gap between the lower and upper bound by showing that asymptotically $N(k)$ is at most $3$ times the Erdős-Lovász lower bound. Conjecturally, the explicit upper bound obtained in this paper is only double the lower bound.