Long and short paths in uniform random recursive dags (Q2431087): Difference between revisions

The authors' main concern is the model of the uniform random recursive \(k\)-directed acyclic graph. This random directed graph is constructed as follows. There is a root vertex labeled as 0 and each succesive node labeled from 1 to \(n\) is joined to \(k\) of the previous nodes chosen uniformly at random with replacement. The authors provide results about the length of a random path starting from a certain node and leading to the root node. In particular, they show convergence in probability to a certain constant which they provide explicitly. However, the main result of the paper regards the length of the shortest path to the root that starts at vertex \(n\). In particular, they show that when divided by \(\log n\), this converges in probability to a certain constant which is determined implicitly through a certain function. Moreover, they show that the maximum shortest distance also satisfies this.