Tree/Endofunction Bijections and Concentration Inequalities

Abstract

We demonstrate a method for proving precise concentration inequalities in uniformly random trees on $n$ vertices, where $n\ge 1$ is a fixed positive integer. The method uses a bijection between mappings $f:\{1,\dots ,n\}\to \{1,\dots ,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. So, we give probabilistic arguments for inequalities that often use combinatorial arguments.

15 pages, 3 figures