Convergence to the Tracy-Widom distribution for longest paths in a directed random graph
2013 (English)In: Latin American Journal of Probability and Mathematical Statistics, ISSN 1980-0436, E-ISSN 1980-0436, Vol. 10, no 2, 711-730 p.Article in journal (Refereed) Published
We consider a directed graph on the 2-dimensional integer lattice, placing 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 n×m rectangle. We show that there is a positive exponent a, such that, if m/na→1, as n→∞, then a properly centered/rescaled version of Ln,m converges weakly to the Tracy-Widom distribution. A generalization to graphs with non-constant probabilities is also discussed.
Place, publisher, year, edition, pages
2013. Vol. 10, no 2, 711-730 p.
Random graph, last passage percolation, strong approximation, Tracy- Widom distribution
Probability Theory and Statistics
IdentifiersURN: urn:nbn:se:uu:diva-304258OAI: oai:DiVA.org:uu-304258DiVA: diva2:1014917