Limit theorems for a random directed slab graph

2010/05/26 by Denis Denisov, Denisov, Denis, Sergey Foss +3 · 1 citation
Mathematics · #05C80 #06A06 (Secondary) #60F17 (Primary) 60K35 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1005.4806

openalex publication_date 2010/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a stochastic directed graph on the integers whereby a directed edge between i and a larger integer j exists with probability p_j-i depending solely on the distance between the two integers. Under broad conditions, we identify a regenerative structure that enables us to prove limit theorems for the maximal path length in a long chunk of the graph. The model is an extension of a special case of graphs studied by Foss and Konstantopoulos, Markov Process and Related Fields, 9, 413-468. We then consider a similar type of graph but on the `slab' \Z × I, where I is a finite partially ordered set. We extend the techniques introduced in the in the first part of the paper to obtain a central limit theorem for the longest path. When I is linearly ordered, the limiting distribution can be seen to be that of the largest eigenvalue of a |I| × |I| random matrix in the Gaussian unitary ensemble (GUE).

Citations

• Foundations of Modern Probability
• Limiting shape for directed percolation models

Cited by

• First-Passage Percolation on Spread-out line graphs: Microscopic Regime

Related

• Critical random graphs: limiting constructions and distributional properties
• Convergence to the Tracy-Widom distribution for longest paths in a\n directed random graph
• The scaling limit of a critical random directed graph
• Diameter and long paths in critical digraph
• Diameter of the stochastic mean-field model of distance