12
$\begingroup$

Background/Motivation

My interest in this problem traces back to an 11 year old girl who really took to one-way path counting problems. After doing several configurations of streets, she decided to come up with a problem of her own. She presented a $3 \times 3$ gridwork of two-way streets (forming 4 blocks in a $2 \times 2$ arrangement) and added the condition that a street could be traversed at most once. She asked how many such paths are there from upper left to lower right? (Answer: 16.)

Stirred by her enthusiasm, we tried generalizing in various directions. If you have 2 long horizontal streets with $N$ verticals, and let $a_N$ be the number of edge-disjoint paths from upper left to lower right and $b_N$ be the number of edge-disjoint paths from upper left to upper right, then $a_{N+1} = b_{N+1} = a_N + b_N$ for $N > 1$ and $a_1 = b_1 = 1$.

The $3 \times N$ case is trickier, but the number of edge-disjoint paths from upper left to lower right still satisfies a finite linear recurrence relation.

Naturally, I turned to OEIS and found sequences A013991-A013997, where Dan Hoey gives the number of edge-disjoint paths between opposite corners of $K \times N$ grids for $K = 3, 4, 5, ..., 9$ and small $N$. He also provides the first few values for the $N \times N$ cases (sequence A013990). (Note, his numbering counts blocks, not streets.) For $K=3$, he provides a generating function. In a recent communication, he explained the computer algorithm he used to compute the values but indicates that he did not find a recurrence relation for these sequences, so as far as I know, there is no known way to determine the answer to the title question for large $N$.

I've also spoken with Gregg Musiker, Bjorn Poonen, and Tim Chow about this problem. Although none knew how to do the $4 \times N$ case, Gregg simplified my recurrence relations for the $3 \times N$ case, Bjorn suggested many related questions and suggested an asymptotic formula for the $N \times N$ case, and Tim suggested looking at the related literature on self-avoiding walks, such as the book by Neal Madras and Gordon Slade, though it's not clear to me how related edge-disjoint and self-avoiding are with respect to counting them.

Because there are finite linear recurrence relations for the $2 \times N$ and $3 \times N$ cases, it seems natural to also ask:

Is there a finite linear recurrence relation for the number of edge-disjoint paths between opposite corners of a $4 \times N$ gridwork of streets?

Are these problems intractable?

$\endgroup$
7
  • 3
    $\begingroup$ An edge-disjoint path on a graph is the same thing as a self-avoiding walk on its line graph. $\endgroup$ Jan 1, 2011 at 19:40
  • $\begingroup$ If I remember correctly a talk I heard from C. Krattenthaler, the number of self-avoiding graph is the value of some explicit Pfaffian. Can anyyone confirm that ? $\endgroup$ Jan 1, 2011 at 21:39
  • $\begingroup$ For a related problem see kcollins.web.wesleyan.edu/publications/grid-r.pdf. $\endgroup$ Jan 2, 2011 at 2:50
  • $\begingroup$ Isn't www-fourier.ujf-grenoble.fr/%7Erivoal/journeehyp/bostan.pdf related? "A chess Rook can move any number of squares horizontally or vertically on an $N\times N$ chess board. Assuming that the Rook moves right or up at every step, how many different paths can the Rook travel in moving from the lower-left corner to the upper-right corner on the board?" $\endgroup$ Jan 2, 2011 at 12:11
  • $\begingroup$ @Wadim: no, that problem is much easier, since the rook cannot move down or to the left. $\endgroup$ Jan 2, 2011 at 16:02

2 Answers 2

9
$\begingroup$

To amplify on Christian's answer, the problem on a $K \times N$ grid for fixed $K$ and varying $N$ admits a finite-state transition model, so in particular is given by a linear recurrence.

The key is to find the right set of states. If you take an edge-disjoint path on a $K \times N$ grid and slice it on a vertical line through the middle passing through a set of horizontal edges, you'll see the path crossing along some odd number of these edges ($\le K$). On both the left and right we'll see a collection of paths with these endpoints. There's another constraint, that we end up with a single, connected path without disjoint loops; to take that in to account, also record a matching: which endpoints are paired up on the right hand side. All but one of the endpoints are paired up in this way. (You could also choose the left, and end up with a slightly different matrix.)

For instance, in the $3 \times N$ case, there are $6$ states. If we record an occupied edge by $\times$ and an unoccupied edge by $\circ$ and turn everything on its side, the states are $$ \times\circ\circ\quad\circ\times\circ\quad\circ\circ\times\quad\times_1\times_1\times \quad\times_1\times\times_1\quad\times\times_1\times_1 $$ where the subscript indicates the matching. (In this case, there is at most one matched pair.)

Next consider the transitions. If you consider two adjacent vertical slicings of a path, you'll see two possibly different states. The set of edges that are occupied in the middle is determined by which edges are occupied in the two different states. There is sometimes a choice about how the strands are connected up. However, some of these choices will be ruled out by the constraints on the connectivity; usually you will end up with just $0$ or $1$ possibilities.

For instance, in the $3 \times N$ case, with the states in the order above, I get the following matrix of possibilities: $$ M =\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} $$

For the ultimate answer, you want to look at paths that start at the upper-left and go to the lower-right. You can incorporate that nicely by adding an extra slice to the left of the entire diagram, with only the top slot occupied, and another to the right of the diagram, with only tho lower slot occupied.

Concretely, in the $3 \times N$ case, the number of paths is given by the $(1,3)$ entry of $M^N$.

For the $4 \times N$ case, you would get a $16 \times 16$ matrix, which is straightforward but somewhat tedious to work out. As a result, the answer will satisfy a linear recurrence of order $16$.

