On the Number of Maximal Intersecting $k$-Uniform Families and Further Applications of Tuza's Set Pair Method

Zoltán Lóránt Nagy, Balázs Patkós

Abstract


We study the function $M(n,k)$ which denotes the number of maximal $k$-uniform intersecting families $\mathcal{F}\subseteq \binom{[n]}{k}$. Improving a bound of Balogh, Das, Delcourt, Liu and Sharifzadeh on $M(n,k)$, we determine the order of magnitude of $\log M(n,k)$ by proving that for any fixed $k$, $M(n,k) =n^{\Theta(\binom{2k}{k})}$ holds. Our proof is based on Tuza's set pair approach.

The main idea is to bound the size of the largest possible point set of a cross-intersecting system. We also introduce and investigate some related functions and parameters.


Keywords


maximal, uniform intersecting system, set pair, cross-intersecting, Bollobás-theorem

Full Text:

PDF