By Fedor Petrov


2019-03-14 21:58:51 8 Comments

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.

2 comments

@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.


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.

@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.

Related Questions

Sponsored Content

0 Answered Questions

4 Answered Questions

1 Answered Questions

0 Answered Questions

0 Answered Questions

Colouring a graph whose edge set is a special union of cliques

0 Answered Questions

Kempe chain color swaps in a partially colored map

1 Answered Questions

[SOLVED] Counting the number of $(d_v,d_c)$ regular bipartite graphs

2 Answered Questions

[SOLVED] Building graphs as unions of disjoint edges

  • 2013-11-12 15:40:27
  • edgecoloring
  • 152 View
  • 3 Score
  • 2 Answer
  • Tags:   co.combinatorics

1 Answered Questions

2 Answered Questions

[SOLVED] Colourings of Graphs with extra conditions

Sponsored Content