An interesting variation is to consider only crossingless paths. In this case, the matching must be crossingless, so we only get 5 states in the $3 \times N$ case and $12$ in the $4 \times N$ case.

Update Jan 7: The matrix above is wrong: it should be $$ M =\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 2 & 2 & 2\\ 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} $$

Update 2: And here's an image illustrating what is actually being counted: Matrix of edge disjoint paths I permuted the entries slightly, but they're labelled along the sides. The dotted paths are there to help in the counting: the non-allowed configurations would form a closed loop.

$\endgroup$
3
  • $\begingroup$ Thanks for including the matrix graphic! I understand now that you're counting physically different path snippets (which includes the information of pairings on the right) without regard to orientation. In retrospect, Christian does seem to have this notion (with pairings on the left), but I was thrown by the first matrix with all zeroes and ones. I think as far as the question I posed here goes, the problem is settled and I think it should be so noted. I wish I could accept both answers. I've marked both up, but will go ahead and accept this one because of the pretty picture... $\endgroup$
    – Ken Fan
    Jan 8, 2011 at 17:30
  • $\begingroup$ It looks like ImageShack has decided to delete your image and replace it with an ad banner. If you can, please reupload your image using the upload button in the editor toolbar. $\endgroup$ Aug 18, 2015 at 11:43
  • $\begingroup$ Thanks for the heads up. I was able to locate the image on my computer. $\endgroup$ Aug 19, 2015 at 15:56
6
$\begingroup$

Let $v_1$, $\ldots$, $v_N$ be the vertical streets and let $h_{1,j}$, $\ldots$, $h_{4,j}$ be the horizontal edges between $v_{j-1}$ and $v_j$. An admissible path $\gamma$ induces a coloring of the horizontal edges as follows: Consider a vertical street $v_j$. The path $\gamma$ uses either one or three of the incoming edges $h_{k,j}$ $(1\le k\le 4)$. If $\gamma$ uses one edge, color it black and the three other edges white. If $\gamma$ uses three edges, two of them are linked to each other by a part of $\gamma$ extending only to the left of $v_j$. Color these two edges red, the third edge black and the unused edge white. In all, there are 16 possible colorings $c:\lbrace 1,2,3,4\rbrace\to\lbrace b, r, w\rbrace$ that can result in this way. There is a $16\times 16$ transition matrix $T$ that encodes the possible matchings between the coloring $c$ of the edges $h_{k,j}$ and the coloring $c'$ of the edges $h_{k,j+1}$ (e.g., circles must be avoided). This matrix $T$ has to be determined "the hard way", i.e., by listing for each $c$ the possible $c'$. The number of admissible paths $\gamma$ is then obtained by applying $T^{N-1}$ to a suitable starting vector; so there is indeed a linear recurrence for the number of these paths.

An example: If $c$ contains one black and two red edges, then using the vertical edges on $v_j$ in an admissible way one may

(a) continue the black and the two red edges into the next column individually, maybe at a different level,

or

(b) connect the black end of $c$ to either one of the red ends by a vertical segment creating a $\supset$ and continue the other red edge of $c$ into the next column, but as a black edge,

and, if room on $v_j$ permits, one may

(c) throw in two red edges beginning on $v_j$ which are connected by a vertical segment creating a $\subset$.

Here is a pictorial list (hopefully complete) of the possible transitions $c\to c'$:

http://www.math.ethz.ch/~blatter/grid.pdf

$\endgroup$
8
  • 2
    $\begingroup$ Is it obvious that admissible colorings correspond exactly to edge-dispoint paths? $\endgroup$ Jan 2, 2011 at 16:04
  • $\begingroup$ @Qiaochu, admissible colorings correspond not to paths, but to possible states of partial paths. $\endgroup$ Jan 3, 2011 at 15:54
  • $\begingroup$ @all commenters: Thanks Dylan and Christian for these detailed answers. I've been thinking about them and here's what I've come up with so far. As described in both answers, it isn't quite right because there is more than one way to string up a given admissible covering into an edge disjoint path. However, in the 3 by N case, if one adds an order to the two horizontal left-to-right edges indicating which is traversed first, then you get a 9 by 9 matrix and this seems to work! For the 4 by N case, this would mean using a 28 by 28 matrix instead of 16 by 16. $\endgroup$
    – Ken Fan
    Jan 4, 2011 at 1:42
  • $\begingroup$ cntd.: However, I think that even with order of traversal information, there is a problem in the 4 by N case because it seems there can be more than one path per admissible covering. (I haven't actually checked it in the 3 by N case, but the agreement with the data seems to suggest that it is ok in this case.) But in the 4 by N case, using a variant of Dylan's notation with U=up and D=down, if o U1 D U2 is stacked on top of U1 D U2 o, there are two ways to string these together. (The numbers indicate the order the streets are traversed.) $\endgroup$
    – Ken Fan
    Jan 4, 2011 at 1:55
  • $\begingroup$ Here's the 9 by 9 matrix for the 3 by N case: [1 1 1 0 0 0 1 0 1; 1 1 1 1 1 1 1 1 1; 1 1 1 1 0 1 0 0 0; 1 1 0 1 0 0 0 0 0; 1 1 0 0 1 0 0 0 0; 0 1 0 0 0 1 0 0 0; 0 1 0 0 0 0 1 0 0; 0 1 1 0 0 0 0 1 0; 0 1 1 0 0 0 0 0 1]. Take powers of this and, just as Dylan says, the (1,3) entry seems to count the number of paths. $\endgroup$
    – Ken Fan
    Jan 4, 2011 at 2:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.