Families with no perfect matchings

DOI10.5070/C61055359zbMATH Open1498.05269arXiv2008.08792OpenAlexW4206380073MaRDI QIDQ5048439FDOQ5048439

Authors: Mihir Singhal 

Publication date: 16 November 2022

Published in: Combinatorial Theory (Search for Journal in Brave)

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.

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

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

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• Title not available (Why is that?)
• Intersecting Families are Essentially Contained in Juntas
• Proof of the Erdős matching conjecture in a new range
• 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

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)