Uniform intersecting families with large covering number

DOI10.1016/J.EJC.2023.103747MaRDI QIDQ6170804zbMATH OpenFDO

Authors Peter Frankl, Andrey B. Kupavskii

Publication date 10 August 2023

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Hilton-Milner theoremErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: A family $mathcalF$ has covering number $au$ if the size of the smallest set intersecting all sets from $mathcalF$ is equal to $au$. Let $M(n,k,au)$ stand for the size of the largest intersecting family $mathcalF$ of $k$-element subsets of $1,ldots,n$ with covering number $au$. It is a classical result of ErdH os and Lov'asz that $M(n,k,k)le{k}^k$ for any $n$. In this short note, we explore the behaviour of $M(n,k,au)$ for $n<k^2$ and large $au$. The results are quite surprising: For example, we show that $M(n,k,au)=(1-o(1))n-1choosek-1$, if $n=lfloor{k}^{3/2}floor$, and $aulek-k^{3/4+o(1)}$ as $koinfty$; $M(n,k,au)<e^{-c{k}^{1/2}}nchoosek$, if $n=lfloor{k}^{3/2}floor$ and $au>k-frac12k^{1/2}$.

Recommendations

• Uniform Intersecting Families with Covering Number Restrictions
• Uniform intersecting families with covering number four
• An upper bound for the size of a \(k\)-uniform intersecting family with covering number \(k\)
• The number of covers in intersecting families with covering number three.
• Covering by intersecting families

Cites work

• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• A generalization of a theorem of Kruskal
• A near-exponential improvement of a bound of Erdős and Lovász on maximal intersecting families
• A short proof of a cross-intersection theorem of Hilton
• A simple proof of the Hilton-Milner theorem
• Covers in uniform intersecting families and a counterexample to a conjecture of Lovász
• Diversity of uniform intersecting families
• Erdős-Ko-Rado theorem for a restricted universe
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Non-trivial intersecting families
• On intersecting families of finite sets
• Regular bipartite graphs and intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Uniform intersecting families with covering number four

Cited in

(12)

• Intersecting k-uniform families containing all the k-subsets of a given set
• An upper bound for the size of a \(k\)-uniform intersecting family with covering number \(k\)
• The structure of maximal non-trivial \(d\)-wise intersecting uniform families with large sizes
• The number of covers in intersecting families with covering number three.
• Uniform s-Cross-Intersecting Families
• Covers in 4-uniform intersecting families with covering number three
• Covering by intersecting families
• Uniform intersecting families with covering number four
• Intersecting families with covering number three
• Diversity of uniform intersecting families
• On large intersecting subfamilies of uniform setfamilies
• Covers in 5-uniform intersecting families with covering number three

This page was built for publication: Uniform intersecting families with large covering number

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