Back to Search
Start Over
On the number of maximal intersecting k-uniform families and further applications of Tuza's set pair method
- Source :
- Electronic J. Combinatorics. 22(1) P1.83 (2015)
- Publication Year :
- 2015
-
Abstract
- We study the function $M(n,k)$ which denotes the number of maximal $k$-uniform intersecting families $F\subseteq \binom{[n]}{k}$. Improving a bound of Balogh at 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(\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.<br />Comment: 11 pages
- Subjects :
- Mathematics - Combinatorics
05D05, 05A16
Subjects
Details
- Database :
- arXiv
- Journal :
- Electronic J. Combinatorics. 22(1) P1.83 (2015)
- Publication Type :
- Report
- Accession number :
- edsarx.1501.00648
- Document Type :
- Working Paper