Konstantopoulos, Takis and Trinajstić, Katja
(2013)
Convergence to the Tracy-Widom distribution for longest paths in a
directed random graph.
Unknown.
![[thumbnail of 1303.6237v2.pdf]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1303.6237v2.pdf - Submitted version Download (267kB) |
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.
| Item Type: | Article |
|---|---|
| Additional Information: | 20 pages, 2 figures |
| Uncontrolled Keywords: | math.PR, math.PR, 05C80, 60F05, 60K35, 06A06 |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 22 Aug 2018 14:29 |
| Last Modified: | 19 Jan 2023 01:26 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3025414 |
Share
Share
