Department of
Applied
Mathematics

On the number of maximal intersecting k-uniform families

Balazs Patkos

Abstract

We study the function M(n,k) which denotes the number of maximal k-uniform intersecting families over an n-element ground set. Improving a bound of Balogh et al. 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((2k \choose 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.

This is a joint work with Zoltan L. Nagy.