<p>Let's try a similar counting argument to the one in the earlier version of my answer, more carefully.</p>

<p>Given an input 0-1 matrix with q nonzeros, define a "solution" to be a permutation of the rows, a permutation of the columns, and the connected 0-1 matrix that one gets as output after performing the permutations. The important observation here is that there are at most $n^2 2^{5q}$ different output matrices possible: once we make one of $n^2$ choices for the position of one of the nonzeros, we can encode the rest of the output matrix in $5q$ bits by doing a preorder traversal of a spanning tree of the nonzeros and recording for each edge in the tree whether it goes to a leaf, whether it is the last edge from its parent, and what its direction is. So the number of solutions is in total at most $n^2 2^{5q} (n!)^2$.</p>

<p>Now each solution works only for a single input, because we can reverse the permutations to get the input back from the output matrix. The number of inputs that have exactly $c$ nonzeros per row is $\binom{n}{c}^n$, and for $c$ constant this can be rewritten $\exp(cn\log n-O(n))$. But for $q=cn$ the number of solutions is $\exp(2n\log n+O(cn))$. For $c&gt;2$, the inputs outnumber the solutions, so there is an unsolvable input.</p>

CC BY-SA 3.0
2011-11-19T15:24:56.560Z
Setting $c=3$ and neglecting $o(n)$ terms, I chased through your inequality to find the "breakeven" point, getting $n > 6*2^{15}/e^2$.  The latter value is remarkably close to 26608.
hardmath
CC BY-SA 3.0
2011-11-19T18:57:14.440Z
That's a curious numerical coincidence. I've asked about it at http://mathoverflow.net/questions/81368/numerical-coincidence-involving-the-number-1663
David Eppstein
CC BY-SA 3.0
2011-11-19T19:30:37.260Z
That's indeed an elegant and convincing proof. (I took me a little while to detail the approximations for my own benefit.) It remains to be seen whether anyone will manage to come up with a concrete counter-example. @hardmath's comment above suggests it could be difficult (the CE would be a an ugly beast); now one doesn't need to have the same number of crumbs in all rows of a CE.
Yann David
CC BY-SA 3.0
2011-11-18T20:20:14.720Z
2011-11-19T00:30:24.347Z
2011-11-19T00:30:24.347Z
David Eppstein
<p>I'd like to know whether the following simple problem has been studied before and if any solution is known.</p>

<p>Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said to be (locally) connected if their coordinates differ by at most one (i.e., if drawn as squares, they share at least one corner point).</p>

<p>Now, one can try to connect the crumbs (their set as a whole) by permutating the lines and the columns of the grid. In other words, the goal is to come up with a permutation of the lines and a permutation of the columns so that any two crumbs in the resulting grid are connected by a chain of (locally) connected crumbs.</p>

<p>Question: is there always a solution?</p>

<p>I don't quite know how to attack it. For lack of a better idea, I have written a raw program that looks for solutions by brute force (it generates the permutations at random and checks whether the resulting grid has its crumbs connected). The program has so far always found solutions on smallish (10x10 or 7x14) grids, and larger grids are clearly out of reach of its simplistic strategy (it would take too long to stumble at random across a solution).</p>

<p>Here is an example of a grid solved by the program:</p>

