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\geq1$ is a fixed positive integer. The method uses a bijection between mappings $f\colon\{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. So, we give probabilistic arguments for inequalities that often use combinatorial arguments.