Ryser–Brualdi–Stein conjecture on rainbow matchings
Ryser–Brualdi–Stein conjecture on rainbow matchings
Let be the complete bipartite graph with vertices in each part, and let its edges have a proper coloring with 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 ; moreover, if 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 , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.