We consider an oriented acyclic version of the Erdős-Rényi random graph: the set of vertices is {1,...,n}, and for each pair i < j, an edge from i to j is independently added to the graph with probability p. The length of the longest path in such a graph grows linearly with the number of vertices in the graph, and its growth rate is a deterministic function C of the probability p of presence of an edge.
Foss and Konstantopoulos introduced a coupling between these graphs and a particle system called the "Infinite-bin model". By using this coupling, we prove some properties of C, that it is analytic on (0,1], its development in series at point 1 and its asymptotic behaviour as p goes to 0.
Further Information
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.