A new construction of non-extendable intersecting families of sets (Q311538)

From MaRDI portal





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
    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

    Identifiers