On The Time Constant for Last Passage Percolation on Complete Graph

Abstract

This paper focuses on the time constant for last passage percolation on complete graph. Let $G_n=([n],E_n)$ be the complete graph on vertex set $[n]=\{1,2,\dots ,n\}$, and i.i.d. sequence $\{X_e:e\in E_n\}$ be the passage times of edges. Denote by $W_n$ the largest passage time among all self-avoiding paths from 1 to $n$. First, it is proved that $W_n/n$ converges to constant $\mu$, where $\mu$ is called the time constant and coincides with the essential supremum of $X_e$. Second, when $\mu <\infty$, it is proved that the deviation probability $P(W_n/n\le \mu -x)$ decays as fast as $e^{-\Theta (n^2)}$, and as a corollary, an upper bound for the variance of $W_n$ is obtained. Finally, when $\mu =\infty$, lower and upper bounds for $W_n/n$ are given.

12 pages, 1 figure

References in corpus (1)

• Limiting shape for directed percolation models