Stein's equitable perfect matching conjecture

About 13 years old · traced to

Let Kn,nK_{n,n} be the complete bipartite graph with nn vertices in each part, and suppose its edges are partitioned into sets E1,…,EmE_1,\ldots,E_m, where m⩽nm\leqslant n. A perfect matching is a matching containing one edge incident with every vertex. Stein's equitable perfect matching conjecture. There exists a perfect matching FF in Kn,nK_{n,n} such that

∣F∩Ei∣⩾⌊∣Ei∣n⌋−1|F\cap E_i|\geqslant\left\lfloor\frac{|E_i|}{n}\right\rfloor-1

for every ii, with strict inequality holding for all but one value of ii. This conjecture is implied by Stein's rainbow matching conjecture and is known in the case m=3m=3 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

Never refreshed

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.