On the number of maximal intersecting k-uniform families and further applications of Tuza's set pair method

preprint2015arXivOpen access

Abstract

We study the function M(n,k)M(n,k) which denotes the number of maximal kk-uniform intersecting families F⊆([n]k)F\subseteq \binom{[n]}{k}. Improving a bound of Balogh at al. on M(n,k)M(n,k), we determine the order of magnitude of log⁡M(n,k)\log M(n,k) by proving that for any fixed kk, M(n,k)=nΘ((2kk))M(n,k) =n^{Θ(\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.