The bipartite multiplicity Ryser-Brualdi-Stein conjecture

About 4 years old · traced to

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 aia_i, for i∈{1,…,n}i\in\{1,\ldots,n\}, be non-negative integers satisfying

∑i=1nai=n−1.\sum_{i=1}^n a_i=n-1.

Multiplicity Ryser-Brualdi-Stein conjecture. There exists a matching MM in GG such that

∣M∩Mi∣=aifor each i∈{1,…,n}.|M\cap M_i|=a_i\qquad\text{for each }i\in\{1,\ldots,n\}.

This is presented as a multiplicity version of the Ryser-Brualdi-Stein conjecture. It would strengthen the three-colour bipartite conclusion to any number of colours and is open in the source. Noga Alon independently asked this question.

References

Primary source

Michael Anastos, David Fabian, Alp Müyesser and Tibor Szabó, “Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets”, arXiv:2212.03100 (2023).

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.