Convergence to the Tracy-Widom distribution for longest paths in a directed random graph

• We consider a directed graph on the 2-dimensional integer lattice, placing a directed edge from vertex (i(1), i(2)) to (j(1), j(2)), whenever i(1) <= j(1), i(2) <= j(2), with probability p, independently for each such pair of vertices. Let L-n,L-m denote the maximum length of all paths contained in an n x m rectangle. We show that there is a positive exponent a, such that, if m/n(a) -> 1, as n -> infinity, then a properly centered/rescaled version of L-n,L-m converges weakly to the Tracy-Widom distribution. A generalization to graphs with non-constant probabilities is also discussed.

Subject headings

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Keyword

Random graph

last passage percolation

strong approximation

Tracy-Widom distribution

Publication and Content Type

ref (subject category)

art (subject category)