The diameter is defined as $$d(G') = sup_{x,y in G} inf_{gamma} sum_{e in gamma} w_{e},$$ where the infimum is over all paths $gamma$ connecting $x$ to $y$, and the sum is over the edges $e$ which $gamma$ crosses. The graph structure is very crucial to this problem. If the graph is very connected (as in your example), then the diameter is essentially the maximum value of the variables ${w_i}$. A large fluctuation of a single $w_i$ will cause the diameter to be very large.
On the other hand, if you're dealing with something more like a lattice (e.g., a large, finite subset of $mathbb Z^2$), then the diameter is a combination of many independent random variables. Large fluctuations of any single variable will be muted and not affect the diameter much, and limit theorems will apply. A variant of Kingman's subadditive ergodic theorem will show that $$d(G') sim d(G).$$
Questions like this are very much in the realm of first-passage percolation. Check out this survey by Howard, as well as this one by Blair-Stahn on the arXiv.
No comments:
Post a Comment