Stein's equitable perfect matching conjecture
Let be the complete bipartite graph with vertices in each part, and suppose its edges are partitioned into sets , where . A perfect matching is a matching containing one edge incident with every vertex. Stein's equitable perfect matching conjecture. There exists a perfect matching in such that
for every , with strict inequality holding for all but one value of . This conjecture is implied by Stein's rainbow matching conjecture and is known in the case by the result cited in the source; the general case remains open.
References
Primary source
Ron Aharoni, Eli Berger, Dani Kotlar and Ran Ziv, “On a conjecture of Stein”, arXiv:1605.01982 (2016).
Additional references
3 papers in this index state this conjecture (2013–2016). The statement above is taken from the most recent of them; the others are arXiv:1601.00943, arXiv:1305.1466.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.