An upper bound for the size of a k-uniform intersecting family with covering number k

DOI10.1016/J.JCTA.2016.11.001MaRDI QIDQ501681zbMATH OpenOpenAlexFDO

Authors Andrii Arman, Troy Retter

Publication date 9 January 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.04686

zbMATH Keywords

blocking numbercovering numberintersecting familyintersecting hypergraphtransversal

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05) Transversal (matching) theory (05D15)

Abstract: Let $r(k)$ denote the maximum number of edges in a $k$-uniform intersecting family with covering number $k$. ErdH{o}s and Lov'asz proved that $lfloork!(e-1)floorleqr(k)leq{k}^k.$ Frankl, Ota, and Tokushige improved the lower bound to $r(k)geqleft(k/2ight{)}^{k-1}$, and Tuza improved the upper bound to $r(k)leq(1-e^{-1}+o(1))k^k$. We establish that $r(k)leq(1+o(1))k^{k-1}$.

Recommendations

• Uniform intersecting families with large covering number
• Uniform intersecting families with covering number four
• Uniform Intersecting Families with Covering Number Restrictions
• The number of covers in intersecting families with covering number three.
• Covers in uniform intersecting families and a counterexample to a conjecture of Lovász

Cites work

• 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?)
• Inequalities for minimal covering sets in set systems of given rank

Cited in

(16)

• The Cayley isomorphism property for Cayley maps
• Coloring cross-intersecting families
• Covers in uniform intersecting families and a counterexample to a conjecture of Lovász
• Pseudo sunflowers
• An improved universal bound for \(t\)-intersecting families
• On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method
• Intersecting k-uniform families containing all the k-subsets of a given set
• Extremal problems in hypergraph colourings
• A near-exponential improvement of a bound of Erdős and Lovász on maximal intersecting families
• Independence numbers of Johnson-type graphs
• Uniform intersecting families with large covering number
• On the size of maximal intersecting families
• Intersecting families with covering number three
• Critically intersecting hypergraphs
• Intersecting families with covering number 3
• Best possible bounds on the double-diversity of intersecting hypergraphs

This page was built for publication: An upper bound for the size of a \(k\)-uniform intersecting family with covering number \(k\)

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