Timeline for What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Current License: CC BY-SA 4.0
35 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2018 at 19:02 | history | edited | j.c. | CC BY-SA 4.0 |
replace broken link to mathematica notebook with internet archive link, replace images (not archived) with figures from the notebook, fix a few typos
|
| Sep 20, 2010 at 22:14 | comment | added | Bill Thurston | I think this was the content of the deleted comment: If it were the case that the growth rate is $O(n^{5+\epsilon})$ for every $\epsilon > 0$, that should imply the Hausdorff dimension of limits of enlarged views of the diameter have Hausdorff dimension 1, since the limit of Delaunay distance is quite uniform. This doesn't seem right. I don't think the selective pressure for a path to be part of the main trunk is strong enough to straighten it. My hunch is based on the rapidity of decay of tails of Gaussian distributions: very rare things aren't much better than rare things. | |
| Sep 20, 2010 at 18:22 | comment | added | Bill Thurston | I think this was the content of the deleted comment: If it were the case that the growth rate is $O( n^.5 + \epsilon)$ for every $\epsilon > 0$, that should imply the Hausdorff dimension of limits of enlarged views of the diameter have Hausdorff dimension 1, since the limit of Delaunay distance is quite uniform. This doesn't seem right. I don't think the selective pressure for a path to be part of the main trunk is strong enough to straighten it. My hunch is based on the rapidity of decay of tails of Gaussian distributions: very rare things aren't much better than rare things. | |
| Sep 20, 2010 at 14:14 | comment | added | Bill Thurston | @Peter: I wish I knew how to edit comments, so my TeX booboo wouldn't make all comments so wide on the page. I'm not yet convinced, either, it's just at the level of plausibility. I'm guessing someone knows enough about percolation to make a rigorous argument. If not, I think divide-and-conquer might work. For $P \cap $ rectangle, take the infimum of functions like $F$ in comments above. This function, along the boundary, seems like it might be enough to build the same data when two rectangles are joined, and with a little more combinatorial information, enough to compute depth and diameter. | |
| Sep 20, 2010 at 13:04 | comment | added | Peter Shor | @Bill: I'm just remembering my random planar matching results, where it was impossible to tell experimentally a $\log^c n$ coefficient from an $n^\alpha$ coefficient, for small $\alpha$. The only way you could figure out the right answer was from a theoretical argument. (Such as in your last comment, although that hasn't really convinced me yet.) | |
| Sep 20, 2010 at 4:59 | comment | added | Bill Thurston | @Peter Shor: Ps: here's data from another version of the experiment, this time it's the mean log diameter, for 2^k, {k,2,8}, again 25 trees for each diameter. {1.03374, 1.71446, 2.30459, 2.91138, 3.41588, 3.92263, 4.37669} Here's what Mma says, when I try to fit: Fit[Log@data1, {1, x + 1, Log[Log[2^(x + 1)] Sqrt[x + 1]]}, x] -0.417826 - 0.0852807 (1 + x) + 0.933709 Log[Sqrt[1 + x] Log[2^(1 + x)]] giving a much bigger coefficient to $\log(n \sqrt n) )$. The data in the answer though has more balanced coefficients. | |
| Sep 20, 2010 at 4:53 | comment | added | Bill Thurston | @Peter Shor: Yes, interesting, that also gives a reasonable fit, perhaps better. I don't think the data is enough to definitively distinguish these two. It should be easy to run bigger experiments, but do you have a theoretical reason to think it should be $O(\sqrt n \log n)$? My reasoning above only shows it has to be more than $O(\sqrt n)$, although there are probably ways to refine it. | |
| Sep 20, 2010 at 4:19 | comment | added | Peter Shor | Wouldn't $O(\sqrt{n} \log n)$ also be a reasonable fit with the data? | |
| Sep 19, 2010 at 16:36 | comment | added | Bill Thurston | Another point: in these experiments, it's best to look at the mean(log diameter), rather than log(mean diameter), since empirically it seems to be governed multiplicatively. I started out using the second measurement, which is what the plot shows, but then ran the experiment again using the first; they're all in the same ballpark, so I didn't edit the response. It would seem interesting if the limiting standard deviation of the distribution of log diameter converges to something positive. However, if there's a multiplicative random process, standard deviation might stabilize much later. | |
| Sep 19, 2010 at 13:29 | comment | added | Bill Thurston | @Louigi. I inserted a link to the Mathematica code. I feel a little sheepish that I didn't think of it until you suggested it, given my recent response to mathoverflow.net/questions/39096. The question was intriguing, and fun to think about --- thanks for posing the question! BTW, I do think the lower bound for Delaunay distances would not be hard to show by similar methods, using the smuggling metric --- it's almost there already. One way, I think, would be to look at concentric Euclidean circles about a vertex, spaced apart widely enough that the Delaunay annuli are usually thick. | |
| Sep 19, 2010 at 13:21 | history | edited | Bill Thurston | CC BY-SA 2.5 |
Added link to code, and description of further ideas for illustrating and analyzing
|
| Sep 19, 2010 at 12:26 | comment | added | Joseph O'Rourke | @Bill: The simulations are immediately convincing! "You can plainly see that paths connecting pairs of vertices are not converging to rectifiable, Lipschitz paths." Indeed. Very nice!! | |
| Sep 19, 2010 at 10:46 | vote | accept | Louigi Addario-Berry | ||
| Sep 19, 2010 at 10:18 | comment | added | Louigi Addario-Berry | @Bill, OK I'm now convinced the answer is unlikely to be $\Theta(\sqrt{n})$. Thanks very much for giving my question such a good think! Any chance you could post a link to your code? I'd like to fiddle with it, perhaps draw some MST geodesics in red, and also perhaps draw some partial MSTs to explore the connection with percolation a bit more. | |
| Sep 19, 2010 at 10:15 | vote | accept | Louigi Addario-Berry | ||
| Sep 19, 2010 at 10:46 | |||||
| Sep 19, 2010 at 2:58 | history | edited | Bill Thurston | CC BY-SA 2.5 |
added 404 characters in body
|
| Sep 19, 2010 at 1:46 | history | edited | Bill Thurston | CC BY-SA 2.5 |
Added data about experimental graph diameters
|
| Sep 19, 2010 at 1:04 | comment | added | Bill Thurston | @Louigi: I'm not sure whether to expect there to be a limiting process for Euclidean MST geodesics that is a measure on continuous, or hopefully, Hölder paths. I suspect they're rather tricky to pin down, because I suspect there's strong interactions between future and past. I.e., after a while, the geodesics should be on main trunks of the tree, which may have different characteristics than the ends of the tree. | |
| Sep 19, 2010 at 0:53 | history | edited | Bill Thurston | CC BY-SA 2.5 |
Added figures of simulations of MST's
|
| Sep 19, 2010 at 0:47 | comment | added | Bill Thurston | I used Mathematica's Combinatorica package and Computational Geometry Package to generate Euclidean MST's for some sets of points. I'm more convinced now. I'll insert figures | |
| Sep 19, 2010 at 0:36 | comment | added | Louigi Addario-Berry | Bill, also, thanks for the update on your response. I see your point, though I am not yet convinced. My objections are not very clear, but I want to think about whether it could happen that the pairs of points for which the tree distance is much greater than the distance in the plane are also typically at distance $o(1)$ from each other, which seems as though it could save my $\Theta(\sqrt{n})$ guess. | |
| Sep 19, 2010 at 0:03 | comment | added | Louigi Addario-Berry | @Bill, I haven't simulated, but I should, it oughtn't to be difficult to do. For your function F, I haven't really had time to think about it since yesterday but perhaps the condition of "no local minimum", plus a condition that $F$ increases to infinity at infinity (or at the north pole if you prefer) would do the trick. | |
| Sep 18, 2010 at 18:57 | history | edited | Bill Thurston | CC BY-SA 2.5 |
Added discussion of the MST
|
| Sep 18, 2010 at 12:32 | comment | added | Bill Thurston | @Louigi. Are there pictures somewhere of simulations of this question: in particular, I'm curious about the typical limiting geometry of shortest paths between points in the MST. Knowing the Hausdorff dimension of such paths should essentially be equivalent to knowing the exponent of $N$ for their length --- $\Theta(N^.5)$ should mean they're Lipschitz, $\Theta(N)$ would mean they're space-filling or nearly so, but in between answers seem plausible (from my limited perspective). | |
| Sep 17, 2010 at 11:19 | comment | added | Louigi Addario-Berry | Pimentel's proof is somewhat complicated (although, as mentioned, he proves something quite a bit more general, about first passage times out of boxes on the Delaunay triangulation with random edge weights) and I don't think it becomes too much simpler if you try to restrict to the special case of unit edge weights. | |
| Sep 17, 2010 at 5:53 | comment | added | Bill Thurston | @Louigi: You're right, I didn't give the lower bound. I think it follows from similar considerations, but I should think through how best to organize it. How difficult is Pimentel's proof? My strategy would be: the diameter of the smuggling metric ~ the Delaunay metric, already discussed. But the smuggling metric restricted to Q doesn't fluctuate too badly from the metric of the sphere. One image that would do it: a line of unlicensed peddlars goes across, trying to intercept most of the roads of the Delaunay triangulation while avoiding the towns, with not too many peddlars on any one road. | |
| Sep 17, 2010 at 2:42 | comment | added | Louigi Addario-Berry | @Bill, yes, I see. It sounds to me like saying $F$ has no local minimum in the complement of $T$ is the right kind of thing but I need to think it over a little. Also, now that I've done some absorbing: unless I'm mistaken the argument in your answer in fact gives an upper but not a lower bound on the diameter of the Delaunay. For the lower bounds you run into the issue of ensuring that there is no clever path the smuggler can take that on the whole stays quite far from radar installations. | |
| Sep 16, 2010 at 17:20 | comment | added | Bill Thurston | @Louigi, Thanks. I think I didn't write down the conditions that I visualized. I want $F$ that is non-decreasing to either side of $T$. Maybe it's enough to say $F$ has no local minimum in the complement of $T$. Probably the nongeneric boundary cases, when $T$ is not unique, need to be specified more carefully, but the idea is: if you can find a proper [=going to infinity at both ends] curve $\gamma$ transverse to any edge of $T$ at its endpoint where $F$ > the value at the midpoint of the edge, it gives a guarantee that the two halves of $P$ as split by $\gamma$ have distance = length(E). | |
| Sep 16, 2010 at 16:44 | comment | added | Louigi Addario-Berry | $F$ is 1-Lipschitz since $F(x)< d(0,x)$ for $x\in T$. Furthermore, F increases along any semi-infinite ray from $(0,0)$ that doesn't pass through one of the vertices of $T$, so $F$ has no local maxima except perhaps on one of $n-1$ special rays passing through a vertex of $T$. But $F$ is identically zero on these rays and just off of them it's positive, so there are no local maxima there, either. | |
| Sep 16, 2010 at 16:42 | comment | added | Louigi Addario-Berry | Unless I'm mistaken it's not true. Take the points $v_i=2\pi i/n$, for $i=1,\ldots,n-1$ (so skipping $+1$), and suppose $n$ odd, $n\ge 7$. Take the non-MST with edges $v_iv_{i+1}$, $i=1,\ldots,n-2$, $i\neq\lfloor n/2\rfloor$, plus edge $v_{n-1}v_1$. In other words, this looks like a regular polygon but there's a long edge on the far right, and a short edge missing on the far left. Then for $p\in\mathbb{R}^2$, which we can write as $cx$, $c\in [0,\infty)$ and $x$ on the tree, take $F(p)=cF(x)$. | |
| Sep 16, 2010 at 12:36 | comment | added | Bill Thurston | Is the following a true characterization of the MST? If it's true, is published? an MST is a tree $T$ whose vertices are $P$ and edges are straight line segments such that the function $d(*,P)$ restricted to $T$ extends to a function $F:\mathbb R^2 \rightarrow \mathbb R_+$ of Lipschitz norm 1 and with no local maximum on the whole plane. If so, this gives a structure to work with to distinguish the MST from an arbitrary spanning tree --- e.g., there is a metric similar to the smuggling metric. | |
| Sep 15, 2010 at 22:30 | comment | added | Bill Thurston | I now see I flew off talking about something that was not the actual question, but it was fun. I have a tendency to skip around when reading, and then start associating --- I need to pay more attention. My guess is that this picture is likely to help with the MST question, but I'll need to think it over --- we'll see. I've edited my answer to help clarify that I didn't answer the real question. | |
| Sep 15, 2010 at 22:27 | history | edited | Bill Thurston | CC BY-SA 2.5 |
added qualifiers about what this addresses
|
| Sep 15, 2010 at 21:54 | comment | added | Louigi Addario-Berry | I'll have to absorb that a little but it sounds very nice and substantially simpler than the existing argument that the diameter of the Delaunay is $\Theta(\sqrt{n})$. Do you see any way to use similar arguments to bound the diameter of the minimum spanning tree? | |
| Sep 15, 2010 at 20:57 | history | answered | Bill Thurston | CC BY-SA 2.5 |