A new construction of non-extendable intersecting families of sets (Q311538)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A new construction of non-extendable intersecting families of sets |
scientific article; zbMATH DE number 6626792
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A new construction of non-extendable intersecting families of sets |
scientific article; zbMATH DE number 6626792 |
Statements
A new construction of non-extendable intersecting families of sets (English)
0 references
13 September 2016
0 references
Summary: \textit{L. Lovsz} [Mat. Lapok 26(1975), 209--264 (1977; Zbl 0397.05040)] 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 \textit{P. Frankl} et al. [J. Comb. Theory, Ser. A 74, No. 1, 33--42 (1996; Zbl 0846.05094)] 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\to\infty\).
0 references
intersecting family of \(k\)-sets
0 references
maximal \(k\)-cliques
0 references
0 references
0 references
0.8857868
0 references
0 references
0.8840046
0 references
0.8832538
0 references
0.8827597
0 references
0.88209456
0 references
0.8819726
0 references