<p>Initial grid (crumbs are denoted by X's, empty cells by dots):</p>

<pre><code>   0 1 2 3 4 5 6 7 8 9 
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .
</code></pre>

<p>Solution:</p>

<pre><code>   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .
</code></pre>

<p>Naturally, the problem can readily be generalized to any dimension d > 2. I suppose other generalizations could be considered.</p>

<p>Thanks in advance,</p>

<p>Yann David</p>

CC BY-SA 3.0
2011-11-18T04:40:30.287Z
interesting problem. is there some application ?
Suresh Venkat
CC BY-SA 3.0
2011-11-18T19:10:20.150Z
@Tsuyoshi: you're right the figure I posted has a solution (the one you provided). I deleted it.
Marzio De Biasi
CC BY-SA 3.0
2011-11-18T20:21:46.123Z
Simultaneous crosspost is discouraged.  http://math.stackexchange.com/questions/83231/connecting-cells-by-line-and-column-permutations-in-a-finite-grid
Tsuyoshi Ito
<ds.algorithms><graph-theory><graph-algorithms>
Connecting cells by line and column permutations in a finite grid
Yann David
# Connecting cells by line and column permutations in a finite grid

(Asked by: username_0 on 2011-11-18)

I'd like to know whether the following simple problem has been studied before and if any solution is known.
Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said to be (locally) connected if their coordinates differ by at most one (i.e., if drawn as squares, they share at least one corner point).
Now, one can try to connect the crumbs (their set as a whole) by permutating the lines and the columns of the grid. In other words, the goal is to come up with a permutation of the lines and a permutation of the columns so that any two crumbs in the resulting grid are connected by a chain of (locally) connected crumbs.
Question: is there always a solution?
I don't quite know how to attack it. For lack of a better idea, I have written a raw program that looks for solutions by brute force (it generates the permutations at random and checks whether the resulting grid has its crumbs connected). The program has so far always found solutions on smallish (10x10 or 7x14) grids, and larger grids are clearly out of reach of its simplistic strategy (it would take too long to stumble at random across a solution).
Here is an example of a grid solved by the program:
Initial grid (crumbs are denoted by X's, empty cells by dots):
   0 1 2 3 4 5 6 7 8 9 
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .

Solution:
   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .

Naturally, the problem can readily be generalized to any dimension d > 2. I suppose other generalizations could be considered.
Thanks in advance,
username_0

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: interesting problem. is there some application ?  
> **username_2**: @Tsuyoshi: you're right the figure I posted has a solution (the one you provided). I deleted it.  
> **username_3**: Simultaneous crosspost is discouraged.  http://math.stackexchange.com/questions/83231/connecting-cells-by-line-and-column-permutations-in-a-finite-grid  

---

## 1 answers

### Answer by username_4 on 2011-11-18. Score: 7 | Accepted answer

Let's try a similar counting argument to the one in the earlier version of my answer, more carefully.

Given an input 0-1 matrix with q nonzeros, define a "solution" to be a permutation of the rows, a permutation of the columns, and the connected 0-1 matrix that one gets as output after performing the permutations. The important observation here is that there are at most $n^2 2^{5q}$ different output matrices possible: once we make one of $n^2$ choices for the position of one of the nonzeros, we can encode the rest of the output matrix in $5q$ bits by doing a preorder traversal of a spanning tree of the nonzeros and recording for each edge in the tree whether it goes to a leaf, whether it is the last edge from its parent, and what its direction is. So the number of solutions is in total at most $n^2 2^{5q} (n!)^2$.

Now each solution works only for a single input, because we can reverse the permutations to get the input back from the output matrix. The number of inputs that have exactly $c$ nonzeros per row is $\binom{n}{c}^n$, and for $c$ constant this can be rewritten $\exp(cn\log n-O(n))$. But for $q=cn$ the number of solutions is $\exp(2n\log n+O(cn))$. For $c>2$, the inputs outnumber the solutions, so there is an unsolvable input.

> **Comments:**
> **username_5**: Setting $c=3$ and neglecting $o(n)$ terms, I chased through your inequality to find the "breakeven" point, getting $n > 6*2^{15}/e^2$.  The latter value is remarkably close to 26608.  
> **username_4**: That's a curious numerical coincidence. I've asked about it at http://mathoverflow.net/questions/81368/numerical-coincidence-involving-the-number-1663  
> **username_0**: That's indeed an elegant and convincing proof. (I took me a little while to detail the approximations for my own benefit.) It remains to be seen whether anyone will manage to come up with a concrete counter-example. @username_5's comment above suggests it could be difficult (the CE would be a an ugly beast); now one doesn't need to have the same number of crumbs in all rows of a CE.  

---

