INDEPENDENT SETS OF RANDOM TREES AND OF SPARSE RANDOM GRAPHS

STEVEN HEILMAN

Abstract. An independent set of size k in a finite undirected graph G is a set of k vertices of the graph, no two of which are connected by an edge. Let x_{k}(G) be the number of independent sets of size k in the graph G and let α(G) = max{k ≥ 0: x_{k}(G) ≠ 0}. In 1987, Alavi, Malde, Schwenk and Erdös asked if the independent set sequence x_{0}(G), x_{1}(G), …, x_{α(G)}(G) of a tree is unimodal (the sequence goes up and then down). This problem is still open. In 2006, Levit and Mandrescu showed that the last third of the independent set sequence of a tree is decreasing. We show that the first 46.8% of the independent set sequence of a random tree is increasing with (exponentially) high probability as the number of vertices goes to infinity. So, the question of Alavi, Malde, Schwenk and Erdös is “four-fifths true”, with high probability.

We also show unimodality of the independent set sequence of Erdös-Renyi random graphs, when the expected degree of a single vertex is large (with (exponentially) high probability as the number of vertices in the graph goes to infinity, except for a small region near the mode). A weaker result is shown for random regular graphs.

The structure of independent sets of size k as k varies is of interest in probability, statistical physics, combinatorics, and computer science.

Contents

1. Introduction  1
2. Preliminaries  7
3. Concentration Bounds and the Planted Model  10
4. Talagrand’s Inequality and Lower Bounds  13
5. Unimodality Arguments: Abstract Version  16
6. Unimodality for Sparse Erdös-Renyi Graphs  18
7. Random Regular Graphs  20
8. Random Trees  23
9. Appendix: Matrix Tree Theorem  25
References  26

1. Introduction

Let G be a finite, undirected graph with no self-loops and no multiple edges, on n ≥ 1 labelled vertices V := {1, …, n}, with edges E ⊆ {{i, j}: i, j ∈ V, i ≠ j}. Let 0 ≤ k ≤ n.

Date: June 8, 2020. 2010 Mathematics Subject Classification. 05C80,60C05,05C69,60E15. Key words and phrases. independent set, random tree, random graph, concentration of measure. Supported by NSF Grants DMS 1839406 and CCF 1911216.

An independent set of size k in G is a subset of vertices no two of which are connected by an edge. Let x_{k} = x_{k}(G) denote the number of independent sets in size k in G. (Note that x_{0}(G) = 1 since we consider the empty set to be a subset of V = {1, …, n}.) We refer to the sequence x_{0}(G), …, x_{n}(G) as the independent set sequence of G.

The general question considered in this paper is: What does the sequences x_{0}, x_{1}, …, x_{n} “look like” for random graphs?

Some motivations for this question include:

• Statistical physics, where an independent set represents molecules in a magnet that do not want to be close to each other;

• Computer Science and Probability, where many combinatorial optimization problems (k-SAT, MAX-Independent Set, etc.) exhibit similar interesting behavior for random instances. See for example the phase transition known as “shattering” discussed in e.g. [CE15] and [DSS16].

• Combinatorics, where one would like to exactly or approximately find the numbers

x_{0}, …, x_{n} for both deterministic and random graphs. We note that a classic NP-complete problem is: For any k ≥ 1 and any graph G, decide

whether or not x_{k}(G) > 0. So, it could be hard for a computer to decide whether or not a large graph has a large independent set. Counting the number of independent sets of a given size is then computationally more difficult. In fact, a remarkable result of [JSV04] implies a computational equivalence between approximately counting combinatorial quantities (such as independent sets), and constructing a stochastic process whose distribution converges to the uniform distribution on those combinatorial objects.

Intuitively, x_{0}, …, x_{n} should resemble the binomial coefficients \binom{n}{0}, \binom{n}{1}, …, \binom{n}{n}. Note that if E = ∅, x_{k} = \binom{n}{k} for all 0 ≤ k ≤ n. The sequence of binomial coefficients is both unimodal and log-concave, so one might expect the independent set sequence of a random graph to have this same behavior.

Definition 1.1. We say a sequence a_{0}, …, a_{n} of real numbers is unimodal if there exists 0 ≤ j ≤ n such that

a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{j} ≥ a_{j+1} ≥ a_{j+2} ≥ ⋯ ≥ a_{n}.

We say a sequence a_{0}, …, a_{n} of real numbers is log-concave if

a_{k}^{2} ≥ a_{k+1}a_{k−1}, ∀ 1 ≤ k ≤ n − 1.

Remark 1.2. A positive log-concave sequence of real numbers is unimodal.

The following example, demonstrated in [AMSE87], shows that the independent set sequence of a graph might not be unimodal.

Example 1.3. For any integer n ≥ 1, let K_{n} denote the complete graph on n vertices. Consider the graph G = K_{37} + 3K_{4} formed by connecting all vertices of a K_{37} to all vertices of three disjoint K_{4}’s. Then

x_{1} = 37 + 4 · 4 = 49,  x_{2} = 4 · 4 · 3 = 48,  x_{3} = 4^{3} = 64.

That is, the independent set sequence of G is not unimodal.

In fact, the independent set sequence can increase or decrease in any prescribed way:

Theorem 1.4 ([AMSE87]). Let π: {1, …, j} → {1, …, j} be any permutation. Then there exists a graph G whose largest independent set is of size j, such that

x_{π(1)}(G) < x_{π(2)}(G) < ⋯ < x_{π(j)}(G).

Theorem 1.4 is proven by iterating the construction in Example 1.3. Perhaps motivated by the odd behavior observed in Theorem 1.4, where many edges in the graph can arbitrarily distort the independent set sequence, it was asked in [AMSE87] if trees or forests have a unimodal independent set sequence.

Definition 1.5. A tree on n vertices is a connected graph with no cycles. A forest is a disjoint union of trees.

Question 1.6 ([AMSE87]). Any tree or forest has a unimodal independent set sequence.

Remark 1.7 ([AMSE87]). A disjoint union of graphs with unimodal independent set sequence might not have a unimodal independent set sequence (the independent set sequence of a disjoint union is the convolution of the two separate sequences, and it can occur that the convolution of two unimodal sequences is not be unimodal). So, the tree case of Question 1.6 does not imply the forest case.

Despite much effort, including [LM02, LM03, Zhu07, WZ11, Gal11, Gal12, BBO14, Zhu16, GH18], Question 1.6 remains open. The cited works mostly focus on answering Question 1.6 for particular families of trees. One general partial result towards Question 1.6 is the following.

Theorem 1.8 ([LM07]). Let T be a tree whose largest independent set is of size j. Then the “last third” of the independence set sequence is unimodal:

x_{⌈(2j−1)/3⌉}(T) ≥ x_{1+⌈(2j−1)/3⌉}(T) ≥ ⋯ ≥ x_{j−1}(T) ≥ x_{j}(T).

That is, Question 1.6 is “one-third true.” The proof of Theorem 1.8 works for any bipartite graph, using that such graphs are perfect with clique number at most 2. It was therefore asked in [LM07] whether all bipartite graphs have unimodal independent set sequence, though this was proven false.

Theorem 1.9 ([BK13]). There exists a bipartite graph whose independent set sequence is not unimodal.

Due to the apparent difficulty of Question 1.6, Galvin asked the (potentially) easier question: Is it possible to answer Question 1.6 for random trees or random forests (with high probability)? As a “first approximation” to random trees, one can also try to prove unimodality of sparse Erdös-Renyi random graphs, since these graphs are known to be locally tree-like (see e.g. [Gri81]).

Here is one such result in this direction. Let V = {1, …, 2n}. Let 0 < p < 1. Let E be a random subset of {{i, j} ∈ V × V : 1 ≤ i ≤ n < j ≤ 2n} such that

ℙ({i, j} ∈ E) = p, ∀ 1 ≤ i ≤ n < j ≤ 2n

and such that the events {{i, j} ∈ E}_{1≤i≤n<j≤2n} are independent. Then G = (V, E) is an Erdös-Renyi random bipartite graph on n vertices with parameter 0 < p < 1. This random graph is sometimes denoted as G = G(n, n, p).

Theorem 1.10 ([Gal11, Gal12]). There exists c > 0 such that, almost surely, as n → ∞, if p ≥ c log n/\sqrt{n}, then G(n, n, p) has unimodal independent set sequence.

When the parameter p is around 2/n, the Erdös-Renyi random bipartite graphs closely resemble trees, since in both cases the expected degree of a fixed vertex is around 2. (Though the Erdös-Renyi random graph will have a constant fraction of its vertices with degree zero, unlike a tree.) One main difficulty in proving a result such as Theorem 1.10 is: when this random graph G is sparse (i.e. it does not have many edges), Var[x_{αn}(G)] is exponentially large as n → ∞ (for fixed small α > 0). So, “standard” concentration of measure results such as Chebyshev’s inequality do not directly help. (On the other hand, if one adjusts the probabilistic model in various ways, then Chebyshev’s inequality can sometimes apply; see e.g. [DM11, DSS16].)

In fact, x_{k}(G) does not concentrate around its expected value at all (see e.g. [CE15, Corollary 19].) So, it seems difficult to apply concentration of measure techniques directly to x_{k}(G). We get around this issue by proving concentration of measure results for the number of vertices not connected to a given independent set, using a conditioning argument of [CE15]. In this way, the vertex expansion property of the random graph plays a key role in the proof.

1.1. Independence Polynomials. A property of sequences that is stronger than logconcavity is the real-rooted property.

Remark 1.11 (Newton). Let a_{0}, …, a_{n} ∈ ℝ. If the polynomial t ↦ ∑_{k=0}^{n} a_{k}t^{k} has all real roots, then a_{0}, …, a_{n} is log-concave. In fact, a_{0}/\binom{n}{0}, …, a_{n}/\binom{n}{n} is log-concave.

Definition 1.12. The independence polynomial of a graph G on n vertices is

I(G, t) := ∑_{k=0}^{n} x_{k}(G)t^{k}, ∀ t ∈ ℝ.

Theorem 1.13 ([Ham90]). If G is claw-free, then x_{0}(G), …, x_{n}(G) is log-concave.

Theorem 1.14 ([CS07]). If G is claw-free, then I(G, t) has all real roots.

Theorem 1.14 generalized Theorem 1.13 by Remark 1.11.

So, when G is quite unlike a tree, its independent set sequence is log-concave and unimodal. Unfortunately, the real-rooted property cannot hold for trees. So, one cannot answer Question 1.6 by proving a real-rootedness property.

Example 1.15 (Claw Graph). The tree on four vertices with one degree 3 vertex has independence polynomial

1 + 4t + 3t^{2} + t^{3},

which has two complex roots.

In contrast, the matching polynomial of a general graph behaves much better than the independence polynomial. For a graph G with n vertices, let m_{i} denote the number of matchings in G with i edges, and let m_{0} := 1. Heilmann and Lieb [HL72] defined the matching polynomial of G as

μ_{G}(t) := ∑_{k≥0}(−1)^{k}m_{k}t^{n−2k}, ∀ t ∈ ℝ.

