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

Abstract

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\le j_1$, $i_2\le j_2$, with probability $p$, independently for each such pair of vertices. Let $L_{n,m}$ denote the maximum length of all paths contained in an $n\times m$ rectangle. We show that there is a positive exponent $a$, such that, if $m/n^a\to 1$, as $n\to \infty$, then a properly centered/rescaled version of $L_{n,m}$ converges weakly to the Tracy-Widom distribution. A generalization to graphs with non-constant probabilities is also discussed.

20 pages, 2 figures

References in corpus (1)

• Level-Spacing Distributions and the Airy Kernel