Multiplicity Ryser-Brualdi-Stein conjecture

Let GG be a complete bipartite graph on 2n2n vertices whose edge set is decomposed into perfect matchings MiM_i, for i=1,,ni=1,\ldots,n. Let a1,,anN0a_1,\ldots,a_n\in\mathbb{N}_0 be nonnegative integers satisfying

iai=n1.\sum_i a_i=n-1.

A matching with prescribed multiplicities is a matching whose intersection with each MiM_i has the specified size. Multiplicity Ryser-Brualdi-Stein conjecture. There exists a matching MM in GG such that

MMi=ai|M\cap M_i|=a_i

for every i{1,,n}i\in\{1,\ldots,n\}. 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

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.