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
default for all languages
No label defined
    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