On a conjecture of Stein
classification
🧮 math.CO
keywords
sizefracmatchingpartialrainbowthereconjecturestein
read the original abstract
Stein proposed the following conjecture: if the edge set of $K_{n,n}$ is partitioned into $n$ sets, each of size $n$, then there is a partial rainbow matching of size $n-1$. He proved that there is a partial rainbow matching of size $n(1-\frac{D_n}{n!})$, where $D_n$ is the number of derangements of $[n]$. This means that there is a partial rainbow matching of size about $(1- \frac{1}{e})n$. Using a topological version of Hall's theorem we improve this bound to $\frac{2}{3}n$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.