A new construction of non-extendable intersecting families of sets

MaRDI QIDQ311538zbMATH OpenFDO

Authors Kaushik Majumder

Publication date 13 September 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p28

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

intersecting family of \(k\)-setsmaximal \(k\)-cliques

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Extremal set theory (05D05)

Review text

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\).

Recommendations

• Almost Intersecting Families of Sets
• Contructions of some new nonextandable P_k sets
• Non-trivial intersecting families
• Non-trivial \(d\)-wise intersecting families
• Non-empty cross-2-intersecting families of subsets
• The structure of large non-trivial \(t\)-intersecting families of finite sets
• Some results on intersecting families of subsets
• Non-trivial r-wise intersecting families
• Intersecting families of finite sets and fixed-point-free 2-elements

Cites work

• A note on a series of families constructed over the cyclic graph
• Covers in uniform intersecting families and a counterexample to a conjecture of Lovász
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• On the maximum number of points in a maximal intersecting family of finite sets

Cited in

(7)

• Two extremal problems on intersecting families
• A note on a series of families constructed over the cyclic graph
• Covers in uniform intersecting families and a counterexample to a conjecture of Lovász
• A new construction for cancellative families of sets
• On a family of covering extended building sets
• A near-exponential improvement of a bound of Erdős and Lovász on maximal intersecting families
• Contructions of some new nonextandable P_k sets

This page was built for publication: A new construction of non-extendable intersecting families of sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q311538)