On The Time Constant for Last Passage Percolation on Complete Graph

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\mathrm{/}n$ converges to constant $\mu$, where $\mu$ is called the time constant and coincides with the essential supremum of $X_e$. Second, when $\mu <\mathrm{\infty }$, it is proved that the deviation probability $P(W_n\mathrm{/}n\le \mu -x)$ decays as fast as $e^{-\mathrm{\Theta }(n^2)}$, and as a corollary, an upper bound for the variance of $W_n$ is obtained. Finally, when $\mu =\mathrm{\infty }$, lower and upper bounds for $W_n\mathrm{/}n$ are given.