Families with no perfect matchings

DOI10.5070/C61055359MaRDI QIDQ5048439zbMATH OpenOpenAlexFDO

Authors Mihir Singhal

Publication date 16 November 2022

Published in Combinatorial Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: We consider families of $k$-subsets of $1,dots,n$, where $n$ is a multiple of $k$, which have no perfect matching. An equivalent condition for a family $mathcalF$ to have no perfect matching is for there to be a blocking set, which is a set of $b$ elements of $1,dots,n$ that cannot be covered by $b$ disjoint sets in $mathcalF$. We are specifically interested in the largest possible size of a family $mathcalF$ with no perfect matching and no blocking set of size less than $b$. Frankl resolved the case of families with no singleton blocking set (in other words, the $b=2$ case) for sufficiently large $n$ and conjectured an optimal construction for general $b$. Though Frankl's construction fails to be optimal for $k=2,3$, we show that the construction is optimal whenever $kge100$ and $n$ is sufficiently large.

Recommendations

• On non-trivial families without a perfect matching
• Families with no matchings of size s
• Families without minimal numberings
• Almost intersecting families
• Families close to disjoint ones
• On families with bounded matching number
• On cross-intersecting families
• Perfect Triangle Families
• Families of sets with no matchings of sizes 3 and 4
• Families with no s pairwise disjoint sets

Cites work

• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting Families are Essentially Contained in Juntas
• Invitation to intersection problems for finite sets
• Maximal number of subsets of a finite set No k of which are pairwise disjoint
• On non-trivial families without a perfect matching
• Proof of the Erdős matching conjecture in a new range

Cited in

(2)

• Diamond-free families
• On non-trivial families without a perfect matching

This page was built for publication: Families with no perfect matchings

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