Theorem 1.16 ([HL72, Theorems 4.2 and 4.3]). For every graph G, μ_{G}(t) has only real roots. Moreover, if G has maximum degree d, then all roots of μ_{G} have absolute value at most 2\sqrt{d − 1}

This Theorem was used in the construction of bipartite Ramanujan graphs in [MSS15], resolving a Conjecture of Lubotzky.

We should also mention that independent sets and “shattering” phenomena have played a role in constructing a counterexample [Bow18] for the weak Pinsker property [Aus18] from ergodic theory.

1.2. Our Contribution. A random tree T on n ≥ 2 vertices is a random graph that is equal to any of the n^{n−2} possible labelled trees on n vertices, each with probability 1/n^{n−2}.

Theorem 1.17 (Main; Partial Unimodality for Random Trees). There exists c > 0 such that, with probability at least 1 − e^{−cn}, a random tree T on n vertices satisfies

x_{0}(T) < x_{1}(T) < ⋯ < x_{⌊(.26543)n⌋}(T).

For comparison, the largest independent set size in a random tree is about ≈ .567143n, with fluctuations of order \sqrt{n}, by the Azuma-Hoeffding inequality [Fri90]. So, the first 46.8% of the nontrivial independent set sequence is unimodal. Combined with Theorem 1.8 of Levit and Mandrescu, Question 1.6 is “four-fifths true”, with high probability. As noted in Remark 8.5, our argument does not currently recover Theorem 1.8 of Levit and Mandrescu, with high probability as n → ∞.

An earlier version of the manuscript had the constant .2 in Theorem 1.17, though David Galvin pointed out that Lemma 8.3 (originally resembling Lemma 3.10), could be replaced with [Win95, Theorem 5.1], thereby improving the constant .2 to .26543 in Theorem 1.17.

Part of the difficulty of improving on Theorem 1.17 and 1.8 is identifying a largest element of the sequence x_{0}(T), …, x_{n}(T). Even for a random tree, it is unclear if a largest element of x_{0}(T), …, x_{n}(T) has index close to (1/2)(.567)n, or far from this value, with high probability.

The proof of Theorem 1.17 has two main ingredients, based upon [CE15]. Let k less than the expected size of the largest independent set in the graph. If we condition on a uniformly random subset S ⊆ {1, …, n} of size k being an independent set (i.e. size-biasing), then we need to show two things:

(1) Probabilities of events do not change too much due to this conditioning (see Remarks 3.4, 3.6, Lemma 3.10 and the improved Corollary 4.5.)

(2) The number of vertices in {1, …, n} \ S that are connected to S concentrates exponentially around its expected value, as in Chernoff bounds. (See Lemma 6.1.)

In a random tree, the largest independent set is more than half of the size of the whole tree. So, conditioning on a uniformly random subset S ⊆ {1, …, n} of size k being an independent set changes the probability law of a uniformly random tree quite a bit. This large change in measure is the reason Theorem 1.17 can only apply for the first 35% of the nontrivial independent set sequence of a random tree.

However, in e.g. an Erdös-Renyi random graph of large degree d, the largest independent set in the graph is approximately a (2/d) log d fraction of the graph. So, conditioning on a uniformly random subset S ⊆ {1, …, n} of size k ≤ (2/d) log d being an independent set does not change the probability law of the random graph very much. This small change in measure with high expected degree results in a proof of unimodality for essentially all of the independent set sequence of an Erdös-Renyi random graph, as follows.

Theorem 1.18 (Second Main Theorem; Unimodality, Sparse Case, High Degree). Let ε > 0. Then for any d ≥ 10^{10/ε}, there exists c > 0 such that, with probability at least 1 − e^{−cn}, G ∈ G(n, d/n) satisfies

x_{0}(G) < x_{1}(G) < ⋯ < x_{⌊β(1−ε)/2⌋}(G), and x_{⌊β(1+ε)/2⌋}(G) > ⋯ > x_{β−1}(G) > x_{β}(G),

where β is the expected size of the largest independent set in G(n, d/n). (It is known that β ≈ (2/d)(log d − log log d − log 2 + 1) by Theorem 2.4 of [Fri90]).

For the sake of demonstration, we write down the sub-optimal results when the expected degree d is small.

Theorem 1.19 (Partial Unimodality, Sparse Case, Low Degree). The independent set sequence of G(n, d/n) is unimodal with high probability (as n → ∞) for independent set sizes k satisfying

• k < .25n and k > .46n, when d = 1. (The largest independent set size is ≈ .728n)

• k < .194n and k > .39n, when d = 2. (The largest independent set size is ≈ .607n)

• k < .172n and k > .35n, when d = e. (The largest independent set size is ≈ .552n)

For random regular graphs, we can prove a result only applying to the increasing part of the independence set sequence.

Theorem 1.20 (Partial Unimodality, Sparse Regular Case, High Degree). Let ε > 0. For any d ≥ 10^{10/ε}, there exists c > 0 such that, with probability at least 1 − e^{−cn}, if G is a uniformly random d-regular random graph on n vertices

x_{0}(G) < x_{1}(G) < ⋯ < x_{⌊β(1−ε)/2⌋}(G),

where β is the expected size of the largest independent set in G(n, d/n).

1.3. Concurrent Results. Abdul Basit and David Galvin [BG20] are working on a result similar to Theorem 1.17, and they can also improve on the result of Levit and Mandrescu, Theorem 1.8.

1.4. Open Questions.

Question 1.21. Does log-concavity hold with high probability, for high-degree Erdös-Renyi random graphs, as the number of vertices goes to infinity? For example, can Theorem 1.18 be improved to give log-concavity of the independent set sequence, rather than just unimodality?

Question 1.22. For uniformly random labelled trees, does the mode of the independent set sequence concentrate? For example, let T be a random tree on n vertices, and let M := {m ∈ {1, …, n}: x_{m}(T) = max_{1≤j≤n} x_{j}(T)}. Let m be the largest element of M. Does m concentrate around any particular value, with high probability, as the number of vertices goes to infinity?

Question 1.23. Is there any exponential improvement to the lower bound of Lemma 8.3? That is, if we rewrite Lemma 8.3 as X_{k,n} ≥ c_{k,n}, does there exist b_{k} > 0 such that the inequality X_{k,n} ≥ e^{nb_{k}}c_{k,n} holds, with high probability as n → ∞? That is, is there a way to improve Theorem 5.1 from [Win95]?

Question 1.24. Is there a (deterministic) tree whose independent set sequence is not logconcave?

1.5. Notation.

• X_{k,n} is the number of independent sets of size k in an n vertex graph.

• G denotes a family of random graphs on n vertices.

• 𝔼 and ℙ denote the expected value with respect to the random graph G.

• Λ_{k}(n) denotes the set of pairs (G, σ) where G ∈ G_{n} and σ ⊆ {1, …, n} is an independent set in G with cardinality 0 ≤ k ≤ n.

• ℙ_{U_{k}(n)} denotes the uniform probability law on Λ_{k}(n) (see Definition 3.2).

• ℙ_{P_{k}(n)} denotes the planted (size-biased) probability law on Λ_{k}(n) (see Definition 3.3).

2. Preliminaries

Let V = {1, …, n}. Let 0 < p < 1. Let E be a random subset of {{i, j} ∈ V × V : i ≠ j} such that

ℙ({i, j} ∈ E) = p, ∀ 1 ≤ i < j ≤ n

and such that the events {{i, j} ∈ E}_{1≤i<j≤n} are independent. Then G = (V, E) is an Erdös-Renyi random graph on n vertices with parameter 0 < p < 1. This random graph is sometimes denoted as G = G(n, p).

Let k ≥ 0 be an integer. Recall that an independent set of G is a subset of vertices such that no two of them are connected by an edge. Let X_{k,n} be the number of independent sets in G of size k.

The second moment method shows that X_{k,n} concentrates around its expected value when p is larger than n^{−1/2}(log n)^{2}.

Lemma 2.1 ([BE76] [JLR11, Lemma 7.3]). Assume that p = p(n) satisfies

n^{−1/2}(log n)^{2} ≤ p ≤ (log n)^{−2}.

Then

𝔼X_{k,n}^{2} = (1 + o(k^{2}/n))(𝔼X_{k,n})^{2}.

Consequently, we have

ℙ(|X_{k,n} − 𝔼X_{k,n}| > t(𝔼X_{k,n})(o(k/\sqrt{n}))) ≤ \frac{1}{t^{2}} , ∀ t > 0.

So, when p ≥ n^{−1/2}(log n)^{2}, X_{0,n}, …, X_{n,n} is unimodal in the sense that, for any 1 ≤ k ≤ n,

ℙ(\frac{1 − ε}{1 + ε} \frac{𝔼X_{k+1,n}}{𝔼X_{k,n}} ≤ \frac{X_{k+1,n}}{X_{k,n}} ≤ \frac{1 + ε}{1 − ε} \frac{𝔼X_{k+1,n}}{𝔼X_{k,n}} ) ≥ 1 − \frac{o(k^{2}/n)}{ε^{2}}, ∀ ε > 0.

More can be said when p ≥ n^{−1/3}(log n)^{2}. Taking a union bound over k,

\begin{matrix}ℙ(∀ 1 ≤ k ≤ (2/p) log(np), \frac{1 − ε}{1 + ε} \frac{𝔼X_{k+1,n}}{𝔼X_{k,n}} ≤ \frac{X_{k+1,n}}{X_{k,n}} ≤ \frac{1 + ε}{1 − ε} \frac{𝔼X_{k+1,n}}{𝔼X_{k,n}} ) \\ ≥ 1 − (\frac{2}{p} log(np))^{3} \frac{o(1/n)}{ε^{2}}, ∀ ε > 0. \end{matrix}  (1)

So, setting β := k/[(2/p) log(np)] and using

\begin{aligned}\frac{𝔼X_{k+1,n}}{𝔼X_{k,n}} & = \frac{\binom{n}{k+1}(1 − p)^{\binom{k+1}{2}}}{\binom{n}{k}(1 − p)^{\binom{k}{2}}} = \frac{n − k}{k + 1} (1 − p)^{k} \\ & = \frac{n − k}{k + 1} e^{−kp+o(kp)} = (1 + o(1))\frac{n − k}{k + 1} e^{−2β log(np)} = (1 + o(1))n(np)^{−2β}, \end{aligned} (2)

this quantity being larger than one or smaller than one tells us if the independent sequence is increasing or decreasing. For example, if p = n^{−1/4}, then n(np)^{−2β} = n^{1−3β/2}, so (2) goes to infinity when β < 2/3 and it goes to zero when β > 2/3. That is, when p = n^{−1/4}, with high probability the first two thirds of the independent set sequence is increasing, and the last third is decreasing, by (1).

The Second Moment Method fails to prove concentration of X_{k,n} around its expected value when p = O(n^{−1/2}). In this sparse case, the graph does not have many edges, and there are many independent sets in the graph that are highly correlated. In the dense case when p ≫ n^{−1/2}, there are fewer independent sets, and they have small correlations. More specifically, we write

X_{k,n} = ∑_{S⊆V : |S|=k} 1_{{S is independent}}.

