Timeline for How many edge-disjoint paths go from upper left to lower right in a $4 \times N$ rectangular gridwork of streets?
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2011 at 2:55 | comment | added | Dylan Thurston | @Ken: I'm sure your $9 \times 9$ transition matrix works, but there is also a $6 \times 6$ matrix that works. See the updated matrix in my entry. Also see Dan Hoey's answer in rec.puzzles: groups.google.com/group/rec.puzzles/msg/… This does essentially the same thing. | |
| Jan 4, 2011 at 17:44 | comment | added | Ken Fan | @Christian: Thanks for the transition list. But, that method won't work because there can be multiple ways to string up a path for a given admissible covering. One can't use a matrix that has >1 entries to fix: local choices influence global possibilities. If one does the analog for 3 X N case using Dylan's matrix, one undercounts. But if Dylan's T is replaced with 6 X 6 that does account for multiple ways, one will overcount because the local situation affects the global situation. That's why I'm not sure about the 4 by N case even with order information. But 3 by N with order is good. | |
| Jan 4, 2011 at 16:51 | history | edited | Christian Blatter | CC BY-SA 2.5 |
added 135 characters in body
|
| Jan 4, 2011 at 2:29 | comment | added | Ken Fan | cntd: so I think in general, for the K by N case, it might be that T has a row and column for every up/down pattern with order information and that the entries can be > 1, and so the basic idea is correct and it's a linear recurrence relation for all those cases...This seems right...I'm not 100% sure yet. | |
| Jan 4, 2011 at 2:06 | comment | added | Ken Fan | 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. | |
| Jan 4, 2011 at 1:55 | comment | added | Ken Fan | 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.) | |
| Jan 4, 2011 at 1:42 | comment | added | Ken Fan | @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. | |
| Jan 3, 2011 at 15:54 | comment | added | Dylan Thurston | @Qiaochu, admissible colorings correspond not to paths, but to possible states of partial paths. | |
| Jan 3, 2011 at 9:31 | history | edited | Christian Blatter | CC BY-SA 2.5 |
added a paragraph
|
| Jan 2, 2011 at 16:04 | comment | added | Qiaochu Yuan | Is it obvious that admissible colorings correspond exactly to edge-dispoint paths? | |
| Jan 2, 2011 at 15:30 | history | answered | Christian Blatter | CC BY-SA 2.5 |