[SOLVED] Resolution of multiple edges

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.

@Max Alekseyev 2019-04-11 04:13:13

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

@Fedor Petrov 2019-04-11 11:24:36

Are edges from cycles of length 2 also available?

@Max Alekseyev 2019-04-11 11:44:12

Yes, we do not care about 2-cycles here.

@Fedor Petrov 2019-04-11 17:11:42

Can the problems occur when we start to use the same edges of $c$? It looks that this does not allow to get many disjoint 4-cycles as we need...

@Max Alekseyev 2019-04-11 20:45:59

@FedorPetrov: I've got same concern, but I did not have time to check this carefully. I'll add a notice in the answer and take a close look soon. In either case, I believe there is a proof somewhere along these lines.

@Fedor Petrov 2019-04-11 21:28:45

If I understand your procedure, each cycle which you are going to add contains some edges from $c$. They certainly can not be disjoint if there are too many of them. Actually something goes wrong quickly when $c$ has length 6.

@Manfred Weis 2019-04-07 19:35:45

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$$

@domotorp 2019-03-17 21:55:52

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.

@Brendan McKay 2019-03-17 23:59:50

I was about to post the same thing, but now I'm not sure. I assume rows are girls and columns are colours. The problem says that no ball can be involved in more than one exchange, but your formulation is that no (girl,colour) pair is involved in more than one exchange. Or did I misunderstand?

@Gerhard Paseman 2019-03-18 00:19:05

Also, tile suggests that the rows and columns are (numerically) adjacent. You might clarify that it is a submatrix of two arbitrary rows and columns. Gerhard "You Should See My Bathroom" Paseman, 2019.03.17.

@domotorp 2019-03-18 06:37:23

@Brendan This is why I wrote that it's easier to see the equivalence with the latter version - there's only a single 1 in every place, so you couldn't get more than 1 exchange.

@Manfred Weis 2019-03-17 17:27:49

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.

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.

@Gerhard Paseman 2019-03-17 18:47:50

Which would be nice if it could be done (and when k or n is 2 such a matching does exist). Now imagine three girls and three colors, where the arrangement is rrb,bbg,ggr. This can be resolved, but not by the matching you propose. Gerhard "If Only It Were Easy" Paseman, 2019.03.17.

@Fedor Petrov 2019-03-17 19:50:55

The matching in this graph does not always correspond to a family of exchanges, say, a cycle of length 3 is also a matching. Or what do I miss?

@Manfred Weis 2019-03-17 21:45:20

@FedorPetrov I have expanded my answer accordingly; I had not read your question careful enough, so I somehow missed that cyclic exchanges along cycles of arbitrary length are permitted. How would the girls agree on such an exchange along a long cycle?

@Manfred Weis 2019-03-17 21:50:12

@FedorPetrov in your question you say that "two girls may exchange a ball"; maybe you could give an example, how a correct exhange for rrb, bbg and ggr would look like when two girl exchange balls until each has rbg balls.

@Fedor Petrov 2019-03-17 22:22:42

1) rrb, bbg - rBb, bRg 2)rBb, ggr - rBG, gBr. Capital letter means that the ball can not be used anymore.

@Manfred Weis 2019-03-18 05:13:01

@FedorPetrov thanks vor the example; I see now, that I habe to rethink my algorithmic solution. Putting aside a maximal set of "correctly" colored balls doesn't solve the problem.