A new construction of non-extendable intersecting families of sets
The electronic journal of combinatorics, Tome 23 (2016) no. 3
In 1975, Lovász conjectured that any maximal intersecting family of $k$-sets has at most $\lfloor(e-1)k!\rfloor$ blocks, where $e$ is the base of the natural logarithm. This conjecture was disproved in 1996 by Frankl and his co-authors. In this short note, we reprove the result of Frankl et al. using a vastly simplified construction of maximal intersecting families with many blocks. This construction yields a maximal intersecting family $\mathbb{G}_{k}$ of $k-$sets whose number of blocks is asymptotic to $e^{2}(\frac{k}{2})^{k-1}$ as $k\rightarrow\infty$.
DOI :
10.37236/5976
Classification :
05D05, 05B05
Mots-clés : intersecting family of \(k\)-sets, maximal \(k\)-cliques
Mots-clés : intersecting family of \(k\)-sets, maximal \(k\)-cliques
Affiliations des auteurs :
Kaushik Majumder 1
@article{10_37236_5976,
author = {Kaushik Majumder},
title = {A new construction of non-extendable intersecting families of sets},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {3},
doi = {10.37236/5976},
zbl = {1344.05144},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5976/}
}
Kaushik Majumder. A new construction of non-extendable intersecting families of sets. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5976
Cité par Sources :