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, plac-ing a directed edge from vertex (i1; i2) to (j1; j2), whenever i1 j1, i2 j2, with probability p, independently for each such pair of vertices. Let Ln;m denote the maximum length of all paths contained in an nm rectangle. We show that there is a positive exponent a, such that, if m=na! 1, as n! 1, then a properly cen-tered/rescaled version of Ln;m converges weakly to the Tracy-Widom distribution. A generalization to graphs with non-constant probabilities is also discussed