Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis

Abstract

Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis Yoshiaki Itoh The Institute of Statistical Mathematics, Research Organization of Information and Systems, Japan ?: We study a class of directed random graphs. In these graphs, the interval [0,x] is the vertex set, while links are generated at random according to the following procedure: From each point y in the interval [0,x], directed links are drawn to points y' in the interval (├ y,x] ┤ which are chosen uniformly at random. 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 study also a continiuum binary search tree to compare with the continuum cascade model. This is a joint work with P.L. Krapivsy.