TREE/ENDOFUNCTION BIJECTIONS AND CONCENTRATION INEQUALITIES

STEVEN HEILMAN

Abstract. We demonstrate a method for proving precise concentration inequalities in uniformly random trees on n vertices, where n ≥ 1 is a fixed positive integer. The method uses a bijection between mappings f: {1, …, n} → {1, …, 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.

Contents

1. Introduction  1
2. Tree/Endofunction Bijections  3
3. Inequalities From Mappings to Trees  9
4. Concentration Inequalities  11
5. Algorithmic Interpretation of Bijection  11
6. Appendix: Cycle Distributions  12
References  14

1. Introduction

Let f: {1, …, n} → {1, …, n} be a mapping with associated directed graph G(f) with vertices {1, …, n} and directed edges {(x, f(x)): 1 ≤ x ≤ n}. It is well known that G(f) can be written as a union of trees connected to the cyclic components of f. Deleting or rearranging some edges within the cycles of G(f) can then produce a tree. For example, we could remove one edge from each cycle in G(f) and then string each of these cycles together, while maintaining the structure of all non-cyclic vertices (see Figure 2.1 below). If the cycles are connected in a reversed order according to their smallest elements (as in Figure 2.2), then we get a bijection R between mappings f: {1, …, n} → {1, …, n} and doubly rooted trees on n vertices. The two roots in the tree correspond to the beginning and the end of the path of cycles, respectively. This bijection requires deleting about log n edges from the directed mapping graph G(f), with high probability (see Lemma 6.1). Consequently, random quantities depending on edges in G(f) are essentially the same after the bijection R is applied to G(f). So, e.g. a concentration inequality for G(f) depending on edges applies essentially unchanged to the image of G(f) under R. Thus, the existence of the bijection R (Theorem 1.1) can lead to concentration inequalities for random trees (Lemma 1.2.)

Date: June 11, 2020.

2010 Mathematics Subject Classification. 60C05,05C80,60E15,05C69.

Key words and phrases. random tree, random mapping, endofunction, bijection, concentration of measure.

Supported by NSF Grants DMS 1839406 and CCF 1911216.

The main point of this paper is a demonstration of a method for proving concentration inequalities on random trees by first proving an inequality for random mappings and then transferring that inequality to random trees via the bijection R.

1.1. History of the Rényi-Joyal Bijection. Joyal’s bijection [Joy81] between mappings from {1, …, n} to itself and doubly rooted trees on n vertices used any bijection between linear orders and permutations, when specifying the action of the mapping bijection on the core of the mapping. That is, if S_{n} denotes the set of permutations on n elements, then any bijection π: S_{n} → S_{n} yields a corresponding lifted bijection R_{π} between mappings from {1, …, n} to itself and doubly rooted trees on n vertices. Choosing π to be the Rényi bijection [R´62, page 11] between linear orderings and permutations, described in the previous paragraph by arranging the cycles of a permutation in reverse order of their smallest elements, seems most natural. Rényi’s bijection π [R´62] is often attributed to Foata [Foa65], e.g. it is referred to as Foata’s transition lemma in https://en.wikipedia.org/wiki/Permutation, though Rényi’s preceding publication [R´62] was pointed out by Stanley [Sta12, page 106]. Given a doubly rooted tree (T, r_{1}, r_{2}), with r_{1}, r_{2} ∈ {1, …, n}, let ρ(T, r_{1}, r_{2}) := T be the un-rooted tree T. We then study the properties of un-rooted tree ρ(R_{π}(f)).

By adding an additional randomization to the Joyal bijection, the authors of [AMP04a, AMP05] (and also [AMP04b]) define a coupling between random walks on mapping directed graphs and random walks on trees. Their coupling also works for non-uniform satisfying ℙ(f(x) = i) = p_{i} for all 1 ≤ x ≤ n, where ∑_{i=1}^{n} p_{i} = 1 and 0 ≤ p_{i} ≤ 1 for all 1 ≤ i ≤ n.

1.2. Concentration Inequalities on Random Trees. Alternative approaches to proving concentration inequalities on random trees include:

• Proving central limit theorems as in [Wag15, RW19, ISZ19], or

• Using martingales [ISZ19] (e.g. the Aldous-Broder algorithm [Bro89, Ald90]) and the

Azuma-Hoeffding inequality, Lemma 4.2. The former approach does not necessarily prove concentration inequalities, so it seems unsuitable for our application. The latter approach proves concentration, but it is often suboptimal, since the Azuma-Hoeffding inequality is not sharp for random quantities with small expected value. One might hope to somehow use Talagrand’s convex distance inequality (Theorem 4.3) in place of the Azuma-Hoeffding inequality, but Talagrand’s inequality requires independence, so it might not be clear how to apply it to random trees.

For more on random mappings, see [Ste69, Kol86] and the references therein.

1.3. Our Contribution. Below, we let E(·) denote the undirected edges of a graph, we let Δ denote the symmetric difference of sets, and we let c(f) denote the number of cycles of a mapping f: {1, …, n} → {1, …, n}.

Theorem 1.1. There exists a bijection R from the set

{f: {1, …, n} → {1, …, n}}

to the set of doubly rooted trees on n vertices such that for all maps f

|E(R(f)) Δ E(G(f))| ≤ 2c(f).

1.4. The Main Application. The following Chernoff-type bounds are used in [Hei20] to prove partial unimodality of the independent set sequence of uniformly random labelled trees, with high probability as the number of vertices n goes to infinity. An independent set in a graph is a subset of vertices no two of which are connected by an edge.

Lemma 1.2 (Main Application to Independent Sets). Let S ⊆ {1, …, n}. Let T be a uniformly random tree on n vertices, conditioned on S being an independent set. Let N be the number of vertices in S^{c} not connected to S. Let α := |S| /n. Then

ℙ(|N − 𝔼N| > s𝔼N + 1) ≤ e^{− min(s,s^{2})n(1−α)^{2}e^{−α/(1−α)}/3}, ∀ s > 0.

More generally,

ℙ(N < (1 − s)𝔼N − 1) ≤ e^{−s^{2}n(1−α)^{2}e^{−α/(1−α)}/2}, ∀ 0 < s < 1
ℙ(N > (1 + s)𝔼N + 1) ≤ e^{−s^{2}n(1−α)^{2}e^{−α/(1−α)}/(2+s)}, ∀ s ≥ 0.

1.5. Organization.

• Theorem 1.1 is stated and proved as Lemma 2.7 below.

• Joyal’s original bijection is presented in Lemma 2.4.

• A restriction of Theorem 1.1 is required to prove the main application, Lemma 1.2. This restriction is demonstrated in Lemma 2.9.

• Section 4 lists some concentration inequalities cited elsewhere in this paper.

• Section 5 gives an algorithmic interpretation of Theorem 1.1. That is, we specify an algorithm for sampling uniformly random labelled trees on n vertices.

• The Appendix, Section 6, proves some concentration inequalities for the number of cycles in a random map. Theorem 1.1 and Lemma 1.2 are proven without Section 6.

2. Tree/Endofunction Bijections

1  38  27 4 6  5 9 mapping directed graph of f Figure 1. Example of the mapping directed graph of f. In this example, f(1) = 3, f(2) = 7, f(3) = 8, f(4) = 6, f(5) = 2, f(6) = 1, f(7) = 2, and f(8) = 1. Also M = {1, 2, 3, 7, 8}. Let n be a positive integer. We refer

to a function f: {1, …, n} → {1, …, n} as a mapping or endofunction. A tree on n labelled vertices {1, …, n} is a connected, undirected graph with no cycles and no self-loops. A doubly rooted tree is a tree together with an ordered pair of roots (r_{1}, r_{2}) ∈ {1, …, n}^{2}.

2.1. Joyal Bijection. We now describe the concepts from the introduction more precisely.

Definition 2.1 (Mapping Directed Graph). Let f: {1, …, n} → {1, …, n}. Define the directed edge set

E(f) := {(x, f(x)): x ∈ {1, …, n}}.

The directed graph ({1, …, n}, E(f)) is called the mapping directed graph of f. This graph has c(f) cycles, where c(f) is the number of cycles of the permutation f|_{M} (using Lemma 2.3).

When T is a tree, we let E(T) denote the set of (undirected) edges of the tree.

Definition 2.2 (Core). Let f: {1, …, n} → {1, …, n}. For any integer j ≥ 1 let f^{j} denote the composition of f with itself j times. Define the core of the mapping f to be

M = M(f) := {x ∈ {1, …, n}: ∃ j ≥ 1 such that f^{j}(x) = x}.

Lemma 2.3. Let f: {1, …, n} → {1, …, n}. Then f|_{M} is a permutation on M.

Proof. Denote ℓ := f|_{M}. We denote gcd as the greatest common divisor of a set of positive integers. If ℓ(x) = ℓ(y) for some x, y ∈ M, then let j := gcd{q ≥ 1: ℓ^{q}(x) = x}, and let k := gcd{q ≥ 1: ℓ^{q}(y) = y}. Without loss of generality, j ≤ k. Then ℓ^{j}(x) = ℓ^{j}(y) = x. Applying ℓ^{k−j} to both sides gives ℓ^{k}(x) = ℓ^{k}(y) = y = ℓ^{k−j}(x) = ℓ^{k−j}(y), implying that k = j by minimality of k, so that x = y. That is, ℓ is injective. If x ∈ M, then ℓ(f^{j−1}(x)) = x, so that ℓ is surjective. (We set f^{0}(x) := x.) □

Since the original Joyal bijection was described in French [Joy81], we present it below for completeness. This bijection will then be improved in Lemma 2.7 below. (A partial translation and commentary of [Joy81] is available at http://ozark.hendrix.edu/∼yorgey/pub/series-formelles.pdf)

Lemma 2.4 (Joyal Bijection, [Joy81]). ∃ a bijection J from the set of mappings {f: {1, …, n} → {1, …, n}} to the set of doubly rooted trees on n vertices such that

|E(f) Δ E(J(f))| ≤ 2(|M(f)| − 1).

(When we compute this symmetric difference, we remove the directions on the edges E(f), and we count multiple edges from E(f) as distinct.)

Proof. Let f: {1, …, n} → {1, …, n}. Let M be the core of f, as in Definition 2.2. Let m := |M|. Denote M =: {s_{1}, s_{2}, …, s_{m}} such that s_{1} < s_{2} < ⋯ < s_{m}. Consider the undirected graph on the vertices V := {1, …, n} with edge set

E := {{x, f(x)}: x ∈ M^{c}}.  (1)

(By definition of M^{c} in Definition 2.2, these edges are all distinct.) Since M^{c} = {x ∈ {1, …, n}: ∀ j ≥ 1 f^{j}(x) ≠ x}, ∀ x ∈ M^{c}, ∃ y ∈ M, j ≥ 1 such that f^{j}(x) = y. For any x ∈ M^{c}, let j(x) denote the smallest positive integer j such that there exists y ∈ M with f^{j}(x) = y. For any y ∈ M, let T_{y} := {x ∈ M^{c}: f^{j(x)}(x) = y}. Then M^{c} is a disjoint union ∪_{y∈M}T_{y}. For any y ∈ M, the edge set {{x, f(x)}: x ∈ T_{y}} forms a (possibly empty) tree. That is, ∪_{y∈M}T_{y} is a disjoint union of m trees. Consider now the edge set

E′ := E ∪ ⋃_{i=1}^{m−1}{f(s_{i}), f(s_{i+1})}.  (2)

(If m = 1, let E′ := E.) (Recall that E defined in (1) are disjoint edges, and by definition of M and Lemma 2.3, all edges in (2) are distinct.) The graph T = (V, E′) is then a (connected) tree with n − 1 edges, and n vertices. More specifically, T is m trees ∪_{y∈M}T_{y} connected along a path {f(s_{1}), …, f(s_{m})} of length m − 1. We define the Joyal bijection J: {mappings} → {doubly rooted trees} by

J(f) := (T, f(s_{1}), f(s_{m})).

It remains to show that J is in fact a bijection.

Proof of injectivity of J. Let f, g: {1, …, n} → {1, …, n}. Let M, N be the cores of f and g, respectively. Suppose J(f) = J(g). By definition of J (i.e (1)), we have M = N, M^{c} = N^{c}, and f|_{M^{c}} = g|_{N^{c}}. Also by definition of J (i.e. (2)), f|_{M} = g|_{M}. That is, f = g.

Proof of surjectivity of J. Let (T, r_{1}, r_{2}) be a doubly rooted tree. Form the unique path p of vertices in T starting at r_{1} and ending at r_{2}. Let T′ := T. Repeat the following procedure until T′ \ p = ∅:

• Choose one x ∈ T′ \p of degree 1, and define f(x) to be the label of the unique vertex connected to x.

• Re-define T′ by removing from T′ the vertex x and the edge emanating from x. In this way, f(x) is defined for all x ∈ T \ p. Now, we define f on p. Label the elements of p in the order they appear in the path as r_{1} = x_{1}, x_{2}, x_{3}, …, x_{m} = r_{2}. Let ℓ: {x_{1}, …, x_{m}} → {x_{1}, …, x_{m}} be the permutation defined so that x_{ℓ(1)} < x_{ℓ(2)} < ⋯ < x_{ℓ(m)}. Then define f so that

f(x_{ℓ(i)}) := x_{i}, ∀ 1 ≤ i ≤ m.

Then J(f) = (T, r_{1}, r_{2}) by (2), so that J is surjective.

Finally, comparing Definition 2.1 with (2) proves the desired inequality. □

1  r_{1} = 3 38  27 4 6  5 9  J  7  8  2  1 = r_{2} 69 4 5 M mapping directed graph of f

Figure 2. Example of the Joyal bijection. In this example, f(1) = 3, f(2) = 7, f(3) = 8, f(7) = 2, and f(8) = 1. So, the chosen order of the core M = {1, 2, 3, 7, 8} in J(f) is 3, 7, 8, 2, 1. Also, r_{1} = f(1) = 3, r_{2} = f(8) = 1.

Example 2.5. Let f: {1, …, n} → {1, …, n} so that f(i) = i for all 1 ≤ i ≤ n. Then M = {1, …, n}, and J(f) is the path that respects the ordering on {1, 2, 3, …, n}. The roots are r_{1} = {1} and r_{2} = {n}.

Example 2.6. Let f: {1, …, n} → {1, …, n} so that f(i) = 1 for all 1 ≤ i ≤ n. Then M = {1}, and J(f) is a star graph with a single vertex of degree n − 1. The roots are r_{1} = r_{2} = {1}.

2.2. Rényi-Joyal Bijection. For the Joyal bijection of Lemma 2.4, |E(f) Δ E(J(f))| is approximately \sqrt{n} with high probability (with respect to a uniformly random choice of f: {1, …, n} → {1, …, n}), since the core of a random mapping is of size approximately \sqrt{n} with high probability [Har60]. Our ultimate goal is to prove a concentration inequality for a random mapping f, and then transfer it to a concentration inequality for a random tree. So, it is most desirable to have a bijection R such that |E(f) Δ E(R(f))| as small as possible. Using Rényi’s bijection within Joyal’s bijection, it is possible to design a bijection R satisfying |E(f) Δ E(R(f))| ≤ 3 log n with high probability, as we describe in Lemma 2.7 below. The idea is: the number of cycles of a random mapping is of size about log n, so removing one edge from each cycle of the random mapping only changes about log n edges. In contrast, the Joyal bijection could change essentially all edges in the core, resulting in about \sqrt{n} edge changes.

Lemma 2.7 (Rényi-Joyal Bijection). There exists a bijection R from the set

{f: {1, …, n} → {1, …, n}}

to the set of doubly rooted trees on n vertices such that for all maps f,

|E(f) Δ E(R(f))| = 2(c(f) − 1).

(When we compute this symmetric difference, we remove the directions on the edges E(f), and we count multiple edges from E(f) as distinct.)

Proof. Let f: {1, …, n} → {1, …, n}. Let M be the core of f, as in Definition 2.2. Let m := |M|. Consider the undirected graph on the vertices V := {1, …, n} with edge set

E := {{x, f(x)}: x ∈ M^{c}}.  (3)

(By definition of M^{c} in Definition 2.2, these edges are all distinct.) Since M^{c} = {x ∈ {1, …, n}: ∀ j ≥ 1 f^{j}(x) ≠ x}, ∀ x ∈ M^{c}, ∃ y ∈ M, j ≥ 1 such that f^{j}(x) = y. For any x ∈ M^{c}, let j(x) denote the smallest positive integer j such that there exists y ∈ M with f^{j}(x) = y. For any y ∈ M, let T_{y} := {x ∈ M^{c}: f^{j(x)}(x) = y}. Then M^{c} is a disjoint union ∪_{y∈M}T_{y}. For any y ∈ M, the edge set {{x, f(x)}: x ∈ T_{y}} forms a tree. That is, ∪_{y∈M}T_{y} is a disjoint union of m trees.

From Lemma 2.3, recall that f|_{M} is a permutation on M. We can then write M = ∪_{i=1}^{c(f)}M_{i}, where M_{1}, …, M_{c(f)} are subsets of vertices corresponding to the disjoint cycles of f|_{M}. For each 1 ≤ i ≤ c(f), denote M_{i} = {m_{i1}, …, m_{ik(i)}}, where k(i) := |M_{i}|, m_{i1} is the smallest element of M_{i}, and m_{i(j+1)} = f(m_{ij}) for all 1 ≤ j < k(i). [That is, we can write M_{i} in cycle notation as (m_{i1} ⋯ m_{ik(i)}), for all 1 ≤ i ≤ c(f).] We also choose the ordering on M_{1}, …, M_{c(f)} such that m_{i1} > m_{(i+1)1} for all 1 ≤ i ≤ c(f) − 1. [That is, we order the cycles in the reverse order of their smallest elements.] Consider now the edge set

E′ := E ∪ ( ⋃_{i=1}^{c(f)} ⋃_{j=1}^{k(i)−1}{m_{ij}, m_{i(j+1)}}) ∪ ⋃_{i=1}^{c(f)−1}{m_{ik(i)}, m_{(i+1)1}}.  (4)

(If m = 1, let E′ := E.) (Recall that E defined in (3) are disjoint edges, and by definition of M and Lemma 2.3, all edges in (3) are distinct.) In words, we write each M_{i} in cycle notation with the lowest number in each cycle appearing first, we remove the edge connecting the first and last endpoints of the cycle, and we connect the last part of the i^{th} cycle to the first part of the (i + 1)^{st} cycle, for all 1 ≤ i ≤ c(f) − 1. The graph T = (V, E′) is then a (connected) tree with n − 1 edges, and n vertices. More specifically, it is m trees connected along a path of length m − 1. The first element in the path is m_{11} and the last element in the path is m_{c(f)k(c(f))}. We define the Rényi-Joyal bijection R: {mappings} → {doubly rooted trees} by

R(f) := (T, m_{11}, m_{c(f)k(c(f))}).

It remains to show that R is one-to-one.

1  1 38  27 4 6  5 9  R  3  8 = m_{23} m_{11} = 2  7  6  9 4 5  M^{2} M^{1} mapping directed graph of f

Figure 3. Example of the Rényi-Joyal bijection R. In this example, f(1) = 3, f(3) = 8, and so on. Also, M = {1, 2, 3, 7, 8}, M_{1} = {2, 7}, M_{2} = {1, 3, 8}.

Proof of injectivity. Let f, g: : {1, …, n} → {1, …, n}. Let M, N be the cores of f and g, respectively. Suppose R(f) = R(g). By definition of R (i.e (3)), we have M = N, M^{c} = N^{c}. Also, f|_{M^{c}} = g|_{M^{c}}. It remains to show that f|_{M} = g|_{M}. Since R(f) = R(g), both f and g have the same ordered path of their cores in R(f), R(g) respectively. (In Figure 2.2, this ordering would be (2, 7, 1, 3, 8).) We can then e.g. recover the action of f on the core (i.e. the permutation f|_{M}) by creating cycles at the smallest elements of this ordering, read from left to right. So, if the ordered path of the core is (s_{1}, …, s_{m}), let k(1) ≥ 1 be the largest integer k so that s_{1} < s_{2} < ⋯ < s_{k}, and inductively define k(i + 1) to be the largest integer k ≤ m such that s_{k(i)+1} < s_{k(i)+2} < ⋯ < s_{k}. It then follows by definition of R that f|_{M} is a permutation in the cycle notation

(s_{1} ⋯ s_{k(1)})(s_{k(1)+1} ⋯ s_{k(2)}) ⋯ (s_{k(c(f)−1)+1} ⋯ s_{k(c(f))}).

Since R(f) = R(g), g|_{M} is also a permutation with this same cycle notation. That is, f|_{M} = g|_{M}. In conclusion, f = g.

Proof of surjectivity of R. Let (T, r_{1}, r_{2}) be a doubly rooted tree. Form the unique path p of vertices in T starting at r_{1} and ending at r_{2}. Let T′ := T. Repeat the following procedure until T′ \ p = ∅:

• Choose one x ∈ T′ of degree 1, and define f(x) to be the label of the vertex connected to x.

• Re-define T′ by removing from T′ the vertex x and the edge emanating from x. In this way, f(x) is defined for all x ∈ T \ p. Now, we define f on p. Label the elements of p in the order they appear in the path as r_{1} = s_{1}, s_{2}, s_{3}, …, s_{m} = r_{2}. Let M := {s_{1}, …, s_{m}}. Let k(1) ≥ 1 be the largest integer k so that s_{1} < s_{2} < ⋯ < s_{k}, and inductively define k(i + 1) to be the largest integer k ≤ m such that s_{k(i)+1} < s_{k(i)+2} < ⋯ < s_{k}. Define f|_{M} to be the following permutation (written in cycle notation)

(s_{1} ⋯ s_{k(1)})(s_{k(1)+1} ⋯ s_{k(2)}) ⋯ (s_{k(c(f)−1)+1} ⋯ s_{k(c(f))}).

Then R(f) = (T, r_{1}, r_{2}), so that J is surjective.

Finally, comparing Definition 2.1 with (4) proves the desired edge inequality. □

By removing the roots of the tree from the definition of R in Lemma 2.7, we arrive at the following.

Corollary 2.8 (Rényi-Joyal Bijection with Roots Removed). There exists an n^{2}-to-one function R from the set

{f: {1, …, n} → {1, …, n}}

to the set of trees on n vertices such that for all maps f,

|E(f) Δ E(R(f))| ≤ 2c(f).

(When we compute this symmetric difference, we remove the directions on the edges E(f), and we count multiple edges from E(f) as distinct.)

2.3. Rényi-Joyal Bijection, Restricted. For the main application, Lemma 1.2, we also need to restrict the bijection in Lemma 2.7 to a specific class of mappings.

Lemma 2.9 (Rényi-Joyal Bijection, Restricted). Let 1 ≤ k < n. Denote S := {1, …, k} and S^{c} := {k + 1, …, n}. There exists a bijection R̃ from the set

{f: {1, …, n} → {1, …, n}, f(S) ⊆ S^{c}}  (5)

to the set {doubly rooted trees on n vertices such that S is an independent set in the tree and the second root is in S^{c}},

(6)

such that for all maps f with f(S) ⊆ S^{c},

|E(f) Δ E(R̃(f))| ≤ 2c(f).

(When we compute this symmetric difference, we remove the directions on the edges E(f), and we count multiple edges from E(f) as distinct.)

Moreover, if N_{S} denotes the number of vertices in the graph that are not connected to S, we have

|N_{S}(R̃(f)) − N_{S}(f)| ≤ 1.  (7)

Proof. Let R̃ be R from Lemma 2.7, restricted to the set (5). Since R itself is a bijection by Lemma 2.7, R̃ is also injective. We therefore show that R̃ is surjective. Let (T, r_{1}, r_{2}) in the set (6), so that T is a tree, r_{1}, r_{2} ∈ {1, …, n} and r_{2} ∈ S^{c}. From Lemma 2.7, there exists a unique f: {1, …, n} → {1, …, n} such that R(f) = (T, r_{1}, r_{2}). As in Lemma 2.7, we write M = ∪_{i=1}^{c(f)}M_{i}, where M_{1}, …, M_{c(f)} are subsets of vertices corresponding to the disjoint cycles of f|_{M}. For each 1 ≤ i ≤ c(f), denote M_{i} = {m_{i1}, …, m_{ik(i)}}, where k(i) := |M_{i}|, m_{i1} is the smallest element of M_{i}, and m_{i(j+1)} = f(m_{ij}) for all 1 ≤ j < k(i). [That is, we can write M_{i} in cycle notation as (m_{i1} ⋯ m_{ik(i)}), for all 1 ≤ i ≤ c(f).] We also choose the ordering on M_{1}, …, M_{c(f)} such that m_{i1} > m_{(i+1)1} for all 1 ≤ i ≤ c(f) − 1. [That is, we order the cycles in the reverse order of their smallest elements.]

Let 1 ≤ i ≤ c(f). Since S = {1, …, k}, if M_{i} ∩ S ≠ ∅, it follows that m_{i1} ∈ S, since m_{i1} is the smallest element of M_{i}. Since f(S) ⊆ S^{c}, if m_{i1} ∈ S, then m_{ik(i)} ∉ S. And if M_{i} ∩ S = ∅, then m_{i1} ∉ S and m_{ik(i)} ∉ S. In either case, we have m_{ik(i)} ∉ S. In particular r_{2} := m_{c(f)k(c(f))} ∉ S. Since S = {1, …, k} and m_{11} > m_{21} > ⋯ > m_{c(f)1}, there exists some integer z satisfying 0 ≤ z ≤ c(f) such that

m_{i1} ∈ S ∀ z < i ≤ c(f),  and m_{i1} ∉ S ∀ 1 ≤ i ≤ z.  (8)

(In the case z = 0, we have m_{i1} ∉ S for all 1 ≤ i ≤ c(f), and in the case z = c(f) we have m_{i1} ∈ S for all 1 ≤ i ≤ c(f).) That is, z is the number of cycles whose smallest element is an element of S^{c}.

Since f(S) ⊆ S^{c}, S is an independent set in the mapping directed graph of f. So, in order for S to be an independent set in R(f), we only need to check that R does not add any edges from S to itself. That is, we need a guarantee that (4) does not add an edge from S to itself. The only new edges added to R(f) are those specified in the right-most term of (4), and none of these edges go from S to itself by (8). Therefore, S is an independent set in R(f). We have already shown that r_{2} := m_{c(f)k(c(f))} ∉ S, so that R(f) is a doubly rooted tree whose second root is in S^{c}. It then remains to show that (7) holds, but this again follows from (4) and (8). These equations imply that R deletes exactly c(f) − z edges from S to S^{c} (one for each of the c(f) − z cycles M_{z+1}, …, M_{c(f)}), and it then adds exactly max(z − 1, 0) edges from S to S^{c} in the right-most term of (4) (one for each term m_{(z+1)1}, …, m_{c(f)1}.) □

Remark 2.10. It follows from the matrix-tree theorem that the number of labelled trees on n > k vertices where vertices {1, …, k} form an independent set is

(n − k)^{k−1}n^{n−k−1}.

This fact also follows from Lemma 2.9. It is unclear if other consequences of the matrix-tree theorem can also follow from Lemma 2.9.

3. Inequalities From Mappings to Trees

In this section we demonstrate that the (randomized) Joyal bijection can find the distribution of some quantities on random trees.

As above, let S ⊆ {1, …, n}, and let k := |S|. Let α := k/n. The following proposition is a corollary of the matrix-tree theorem, but it also follows from Lemma 2.7.

Proposition 3.1. Let T be a uniformly random tree on n vertices, conditioned on S being an independent set. Let N be the number of vertices in S^{c} not connected to S. Then

𝔼N = n(1 − α)^{2}e^{−α/(1−α)}(1 + o_{n}(1)).

Proof. Let F be a uniformly random mapping from {1, …, n} → {1, …, n} conditioned on F (S) ⊆ S^{c}. For any x ∈ S^{c}, let N_{x} be 1 if x is not connected to S, and let N_{x} be 0 otherwise. Then

ℙ(N_{x} = 1) = (1 − \frac{1}{n − k} )^{k}(1 − k/n), ∀ x ∈ S^{c}.

So,

𝔼N = 𝔼 ∑_{x∈S^{c}} N_{x} = (n − k)(1 − \frac{1}{n − k} )^{k}(1 − k/n)
= (1 + o(1))e^{−k/(n−k)}n(1 − α)^{2} = n(1 − α)^{2}e^{−α/(1−α)}(1 + o(1)).

Lemma 2.9 then completes the proof. □

Remark 3.2. With no constraints on F, we have

𝔼N = (n − k)(1 − \frac{1}{n})^{k}(1 − k/n) = n(1 − α)^{2}e^{−α}(1 + o(1)).

Remark 3.3. It follows from the Azuma-Hoeffding Inequality, Lemma 4.2 (using e.g. the Aldous-Broder algorithm [Bro89, Ald90] to construct a tree one edge at a time, as a martingale) and Proposition 3.1 that ∀ t > 0,

ℙ(|N − 𝔼N| > t𝔼N | S is an independent set) ≤ 2e^{−(n−1) \frac{t^{2}(1−α)^{4}e^{−2α/(1−α)}}{2} (1+O(log n/n))}.

However, this inequality can be improved to Lemma 1.2, and this is important for our application to independent sets in uniformly random labelled trees.

Below we will Prove Lemma 1.2. We will use several properties of negatively associated (NA) random variables from [JDP83]. A function f: ℝ^{k} → ℝ is said to be increasing if for any 1 ≤ i ≤ k, and for any x_{1}, …, x_{k}, x′_{i} ∈ ℝ with x_{i} ≤ x′_{i}, we have f(x_{1}, …, x_{k}) ≤ f(x_{1}, …, x_{i−1}, x′_{i}, x_{i+1}, …, x_{k}). Real-valued random variables X_{1}, …, X_{k} are said to be negatively associated, denoted NA, if for any disjoint subsets A, B ⊆ {1, …, k}, and for any increasing functions f: ℝ^{|A|} → ℝ g: ℝ^{|B|} → ℝ such that the following expression is welldefined,

𝔼f({X_{i}}_{i∈A})g({X_{i}}_{i∈B}) − 𝔼f({X_{i}}_{i∈A}) · 𝔼g({X_{i}}_{i∈B}) ≤ 0.

An equivalent definition can be made by requiring both f and g to be decreasing. Here are some properties of NA random variables, listed in [JDP83, Page 288].

(i) A set of independent random variables is NA.

(ii) Increasing functions defined on disjoint subsets of a set of NA random variables are NA. (Similarly, decreasing functions defined on disjoint subsets of a set of NA random variables are NA.)

(iii) The disjoint union of independent families of NA random variables is NA.

Proof of Lemma 1.2. Let f: {1, …, n} → {1, …, n} be a uniformly random mapping, conditioned on the event f(S) ⊆ S^{c}. Let V′ := {1, …, n} \ (S ∪ f(S)) to be the vertices in S^{c} that are not in the image of f(S). For any x ∈ S^{c}, let N_{x} := 1_{x∈V′}. The distribution of N′ := |V′| is well-known as the classical occupancy problem. It is also well known, that the random variables {N_{x}}_{x∈S^{c}} are NA [DR98, BGI18]. Now, for any x ∈ S^{c}, let M_{x} := 1_{f(x)∉S}. Since f is a uniformly random mapping, the random variables {M_{x}}_{x∈S^{c}} are independent of each other, and independent of {N_{x}}_{x∈S^{c}}. So, the random variables {M_{x}}_{x∈S^{c}} are NA by Property (i) and the union of the random variables {N_{x}}_{x∈S^{c}} ∪ {M_{x}}_{x∈S^{c}} also is NA by Property (iii). Since the minimum function is monotone decreasing, the random variables {min(N_{x}, M_{x})}_{x∈S^{c}} are also NA by Property (ii). Finally, define

Ñ := ∑_{x∈S^{c}} min(N_{x}, M_{x}).

(If we started the proof with a random tree instead of a uniformly random mapping, then N would be equal to Ñ.) Since Ñ is the sum of NA random variables, Ñ satisfies Chernoff bounds, Lemma 4.1, by repeating the standard proof of Chernoff bounds, as noted e.g. in [DR98, Proposition 29]. We then transfer this inequality to the random tree by the last part of Lemma 2.9. (The computation of 𝔼N was done in Proposition 3.1.) □

Remark 3.4. It is not obvious to the author how to apply the negative association property directly to random trees. That is, we are not aware of a proof of Lemma 1.2 that uses the negative association property for random variables on trees, the main difficulty being lack of any obvious independence. So, at present it seems necessary to use the bijection from Lemma 2.9 to prove Lemma 1.2.

4. Concentration Inequalities

These concentration inequalities are referenced elsewhere in the paper.

Lemma 4.1 (Chernoff Bounds). Let N be a binomial random variable with parameters n and p. Then

ℙ(|N − 𝔼N| > s𝔼N) ≤ e^{− min(s,s^{2})𝔼N/3}, ∀ s > 0.
ℙ(N < (1 − s)𝔼N) ≤ e^{−s^{2}𝔼N/2}, ∀ 0 < s < 1
ℙ(N > (1 + s)𝔼N) ≤ e^{−s^{2}𝔼N/(2+s)}, ∀ s ≥ 0.

Lemma 4.2 (Azuma-Hoeffding Inequality[SS87]). Let c > 0. Let Y_{0}, …, Y_{n} be a realvalued martingale with Y_{0} constant and |Y_{m+1} − Y_{m}| ≤ c for all 0 ≤ m ≤ n − 1. Then

ℙ(|Y_{n} − Y_{0}| > t) ≤ 2e^{− \frac{t^{2}}{2c^{2}n}} , ∀ t > 0.

Theorem 4.3 (Talagrand’s Convex Distance Inequality, [JLR11, Theorem 2.29]). Let Z_{1}, …, Z_{n} be independent random variables taking values in Γ_{1}, …, Γ_{n}, respectively. Let f: Γ_{1} × ⋯ × Γ_{n} → ℝ. Let X := f(Z_{1}, …, Z_{n}). Suppose there are constants c_{1}, …, c_{n} ∈ ℝ and ψ: ℝ → ℝ such that

• Let 1 ≤ k ≤ n. If z, z′ ∈ Γ := ∏_{i=1}^{n} Γ_{i} differ in only the k^{th} coordinate, then |f(z) − f(z′)| ≤ c_{k}.

• If z ∈ Γ and r ∈ ℝ satisfy f(z) ≥ r, then there exists a “certificate” J ⊆ {1, …, n} with ∑_{i∈J} c_{i}^{2} ≤ ψ(r) such that, for all y ∈ Γ with y_{i} = z_{i} for all i ∈ J, we have f(y) ≥ r.

If m is a median for X, then for every t > 0,

ℙ(X ≤ m − t) ≤ 2e^{−t^{2}/(4ψ(m))}.
ℙ(X ≥ m + t) ≤ 2e^{−t^{2}/(4ψ(m+t))}.

5. Algorithmic Interpretation of Bijection

The bijection R from Lemma 2.7 also gives an algorithm for sampling from uniformly random trees on n vertices. Prüfer codes themselves give a somewhat elementary way to generate random trees, though Algorithm 5.1 is arguably more elementary. The Aldous-Broder algorithm [Bro89, Ald90] is perhaps the most elementary way to generate a uniformly random labelled tree on n vertices, though its run time is O(n^{2}).

Algorithm 5.1 (Sampling a Uniformly Random Labelled Tree on n vertices).

• The input of the algorithm is a random mapping f: {1, …, n} → {1, …, n}, presented as a list (f(1), …, f(n)) of n independent identically distributed random variables, each uniformly distributed in {1, …, n}.

• The output of the algorithm is a uniformly random labelled tree on n vertices.

The algorithm proceeds as follows.

(i) Compute the core of f, via a standard algorithm such as Algorithm 5.2. The core is the set of 1 ≤ k ≤ n cycles of f, written as C_{1}, …, C_{k}.

(ii) For each 1 ≤ i ≤ k, the smallest element of C_{i} is given the left-most position in the

cycle notation for C_{i}. (so e.g. the cycle (365) is written rather than (653)). (iii) Arrange the cycles in reverse age order, according to their smallest elements (so e.g.

we write two cycles in the ordering (365)(289) rather than (289)(365).) (iv) Let C be the set of vertices in the core of f. Output the tree formed by the edges

{{x, f(x)}: x ∈ {1, …, n} \ C}

together with the path that passes through the cycles in the order specified by (iii).

The proof of Theorem 1.1 implies that the output of Algorithm 5.1 is a uniformly random labelled tree on n vertices with run time O(n).

Algorithm 5.2 (Computing the Core of a Mapping).

• The input of the algorithm is a mapping f: {1, …, n} → {1, …, n}, presented as a list (f(1), …, f(n)).

• The output of the algorithm is the set of 1 ≤ k ≤ n cycles of f presented in cycle notation as C_{1}, …, C_{k} (so e.g. C_{1} = (245) indicates that f(2) = 4, f(4) = 5 and f(5) = 2.)

The algorithm proceeds as follows. Let B := ∅, k := 0. While B ≠ {1, …, n}, repeat the following procedure.

• Let x ∈ {1, …, n}\B. Compute the sequence f(x), f(f(x)), f(f(f(x))), … until one element of the sequence is repeated (so that f^{j}(x) = f^{k}(x) for some 1 ≤ j < k ≤ n).

• Define C_{k+1} := (f^{j}(x), f^{j+1}(x), …, f^{k−1}(x)). This is the (k + 1)^{st} cycle of f.

• Re-define k to be one more than its previous value. Also re-define B to be B, less the set {x, f(x), f^{2}(x), …, f^{k}(x)}.

6. Appendix: Cycle Distributions

Let C_{n}(f) be the number of cycles in a mapping f: {1, …, n} → {1, …, n}. The following Lemma is sketched in [Har60]. We give a detailed proof.

Lemma 6.1 (Cycle Distribution of a Random Mapping).

ℙ(C_{n} > (1 + t) log n) ≤ (1 + o_{n}(1))e^{− \frac{t^{2}}{2+t} (log n)/4}, ∀ t > 0.

Proof. Let Π be a uniformly random element of the group S_{n} of permutations on n elements. As in [Dur19, Lemma 2.2.9], let X_{n,k}(π) := 1 if a right parenthesis occurs after entry k in the standard cycle notation of the permutation π ∈ S_{n}, and X_{n,k}(π) := 0 otherwise. Then X_{n,1}, …, X_{n,n} are independent random variables with ℙ(X_{n,k} = 1) = 1/(n − k + 1). Let C(π) be the number of cycles in π ∈ S_{n}. Then C = C_{n} = ∑_{k=1}^{n} X_{n,k}, 𝔼C_{n} = ∑_{k=1}^{n} 𝔼X_{n,k}, and from Chernoff’s bound 4.1,

ℙ(C_{n}(Π) ≥ (1 + t)𝔼C_{n}(Π)) ≤ e^{− \frac{t^{2}}{2+t} 𝔼C_{n}(Π)},  ∀ t > 0.  (9)

When we condition a random mapping f: {1, …, n} → {1, …, n} such that its core size |M| is constant, then f|_{M} is a uniformly random permutation on |M| elements.

Let Y_{n}(f) be the total number of vertices in all cycles of a uniformly random mapping f: \{1, …, n\} → \{1, …, n\}. As in [Har60], ℙ(Y_{n} = k) = \frac{k(n−1)!}{n^{k}(n−k)} for all 0 ≤ k ≤ n. Then, ∀ 0 < a < b < \sqrt{n},

ℙ(a\sqrt{n} ≤ Y_{n} ≤ b\sqrt{n}) = ℙ(a < \frac{Y_{n}}{\sqrt{n}} < b) = ∑_{k=a\sqrt{n}}^{b\sqrt{n}} \frac{k(n − 1)!}{n^{k}(n − k)} = ∑_{j=a,a+1/\sqrt{n},...,b} \frac{j\sqrt{n}(n − 1)!}{n^{j\sqrt{n}}(n − j\sqrt{n})!}

= (1 + o(1)) ∑_{j=a,a+1/\sqrt{n},...,b} j\sqrt{n}\sqrt{\frac{n − 1}{n − j\sqrt{n}}} \frac{(n − 1)^{n−1}e^{−n+1}}{n^{j\sqrt{n}}(n − j\sqrt{n})^{n−j\sqrt{n}}e^{−n+j\sqrt{n}}}

= (1 + o(1)) ∑_{j=a,a+1/\sqrt{n},...,b} je^{1}\sqrt{n}(\frac{n − 1}{n})^{n−1/2}(\frac{n − j\sqrt{n}}{n})^{−n+j\sqrt{n}−1/2}e^{−j\sqrt{n}}

= (1 + o(1)) ∑_{j=a,a+1/\sqrt{n},...,b} je^{1}\sqrt{n}(1 − \frac{1}{n})^{n−1/2}(1 − \frac{j}{\sqrt{n}})^{−n+j\sqrt{n}−1/2}e^{−j\sqrt{n}}.

We write

(1 − \frac{j}{\sqrt{n}})^{−n+j\sqrt{n}−1/2} = e^{[log(1−j/\sqrt{n})](−n+j\sqrt{n}−1/2)} = e^{[−j/\sqrt{n}−j^{2}/(2n)+O(j/\sqrt{n})^{3/2}](−n+j\sqrt{n}−1/2)}
= e^{j\sqrt{n}+j^{2}/2−j^{2}+O(1/\sqrt{n})} = e^{j\sqrt{n}}e^{−j^{2}/2+O(1/\sqrt{n})}.

Therefore

ℙ(a\sqrt{n} ≤ Y_{n} ≤ b\sqrt{n}) = (1 + o(1)) ∑_{j=a,a+1/\sqrt{n},...,b} jn^{−1/2}e^{−j^{2}/2}

= (1 + o(1)) ∫_{a}^{b} xe^{−x^{2}/2}dx = (1 + o(1))(e^{−a^{2}/2} − e^{−b^{2}/2}).

If ε > 0, then

ℙ(Y_{n} ∉ \sqrt{n}[\sqrt{ε}, \sqrt{log(1/ε)}]) = (1 + o(1))(1 − e^{−ε/2} + e^{− log(1/ε)/2}) = (1 + o(1))ε. (10)

So, recalling that C_{n}(f) is the number of cycles in a mapping f: {1, …, n} → {1, …, n},

ℙ(C_{n} > (1 + t) log n) ≤ (1 + o(1))(1 + ε)ℙ(C_{n} > (1 + t) log n | Y_{n} ∈ \sqrt{n}[\sqrt{ε}, \sqrt{log(1/ε)}])

≤^{(9)} (1 + o(1))(1 + ε) sup ; m∈\sqrt{n}[\sqrt{ε},\sqrt{log(1/ε)}] e^{− \frac{t^{2}}{2+t} log m} ≤ e^{− \frac{t^{2}}{2+t} [log n−log(1/ε)]/2}.

Choosing ε := 1/\sqrt{n},

ℙ(C_{n} > (1 + t) log n) ≤ (1 + o_{n}(1))e^{− \frac{t^{2}}{2+t} (log n)/4}.
□

Remark 6.2. It is tempting to try to apply Talagrand’s convex distance inequality to prove Lemma 6.1 but it is not obvious to the author how to make such an argument.

6.1. Independent Set Case. Let S ⊆ {1, …, n}, and let k := |S|. Let α := k/n. Let C_{n}(f) be the number of cycles in a mapping f: {1, …, n} → {1, …, n}.

Lemma 6.3. Let F be a uniformly random mapping from {1, …, n} \ S → {1, …, n} \ S. Let G be a random mapping, uniformly distributed over all f: {1, …, n} → {1, …, n} such that f(S) ⊆ S^{c}. Then the random variables

C_{n−k}(F), C_{n}(G)

are identically distributed.

Proof. Define r(G): {1, …, n} \ S → {1, …, n} \ S by

r(G)(x) = \begin{cases}G(x) & , if G(x) ∈ S^{c} \\ G(G(x)) & , if G(x) ∈ S. \end{cases}

Since G(S) ⊆ S^{c}, if G(x) ∈ S then G(G(x)) ∈ S^{c}, so that r(G) always takes values in S^{c}.

Note that G and r(G) have the same number of cycles, since r(G) removes all elements of S from all cycles of G, but each cycle in G must have at least one element in S^{c}. That is, C_{n}(G) = C_{n}(r(G)).

Also, r(G) is a uniformly random mapping on {1, …, n} \ S. To see this, denote S =: {s_{1}, …, s_{k}}, let x_{1}, …, x_{k} ∈ {1, …, n} \ S and let y_{1}, …, y_{k} ∈ {1, …, n}. Then the conditional probability

ℙ(r(G)(s_{i}) = x_{i} ∀ 1 ≤ i ≤ k | G(x_{j}) = y_{j} ∀ 1 ≤ j ≤ k)

does not depend on x_{1}, …, x_{k}, y_{1}, …, y_{k}. So, we can remove the conditioning and conclude that

ℙ(r(G)(s_{i}) = x_{i} ∀ 1 ≤ i ≤ k)

does not depend on x_{1}, …, x_{k}. That is, r(G) is a uniformly random element of mappings from {1, …, n} \ S to itself. Re-labeling r(G) as F completes the proof. □

Lemma 6.4 (Cycle Distribution of a Restricted Random Mapping).

ℙ(C_{n}(f) > (1 + t) log(n − k) | f(S) ⊆ S^{c}) ≤ (1 + o_{n}(1)e^{− \frac{t^{2}}{2+t} (log(n−k))/4}, ∀ t > 0.

Proof. Combine Lemmas 6.1 and 6.3. □

Acknowledgement. Thanks to Richard Arratia for explaining to me various things such as the Joyal bijection (Lemma 2.4) and the improved Rényi-Joyal bijection (Lemma 2.7), and for suggesting that these bijections could play a role in the main application (Lemma 1.2). Thanks also to Larry Goldstein for helpful discussions.

References

[Ald90] David J. Aldous, The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math. 3 (1990), no. 4, 450–465. MR 1069105 2, 10, 11

[AMP04a] David Aldous, Grégory Miermont, and Jim Pitman, Brownian bridge asymptotics for random p-mappings, Electron. J. Probab. 9 (2004), no. 3, 37–56. MR 2041828 2

[AMP04b] , The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity, Probab. Theory Related Fields 129 (2004), no. 2, 182–218. MR 2063375 2 [AMP05] , Weak convergence of random p-mappings and the exploration process of inhomogeneous

continuum random trees, Probab. Theory Related Fields 133 (2005), no. 1, 1–17. MR 2197134 2

[BGI18] Jay Bartroff, Larry Goldstein, and Ümit Işlak, Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models, Bernoulli 24 (2018), no. 4B, 3283–3317. 10

[Bro89] A. Broder, Generating random spanning trees, Proceedings of the 30th Annual Symposium on Foundations of Computer Science (USA), SFCS ’89, IEEE Computer Society, 1989, p. 442–447. 2, 10, 11

[DR98] Devdatt Dubhashi and Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures Algorithms 13 (1998), no. 2, 99–124. MR 1642566 10

[Dur19] Rick Durrett, Probability—theory and examples, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 49, Cambridge University Press, Cambridge, 2019, Fifth edition of [ MR1068527]. MR 3930614 12

[Foa65] Dominique Foata, Étude algébrique de certains problèmes d’analyse combinatoire et du calcul des probabilités, Publ. Inst. Statist. Univ. Paris 14 (1965), 81–241. MR 220327 2

[Har60] Bernard Harris, Probability distributions related to random mappings, Ann. Math. Statist. 31 (1960), 1045–1062. MR 119227 5, 12, 13

[Hei20] Steven Heilman, Independent sets of random trees and of sparse random graphs, Preprint, 2020. 3

[ISZ19] Mikhail Isaev, Angus Southwell, and Maksim Zhukovskii, Distribution of tree parameters by martingale approach, preprint, arXiv:1912.09838, 2019. 2

[JDP83] Kumar Joag-Dev and Frank Proschan, Negative association of random variables with applications, The Annals of Statistics 11 (1983), no. 1, 286–295. 10

[JLR11] S. Janson, T. Luczak, and A. Rucinski, Random graphs, Wiley Series in Discrete Mathematics and Optimization, Wiley, 2011. 11

[Joy81] André Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), no. 1, 1–82. MR 633783 2, 4

[Kol86] Valentin F. Kolchin, Random mappings, Translation Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York, 1986, Translated from the Russian, With a foreword by S. R. S. Varadhan. MR 865130 2

[R´62] Alfréd Rényi, Théorie des éléments saillants d’une suite d’observations, Ann. Fac. Sci. Univ.

Clermont-Ferrand 8 (1962), 7–13. MR 286162 2

[RW19] Dimbinaina Ralaivaosaona and Stephan Wagner, A central limit theorem for additive functionals of increasing trees, Combin. Probab. Comput. 28 (2019), no. 4, 618–637. MR 3984050 2

[SS87] Eli Shamir and Joel Spencer, Sharp concentration of the chromatic number on random graphsgn, p, Combinatorica 7 (1987), no. 1, 121–129. 11

[Sta12] Richard P. Stanley, Enumerative combinatorics. Volume 1, second ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR 2868112 2

[Ste69] V. E. Stepanov, Limit distributions of certain characteristics of random mappings, Theor. Probability Appl. 14 (1969), 612–626. 2

[Wag15] Stephan Wagner, Central limit theorems for additive tree parameters with small toll functions, Combin. Probab. Comput. 24 (2015), no. 1, 329–353. MR 3318048 2

Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532

E-mail address: stevenmheilman@gmail.com