Resolution of multiple edges

Question

Given $k$ girls, they are given $kn$ balls so that each girl has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each colour. Two girls may exchange the balls (1 ball for 1 ball, so each girl still has $n$ balls), but no ball may participate in more than one exchange. They want to achieve the situation when each girl has balls of all $n$ colours. Is it always possible?

On other language. Given is a bipartite multigraph $G=(V_1,V_2,E)$, $|V_1|=k$, $|V_2|=n$, each vertex in $V_1$ has degree $n$ and each vertex in $V_2$ has degree $k$. We may replace two edges $ab,cd$ ($a,c\in V_1, b,d \in V_2$) to $ad,cb$, but new edges can not be used in exchanges anymore. Is it possible to get a usual $K_{k,n}$ without multiplicities?

If yes, this implies the positive answer to this question, which I find quite interesting itself.

I think I may prove it when $\min(n,k)\leqslant 3$, but already for $3$ there are many cases to consider.

UPDATE (May 2021) Here is the proof of $n=k$ case (due to Ilya Bogdanov), that was recently proposed as a problem on All-Russian olympiad.

Lemma. Let $r$ be a natural number and every girl has $r$ balls, and all girls together have exactly $r$ balls of any of $n$ colors. Then every girl can choose exactly one ball, such that all chosen balls have different colors.

