Timeline for Shortest grid-graph paths with random diagonal shortcuts
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2017 at 12:37 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Image links broken; now fixed.
|
| Nov 25, 2010 at 17:54 | answer | added | Raphaël Rossignol | timeline score: 7 | |
| Nov 14, 2010 at 2:23 | answer | added | Omer | timeline score: 5 | |
| Nov 13, 2010 at 23:22 | comment | added | Joseph O'Rourke | @Andrew and Tom: That's a cool connection! I am perhaps overly wedded to the geometric viewpoint, but I can see this is really "just" combinatorics. | |
| Nov 13, 2010 at 23:21 | comment | added | Tom LaGatta | Edit: the longest increasing subsequences of permutations problem. | |
| Nov 13, 2010 at 23:07 | comment | added | Tom LaGatta | Andrew: a lot of work has been done on the longest increasing subsequences of permutations, and it is closely related to last-passage percolation and random matrix models. | |
| Nov 13, 2010 at 23:06 | answer | added | Tom LaGatta | timeline score: 5 | |
| Nov 13, 2010 at 21:27 | comment | added | Andrew D. King | This seems to me to reduce to a somewhat more natural question on strictly increasing sequences. That is, given a grid with 0-1 entries chosen from your distribution, find a maximum set of 1s that is strictly increasing in both x and y coordinates. I would guess that such a thing is well understood (and can be managed with a straightforward recurrence), but I'm no expert. | |
| Nov 13, 2010 at 20:49 | comment | added | j.c. | I meant the variance. Thanks, very interesting. | |
| Nov 13, 2010 at 19:17 | history | edited | Joseph O'Rourke | CC BY-SA 2.5 |
Typo.
|
| Nov 13, 2010 at 18:40 | comment | added | Joseph O'Rourke | @jc: That is one of the natural questions I did not ask. What is the expected maximum departure from the diagonal? [I assume this is what you mean?] This is of course connected to the expected length. Or do you mean: What is the variance in my plot? If the latter, the answer is: Extremely small. That I could quantify. The five runs that determine the point plotted for $n=200$ fall within 303.5$\pm$1.6. | |
| Nov 13, 2010 at 18:22 | comment | added | j.c. | Do you have data on the fluctuations away from linearity? | |
| Nov 13, 2010 at 18:15 | answer | added | Ori Gurel-Gurevich | timeline score: 7 | |
| Nov 13, 2010 at 16:50 | answer | added | R W | timeline score: 10 | |
| Nov 13, 2010 at 15:40 | answer | added | sleepless in beantown | timeline score: 5 | |
| Nov 13, 2010 at 15:38 | comment | added | Joseph O'Rourke | Obvious but useful observation, and I have to admit I didn't see its implication. Thanks! | |
| Nov 13, 2010 at 14:34 | comment | added | JBL | This is a trivial comment, but the growth rate has to be linear in $n$ as it is bounded between $n\sqrt{2}$ and $2n$. | |
| Nov 13, 2010 at 14:01 | history | asked | Joseph O'Rourke | CC BY-SA 2.5 |