2011/10/14 by Jian Ding, Ding, Jian · 1 citation
Mathematics · Physics and Astronomy · #60C05 #60G70 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.1110.3361
openalex publication_date 2011/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a complete graph of size n, assign each edge an i.i.d. exponential variable with mean n. For λ>0, consider the length of the longest path whose average weight is at most λ. It was shown by Aldous (1998) that the length is of order log n for λ< 1/e and of order n for λ> 1/e. Aldous (2003) posed the question on detailed behavior at and near criticality 1/e. In particular, Aldous asked whether there exist scaling exponents μ, ν such that for λ within 1/e of order n-μ, the length for the longest path of average weight at most λ has order nν. We answer this question by showing that the critical behavior is far richer: For λ around 1/e within a window of α(log n)-2 with a small absolute constant α>0, the longest path is of order (log n)3. Furthermore, for λ≥ 1/e + β(log n)-2 with β a large absolute constant, the longest path is at least of length a polynomial in n. An interesting consequence of our result is the existence of a second transition point in 1/e + [α(log n)-2, β(log n)-2]. In addition, we demonstrate a smooth transition from subcritical to critical regime. Our results were not known before even in a heuristic sense.