Proof of Lemma. We say that a girl is friendly with a color if she has a ball with this color. Note that every $m=1,2,...,n$ girls are friendly with at least $m$ colors by pigeonhole principle (otherwise their $rm$ ball are colored with less than $m$ colors, thus there exists a color with more than $r$ balls of this color). Then with Hall`s Marriage theorem we can give to every girl one ball, and all these balls have different colors.

Let girls go to an $n \times n$ field and every girl choose her own column on the field. By Lemma they can choose $n$ balls of different colors, each girl choosing one ball, and put them in first row. Then by Lemma for $k=n-1,n-2,...,1$ they can choose balls of different colors and put them in the second, third,...,$n$-th row. Eventually we have a matrix, where in every row we have all balls of different colors, and in every column we have all balls of some girl. Now transposing this matrix (that corresponds to $n(n-1)/2$ legal balls changes) gives what we need: every column contains balls of different color.

Answer 1

First off, let me reformulate the problem. I call edges of $G$ black. Let $K_{k,n}$ be the complete graph on the same partite sets $V_1, V_2$, whose edges I will refer to as red. Let $H$ be the superposition (i.e. gluing of identical vertices) of $G$ and $K_{k,n}$. The graph $H$ is a two-colored graph, where each vertex has as many incident black edges as red ones. Hence, $H$ can be decomposed into a collection of alternating cycles (where the color of edges along each cycle alternate between black and red).

The problem is equivalent to finding an alternating cycle decomposition composed of 2- and 4-cycles only. Indeed, one can set up a one-to-one correspondence between pairs of black edges being exchanged in $G$ and 4-cycles (formed by the original two black edges and a pair of red edges corresponding to what the black edges become after the exchange) in $H$, and between black edges staying put in $G$ and 2-cycles (formed by parallel black and red edges) in $H$.

Theorem. The graph $H$ has an alternating cycle decomposition into 2- and 4-cycles.

---

The proof below may be incomplete. See comments.

Proof. Let $D$ be an alternating cycle decomposition of $H$ with the maximum number of 4-cycles. We will show that in $D$ there are no cycles of length $>4$. Assume that such a cycle $c$ exists.

I will call a red edge available if in $D$ it belongs to a cycle of length $\ne 4$.

Consider any triple of consecutive black-red-black edges (brb-path) $p$ in $c$. Clearly, its endpoints belong to distinct partite sets in $H$ and thus are connected by a red edge $e$. If $e$ is available, then we can form a new 4-cycle from $p$ and $e$ (and reshuffle the remaining edges from $c$ and the cycle of $e$ into some new cycles) to obtain a new cycle decomposition, where the number of 4-cycles is one more than in $D$. This contradiction to the definition of $D$ implies that $e$ is not available, and thus $e$ belongs to a 4-cycle $q$ in $D$. Let $T_1$ be the superposition of $c$ and $q$, and $b_1$ be any of the black edges of $q$. It is easy to see that $b_1$ is attached to $c$ (at an endpoint of $e$) in $T_1$.

Now, let us consider a brb-path $p_1$ starting at $b_1$ and then going along $c$. Again, its endpoinds are connected by a red edge $e_1$ in $H$. If $e_1$ is available, we can construct two new 4-cycles formed by $p_1$ and $e_1$, and by $p$ and $e$, which will destroy only one 4-cycle $q$. Hence, we'd obtain a cycle decomposition with a larger number of 4-cycles than $D$, a contradiction. It follows that $e_1$ is not available, and thus $e_1$ belongs to a 4-cycle $q_1$ in $D$. Let $T_2$ be the superposition of $T_1$ and $q_1$, and $b_2$ be a black edge of $q_1$ that is attached to $c$ in $T_2$.

Continuing this process we will get an infinite series $(T_k,b_k)$, where the size of $T_k$ grows, which is impossible. The contradiction proves that cycle $c$ does not exist, and thus all cycles in $D$ have length $2$ or $4$. QED

Answer 2

For the algorithmic solution, i.e. reducing the problem to an ordinary matching problem, the following idea helps:

• every of the $k$ girls has bucket with $n$ balls and every girl also has $n$ empty boxes that are labeled with the $n$ color names.

• now every girl puts the correctly filled boxes aside and looks for partner girls to exchange one of her leftover balls; say Ann has a blue leftover ball and an empty box labeled 'red'; so her problem is to find a girl with a red leftover ball and an empty box labeled 'blue'. That observation leads to the formulation as a matching problem.

After having put aside the correctly filled boxes the girls need to find a matching from the balls in the buckets to empty boxes that are labeled with such a ball's color.

Graph theoretic formulation:
every ball in a bucket corresponds to a vertex of partition $A$ and every empty box corresponds to a vertex of partition $B$; the edges in that bipartite graph connect the vertices of $A$ that corresponds to a ball of color $c$ to every vertex in $B$ that corresponds to an empty box that is also labeled $c$.

if a perfect matching exists, then its edges define the pairing for exchanging pairs of misplaced balls that renders each girl with balls of all $n$ colors.

Addendum:

I had assumed that only pairwise interchanges are the admissible operations; then the proposed algorithm works. If however also cyclic exchanges are allowed, then the proposed solution must be modified as follows:

Assume that all balls are in boxes and each girls has put as many balls as possible in a box that is labeled with a ball's color and then puts aside the balls and boxes where the ball's color matches the boxes label.

That leaves every girl with a maximal set of boxes whose labels do not match the color of the contained ball. Now we built a directed graph that is induced by arcs from all balls of color $c$ to all boxes with label $c$.

The solution, provided existence, corresponds then to a collection of vertex disjoint directed cycles that covers all vertices, which in turn correspond to the labeled boxes.

Answer 3

Another reformulation of the problem. Call the matrix $\bigl( \begin{smallmatrix}+1 & -1\\ -1 & +1\end{smallmatrix}\bigr)$ and its negation a tile. Suppose we are given a $k\times n$ matrix $M$ of natural numbers such that the sum in each row is $n$ and the sum in each column is $k$.

Can we tile it to obtain the all-1 matrix such that any entry of $M$ is covered by at most one tile's '+1' entry? Equivalently, can we tile the all-1 matrix to obtain $M$ such that any entry is covered by at most one tile's '-1' entry?

I think it is straight-forward to see why this latter version is equivalent to the original question.

Answer 4

One aspect of exhanging the balls a girl initially has with balls from other girls can be interpreted as an assignment problem, namely matching the balls a girl has with the colors (depicted as squares) of the balls she receives; that aspect guarantees, that the girl has balls of all colors after the exchange:

Another aspect is "communicating" the exchange of a pair of balls to the assignment-gadgets; that can be accomplished via the following gagdet, that connects two edges of different assignment-gadgets:

letting girl $i$ initially have balls $b_{ij}$, of which the color can be determined by evaluating by checking $\mathrm{color}(b_{ij})$; letting further $c_{ij}$ denote the color of the ball, against which ball $b_{ik}$ is exchanged.

The sought matching problem is then modeled by a graph with node sets $B_i=\lbrace b_{ij}\rbrace,\ C_i=\lbrace c_{ik}\rbrace,\ X_i=\lbrace x_{ijk}\rbrace$, for girl $i$. The edgesets are $\lbrace(b_{ij},c_{ik})\rbrace$ that constitute to the individual assignmet gadgets, $\lbrace(b_{ij},x_{ijk}),\ (x_{ijk},c_{ik})\rbrace$ that connect the assignment edges to the ball-exchange vertices, and $\lbrace(x_{iuv},x_{jrs})\ |\ \mathrm{color}(b_{iu})=c_{js}\ \wedge\ \mathrm{color}(b_{jr})=c_{iv}\rbrace$ for exchanging a pair of balls with colors $c_{iv}$ and $c_{js}$ between girls $i$ and $j$