CS294 Lecture 19: Expansion of Random Graphs

In which we present a probabilistic construction of expanders.

We have seen a combinatorial construction of expanders, based on the zig-zag graph product, and an algebraic one. Today we see how to use the probabilistic method to show that random graphs, selected from an appropriate probability distribution, are expanders with high probability.

A non-trivial part of today’s lecture is the choice of distribution. For us, a family of expanders is a family of regular graphs of fixed degree, but if we pick a graph at random according to the Erd\” os-Renyi distribution, selecting each pair {\{ u,v \}} to be an edge independently with probability {p}, then we do not get a regular graph and, indeed, not even a bounded-degree graph. (Even when {p= O(1/n)}, ensuring constant average degree, the maximum degree is of the order of {\log n / \log\log n}.)

This means that we have to study distributions of graphs in which there are correlations between edges, which are often difficult to reason about.

We could study the expansion of random {d}-regular graphs, but that is a particularly challenging distribution of graphs to analyze. Instead, the following distributions over {d}-regular graphs are usually considered over a vertex set {V}:

  • Pick at random {d} perfect matching over {V}, and let {E} be their union
  • Pick at random {d/2} permutations {f_1,\ldots, f_{\frac d2} : V \rightarrow V}, and have an edge for each pair {\{ v, f(v) \}}, for {i=1,\ldots, d/2}.

The first method is applicable when {n} is even, and the second method is applicable when {d} is even. (When {n} and {d} are both odd, it is not possible to have an {n}-vertex {d}-regular graph, because the number of edges in such a graph is {dn/2}.)

We will study the expansion of graphs generated according to the first distribution, and show that there exists an integer {d} and a {c>0}, such that a random {d} regular graph on {n} vertices has probability at least {1- 1/n^{\Omega(1)}} of having edge expansion at least {c}.

In particular, we will show that for {d=18}, the probability that a random {18}-regular graph has expansion {\geq \frac 1 {108}} is at least {1- O(1/n^2)}. Our bounds will be very loose, and much tighter analyses are possible.

We have to show that, with high probability over the choice of the graph, every set of vertices {S\subseteq V} with {|S| \leq |V|/2} has at least { c\cdot d \cdot |S|} edges leaving it.

The common approach to prove that a random object satisfies a certain collection of properties is to prove that each property holds with high probability, and then to use a union bound to show that all properties are simultaneously true with high probability. For a {d}-regular graph to have expansion {c}, we want every set {S} of size {\leq n/2} to have at least {cd|S|} outgoing edges; a naive approach would be to show that such a property holds for every fixed set except with probability at most {<< \frac 1{2^n}}, and then take a union bound over all {2^{n-1}} sets of size {\leq n/2}.

Unfortunately the naive approach does not work, because the probability that small sets fail to expand is much higher than {2^{n-1}}. For example, the probability that a fixed set of {d+1} nodes form a clique is at least of the order of {1/n^{d^2}}. Fortunately, the number of small sets is small, and if the probability of a fixed set of size {k} being non-expanding is, say, at most {1/{n \choose k}^2}, then, by taking a union bound over all sets of size {k}, the probability that there is a non-expanding set of size {k} is at most {1/{n\choose k}}, and then by taking a union bound over all sizes {k} we get that the probability that there is a non-expanding set is at most inverse polynomial in {n}.

Let {\Gamma(S)} denote the set of nodes that have at least a neighbor in {S}. If {|\Gamma(S) - S| \leq t}, then there are most {t} edges leaving from {S}. In order to upper bound the probability that there are {\leq \frac 12 |S|} edges leaving {S}, we will upper bound the probability that {| \Gamma (S) - S| \leq \frac 12 |S|}.

It will be convenient to have the following model in mind for how a random perfect matchings is chosen. Let {v_1,\ldots, v_n} be an arbirtary ordering of the vertices such that {S= \{ v_1,\ldots,v_k\}}, then the following algorithm samples a random perfect matching over {V}:

  • {M:= \emptyset}, {C:= \emptyset}
  • while {C\neq V}
    • let {v} be the smallest-index unmatched vertex in {V- C}
    • let {w} be a randomly selected unmatched vertex in {V - (C \cup \{ v\})}
    • {M:= M \cup \{ \{ v,w \} \}}; {C:= C \cup \{ v, w \}}
  • return {M}

It is easy to see that the above algorithm has {(n-1)\cdot (n-3) \cdots 3 \cdot 1} possible outputs, each equally likely, each distinct, and that {(n-1) \cdot (n-3) \cdots 3} is also the number of perfect matchings over a set of {n} vertices, so that the algorithm indeed samples a uniformly distributed perfect matching.

Now, fix a set {S} of size {k\leq n/2} and a set {T\subseteq V-S} of size {k/6}. The probability that, in a random matching, the vertices of {S} are all matched to vertices in {S\cup T} is at most the probability that, during the first {k/2} executions of the “while” loop, the randomly selected vertex {v_j} is in {S\cup T}.

For {i=1,\ldots,k/2}, conditioned on the first {i-1} iterations picking a vertex {w \in S\cup T}, the probability that this happens on the {i}-th iteration is the number of unmatched vertices in {(S\cup T)- (C \cup \{ v \})} which is {\frac 76 k -2i + 1}, divided by the total number of unmatched vertices in {V - (C \cup \{ v \})}, which is {n-2i+1}.

Thus, the probability that, in a random matching, all vertices of {S} are matched to vertices in {S\cup T} is at most

\displaystyle  \prod_{i=1}^{k/2} \frac{\frac76 k - 2i+1}{n-2i + 1} < \prod_{i=k/3+1}^{k/2} \frac {.5k}{.5n} = \left( \frac kn \right)^{k/6}

when we pick {G} as the union of {d} random matchings, the probability that all the neighbors of {S} are in {S\cup T} is at most the above bound raised to the power of {d}:

\displaystyle  \Pr [ \Gamma(S) \subseteq S \cup T ] \leq \left( \frac kn \right) ^{dk/6}

and taking a union bound over all choices of {S} of size {k} and all choices of {T} of size {k/6}, we have

\displaystyle  \Pr [\exists S\ {\rm such\ that} \ |S| = k \ {\rm and} \ \phi(S) \leq 1/6d] \leq

\displaystyle  	\Pr [\exists S\ {\rm such\ that} \ |S| = k \ {\rm and} \ | \Gamma(S) -S| \leq k/6 ]

\displaystyle  \leq \left( \frac kn \right) ^{dk/6} \cdot {n \choose k/6} \cdot {n\choose k}

\displaystyle  \leq \left( \frac kn \right) ^{dk/6} \cdot {n\choose k}^2

\displaystyle  \leq {n \choose k}^{- d/6} \cdot {n\choose k}^2

Now, for {d=18}, taking a union bound over all {k \geq 2} (in a graph without self-loops, every singleton set is expanding), we have

\displaystyle  \Pr \left[ \phi(G) \leq \frac 1 {18\cdot 6} \right] \leq \sum_{k=2}^{n/2} \frac 1 {{n \choose k}} \leq O \left( \frac 1{n^2} \right)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s