[Zurück]

A. Panholzer:
"A combinatorial approach for discrete car parking on random labelled trees";
Journal of Combinatorial Theory Series A, 173 (2020), 105233.

We consider two analogues of a discrete version of the famous car parking problem of Rényi for trees, which are also known under the term random sequential adsorption. For both models, the blocking model, where cars arrive sequentially at the nodes and only park if the site and all neighbouring nodes are free, and the dimer model, where cars arrive sequentially at the edges and only park if both endnodes are free, we provide a detailed analysis of the number of occupied nodes in a randomly chosen labelled tree of a certain size. In particular, by introducing a combinatorial approach and an analytic combinatorics treatment, we show exact and asymptotic results for the first moments and thus characterize the jamming density, i.e., the limiting ratio of the mean number of occupied nodes to the total number of nodes in the tree; moreover, we state distributional results and a central limit theorem.

http://dx.doi.org/10.1016/j.jcta.2020.105233