Ryser–Brualdi–Stein conjecture on rainbow matchings

Let Kn,nK_{n,n} be the complete bipartite graph with nn vertices in each part, and let its edges have a proper coloring with nn colors. A rainbow matching is a matching whose edges have pairwise distinct colors.

Ryser–Brualdi–Stein conjecture. Every such coloring contains a rainbow matching of size n1n-1; moreover, if nn is odd, it contains a perfect rainbow matching.

This is equivalent to the classical transversal problem for Latin squares: every Latin square has a partial transversal of size n1n-1, and odd-order Latin squares have a full transversal. The supplied text does not state a resolution.

Sources & referencesView supporting material

Primary source

Benny Sudakov, “Restricted subgraphs of edge-colored graphs and applications”, arXiv:2412.13945 (2024).

Additional references

3 papers in this index state this conjecture (2016–2024). The statement above is taken from the most recent of them; the others are arXiv:2007.00395, arXiv:1601.00943.

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.