Speed of convergence in first passage percolation and geodesicity of the average distance

Abstract

We give an elementary proof that Talagrand's sub-Gaussian concentration inequality implies a limit shape theorem for first passage percolation on any Cayley graph of Z^d, with a bound on the speed of convergence that slightly improves Alexander's bounds. Our approach, which does not use the subadditive theorem, is based on proving that the average distance is close to being geodesic. Our key observation, of independent interest, is that the problem of estimating the rate of convergence for the average distance is equivalent (in a precise sense) to estimating its "level of geodesicity".

arXiv commentThe proof of the main theorem contained a few mistakes that have been corrected. The presentation has also been improved

Cited by in corpus (4)

• Uniform fluctuation and wandering bounds in first passage percolation
• Lower bounds for fluctuations in first-passage percolation for general distributions
• Speed of Convergence and Moderate Deviations of FPP on Random Geometric Graphs
• Evolution and Limiting Configuration of a Long-Range Schelling-Type Spin System