Taking the variance of both sides,

Var( ∑_{S⊆V : |S|=k} 1_{{S is independent}})

= ∑_{S⊆V : |S|=k} Var1_{\{S is independent\}} + ∑_{\begin{matrix}S,T ⊆V : \\ |S|=|T |=k, S≠T \end{matrix}} Cov(1_{\{S is independent\}}, 1_{\{T is independent\}}),

where cov(X, Y) = 𝔼((X−𝔼X)(Y −𝔼Y)). In the uncorrelated case p ≫ n^{−1/2}, the rightmost terms are small, so the variance of X_{k,n} is smaller. But in the correlated case p = O(n^{−1/2}), the rightmost terms are large, so the variance of X_{k,n} is larger.

Nevertheless, the size of the largest independent set in the Erdös-Renyi random graph does concentrate around its expected value by the Azuma-Hoeffding inequality (Lemma 2.3) or Talagrand’s convex distance inequality (Theorem 2.2); see Theorem 2.4 below.

Theorem 2.2 (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))}.

2.1. Estimates for the Independent Set of Largest Size. Let V = {1, …, n}. Let E be a random subset of {{i, j} ∈ V × V : i ≠ j}. Then G = (V, E) is a random graph on n vertices. Fix 0 ≤ m ≤ n. Let F_{m} denote the set of subgraphs of V with the equivalence relation defined so that A, B ∈ F_{m} are equivalent if and only if: for all 1 ≤ i ≤ m, for all 1 ≤ j ≤ n, {i, j} ∈ A if and only if {i, j} ∈ B. Then F_{0} ⊆ F_{1} ⋯ ⊆ F_{n}.

Let Y : G → ℝ be a function. For any 1 ≤ m ≤ n, define

Y_{m} := 𝔼(Y |F_{m}).

Then Y_{0}, Y_{1}, …, Y_{n} is a martingale, Y_{0} = 𝔼Y and Y_{n} = Y.

In the case that G is an Erdös-Renyi random graph, and Y is the size of the largest independent set in the graph, we have |Y_{m+1} − Y_{m}| ≤ 1 for all 0 ≤ m ≤ n − 1, and we can use the following Lemma.

Lemma 2.3 (Azuma-Hoeffding Inequality [SS87]). Let Y_{0}, …, Y_{n} be a 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.

The following Theorem follows from Lemma 2.3 inequality (and some additional arguments).

Theorem 2.4 ([Fri90]). Let Y_{n} denote the size of the largest independent set of an Erdös-Renyi random graph on n vertices with parameter 0 < p < 1. Let d := np and let ε > 0 both be fixed. Then ∃ d_{ε} a suitably large constant such that d_{ε} ≤ d such that the following holds. With probability 1 as n → ∞, we have

|X_{n,p} − \frac{2n}{d}(log d − log log d − log 2 + 1)| ≤ \frac{εn}{d}.

In fact, this inequality is violated with probability at most 2 exp(−\frac{ε^{2}nd}{2(log d)^{2}} ). Also, we may choose d_{ε} := 10^{10/ε}.

Theorem 2.4 gives an explicit concentration of Y_{n} around its expected value when the expected degree of the Erdös-Renyi random graph has sufficiently high expected degree. The case that the expected degree is close to 1 follows a different argument.

Lemma 2.5 ([KS81, Theorem 1; Corollary p. 375; for G(n, p)]). Let d ∈ ℝ satisfy 0 < d < e. Let n be a positive integer. The expected size of the largest matching in G(n, d/n) is

n(1 − \frac{a + b + ab}{2d}) + o(n).

Here a is the smallest solution of the equation x = de^{−de^{−x}} and b = de^{−a}. So (as noted in [GNS06, Corollary 1]), the expected size of the largest independent set in G(n, d/n) is

n\frac{a + b + ab}{2d} + o(n).

Example 2.6. When d = 1, we have a ≈ .567, and b ≈ .567, and 𝔼Y_{n} = n(.272 + o(1)).

Example 2.7. When d = 2, we have a ≈ .852, and b ≈ .853 and 𝔼Y_{n} = n(.393 + o(1)).

Example 2.8. When d = e, we have a = b = 1, and 𝔼Y_{n} = n(.448 + o(1)).

Remark 2.9. In a bipartite graph, the size ν of the maximum matching is equal to the size β of the minimum vertex cover, by König’s Theorem. In any n-vertex graph, we have α + β = n, where α is the size of the largest independent set. A tree is a bipartite graph. So, in a tree, we have α = n − ν.

In general, β ≥ ν (since the minimum vertex cover must contain at least one vertex from each matched edge of the maximum matching), so α ≤ n − ν in general.

Let Y_{n} be the size of the largest independent set in a random labelled tree on n vertices. It follows from [MM88, p. 278, p. 282] (see also [BES12, Theorem 4.7]) that, as n → ∞, Y_{n}/n converges in probability to the constant

.567 …

More generally, we have

Theorem 2.10 (Central Limit Theorem for Largest Independent Set of Random Trees, [Pit99]). Let ρ satisfy ρe^{ρ} = 1, so that ρ ≈ .567143. Define

σ := ρ(1 − ρ − ρ^{2})(1 + ρ)^{−1}.

Let Y_{n} denote the largest size of an independent set in a uniformly random labelled connected tree on n vertices. Then

𝔼Y_{n} = ρn + \frac{ρ^{2}(ρ + 2)}{2(ρ + 1)^{3}} + O(n^{−1}), Var(Y_{n}) = σ^{2}n + O(1),

and

\frac{Y_{n} − 𝔼Y_{n}}{\sqrt{Var(Y_{n})}}

converges in distribution to a standard Gaussian random variable as n → ∞.

3. Concentration Bounds and the Planted Model

We assume there is a probability law ℙ on G_{n} that defines the probability that the graph G ∈ G_{n} occurs. We let 𝔼 denote the expected value with respect to ℙ.

Definition 3.1. Let Λ_{k}(n) be the set of pairs (G, σ) of graphs G ∈ G_{n} together with independent sets σ of vertices of size k. Let X_{k,n}(G) be the number of independent sets of size k in the graph G.

Definition 3.2 (The Distribution U_{k}(n)). The distribution U_{k}(n) is defined on Λ_{k}(n) as follows.

• Let G be a graph in G_{n}, drawn with probability ℙ.

• Let σ be chosen uniformly at random among all independent sets in G of size k (if it exists).

• Output the pair (G, σ). (If no such σ exists, output nothing.)

Definition 3.3 (The Distribution P_{k}(n), or the “Planted Model”). The distribution P_{k}(n) is the distribution U_{k}(n), conditioned on a uniformly random subset of size k being independent. That is, the distribution P_{k}(n) is defined by

• Selecting a subset σ of {1, …, n} of size k uniformly at random,

• selecting a graph G ∈ G_{n} in which σ is an independent set, with probability ℙ(G|σ is independent in G) = ℙ(G)/ ∑_{{G′∈G_{n}: σ is independent in G′}} ℙ(G′),

• then outputting the pair (G, σ). The distribution P_{k}(n) could also be called the size-biased distribution. Lemma 3.4. Let G = G_{n} be a family of random graphs on the labelled vertices {1, …, n} that is invariant with respect to permutations of the vertices. That is, ∀ G ∈ G_{n}, ℙ(G) = ℙ(G′) where G′ is G with its vertices permuted by an arbitrary permutation of {1, …, n}. Then

ℙ_{P_{k}(n)}(G, σ) = \frac{ℙ(G)}{𝔼X_{k,n}} , ∀ (G, σ) ∈ Λ_{k}(n).

ℙ_{U_{k}(n)}(G, σ) = \frac{ℙ(G)}{X_{k,n}(G)}, ∀ (G, σ) ∈ Λ_{k}(n).

Remark 3.5. If (G, σ) ∈ Λ_{k}(n) exists, then 𝔼X_{k,n} > 0 and X_{k,n} > 0, so a division by zero does not occur. Proof. The first identity follows from Definition 3.2. Now, by Definition 3.3,

ℙ_{P_{k}(n)}(G, σ) = \frac{ℙ(G)}{\binom{n}{k} ∑_{\{G′∈G_{n}: σ̃ is independent in G′\}} ℙ(G′)}.

Also,

𝔼X_{k,n} = ∑_{σ̃⊆{1,...,n}: |σ̃|=k} ℙ(σ is an independent set)
= ∑_{σ̃⊆{1,...,n}: |σ̃|=k} ∑_{{G′∈G_{n}: σ̃ is independent in G′}} ℙ(G′).

So,

𝔼X_{k,n} · ℙ_{P_{k}(n)}(G, σ) = ℙ(G)\frac{∑_{σ̃⊆\{1,...,n\}: |σ̃|=k} ∑_{\{G′∈G_{n}: σ̃ is independent in G′\}} ℙ(G′)}{\binom{n}{k} ∑_{\{G′∈G_{n}: σ is independent in G′\}} ℙ(G′)}
= ℙ(G)\frac{𝔼σ̃ℙ(σ̃ is independent)}{ℙ(σ is independent)}.

In the permutation invariant case, the last fraction is one. □ Remark 3.6. So, X_{k,n} concentrates around its expected value if and only if ℙ_{P_{k}(n)} and ℙ_{U_{k}(n)} are comparable probability measures. Remark 3.7. Without the permutation invariance assumption, we have

ℙ_{U_{k}(n)}(G, σ) = \frac{ℙ(G)}{X_{k,n}(G)}, ∀ (G, σ) ∈ Λ_{k}(n).

ℙ_{P_{k}(n)}(G, σ) = \frac{ℙ(G)}{𝔼X_{k,n}} \frac{𝔼σ̃ℙ(σ̃ is independent)}{ℙ(σ is independent)}, ∀ (G, σ) ∈ Λ_{k}(n).

Here 𝔼σ̃ denotes the uniform probability law over all subset of {1, …, n} of size k.

3.1. Change of Measure. In this section, we give a comparison between the uniform and size biased measures.

Lemma 3.8. Let A ⊆ Λ_{k}(n). Let G be a family of random graphs that is invariant under permutations of the vertices {1, …, n}. Let c > 0. Let C ⊆ Λ_{k}(n) be the set of (G, σ) such that X_{k,n} ≥ c𝔼X_{k,n}. Then

ℙ_{U_{k}(n)}(A) ≤ \frac{1}{c}ℙ_{P_{k}(n)}(A ∩ C) + ℙ_{U_{k}(n)}(C^{c}).  (3)

Proof. By Lemma 3.4 and by definition of C,

ℙ_{U_{k}(n)}(A ∩ C) = ∑_{(G,σ)∈A∩C} \frac{ℙ(G)}{X_{k,n}(G)} ≤ \frac{1}{c} ∑_{(G,σ)∈A∩C} \frac{ℙ(G)}{𝔼X_{k,n}} = \frac{1}{c}ℙ_{P_{k}(n)}(A ∩ C).  (4)

Therefore,

