Barak-Erdös graphs and the infinite-bin model

Sanjay Ramassamy

IPhT

Mon, Jun. 14th 2021, 11:00-12:00

Salle Claude Itzykson, Bât. 774, Orme des Merisiers

Barak-Erdös graphs are the directed acyclic version of Erdös-Rényi random graphs : the vertex set is {1,...,n} and for each i<j with probability p we add an edge directed from i to j, independently for each pair i<j. The length of the longest path of Barak-Erdös graphs grows linearly with the number of vertices, where the growth rate C(p) is a function of the edge probability p.
Foss and Konstantopoulos introduced a coupling between Barak-Erdös graphs and a special case of an interacting particle system called the infinite-bin model. Using this coupling, we show that C(p) is analytic for p strictly positive and is differentiable once but not twice at p=0. We also show that the coefficients of the Taylor expansion at p=1 of C(p) are integers, suggesting that C(p) is the generating function of some class of combinatorial objects.
Barak-Erdös graphs arise as a special case of last-passage percolation on the complete directed acyclic graph.
This is joint work with Bastien Mallein (Université Paris-13).

Contact : Pierfrancesco
URBANI