ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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,…,an∈N0a_1,\ldots,a_n\in\mathbb{N}_0 be nonnegative integers satisfying

∑iai=n−1.\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

∣M∩Mi∣=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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.