ℙ_{U_{k}(n)}(A) = ℙ_{U_{k}(n)}(A ∩ C) + ℙ_{U_{k}(n)}(A ∩ C^{c}) ≤^{(4)} \frac{1}{c}ℙ_{P_{k}(n)}(A ∩ C) + ℙ_{U_{k}(n)}(C^{c}).

□

Remark 3.9. Without the permutation invariance assumption, we have

ℙ_{U_{k}(n)}(A ∩ C) ≤ \frac{1}{c}ℙ_{P_{k}(n)}(A ∩ C)\frac{𝔼σ̃ℙ(σ̃ is independent)}{min_{σ: (G,σ)∈A∩C} ℙ(σ is independent)},

ℙ_{U_{k}(n)}(C) ≤ ε + \frac{1}{c}ℙ_{P_{k}(n)}(A)\frac{𝔼σ̃ℙ(σ̃ is independent)}{min_{σ: (G,σ)∈A∩C} ℙ(σ is independent)}.

3.2. A Lower Bound. Applying Lemma 3.8 requires a lower bound on X_{k,n} that holds with high probability. The following elementary lower bound is suitable for small degree graphs, but for large degree graphs we require an even sharper bound in Section 4.

Lemma 3.10 (Lower Bound). Let βn be the expected size of the largest size independent set in G(n, d/n). Then, for all t > 0, with probability at least 1 − e^{−t^{2}/(2n)},

X_{k,n} ≥ e^{−t log(1−α/β)}\sqrt{\frac{β(1 − α)}{β − α}}e^{dα}e^{−n[(β−α) log(β−α)−β log β−(1−α) log(1−α)−dα^{2}/2]}𝔼X_{k,n}.

Proof. Note that

𝔼X_{k,n} = \binom{n}{αn}(1 − d/n)^{\binom{αn}{2}}.  (5)

Also, the size of the largest independent set concentrates around it’s expected value by the Azuma-Hoeffding inequality 2.3. A lower bound for X_{k,n} is given by taking size k = αn subsets of the largest independent set, i.e.

ℙ (X_{k,n} ≥ \binom{βn − t}{αn}) ≥ e^{−t^{2}/[2n]}, ∀ t ≥ 0.

Therefore, by Stirling’s formula and (1 − x) ≤ e^{−x} for all x ∈ ℝ,

\begin{matrix}( & {n \atop αn} & ) \\ ( & {βn \atop αn} & ) \end{matrix}(1 − d/n)^{\binom{αn}{2}} = \frac{n![(β − α)n]!}{(βn)![(1 − α)n]!}(1 − d/n)^{\binom{αn}{2}}

= \sqrt{\frac{β − α}{β(1 − α)}}e^{−dα/2}e^{n[(β−α) log(β−α)−β log β−(1−α) log(1−α)−dα^{2}/2]}(1 + o_{n}(1)).

More specifically,

\begin{matrix}( & {n \atop αn} & ) \\ ( & {βn−t \atop αn} & ) \end{matrix}(1 − d/n)^{\binom{αn}{2}}

≤ \sqrt{\frac{β − α}{β(1 − α)}}e^{−dα/2}e^{n[(β−α) log(β−α)−β log β−(1−α) log(1−α)−dα^{2}/2]}e^{t log(1−α/β)}(1 + o_{n}(1)).

(6)

That is, with probability at least 1 − e^{−t^{2}/(2n)},

