Skip to main content
1 of 2

First passage percolation for general graphs

There have been many questions about the behavior of first-passage percolation on specific graphs. In particular, it seems like cliques, grids, random graphs, and ladders are well-studied. But I can't find much on general graphs. Rather than computing the distance explictly, I just want to show that the distance concentrates.

Note that the variance of a sum of independent Bernoulli random variables is always less than its expectation, so we get good concentration bounds even if the mean is small. More generally, consider a graph G and let the weights be independent (not necessarily i.d.) Bernoullis. For any two vertices s and t, does the shortest path distance between s and t have variance less than its mean as long as the distance is greater than 1? I am especially interested in the case where the Bernoullis are heavily biased towards 0.