On The Time Constant for Last Passage Percolation on Complete Graph

Publication date 10 November 2017

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, l d o t s, n

, and i.i.d. sequence

X_{e} : e i n 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

m u

, where

m u

is called the time constant and coincides with the essential supremum of

X_{e}

. Second, when

m u < i n f t y

, it is proved that the deviation probability

P (W_{n} / n l e q m u - x)

decays as fast as

e^{- T h e t a (n^{2})}

, and as a corollary, an upper bound for the variance of

W_{n}

is obtained. Finally, when

m u = i n f t y

, lower and upper bounds for

W_{n} / n

are given.

This page was built for publication: On The Time Constant for Last Passage Percolation on Complete Graph