Continuum cascade model of directed random graphs: traveling wave analysis

DOI10.1088/1751-8113/45/45/455002MaRDI QIDQ4920329zbMATH OpenOpenAlexFDO

Authors Yoshiaki Itoh, P. L. Krapivsky

Publication date 17 May 2013

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.3711

zbMATH Keywords

asymptotic behaviourcascade treedirected random graphslength of longest directed path

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study a class of directed random graphs. In these graphs, the interval [0,x] is the vertex set, and from each yin [0,x], directed links are drawn to points in the interval (y,x] which are chosen uniformly with density one. We analyze the length of the longest directed path starting from the origin. In the large x limit, we employ traveling wave techniques to extract the asymptotic behavior of this quantity. We also study the size of a cascade tree composed of vertices which can be reached via directed paths starting at the origin.

Recommendations

• Chain Lengths in Certain Random Directed Graphs
• Long paths and cycles in dynamical graphs
• Convergence to the Tracy-Widom distribution for longest paths in a directed random graph
• Convergence of directed random graphs to the Poisson-weighted infinite tree
• scientific article; zbMATH DE number 5722222

Cited in

(7)

• Limiting properties of random graph models with vertex and edge weights
• On the length of the shortest path in a sparse Barak-Erdős graph
• Impulsive processes on the weighted directed graphs
• Convergence to the Tracy-Widom distribution for longest paths in a directed random graph
• Convergence of directed random graphs to the Poisson-weighted infinite tree
• Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph
• Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models

This page was built for publication: Continuum cascade model of directed random graphs: traveling wave analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4920329)