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 17:30 | vote | accept | Ken Fan | ||
| Jan 3, 2011 at 16:37 | answer | added | Dylan Thurston | timeline score: 9 | |
| Jan 3, 2011 at 16:10 | comment | added | Dylan Thurston | @Qiaochu: However, the line graph in this case is not planar, so I suspect the asymptotic behaviour will be quite different from the usual self-avoiding walks. If you don't allow crossings (so only 14 paths in the $3 \times 3$ case), then I would expect a similar shape to the answer for large $N$. | |
| Jan 2, 2011 at 22:43 | comment | added | Wadim Zudilin | @Qiaochu, I nevertheless believe that more general settings and the references in arxiv.org/abs/0909.1965 might be of help. There are many similar situations where one can prove that the generating function is or is not $D$-finite. | |
| Jan 2, 2011 at 16:02 | comment | added | Qiaochu Yuan | @Wadim: no, that problem is much easier, since the rook cannot move down or to the left. | |
| Jan 2, 2011 at 15:30 | answer | added | Christian Blatter | timeline score: 6 | |
| Jan 2, 2011 at 12:11 | comment | added | Wadim Zudilin | 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?" | |
| Jan 2, 2011 at 2:50 | comment | added | Richard Stanley | For a related problem see kcollins.web.wesleyan.edu/publications/grid-r.pdf. | |
| Jan 1, 2011 at 21:39 | comment | added | Denis Serre | 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 ? | |
| Jan 1, 2011 at 19:40 | comment | added | Qiaochu Yuan | An edge-disjoint path on a graph is the same thing as a self-avoiding walk on its line graph. | |
| Jan 1, 2011 at 18:35 | history | asked | Ken Fan | CC BY-SA 2.5 |