Uniform intersecting families with large covering number

DOI10.1016/J.EJC.2023.103747zbMATH Open1519.05239arXiv2106.05344MaRDI QIDQ6170804FDOQ6170804

Authors: Peter Frankl, Andrey B. Kupavskii 

Publication date: 10 August 2023

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

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}$.

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

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

zbMATH Keywords

Hilton-Milner theoremErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

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

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
• On large intersecting subfamilies of uniform setfamilies
• Diversity of uniform intersecting families
• 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)