Tree/endofunction bijections and concentration inequalities (Q2144318)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tree/endofunction bijections and concentration inequalities |
scientific article |
Statements
Tree/endofunction bijections and concentration inequalities (English)
0 references
13 June 2022
0 references
Summary: We demonstrate a method for proving precise concentration inequalities in uniformly random trees on \(n\) vertices, where \(n\geqslant 1\) is a fixed positive integer. The method uses a bijection between mappings \(f:\{1, \ldots, n\} \to \{1, \ldots, n\}\) and doubly rooted trees on \(n\) vertices. The main application is a concentration inequality for the number of vertices connected to an independent set in a uniformly random tree, which is then used to prove partial unimodality of its independent set sequence. While inequalities for random trees often use combinatorial arguments, our argument is perhaps more probabilistic.
0 references
concentration inequalities
0 references
uniformly random trees
0 references
0 references
0 references
0 references