Multiplicity Ryser-Brualdi-Stein conjecture
Multiplicity Ryser-Brualdi-Stein conjecture
Let be a complete bipartite graph on vertices whose edge set is decomposed into perfect matchings , for . Let be nonnegative integers satisfying
A matching with prescribed multiplicities is a matching whose intersection with each has the specified size. Multiplicity Ryser-Brualdi-Stein conjecture. There exists a matching in such that
for every . The conjecture extends the rainbow matching formulation by prescribing how many edges are selected from each color class; the paper presents it as an open conjecture and proves the three-color case.
Sources & referencesView supporting material
Primary source
Simona Boyadzhiyska, Micha Christoph and Tibor Szabó, “Almost-perfect colorful matchings in three-edge-colored bipartite graphs”, arXiv:2504.15167 (2025).
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.