\frac{𝔼X_{k,n}}{X_{k,n}} ≤ \frac{𝔼X_{k,n}}{# size k subsets of the largest independent set}

≤^{(5)∧(6)} \sqrt{\frac{β − α}{β(1 − α)}}e^{−dα/2}e^{n[(β−α) log(β−α)−β log β−(1−α) log(1−α)−dα^{2}/2]}e^{t log(1−α/β)}.

□

4. Talagrand’s Inequality and Lower Bounds

The lower bound of Lemma 3.10 is not precise enough to prove full unimodality of the independent set sequence, since it only uses the Azuma-Hoeffding inequality. A more precise lower bound appears in [CE15, Proposition 22] using the more precise Talagrand convex distance inequality, Theorem 2.2. Due to a few small typos, and focusing on G(n, m) as opposed to G(n, p), we present the argument of [CE15] below.

Theorem 4.1 ([DM11, Theorem 1]). For any 0 < α < 1, define

d′(α) := sup{d > 0: lim_{n→∞} ℙ(X_{αn,n}(G(n, d/n)) > 0) = 1}.  (7)

Then, for all 0 < α < 10^{−9},

d′(α) ≥ 2\frac{log(1/α) + 1}{α} − \frac{2}{\sqrt{α}}.

Talagrand’s large deviation inequality then implies

Theorem 4.2 ([CE15, Theorem 14]). Define d′(α) by (7). Let d ≥ d′(α) and let 0 < α < 10^{−9}. Let Y_{n} be the size of the largest independent set in the graph G(n, d/n). Then

ℙ(Y_{n}(G(n, d/n)) < t) ≤ 4e^{− \frac{(αn−t+1)^{2}}{4αn}} , ∀ t < αn.

Corollary 4.3 ([CE15, Corollary 15]). Let 0 < α < 10^{−4}. Define

d := 2\frac{log(1/α) + 1}{α} − \frac{8}{\sqrt{α}}.  (8)

Then ∃ c > 0 such that

ℙ(Y_{n}(G(n, d/n)) < αn) ≤ 4e^{− \frac{n}{d^{2}(log d)^{4}}} , ∀ n ≥ 1.
𝔼X_{αn,n} ≤ c · e^{10n(log d)^{3/2}d^{−3/2}}, ∀ n ≥ 1.

Proof. Let α < α′ < 2α such that d = 2\frac{log(1/α′)+1}{α′} − \frac{2}{\sqrt{α′}}. By Theorem 4.2 (applied for the parameters d and α′),

ℙ(Y_{n}(G(n, d/n)) < αn) ≤ 4e^{− \frac{([α′−α]n+1)^{2}}{4α′n}} ≤ 4e^{−n \frac{(α′−α)^{2}}{8α}} .

A calculation as in [CE15, Corollary 4] shows that

α′ − α ≥ 10α/\sqrt{d(log d)^{5}}.

Also, α > 1.5(log d)/d, so

ℙ(Y_{n}(G(n, d/n)) < αn) ≤ 4e^{−nα \frac{100}{8d(log d)^{5}}} ≤ 4e^{−n \frac{150}{8d^{2}(log d)^{4}}} .

Meanwhile, by Stirling’s formula,

𝔼X_{αn,n} = \binom{n}{αn}(1 − d/n)^{\binom{αn}{2}} ≤ \frac{1}{\sqrt{α(1 − α)}}e^{n[−α log α−(1−α) log(1−α)−(d/2)α^{2}]}e^{−dα}(1 + o_{n}(1))

=^{(8)} e^{n[−α log α−(1−α) log(1−α)−α(log(1/α)+1)+4α^{3/2}]} \frac{e^{2(log(1/α)+1)−8α^{1/2}}}{\sqrt{α(1 − α)}} (1 + o_{n}(1))

≈ e^{n[−(1−α) log(1−α)−α+4α^{3/2}]}c(α)(1 + o_{n}(1))

≈ e^{n[−(1−α)[−α+O(α^{2})]−α+4α^{3/2}]}c(α)(1 + o_{n}(1))

≈ e^{n[4α^{3/2}+O(α^{2})]} ≈ e^{4n[α^{3/2}+O(α^{2})]}c(α)(1 + o_{n}(1)).

And α ≤ 2(log d)/d by (inverting) the assumption (8), so the conclusion follows. □

Lemma 4.4 ([CE15, Lemma 23]). Let d′ > d. Let 0 < k < n. Then

ℙ(X_{k,n}(G(n, d/n)) < \frac{𝔼X_{k,n}(G(n, d/n))}{2𝔼X_{k,n}(G(n, d′/n))}) ≤ 2ℙ(X_{k,n}(G(n, d′/n)) = 0).

Proof. By direct calculation,

𝔼X_{k,n}(G(n, d/n)) = \binom{n}{k}(1 − d/n)^{\binom{k}{2}},  𝔼X_{k,n}(G(n, d′/n)) = \binom{n}{k}(1 − d′/n)^{\binom{k}{2}}. (9)

Let d′′ > 0 and note that (1 − d/n)(1 − d′′/n) = (1 − (d + d′′)/n + d[d′′]/n^{2}). So, if we define d′′ := [d′ − d]/(1 + d/n), then G(n, d′) can be described by the following two-step procedure. The probability that any edge exists in G(n, d′/n) is given by first constructing G(n, d/n), and then keeping every edge in G(n, d/n) with probability d′′/n. By (9),

𝔼[X_{k,n}(G(n, d′/n))|X_{k,n}(G(n, d/n))] = X_{k,n}(G(n, d/n))(1 − d′′/n)^{\binom{k}{2}}.  (10)

Let C be the event that

X_{k,n}(G(n, d/n)) < \frac{𝔼X_{k,n}(G(n, d/n))}{2𝔼X_{k,n}(G(n, d′/n))}.

By Markov’s inequality,

\frac{1}{2} ≤ ℙ(X_{k,n}(G(n, d′/n)) < 2𝔼[X_{k,n}(G(n, d′/n))|C]|C)

≤^{(10)} ℙ(X_{k,n}(G(n, d′/n)) < 2\frac{(1 − d′′/n)^{\binom{k}{2}}𝔼X_{k,n}(G(n, d/n))}{𝔼X_{k,n}(G(n, d′/n))}|C).

So, by definition of conditional probability and (10),

ℙ(C) ≤ 2ℙ(X_{k,n}(G(n, d′/n)) < 1) = 2ℙ(X_{k,n}(G(n, d′/n)) = 0).
□

Corollary 4.5 (Lower Bound, [CE15, Proposition 22]). There exists ε_{d} := log log d/ log d such that, for any k < (2 − ε_{d})n(log d)/d,

ℙ(X_{k,n}(G(n, d/n)) ≥ e^{−20nd^{−3/2}(log d)^{−3/2}}𝔼X_{k,n}(G(n, d/n))) ≥ 1 − 8 exp ( − \frac{n}{2d^{2}(log d)^{2}} ).

Proof. Define k such that

k ≤ (2n/d)(log d − log log d + 1 − log 2),  α := k/n,  (11)
d̃:= 2(− log α + 1)/α − 8/\sqrt{α}.  (12)

From Corollary 4.3, (applied to the parameters α, d̃> d),

ℙ(Y_{n}(G(n, d̃/n)) < αn) ≤ 4 exp ( − \frac{n}{d̃^{2}(log d̃)^{4}} ).
𝔼X_{αn,n}(G(n, d̃/n)) ≤ c · e^{10n(log d̃)^{3/2}d̃^{−3/2}}.

(13)

We now compare d and d̃. We have

− log α + 1 =^{(11)} log d − log log d + 1 − log 2 − log (1 − \frac{log log d − 1 + log 2}{log d})
= log d − log log d + 1 − log 2 + \frac{log log d − 1 + log 2}{log d} + O(\frac{log log d}{log d})^{2}.

(14)

So

d̃ =^{(12)} \frac{2}{α}(− log α + 1) + 8/\sqrt{α}
=^{(11)∧(14)} \frac{d}{log d − log log d + 1 − log 2} · ( log d − log log d + 1 − log 2
+ \frac{log log d − 1 + log 2}{log d} + O(\frac{log log d}{log d})^{2}) + 8/\sqrt{α}
= d[1 + \frac{log log d}{(log d)^{2}} + O(\frac{(log log d)^{2}}{(log d)^{3}} )] + O(\sqrt{d}).

So, as d → ∞, d̃> d are asymptotically comparable as d → ∞, so (13) implies that

ℙ(Y_{n}(G(n, d/n)) < αn) ≤ ℙ(Y_{n}(G(n, d̃/n)) < αn)

≤ 4 exp ( − \frac{n}{d̃^{2}(log d̃)^{4}} ) ≤ 4 exp ( − \frac{n}{2d^{2}(log d)^{2}} ). (15)

𝔼X_{αn,n}(G(n, d̃/n)) ≤ c · e^{10n(log d̃)^{3/2}d̃^{−3/2}} ≤ c · e^{10n(log d)^{−3/2}d^{−3/2}}.  (16)

Now, note that the following two events are equal:

{Y_{n} < αn} = {X_{αn,n} = 0}.  (17)

(Recall that Y_{n} is the size of the largest independent set and X_{αn,n} is the number of independent sets of size αn.) Lemma 4.4 then implies that

ℙ(X_{αn,n}(G(n, d/n)) < \frac{1}{2}c · e^{10n(log d)^{−3/2}d^{−3/2}}𝔼X_{αn,n}(G(n, d/n)))

≤^{(16)} ℙ(X_{αn,n}(G(n, d/n)) < \frac{𝔼X_{αn,n}(G(n, d/n))}{2𝔼X_{αn,n}(G(n, d̃/n))})

≤ 2ℙ(X_{αn,n}(G(n, d̃/n)) = 0) =^{(17)} 2ℙ(Y_{n}(G(n, d̃/n)) < αn) ≤^{(15)} 8 exp ( − \frac{n}{2d^{2}(log d)^{2}} ).

□

5. Unimodality Arguments: Abstract Version

Lemma 5.1 (Counting Lemma). Let G = (V, E) be any (deterministic) graph. Then

∑_{\begin{matrix}S⊆\{1,...,n\}: \\ |S|=k \end{matrix}} 1_{\{S is independent\}} · #\{vertices not connected to S\} = (k + 1)X_{k+1,n}.

Proof. Each side is found by counting the number of ordered pairs (S, T) of independent sets such that S ⊆ T, where |S| = k and |T | = k +1. These pairs can be counted by first starting with any independent set S of size k, and then adding a single vertex to it. This count gives the left side. On the right side, we can alternatively start with an independent set T of size k + 1, and then delete a single vertex from it, in k + 1 different ways. □

Let (G, σ) ⊆ Λ_{k}(n). Let N = N_{σ} be the number of vertices in G \ σ not connected to σ. Let s, s′ > 0. Let A be the event that (G, σ) satisfies

{N_{σ} − 𝔼_{P_{k}(n)}N_{σ} < −s𝔼_{P_{k}(n)}N_{σ}} ∪ {N_{σ} − 𝔼_{P_{k}(n)}N_{σ} > s′𝔼_{P_{k}(n)}N_{σ}}.

Lemma 5.2 (Ratio Bound). Let c, ε_{1}, ε_{2} > 0 and let C := {X_{k,n} ≥ c𝔼X_{k,n}}. Assume that G_{n} is a permutation invariant family of random graphs such that:

(i) ℙ_{P_{k}(n)}(A ∩ C) ≤ ε_{1} (ii) ℙ_{U_{k}(n)}(C) ≥ 1 − ε_{2}, and

Then, for any γ > 0,

ℙ(∀ 0 ≤ k ≤ n, \frac{(1 − s)(𝔼_{P_{k}(n)}N_{σ} − γ)}{k + 1} ≤ \frac{X_{k+1,n}}{X_{k,n}} ≤ \frac{(1 + s′)𝔼_{P_{k}(n)}N_{σ}}{k + 1} + n\frac{γ}{k + 1})

≥ 1 − \frac{n}{γ}(\frac{ε_{1}}{c} + ε_{2}).

Remark 5.3. If X_{k} = 0 then X_{k+1} = 0, so division by zero does not occur in the above event. If X_{k+1} = X_{k} = 0, we interpret the event {a ≤ X_{k+1}/X_{k} ≤ b} to always be true, so that it is the whole sample space.

Proof. From Lemma 3.8,

ℙ_{U_{k}(n)}(A) ≤ \frac{1}{c}ℙ_{P_{k}(n)}(A ∩ C) + ℙ_{U_{k}(n)}(C^{c}) =^{(i)∧(ii)} \frac{ε_{1}}{c} + ε_{2} =: η.  (18)

Using Definition 3.2, and as usual letting 𝔼 denote expected value with respect to the random graph itself,

ℙ_{U_{k}(n)}(A) = ∑_{(G,σ)∈Λ_{k}(n)} \frac{ℙ(G)1_{(G,σ)∈A}}{X_{k,n}(G)} = 𝔼 ∑_{σ: (G,σ)∈Λ_{k}(n)} \frac{1_{(G,σ)∈A}}{X_{k,n}(G)}.  (19)

So, as usual denoting ℙ as the probability law with respect to the random graph itself, by Markov’s inequality,

ℙ( ∑_{σ: (G,σ)∈Λ_{k}(n)} \frac{1_{(G,σ)∈A}}{X_{k,n}(G)} > γ) ≤^{(19)∧(18)} η/γ,  ∀ γ > 0.  (20)

Consider now the left sum in Lemma 5.1. We write

∑_{|S|=k} 1_{{S is independent}} · N_{S} = ∑_{|S|=k}[1_{(G,S)∈A^{c}} + 1_{(G,S)∈A}]1_{{S is independent}}N_{S}.

From the Definition of A, we therefore have

(1 − s)𝔼_{P_{k}(n)}N_{σ} ∑_{|S|=k} 1_{(G,S)∈A^{c}}1_{{S is independent}} + ∑_{|S|=k} 1_{(G,S)∈A}1_{{S is independent}}N_{S}

≤ ∑_{|S|=k} 1_{{S is independent}}N_{S} ≤ (1 + s′)X_{k,n}𝔼_{P_{k}(n)}N_{σ} + ∑_{|S|=k} 1_{(G,S)∈A}1_{{S is independent}}N_{S}.

Adding and subtracting 1_{(G,S)∈A} in the first term gives

(1 − s)X_{k,n}𝔼_{P_{k}(n)}N_{σ} − (1 − s)𝔼_{P_{k}(n)}N_{σ} ∑_{|S|=k} 1_{(G,S)∈A}1_{{S is independent}}

+ ∑_{|S|=k} 1_{(G,S)∈A}1_{{S is independent}}N_{S} ≤ ∑_{|S|=k} 1_{{S is independent}}N_{S}

≤ (1 + s′)X_{k,n}𝔼_{P_{k}(n)}N_{σ} + ∑_{|S|=k} 1_{(G,S)∈A}1_{{S is independent}}N_{S}.

The event (G, S) ∈ A implies that S is an independent set, so we can remove that redundancy. Also, getting rid of the last part of the first term then gives

(1 − s)X_{k,n}𝔼_{P_{k}(n)}N_{σ} − (1 − s)𝔼_{P_{k}(n)}N_{σ} ∑_{|S|=k} 1_{(G,S)∈A}

≤ ∑_{|S|=k} 1_{{S is independent}}N_{S} ≤ (1 + s′)X_{k,n}𝔼_{P_{k}(n)}N_{σ} + ∑_{|S|=k} 1_{(G,S)∈A}N_{S}.

Then, dividing by (k + 1)X_{k,n}, using Lemma 5.1, and using N_{S} ≤ n in the last inequality

\frac{(1 − s)𝔼_{P_{k}(n)}N_{σ}}{k + 1} − (1 − s)𝔼_{P_{k}(n)}N_{σ} \frac{1}{k + 1} ∑_{|S|=k} \frac{1_{(G,S)∈A}}{X_{k,n}(G)}

≤ \frac{X_{k+1,n}}{X_{k,n}} = \frac{1}{(k + 1)X_{k,n}} ∑_{|S|=k} 1_{\{S is independent\}}N_{S}

≤ \frac{(1 + s′)𝔼_{P_{k}(n)}N_{σ}}{k + 1} + n\frac{1}{k + 1} ∑_{|S|=k} \frac{1_{(G,S)∈A}}{X_{k,n}} .

From Markov’s inequality (20), for any γ > 0, we therefore have

ℙ(\frac{(1 − s)(𝔼_{P_{k}(n)}N_{σ} − γ)}{k + 1} ≤ \frac{X_{k+1,n}}{X_{k,n}} ≤ \frac{(1 + s′)𝔼_{P_{k}(n)}N_{σ}}{k + 1} + n\frac{γ}{k + 1}) ≥ 1 − η/γ.  (21)

Finally, taking the union bound over all 0 ≤ k ≤ n,

ℙ(∀ 0 ≤ k ≤ n, \frac{(1 − s)(𝔼_{P_{k}(n)}N_{σ} − γ)}{k + 1} ≤ \frac{X_{k+1,n}}{X_{k,n}} ≤ \frac{(1 + s′)𝔼_{P_{k}(n)}N_{σ}}{k + 1} + n\frac{γ}{k + 1}) ≥ 1 − \frac{nη}{γ} .

The proof is concluded by substituting the definition of η in (18). □

6. Unimodality for Sparse Erdös-Renyi Graphs

Lemma 6.1. Let (G, σ) ∈ Λ_{k}(n) be a random sample from P_{k}(n). Let N_{σ} be the number of vertices in G \ σ that are not connected to σ. Then

ℙ_{P_{k}(n)}(|N_{σ} − 𝔼_{P_{k}(n)}N_{σ}| ≥ t𝔼_{P_{k}(n)}N_{σ}) ≤ 2e^{−n min(t,t^{2})(1−α)e^{−dα}/3} ∀ t ≥ 0.

Proof. Let α := k/n. Let v ∈ {1, …, n} be a vertex with v ∉ σ. Let C_{v} be the event that v is connected to some vertex in σ. The events {C_{v}}_{v∈{1,...,n}\σ} are independent, and ℙ(C_{v}^{c}) = (1 − p)^{k}. So, N_{σ} is a binomial random variable with expected value

𝔼_{P_{k}(n)}N_{σ} = (n − k)(1 − p)^{k} = (n − k)(1 − d/n)^{αn} = (1 + o(1))n(1 − α)e^{−dα}.

So, from Chernoff bounds,

ℙ_{P_{k}(n)}(|N_{σ} − 𝔼_{P_{k}(n)}N_{σ}| ≥ t𝔼_{P_{k}(n)}N_{σ}) ≤ 2e^{−n min(t,t^{2})(1−α)e^{−dα}/3}, ∀ t ≥ 0.
□

Proof of Theorem 1.18. Denote α := k/n. From Corollary 4.5, with probability at least 1 − 8 exp ( − \frac{n}{2d^{2}(log d)^{2}} ) =: 1 − ε_{2},

X_{k,n} ≥ e^{−20nd^{−3/2}(log d)^{−3/2}}𝔼X_{k,n} =: c_{1}𝔼X_{k,n}.

Let C denote this event.

Then, let A be the event that (G, σ) satisfies |N_{σ} − 𝔼_{P_{k}(n)}N_{σ}| > s𝔼_{P_{k}(n)}N_{σ}. From Lemma 6.1,

ℙ_{P_{k}(n)}(A) ≤ 2e^{−n min(s,s^{2})(1−α)e^{−dα}/3} =: ε_{1} ∀ t ≥ 0.

We therefore apply Lemma 5.2 so that, for γ := e^{−nε′},

ℙ(∀ 0 ≤ k ≤ n, \frac{(1 − s)(𝔼_{P_{k}(n)}N_{σ} − γ)}{k + 1} ≤ \frac{X_{k+1,n}}{X_{k,n}} ≤ \frac{(1 − γ + s)𝔼_{P_{k}(n)}N_{σ}}{k + 1} + γ \frac{n}{k + 1})

≥ 1 − \frac{n}{γ}(\frac{ε_{1}}{c_{1}} + ε_{2})

≥ 1 − ne^{nε′}2e^{−n min(s,s^{2})(1−α)e^{−dα}/3}e^{20nd^{−3/2}(log d)^{−3/2}} − ne^{nε′}8 exp^{−nd^{−2}(log d)^{−2}} .

(22)

So, if we choose s := \sqrt{100\frac{20nd^{−3/2}(log d)^{−3/2}}{(1−α)e^{−dα}}}, then we can also take γ := e^{−nε′} for some ε′ > 0. For d sufficiently large, by Theorem 2.4, the largest independent set has expected size nβ, where

β := (2/d)(log d − log log d − log 2 + 1 + o_{d}(1)).  (23)

Let δ := α/β so that 0 < δ < 1. If s < 1, then

s := \sqrt{100\frac{20nd^{−3/2}(log d)^{−3/2}}{(1 − α)e^{−dα}}} ≈^{(23)} \sqrt{100\frac{20nd^{−3/2}(log d)^{−3/2}}{(1 − α)e^{−2δ(log d−log log d−log 2+1)}}}

≈ \sqrt{100\frac{20nd^{−3/2}(log d)^{−3/2}}{(1 − α)d^{−2δ}(log d)^{2δ}}} ≈ \sqrt{d^{2δ−3/2}(log d)^{−3/2−2δ}} = d^{δ−3/4}(log d)^{−δ−3/4}.

Similarly, if s > 1, then

s ≈ d^{2δ−3/2}(log d)^{−2δ−3/2}.

So, if δ < 3/4, then s ≈ d^{δ−3/4}, and s → 0 as d → ∞. That is, (22) completes the proof when 0 < δ < 3/4 since by Lemma 6.1

𝔼_{P_{k}(n)}N_{σ}/k ≈ \frac{1 − α}{α}e^{−dα} ≈ \frac{1 − α}{α}^{−1}d^{−2δ} ≈^{(23)} d^{1−2δ}.

As d → ∞, this quantity is larger than 1 when β < 1/2 and less than 1 when β > 1/2. That is, define ε := |1 − 2δ|.

In the remaining case that 3/4 ≤ δ < 1, we have s → ∞ as d → ∞, and by Lemma 6.1,

\frac{s𝔼_{P_{k}(n)}N}{k} ≈ \frac{20d^{−3/2}(log d)^{−3/2}}{α} ≈ \frac{20d^{−3/2}(log d)^{−3/2}}{d^{−1} log d} ≈ d^{−1/2}(log d)^{−5/2}.

That is, \frac{s𝔼N}{k} → 0 as d → ∞. So, X_{k+1,n}/X_{k,n} < 1/2 as n → ∞, so (22) completes the proof in the remaining case δ > 3/4.

□

Proof of Theorem 1.19. For all t > 0, with probability at least 1 − e^{−t^{2}/(2n)}, by Lemma 3.10,

X_{k,n} ≥ e^{−t log(1−α/β)}\sqrt{\frac{β(1 − α)}{β − α}}e^{dα}e^{−n[(β−α) log(β−α)−β log β−(1−α) log(1−α)−dα^{2}/2]}𝔼X_{k,n}.

Let C denote this event. Here βn is the expected size of the largest independent set in the random graph.

Then, let A be the event that (G, σ) satisfies |N_{σ} − 𝔼_{P_{k}(n)}N_{σ}| > s𝔼_{P_{k}(n)}N_{σ}. From Lemma 6.1,

ℙ_{P_{k}(n)}(A) ≤ 2e^{−n min(s,s^{2})(1−α)e^{−dα}/3} =: ε_{1} ∀ t ≥ 0.

ℙ(∀ 0 ≤ k ≤ n, \frac{(1 − γ − s)𝔼_{P_{k}(n)}N_{σ}}{k + 1} ≤ \frac{X_{k+1}}{X_{k}} ≤ \frac{(1 − γ + s)𝔼_{P_{k}(n)}N_{σ}}{k + 1} + γ \frac{(n − k)}{k + 1})

≥ 1 − \frac{n}{γ}(\frac{ε_{1}}{c_{1}} + ε_{2}) ≥ 1 − ne^{nε′}2e^{−n min(s,s^{2})(1−α)e^{−dα}/3}e^{t log(1−α/β)}

· \sqrt{\frac{β − α}{β(1 − α)}}e^{dα}e^{n[(β−α) log(β−α)−β log β−(1−α) log(1−α)−dα^{2}/2]} − ne^{nε′}e^{−t^{2}/(2n)}.

(24)

If s < 1 and we choose s := \sqrt{3.03\frac{−β log β−(1−α) log(1−α)+(β−α) log(β−α)−dα^{2}/2}{(1−α)e^{−dα}}}, t := \sqrt{n log n},

then we can also take γ := e^{−nε′} for some ε′ > 0. (If s > 1, then we remove the square root in the definition of s.) For example

• When d = 1, β ≈ .728, the left side (i.e. the term \frac{(1−s)𝔼_{P_{k}(n)}N_{σ}}{k+1} ) exceeds 1 when

α < .25, and the right side (i.e. the term \frac{(1+s)𝔼_{P_{k}(n)}N_{σ}}{k+1} ) is less than 1 when α > .46.

• When d = 2, β ≈ .607, the left side exceeds 1 when α < .194, and the right side is less than 1 when α > .39.

• When d = e, β ≈ .552, the left side exceeds 1 when α < .172, and the right side is less than 1 when α > .35.

□

7. Random Regular Graphs

Lemma 7.1. Let (G, σ) ∈ Λ_{k}(n) be a random sample from P_{k}(n). Let N_{σ} be the number of vertices in G \ σ that are not connected to σ. Then

ℙ_{P_{k}(n)}(|N_{σ} − 𝔼_{P_{k}(n)}N_{σ}| ≥ t𝔼_{P_{k}(n)}N_{σ}) ≤ 2e^{−n min(t,t^{2})(1−α)e^{−dα}/3} ∀ t ≥ 0.

Proof. Let α := k/n. Let h(x) := x log x. Let v ∈ {1, …, n} be a vertex with v ∉ σ. Let D_{v} be the number of vertices in σ that v is connected to. Then {D_{v}}_{v∉σ} have the same distribution as a set of independent binomial random variables {B_{v}}_{v∉σ} each with parameters d and p := α/(1 − α), conditioned on ∑_{v∉σ} B_{v} = ndα. Then N_{σ} = ∑_{v∉σ} 1_{{B_{v}=0}} and for any 0 ≤ j ≤ nd(1 − α), (writing j = βn)

ℙ_{P_{k}(n)}(N_{σ} = j) = ℙ(N_{σ} = βn) = \frac{ℙ(exactly βn of B_{v} are 0 and ∑_{v∉σ} B_{v} = ndα)}{ℙ(∑_{v∉σ} B_{v} = ndα)}

= \frac{\binom{n(1−α)}{βn}(1 − p)^{ndβ}\binom{nd(1−α−β)}{ndα}p^{ndα}(1 − p)^{nd(1−2α−β)}}{\binom{nd(1−α)}{ndα}p^{ndα}(1 − p)^{nd(1−2α)}}

= \frac{\frac{[n(1−α)]!}{[βn]![n(1−α−β)]!}(1 − p)^{ndβ} \frac{[nd(1−α−β)]!}{[nd(1−2α−β)]![ndα]!}(1 − p)^{−dβn}}{\frac{[nd(1−α)]!}{[nd(1−2α)]![ndα]!}}

= \frac{[n(1 − α)]!}{[βn]![n(1 − α − β)]!} \frac{[nd(1 − α − β)]!}{[nd(1 − α)]!} \frac{[nd(1 − 2α)]!}{[nd(1 − 2α − β)]!}

= exp (n[h(1 − α) − h(β) − h(1 − α − β) + h(d(1 − α − β))

− h(d(1 − α)) + h(d(1 − 2α)) − h(d(1 − 2α − β))])

= exp (n[h(1 − α) − h(β) − h(1 − α − β) + h(d(1 − α − β))

− h(d(1 − α)) + h(d(1 − 2α)) − h(d(1 − 2α − β))]).

𝔼_{P_{k}(n)}N_{σ} = |σ^{c}| ℙ(B_{1} = 0) = (1 − α)n\frac{ℙ(B_{v} = 0 and ∑_{v∉σ,v≠1} B_{v} = ndα)}{ℙ(∑_{v∉σ} B_{v} = ndα)}

= (1 − α)n\frac{(1 − p)^{d}\binom{nd(1−α)−d}{ndα}p^{ndα}(1 − p)^{nd(1−2α)−d}}{\binom{nd(1−α)}{ndα}p^{ndα}(1 − p)^{nd(1−2α)}}

= (1 − α)n\frac{[d[n(1 − α) − 1]]!}{[dn(1 − α)]!} \frac{[nd(1 − 2α)]!}{[nd(1 − 2α) − d]!}

= (1 − α)n\frac{(nd(1 − 2α))(nd(1 − 2α) − 1) ⋯ (nd(1 − 2α) − d + 1)}{(nd(1 − α))(nd(1 − α) − 1) ⋯ (nd(1 − α) − d + 1)}.

As n → ∞, 𝔼_{P_{k}(n)}N_{σ}/n ≈ [(1 − 2α)/(1 − α)]^{d} = (1 − α)(1 − p)^{d} ≈ (1 − α)e^{−αd}.

ℙ_{P_{k}(n)}(N_{σ} ≥ j) = ∑_{γ=β,β+1/n,...,1} exp (n[h(1 − α) − h(γ) − h(1 − α − γ) + h(d(1 − α − γ))
− h(d(1 − α)) + h(d(1 − 2α)) − h(d(1 − 2α − γ))])
≈ ∫_{β}^{1} exp (n[h(1 − α) − h(γ) − h(1 − α − γ) + h(d(1 − α − γ))
− h(d(1 − α)) + h(d(1 − 2α)) − h(d(1 − 2α − γ))])dγ.

As a function of γ, the integrand is uniformly log-concave, so the result follows.

□

Lemma 7.2 (Lower Bound). Let α := k/n and let βn be the size of the largest size independent set in the graph. Then, with probability at least 1 − e^{−t^{2}/(2dn)},

X_{k,n} ≥ e^{−t log(1−α/β)}e^{−n[(β−α) log(β−α)−β log β+(d−1)(1−α) log(1−α)−(d/2)(1−2α) log(1−2α)]}𝔼X_{k,n}.

Proof. By Stirling’s formula, [DSS16, Lemma 2.1]

𝔼X_{k,n} = n^{O(1)} exp (n((d − 1)(1 − α) log(1 − α) − α log α − (d/2)(1 − 2α) log(1 − 2α))).

Also, the size of the largest independent set concentrates around it’s expected value by the Azuma-Hoeffding inequality (using the edge-revealing filtration). So a lower bound for X_{k,n} is given by taking size k = αn subsets of this large independent set, i.e.

ℙ (X_{k,n} ≥ \binom{βn − t}{αn}) ≥ e^{−t^{2}/[2dn]}, ∀ t ≥ 0.

Therefore

\frac{𝔼X_{k,n}}{\binom{βn}{αn}} = \frac{(αn)![(β − α)n]!}{(βn)!}n^{O(1)} exp (n((d − 1)(1 − α) log(1 − α) − α log α
− (d/2)(1 − 2α) log(1 − 2α))).
= n^{O(1)} exp (n((β − α) log(β − α) − β log β + (d − 1)(1 − α) log(1 − α)
− (d/2)(1 − 2α) log(1 − 2α))).

More specifically,

\begin{matrix}( & {n \atop αn} & ) \\ ( & {βn−t \atop αn} & ) \end{matrix}(1 − d/n)^{\binom{αn}{2}} = n^{O(1)} exp (n((β − α) log(β − α) − β log β + (d − 1)(1 − α) log(1 − α)
− (d/2)(1 − 2α) log(1 − 2α)))e^{t log(1−α/β)}.

That is, with probability at least 1 − e^{−t^{2}/(2n)},

\frac{𝔼X_{k,n}}{X_{k,n}} ≤ \frac{𝔼X_{k,n}}{# size k subsets of the largest independent set}
≤ n^{O(1)} exp (n((β − α) log(β − α) − β log β + (d − 1)(1 − α) log(1 − α)
− (d/2)(1 − 2α) log(1 − 2α)))e^{t log(1−α/β)}.
□

Proof of Theorem 1.20. Denote α := k/n. From Lemma 7.2,with probability at least 1 − e^{−t^{2}/(2dn)} =: 1 − ε_{2},

X_{k,n} ≥ e^{−t log(1−α/β)}e^{−n[(β−α) log(β−α)−β log β+(d−1)(1−α) log(1−α)−(d/2)(1−2α) log(1−2α)]}𝔼X_{k,n}.

Let C denote this event.

Then, let A be the event that (G, σ) satisfies |N_{σ} − 𝔼_{P_{k}(n)}N_{σ}| > s𝔼N_{σ}. From Lemma 7.1,

ℙ_{P_{k}(n)}(A) ≤ 2e^{−n min(s,s^{2})(1−α)e^{−dα}/3} =: ε_{1} ∀ t ≥ 0.

We therefore apply Lemma 5.2 so that, for γ := e^{−nε′}, and t := \sqrt{n log n}

ℙ(∀ 0 ≤ k ≤ n, \frac{(1 − s)(𝔼_{P_{k}(n)}N_{σ} − γ)}{k + 1} ≤ \frac{X_{k+1,n}}{X_{k,n}} ≤ \frac{(1 + s′)𝔼_{P_{k}(n)}N_{σ}}{k + 1} + n\frac{γ}{k + 1})

≥ 1 − \frac{n}{γ}(\frac{ε_{1}}{c_{1}} + ε_{2}) ≥ 1 − ne^{nε′}2e^{−n min(s,s^{2})(1−α)e^{−dα}/3}e^{t log(1−α/β)}

· \sqrt{\frac{β − α}{β(1 − α)}}e^{dα}e^{n[(β−α) log(β−α)−β log β−(1−α) log(1−α)−dα^{2}/2]} − ne^{nε′}e^{−t^{2}/(2n)}.

So, if we choose s := \sqrt{3.03\frac{−β log β−(1−α) log(1−α)+(β−α) log(β−α)−dα^{2}/2}{(1−α)e^{−dα}}} and t := \sqrt{n log n}, then

we can also take γ := e^{−nε′} for some ε′ > 0.

For d sufficiently large, by Theorem 2.4 (whose conclusion holds in this case by e.g. [Wor99, page 21]), the largest independent set has size nβ, where

β := (2/d)(log d − log log d − log 2 + 1).  (25)

Let δ := α/β so that 0 < δ < 1. Then

s := \sqrt{100\frac{−β log β − (1 − α) log(1 − α) + (β − α) log(β − α) − dα^{2}/2 − dα/n}{(1 − α)e^{−dα}}}

≈ \sqrt{100\frac{−β log β + β(1 − δ) log(β(1 − δ)) − dβ^{2}δ^{2}/2 − dβδ/n}{(1 − α)e^{−dδβ}}}

≈^{(25)} \sqrt{100\frac{−β log β + β(1 − δ) log β + β(1 − δ) log(1 − δ) − dβ^{2}δ^{2}/2 − dβδ/n}{(1 − α)e^{−2δ(log d−log log d−log 2+1)}}}

= \sqrt{100\frac{−δβ log β + β(1 − δ) log(1 − δ) − dβ^{2}δ^{2}/2 − dβδ}{(1 − α)e^{−2δ(log d−log log d−log 2+1)}}}

≈ \sqrt{100\frac{−δ(2/d) log d log(2/d) + (2/d) log(d)(1 − δ) log(1 − δ) − 4(1/d) log^{2}(d)δ^{2}/2}{d^{−2δ}}}

≈ \sqrt{100\frac{−δ(2/d) log d log(2/d) − 4(1/d) log^{2}(d)δ^{2}/2}{d^{−2δ}}}

≈ d^{δ−1/2}\sqrt{200}\sqrt{δ log d}\sqrt{log(d/2) − δ log(d)} = d^{δ−1/2}\sqrt{200}\sqrt{δ(1 − δ)} log d.

So, if δ < 1/2, s → 0 as d → ∞. So, we define ε := |δ − 1/2| to conclude.

□

8. Random Trees

Let Y be a random variable defined on trees. Suppose we use the Aldous-Broder algorithm [Bro89, Ald90] to generate a random tree. For any integer 0 ≤ k ≤ n − 1, let F_{k} denote the set of edges revealed by the algorithm. Each time a new edge is added to the tree, there is another piece of information given, so this naturally yields a (Doob) martingale. For any integer 0 ≤ k ≤ n − 1, let Y_{k} := 𝔼(Y | F_{k}).

Lemma 8.1 (Azuma-Hoeffding for Aldous-Broder). Assume that |Y_{k} − Y_{k−1}| ≤ 1 for all 1 ≤ k ≤ n − 1. Then

ℙ(|Y − EY | > t𝔼Y) ≤ 2e^{− \frac{t^{2}(𝔼Y )^{2}}{2(n−1)}} , ∀ t > 0.

Proof. Apply the Azuma-Hoeffding Inequality, Lemma 2.3. □

Let σ ⊆ {1, …, n} with |σ| = k. Let α := k/n. Let v ∈ {1, …, n} be a vertex with v ∉ S. Let C_{v} be the event that v is connected to some vertex in σ. Let N_{σ} := ∑_{v∉S} 1_{C_{v}^{c}} be the number of vertices not connected to σ.

Lemma 8.2.

𝔼_{P_{k}(n)}N_{σ} = n(1 − α)^{2}e^{−α/(1−α)}(1 + O(1/n)).
ℙ_{P_{k}(n)}(|N_{σ} − 𝔼P_{k}(n)N_{σ}| > t) ≤ 2e^{−(n−1) \frac{t^{2}(1−α)^{4}e^{−2α/(1−α)}}{2} (1+O(log n/n))}, ∀ t > 0.

Proof. The first equality follows from Lemma 9.1, i.e. the matrix-tree theorem, since the probability that vertices {1, …, k + 1} form an independent set, given that the vertices {1, …, k} form an independent set is

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

So, 𝔼_{P_{k}(n)}N_{σ} is n − k times this number. The second inequality follows from the first and Lemma 8.1. □

Lemma 8.3 (Lower Bound for Trees). For a uniformly random labelled tree on n vertices, we have the following deterministic bound (i.e. with probability one):

X_{k,n} ≥ (1 + o(1))e^{n[(2−3α) log(1−α)−(1−2α) log(1−2α)]}𝔼X_{k,n}.

Proof. Rather than repeating the proof of Lemma 3.10, we use a deterministic bound for X_{k,n} from [Win95], as pointed out to use by David Galvin.

From Lemma 9.1, and since there are n^{n−2} labelled trees on n vertices,

𝔼X_{k,n} = \binom{n}{αn}(1 − α)^{αn}.  (26)

Theorem 5.1 from [Win95] says that

X_{k,n} ≥ \binom{n − k + 1}{k} = \binom{n(1 − α) − 1}{αn}.

So, from Stirling’s formula,

\frac{X_{k,n}}{𝔼X_{k,n}} ≥^{(26)} (1 + o(1))e^{n[(1−α) log(1−α)−α log α−(1−2α) log(1−2α)]}
· e^{−n[−α log α−(1−α) log(1−α)+α log(1−α)]}
= (1 + o(1))e^{n[(2−3α) log(1−α)−(1−2α) log(1−2α)]}.
□

8.1. Conditioning Arguments. The concentration inequality in Lemma 8.2 can be used with Lemma 5.2 to show that roughly the first 30% of the nonzero independent set sequence of a random tree is increasing. However, the constants appearing in Lemma 8.2 are not sharp. They can be improved to the following form, yielding a better unimodality result.

Lemma 8.4 ([AH20].). Let T be a uniformly random tree on n vertices, conditioned on σ being an independent set. Let N_{σ} be the number of vertices in σ^{c} not connected to σ. Then

ℙ_{P_{k}(n)}(|N_{σ} − 𝔼P_{k}(n)N_{σ}| > s𝔼P_{k}(n)N_{σ} + 1) ≤ e^{− min(s,s^{2})n(1−α)^{2}e^{−α/(1−α)}/3}.

More generally,

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

The proof of Lemma 8.4 will appear separately in [AH20].

Proof of Theorem 1.17. Denote α := k/n. From Lemma 8.3, with probability 1,

X_{k,n} ≥ (1 + o(1))e^{n[(2−3α) log(1−α)−(1−2α) log(1−2α)]}

Let C denote this event, and let ε_{2} := 0.

Then, let A be the event that (G, σ) satisfies N_{σ} − 𝔼_{P_{k}(n)}N_{σ} < −s𝔼_{P_{k}(n)}N_{σ} − 1 = 𝔼_{P_{k}(n)}N_{σ}(−s − 1/𝔼_{P_{k}(n)}N_{σ}). From Lemma 8.4,

ℙ_{P_{k}(n)}(A) ≤ e^{−s^{2}n(1−α)^{2}e^{−α/(1−α)}/2}, ∀ 0 < s < 1.

We therefore apply Lemma 5.2 so that, for γ := e^{−nε′},

ℙ(∀ 0 ≤ k ≤ n, −\frac{1}{k + 1}(1 − \frac{γ}{𝔼_{P_{k}(n)}N_{σ}} ) + \frac{(1 − s)(𝔼_{P_{k}(n)}N_{σ} − γ)}{k + 1} ≤ \frac{X_{k+1,n}}{X_{k,n}} )

≥ 1 − \frac{n}{γ}(\frac{ε_{1}}{c_{1}} + ε_{2}) ≥ 1 − ne^{nε′}2e^{−s^{2}n(1−α)^{2}e^{−α/(1−α)}/2}

· e^{−n[−(2−3α) log(1−α)+(1−2α) log(1−2α)]}e^{t log(1−α/β)}.

(27)

So, if we choose s := \sqrt{2\frac{−(2−3α) log(1−α)+(1−2α) log(1−2α)}{(1−α)^{2}e^{−α/(1−α)}}}, then we can also take γ := e^{−nε′} for

some ε′ > 0. The term −\frac{1}{k+1}(1 − \frac{γ}{𝔼_{P_{k}(n)}N_{σ}} ) in (27) is negligible for fixed α and n large since

it is of the form O((αn)^{−1}(1 − O(e^{−nε′}n^{−1}))).

The left-most term in the quantity (27) gives unimodality when it is greater than 1, i.e. when α satisfies

\frac{(1 + o(1))(1 − α)^{2}e^{− \frac{α}{1−α}}}{α} ; · (1 − \sqrt{2\frac{−(2 − 3α) log(1 − α) + (1 − 2α) log(1 − 2α)}{(1 − α)^{2}e^{−α/(1−α)}}}) > 1.  (28)

This inequality holds when α < .26543. (Also s < 1 when α < .4.) □

Remark 8.5. We note the following in passing. The right part of the quantity in (27) gives unimodality when it is less than 1, i.e. when α satisfies

\frac{(1 + o(1))(1 − α)^{2}e^{− \frac{α}{1−α}}}{α} ; · (1 + \sqrt{2\frac{−(2 − 3α) log(1 − α) + (1 − 2α) log(1 − 2α)}{(1 − α)^{2}e^{−α/(1−α)}}}) < 1.  (29)

This inequality holds when α > .37824. This result nearly recovers the result of Levit-Mandrescu, Theorem 1.8, which holds for all trees, for all α > .378095.

9. Appendix: Matrix Tree Theorem

Lemma 9.1 ([Bed64]). The number of labelled trees on n ≥ k + 1 vertices where vertices 1, …, k form an independent set is

\frac{1}{n}(n − k)^{k−1}n^{n−k} = (n − k)^{k−1}n^{n−k−1}.

Proof. Consider the adjacency matrix

k  n − k
n − k ⋯ 0  −1 −1 ⋯ −1
k  ⋮  ...  ⋮  ⋮  ⋮ ⋯  ⋮
0 ⋯ n − k −1 −1 ⋯ −1
−1 ⋯ −1 n − 1 −1 ⋯ −1
n − k−1 ⋯ −1 −1 n − 1 ⋯ −1
⋮ ⋯  ⋮  ⋮  ... ⋮
−1 ⋯ −1 −1 ⋯ −1 n − 1

A basis of eigenvectors exists including vectors of the form

(1, 0, …, −1, 0, …, 0 | 0, …, 0), (1, …, 1 | 0 …, 0, −k, 0, …, 0).

The eigenvalues of these vectors are n − k and n respectively. The first eigenvalue appears k − 1 times and the second appears n − k times.

So, the matrix-tree theorem implies that the number of labelled trees where vertices 1, …, k form an independent set is

\frac{1}{n}(n − k)^{k−1}n^{n−k} = (n − k)^{k−1}n^{n−k−1}.

□

Acknowledgement. Thanks to David Galvin for introducing us to this problem, and for suggesting an improvement to Lemma 8.3, which then led to an improved constant in Theorem 1.17. Thanks to Larry Goldstein for several helpful discussions. Thanks to Richard Arratia for explaining to me the Joyal bijection along with several of its improvements. Thanks to Tim Austin for emphasizing the importance of [CE15] and informing us of the reference [Bow18]. Thanks also to Ken Alexander, Sarah Cannon, Will Perkins, and Tianyi Zheng.

References

[AH20] Richard Arratia and Steven Heilman, Tree/endofunction bijections and concentration inequalities, Preprint, 2020. 24, 25

[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 23

[AMSE87] Yousef Alavi, Paresh J. Malde, Allen J. Schwenk, and Paul Erdős, The vertex independence sequence of a graph is not constrained, vol. 58, 1987, Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla., 1987), pp. 15– 23. MR 944684 2, 3

[Aus18] Tim Austin, Measure concentration and the weak Pinsker property, Publ. Math. Inst. Hautes Études Sci. 128 (2018), 1–119. MR 3905465 5

[BBO14] Patrick Bahls, Elizabeth Bailey, and McCabe Olsen, New families of graphs whose independence polynomials have only real zeros, Australas. J. Combin. 60 (2014), 128–135. MR 3251932 3

[BE76] B. Bollobas and P. Erdös, Cliques in random graphs, Mathematical Proceedings of the Cambridge Philosophical Society 80 (1976), no. 3, 419–427. 7 [Bed64] S. D. Bedrosian, Generating formulas for the number of trees in a graph, J. Franklin Inst. 277

(1964), 313–326. MR 162240 25

[BES12] Shankar Bhamidi, Steven N. Evans, and Arnab Sen, Spectra of large random trees, Journal of Theoretical Probability 25 (2012), no. 3, 613–654. 10

[BG20] Abdul Basit and David Galvin, On the independent set sequence of a tree, Preprint., 2020. 6 [BK13] Arnab Bhattacharyya and Jeff Kahn, A bipartite graph with non-unimodal independent set se-

quence, Electron. J. Combin. 20 (2013), no. 4, Paper 11, 3. MR 3139396 3

[Bow18] Lewis Bowen, Sofic homological invariants and the weak pinsker property, Preprint, arXiv:1807.08191, 2018. 5, 26

[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. 23

[CE15] Amin Coja-Oghlan and Charilaos Efthymiou, On independent sets in random graphs, Random Struct. Algorithms 47 (2015), no. 3, 436–486. 2, 4, 5, 13, 14, 15, 26

[CS07] Maria Chudnovsky and Paul Seymour, The roots of the independence polynomial of a clawfree graph, Journal of Combinatorial Theory, Series B 97 (2007), no. 3, 350 – 357. 4

[DM11] Varsha Dani and Cristopher Moore, Independent sets in random graphs from the weighted second moment method, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Berlin, Heidelberg) (Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and José D. P. Rolim, eds.), Springer Berlin Heidelberg, 2011, pp. 472–482. 4, 13

[DSS16] Jian Ding, Allan Sly, and Nike Sun, Maximum independent sets on random regular graphs, Acta Math. 217 (2016), no. 2, 263–340. 2, 4, 21

[Fri90] A. M. Frieze, On the independence number of random graphs, Discrete Math. 81 (1990), no. 2, 171–175. 5, 6, 9

[Gal11] David Galvin, Two problems on independent sets in graphs, Discrete Math. 311 (2011), no. 20, 2105–2112. MR 2825652 3, 4

[Gal12] , The independent set sequence of regular bipartite graphs, Discrete Math. 312 (2012), no. 19, 2881–2892. MR 2946949 3, 4

[GH18] David Galvin and Justin Hilyard, The independent set sequence of some families of trees, Australas. J. Combin. 70 (2018), 236–252. MR 3737109 3

[GNS06] David Gamarnik, Tomasz Nowicki, and Grzegorz Swirszcz, Maximum weight independent sets and matchings in sparse random graphs. exact results using the local weak convergence method, Random Structures & Algorithms 28 (2006), no. 1, 76–106. 9

[Gri81] G. R. Grimmett, Random labelled trees and their branching networks, J. Austral. Math. Soc. Ser. A 30 (1980/81), no. 2, 229–237. MR 607933 3

[Ham90] Yahya Hamidoune, On the numbers of independent k-sets in a claw free graph, Journal of Combinatorial Theory, Series B 50 (1990), 241–244. 4

[HL72] Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190–232. MR 297280 4, 5

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

[JSV04] Mark Jerrum, Alistair Sinclair, and Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM 51 (2004), no. 4, 671–697. 2

[KS81] R. M. Karp and M. Sipser, Maximum matching in sparse random graphs, Proceedings of the 22Nd Annual Symposium on Foundations of Computer Science (Washington, DC, USA), SFCS ’81, IEEE Computer Society, 1981, pp. 364–375. 9

[LM02] Vadim E. Levit and Eugen Mandrescu, On well-covered trees with unimodal independence polynomials, Proceedings of the Thirty-third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002), vol. 159, 2002, pp. 193–202. MR 1985180 3

[LM03] , On unimodality of independence polynomials of some well-covered trees, Discrete mathematics and theoretical computer science, Lecture Notes in Comput. Sci., vol. 2731, Springer, Berlin, 2003, pp. 237–256. MR 2062222 3 [LM07] , Independence polynomials and the unimodality conjecture for very well-covered, quasi-

regularizable, and perfect graphs, Graph theory in Paris, Trends Math., Birkhäuser, Basel, 2007, pp. 243–254. MR 2279180 3

[MM88] A. Meir and J. W. Moon, On maximal independent sets of nodes in trees, Journal of Graph Theory 12 (1988), no. 2, 265–283. 10

[MSS15] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. (2) 182 (2015), no. 1, 307–325. MR 3374962 5

[Pit99] Boris Pittel, Normal convergence problem? two moments and a recurrence may be the clues, Ann. Appl. Probab. 9 (1999), no. 4, 1260–1302. 10

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

[Win95] George Clifton Wingard, Properties and applications of the Fibonacci polynomial of a graph, ProQuest LLC, Ann Arbor, MI, 1995, Thesis (Ph.D.)–The University of Mississippi. MR 2692771 5, 6, 24

[Wor99] N. C. Wormald, Models of random regular graphs, Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239–298. MR 1725006 23

[WZ11] Yi Wang and Bao-Xuan Zhu, On the unimodality of independence polynomials of some graphs, European J. Combin. 32 (2011), no. 1, 10–20. MR 2727455 3

[Zhu07] Zhi-Feng Zhu, The unimodality of independence polynomials of some graphs, Australas. J. Combin. 38 (2007), 27–33. MR 2324272 3

[Zhu16] Bao-Xuan Zhu, Clique cover products and unimodality of independence polynomials, Discrete Appl. Math. 206 (2016), 172–180. MR 3490439 3

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

E-mail address: stevenmheilman@gmail.com