A new combinatorial representation of the additive coalescent. Issue 2 (2nd April 2018)

• Record Type: Journal Article
• Authors: Marckert, Jean‐François; Wang, Minmin
• Is Part Of: Random structures & algorithms. Volume 54:Issue 2(2019)
• Page Start: 340
• Page End: 370
• Publication Date: 2018-04-02
• Subjects: additive coalescent -- Cayley trees -- increasing trees -- parking -- random walks on trees; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20775
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The standard additive coalescent starting with n particles is a Markov process which owns several combinatorial representations, one by Pitman as a process of coalescent forests, and one by Chassaing and Louchard as the block sizes in a parking scheme. In the coalescent forest representation, edges are added successively between a random node and a random root. In this paper, we investigate an alternative construction by, instead, adding edges between roots. This construction induces exactly the same process in terms of cluster sizes, meanwhile, it allows us to make numerous new connections with other combinatorial and probabilistic models: size biased percolation, parking scheme in a tree, increasing trees, random cuts of trees. The variety of the combinatorial objects involved justifies our interest in this construction.