On a conjecture of Stein

Original · EN

Stein proposed the following conjecture: if the edge set of Kₙ,ₙ 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-Dₙ/n!), where Dₙ is the number of derangements of [n]. This means that there is a partial rainbow matching of size about (1- 1/e)n. Using a topological version of Hall's theorem we improve this bound to 2/3n.