Classification of maximum hittings by large families

Abstract

For integers $r$ and $n$, where $n$ is sufficiently large, and for every set $X\subseteq [n]$ we determine the maximal left-compressed intersecting families $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ which achieve maximum hitting with $X$ (i.e. have the most members which intersect $X$). This answers a question of Barber, who extended previous results by Borg to characterise those sets $X$ for which maximum hitting is achieved by the star.

v2: minor corrections in response to reviewer comments. To appear in Graphs and Combinatorics