Long and short paths in uniform random recursive dags
In a uniform random recursive k-directed acyclic graph, there is a root, 0, and each node in turn, from 1 to n, chooses k uniform random parents from among the nodes of smaller index. If Sn is the shortest path distance from node n to the root, then we determine the constant σ such that Sn/log n→σ in probability as n→∞. We also show that max 1≤i≤nSi/log n→σ in probability.