pith. sign in

arxiv: 1605.01982 · v1 · pith:E3GNFFPLnew · submitted 2016-05-06 · 🧮 math.CO

On a conjecture of Stein

classification 🧮 math.CO
keywords sizefracmatchingpartialrainbowthereconjecturestein
0
0 comments X
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.