Weekly seminars

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

by Sanjay Ramassamy (Institut de Physique Théorique (CEA Saclay))

auditorium (LAPTh)



9 chemin de Bellevue 74940 Annecy

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 and computing the speed of the front of the infinite-bin model, we show that C(p) is analytic for p>0 and is differentiable once but not twice at p=0. We also show via a perturbative expansion approach 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.

This is joint work with Bastien Mallein (Université Paris-13).