Combinatorics (Fall 2010)/Random graphs

Tail Inequalities

Markov's inequality

One of the most natural information about a random variable is its expectation, which is the first moment of the random variable. Markov's inequality draws a tail bound for a random variable from its expectation.

Theorem (Markov's Inequality)

Let [math]\displaystyle{ X }[/math] be a random variable assuming only nonnegative values. Then, for all [math]\displaystyle{ t\gt 0 }[/math], [math]\displaystyle{ \begin{align} \Pr[X\ge t]\le \frac{\mathbf{E}[X]}{t}. \end{align} }[/math]

Proof. Let [math]\displaystyle{ Y }[/math] be the indicator such that [math]\displaystyle{ \begin{align} Y &= \begin{cases} 1 & \mbox{if }X\ge t,\\ 0 & \mbox{otherwise.} \end{cases} \end{align} }[/math] It holds that [math]\displaystyle{ Y\le\frac{X}{t} }[/math]. Since [math]\displaystyle{ Y }[/math] is 0-1 valued, [math]\displaystyle{ \mathbf{E}[Y]=\Pr[Y=1]=\Pr[X\ge t] }[/math]. Therefore, [math]\displaystyle{ \Pr[X\ge t] = \mathbf{E}[Y] \le \mathbf{E}\left[\frac{X}{t}\right] =\frac{\mathbf{E}[X]}{t}. }[/math] [math]\displaystyle{ \square }[/math]

For any random variable [math]\displaystyle{ X }[/math], for an arbitrary non-negative real function [math]\displaystyle{ h }[/math], the [math]\displaystyle{ h(X) }[/math] is a non-negative random variable. Applying Markov's inequality, we directly have that

[math]\displaystyle{ \Pr[h(X)\ge t]\le\frac{\mathbf{E}[h(X)]}{t}. }[/math]

This trivial application of Markov's inequality gives us a powerful tool for proving tail inequalities. With the function [math]\displaystyle{ h }[/math] which extracts more information about the random variable, we can prove sharper tail inequalities.

Variance

Definition (variance)

The variance of a random variable [math]\displaystyle{ X }[/math] is defined as [math]\displaystyle{ \begin{align} \mathbf{Var}[X]=\mathbf{E}\left[(X-\mathbf{E}[X])^2\right]=\mathbf{E}\left[X^2\right]-(\mathbf{E}[X])^2. \end{align} }[/math] The standard deviation of random variable [math]\displaystyle{ X }[/math] is [math]\displaystyle{ \delta[X]=\sqrt{\mathbf{Var}[X]}. }[/math]

We have seen that due to the linearity of expectations, the expectation of the sum of variable is the sum of the expectations of the variables. It is natural to ask whether this is true for variances. We find that the variance of sum has an extra term called covariance.

Definition (covariance)

The covariance of two random variables [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] is [math]\displaystyle{ \begin{align} \mathbf{Cov}(X,Y)=\mathbf{E}\left[(X-\mathbf{E}[X])(Y-\mathbf{E}[Y])\right]=\mathbf{E}[XY]-\mathbf{E}[X]\mathbf{E}[Y]. \end{align} }[/math]

We have the following theorem for the variance of sum.

Theorem

For any two random variables [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math], [math]\displaystyle{ \begin{align} \mathbf{Var}[X+Y]=\mathbf{Var}[X]+\mathbf{Var}[Y]+2\mathbf{Cov}(X,Y). \end{align} }[/math] Generally, for any random variables [math]\displaystyle{ X_1,X_2,\ldots,X_n }[/math], [math]\displaystyle{ \begin{align} \mathbf{Var}\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbf{Var}[X_i]+\sum_{i\neq j}\mathbf{Cov}(X_i,X_j). \end{align} }[/math]

Proof. The equation for two variables is directly due to the definition of variance and covariance. The equation for [math]\displaystyle{ n }[/math] variables can be deduced from the equation for two variables. [math]\displaystyle{ \square }[/math]

We will see that when random variables are independent, the variance of sum is equal to the sum of variances. To prove this, we first establish a very useful result regarding the expectation of multiplicity.

Theorem

For any two independent random variables [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math], [math]\displaystyle{ \begin{align} \mathbf{E}[X\cdot Y]=\mathbf{E}[X]\cdot\mathbf{E}[Y]. \end{align} }[/math]

Proof. [math]\displaystyle{ \begin{align} \mathbf{E}[X\cdot Y] &= \sum_{x,y}xy\Pr[X=x\wedge Y=y]\\ &= \sum_{x,y}xy\Pr[X=x]\Pr[Y=y]\\ &= \sum_{x}x\Pr[X=x]\sum_{y}y\Pr[Y=y]\\ &= \mathbf{E}[X]\cdot\mathbf{E}[Y]. \end{align} }[/math] [math]\displaystyle{ \square }[/math]

With the above theorem, we can show that the covariance of two independent variables is always zero.

Theorem

For any two independent random variables [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math], [math]\displaystyle{ \begin{align} \mathbf{Cov}(X,Y)=0. \end{align} }[/math]

Proof. [math]\displaystyle{ \begin{align} \mathbf{Cov}(X,Y) &=\mathbf{E}\left[(X-\mathbf{E}[X])(Y-\mathbf{E}[Y])\right]\\ &= \mathbf{E}\left[X-\mathbf{E}[X]\right]\mathbf{E}\left[Y-\mathbf{E}[Y]\right] &\qquad(\mbox{Independence})\\ &=0. \end{align} }[/math] [math]\displaystyle{ \square }[/math]

Chebyshev's inequality

With the information of the expectation and variance of a random variable, one can derive a stronger tail bound known as Chebyshev's Inequality.

Theorem (Chebyshev's Inequality)

For any [math]\displaystyle{ t\gt 0 }[/math], [math]\displaystyle{ \begin{align} \Pr\left[|X-\mathbf{E}[X]| \ge t\right] \le \frac{\mathbf{Var}[X]}{t^2}. \end{align} }[/math]

Proof. Observe that [math]\displaystyle{ \Pr[|X-\mathbf{E}[X]| \ge t] = \Pr[(X-\mathbf{E}[X])^2 \ge t^2]. }[/math] Since [math]\displaystyle{ (X-\mathbf{E}[X])^2 }[/math] is a nonnegative random variable, we can apply Markov's inequality, such that [math]\displaystyle{ \Pr[(X-\mathbf{E}[X])^2 \ge t^2] \le \frac{\mathbf{E}[(X-\mathbf{E}[X])^2]}{t^2} =\frac{\mathbf{Var}[X]}{t^2}. }[/math] [math]\displaystyle{ \square }[/math]

Erdős–Rényi Random Graphs

Consider a graph [math]\displaystyle{ G(V,E) }[/math] which is randomly generated as:

• [math]\displaystyle{ |V|=n }[/math];
• [math]\displaystyle{ \forall \{u,v\}\in{V\choose 2} }[/math], [math]\displaystyle{ uv\in E }[/math] independently with probability [math]\displaystyle{ p }[/math].

Such graph is denoted as [math]\displaystyle{ G(n,p) }[/math]. This is called the Erdős–Rényi model or [math]\displaystyle{ G(n,p) }[/math] model for random graphs.

Informally, the presence of every edge of [math]\displaystyle{ G(n,p) }[/math] is determined by an independent coin flipping (with probability of HEADs [math]\displaystyle{ p }[/math]).

Coloring large-girth graphs

The girth of a graph is the length of the shortest cycle of the graph.

Definition

Let [math]\displaystyle{ G(V,E) }[/math] be an undirected graph. A cycle of length [math]\displaystyle{ k }[/math] in [math]\displaystyle{ G }[/math] is a sequence of distinct vertices [math]\displaystyle{ v_1,v_2,\ldots,v_{k} }[/math] such that [math]\displaystyle{ v_iv_{i+1}\in E }[/math] for all [math]\displaystyle{ i=1,2,\ldots,k-1 }[/math] and [math]\displaystyle{ v_kv_1\in E }[/math]. The girth of [math]\displaystyle{ G }[/math], dented [math]\displaystyle{ g(G) }[/math], is the length of the shortest cycle in [math]\displaystyle{ G }[/math].

The chromatic number of a graph is the minimum number of colors with which the graph can be properly colored.

Definition (chromatic number)

The chromatic number of [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ \chi(G) }[/math], is the minimal number of colors which we need to color the vertices of [math]\displaystyle{ G }[/math] so that no two adjacent vertices have the same color. Formally, [math]\displaystyle{ \chi(G)=\min\{C\in\mathbb{N}\mid \exists f:V\rightarrow[C]\mbox{ such that }\forall uv\in E, f(u)\neq f(v)\} }[/math].

In 1959, Erdős proved the following theorem: for any fixed [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math], there exists a finite graph with girth at least [math]\displaystyle{ k }[/math] and chromatic number at least [math]\displaystyle{ \ell }[/math]. This is considered a striking example of the probabilistic method. The statement of the theorem itself calls for nothing about probability or randomness. And the result is highly contra-intuitive: if the girth is large there is no simple reason why the graph could not be colored with a few colors. We can always "locally" color a cycle with 2 or 3 colors. Erdős' result shows that there are "global" restrictions for coloring, and although such configurations are very difficult to explicitly construct, with the probabilistic method, we know that they commonly exist.

Theorem (Erdős 1959)

For all [math]\displaystyle{ k,\ell }[/math] there exists a graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ g(G)\gt \ell }[/math] and [math]\displaystyle{ \chi(G)\gt k\, }[/math].

It is very hard to directly analyze the chromatic number of a graph. We find that the chromatic number can be related to the size of the maximum independent set.

Definition (independence number)

The independence number of [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ \alpha(G) }[/math], is the size of the largest independent set in [math]\displaystyle{ G }[/math]. Formally, [math]\displaystyle{ \alpha(G)=\max\{|S|\mid S\subseteq V\mbox{ and }\forall u,v\in S, uv\not\in E\} }[/math].

We observe the following relationship between the chromatic number and the independence number.

Lemma

For any [math]\displaystyle{ n }[/math]-vertex graph, [math]\displaystyle{ \chi(G)\ge\frac{n}{\alpha(G)} }[/math].

Proof. In the optimal coloring, [math]\displaystyle{ n }[/math] vertices are partitioned into [math]\displaystyle{ \chi(G) }[/math] color classes according to the vertex color. Every color class is an independent set, or otherwise there exist two adjacent vertice with the same color. By the pigeonhole principle, there is a color class (hence an independent set) of size [math]\displaystyle{ \frac{n}{\chi(G)} }[/math]. Therefore, [math]\displaystyle{ \alpha(G)\ge\frac{n}{\chi(G)} }[/math]. The lemma follows. [math]\displaystyle{ \square }[/math]

Therefore, it is sufficient to prove that [math]\displaystyle{ \alpha(G)\le\frac{n}{k} }[/math] and [math]\displaystyle{ g(G)\gt \ell }[/math].

Proof of Erdős theorem Fix [math]\displaystyle{ \theta\lt \frac{1}{\ell} }[/math]. Let [math]\displaystyle{ G }[/math] be [math]\displaystyle{ G(n,p) }[/math] with [math]\displaystyle{ p=n^{\theta-1} }[/math]. For any length-[math]\displaystyle{ i }[/math] simple cycle [math]\displaystyle{ \sigma }[/math], let [math]\displaystyle{ X_\sigma }[/math] be the indicator random variable such that [math]\displaystyle{ X_\sigma= \begin{cases} 1 & \sigma\mbox{ is a cycle in }G,\\ 0 & \mbox{otherwise}. \end{cases} }[/math] The number of cycles of length at most [math]\displaystyle{ \ell }[/math] in graph [math]\displaystyle{ G }[/math] is [math]\displaystyle{ X=\sum_{i=3}^\ell\sum_{\sigma:i\text{-cycle}}X_\sigma }[/math]. For any particular length-[math]\displaystyle{ i }[/math] simple cycle [math]\displaystyle{ \sigma }[/math], [math]\displaystyle{ \mathbf{E}[X_\sigma]=\Pr[X_\sigma=1]=\Pr[\sigma\mbox{ is a cycle in }G]=p^i=n^{\theta i-i} }[/math]. For any [math]\displaystyle{ 3\le i\le n }[/math], the number of length-[math]\displaystyle{ i }[/math] simple cycle is [math]\displaystyle{ \frac{n(n-1)\cdots (n-i+1)}{2i!} }[/math]. By the linearity of expectation, [math]\displaystyle{ \mathbf{E}[X]=\sum_{i=3}^\ell\sum_{\sigma:i\text{-cycle}}\mathbf{E}[X_\sigma]=\sum_{i=3}^\ell\frac{n(n-1)\cdots (n-i+1)}{2i!}n^{\theta i-i}\le \sum_{i=3}^\ell\frac{n^{\theta i}}{2i!}=o(n) }[/math]. Applying Markov's inequality, [math]\displaystyle{ \Pr\left[X\ge \frac{n}{2}\right]\le\frac{\mathbf{E}[X]}{n/2}=o(1). }[/math] Therefore, with high probability the random graph has less than [math]\displaystyle{ n/2 }[/math] short cycles. Now we proceed to analyze the independence number. Let [math]\displaystyle{ m=\left\lceil\frac{3\ln n}{p}\right\rceil }[/math], so that [math]\displaystyle{ \begin{align} \Pr[\alpha(G)\ge m] &\le\Pr\left[\exists S\in{V\choose m}\forall \{u,v\}\in{S\choose 2}, uv\not\in G\right]\\ &\le{n\choose m}(1-p)^{m\choose 2}\\ &\lt n^m\mathrm{e}^{-p{m\choose 2}}\\ &=\left(n\mathrm{e}^{-p(m-1)/2}\right)^m=o(1) \end{align} }[/math] The probability of the or of the above events is [math]\displaystyle{ \begin{align} \Pr\left[X\lt \frac{n}{2}\vee \alpha(G)\lt m\right] \le \Pr\left[X\lt \frac{n}{2}\right]+\Pr\left[\alpha(G)\lt m\right] =o(1). \end{align} }[/math] Therefore, there exists a graph [math]\displaystyle{ G }[/math] with less than [math]\displaystyle{ n/2 }[/math] "short" cycles, i.e., cycles of length at most [math]\displaystyle{ \ell }[/math], and with [math]\displaystyle{ \alpha(G)\lt m\le 3n^{1-\theta}\ln n }[/math]. Take each "short" cycle in [math]\displaystyle{ G }[/math] and remove a vertex from the cycle (and also remove all adjacent edges to the removed vertex). This gives a graph [math]\displaystyle{ G' }[/math] which has no short cycles and has at least [math]\displaystyle{ n/2 }[/math] (because at most [math]\displaystyle{ n/2 }[/math] vertices are removed). Hence the girth [math]\displaystyle{ g(G')\ge\ell }[/math]. Notice that removing vertices cannot makes [math]\displaystyle{ \alpha(G) }[/math] grow. It holds that [math]\displaystyle{ \alpha(G')\le\alpha(G) }[/math]. Thus [math]\displaystyle{ \chi(G')\ge\frac{n/2}{\alpha(G')}\ge\frac{n}{2m}\ge\frac{n^\theta}{6\ln n} }[/math]. The theorem is proved by taking [math]\displaystyle{ n }[/math] sufficiently large so that this value is greater than [math]\displaystyle{ k }[/math]. [math]\displaystyle{ \square }[/math]

The proof contains a very simple procedure which for any [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math] generates such a graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ g(G)\gt \ell }[/math] and [math]\displaystyle{ \chi(G)\gt k }[/math]. The procedure is as such:

• Fix some [math]\displaystyle{ \theta\lt \frac{1}{\ell} }[/math]. Choose sufficiently large [math]\displaystyle{ n }[/math] with [math]\displaystyle{ \frac{n^\theta}{6\ln n}\gt k }[/math], and let [math]\displaystyle{ p=n^{\theta-1} }[/math].
• Generate a random graph [math]\displaystyle{ G }[/math] as [math]\displaystyle{ G(n,p) }[/math].
• For each cycle of length at most [math]\displaystyle{ \ell }[/math] in [math]\displaystyle{ G }[/math], remove a vertex from the cycle.

The resulting graph [math]\displaystyle{ G' }[/math] satisfying that [math]\displaystyle{ g(G)\gt \ell }[/math] and [math]\displaystyle{ \chi(G)\gt k }[/math] with high probability.

Monotone properties

Definition

Let [math]\displaystyle{ \mathcal{G}_n=2^{V\choose 2} }[/math], where [math]\displaystyle{ |V|=n }[/math], be the set of all possible graphs on [math]\displaystyle{ n }[/math] vertices. A graph property is a boolean function [math]\displaystyle{ P:\mathcal{G}_n\rightarrow\{0,1\} }[/math] which is invariant under permutation of vertices, i.e. [math]\displaystyle{ P(G)=P(H) }[/math] whenever [math]\displaystyle{ G }[/math] is isomorphic to [math]\displaystyle{ H }[/math].

Definition

A graph property [math]\displaystyle{ P }[/math] is monotone if for any [math]\displaystyle{ G\subseteq H }[/math], both on [math]\displaystyle{ n }[/math] vertices, [math]\displaystyle{ G }[/math] having property [math]\displaystyle{ P }[/math] implies [math]\displaystyle{ H }[/math] having property [math]\displaystyle{ P }[/math].

Theorem

Let [math]\displaystyle{ P }[/math] be a monotone graph property. Suppose [math]\displaystyle{ G_1=G(n,p_1) }[/math], [math]\displaystyle{ G_2=G(n,p_2) }[/math], and [math]\displaystyle{ 0\le p_1\le p_2\le 1 }[/math]. Then [math]\displaystyle{ \Pr[P(G_1)]\le \Pr[P(G_2)] }[/math].

Threshold phenomenon

Theorem

The threshold for a random graph [math]\displaystyle{ G(n,p) }[/math] to contain a 4-clique is [math]\displaystyle{ p=n^{2/3} }[/math].

Definition

The density of a graph [math]\displaystyle{ G(V,E) }[/math], denoted [math]\displaystyle{ \rho(G)\, }[/math], is defined as [math]\displaystyle{ \rho(G)=\frac{|E|}{|V|} }[/math]. A graph [math]\displaystyle{ G(V,E) }[/math] is balanced if [math]\displaystyle{ \rho(H)\le \rho(G) }[/math] for all subgraphs [math]\displaystyle{ H }[/math] of [math]\displaystyle{ G }[/math].

Theorem (Erdős–Rényi 1960)

Let [math]\displaystyle{ H }[/math] be a balanced graph with [math]\displaystyle{ k }[/math] vertices and [math]\displaystyle{ \ell }[/math] edges. The threshold for the property that a random graph [math]\displaystyle{ G(n,p) }[/math] contains a (not necessarily induced) subgraph isomorphic to [math]\displaystyle{ H }[/math] is [math]\displaystyle{ p=n^{-k/\ell}\, }[/math].

References

(声明: 资料受版权保护, 仅用于教学.)

(Disclaimer: The following copyrighted materials are meant for educational uses only.)

• Diestel. Graph Theory, 2nd Edition. Springer-Verlag 2000. Chapter 11.
• Alon and Spencer. The Probabilistic Method, 3rd Edition. Wiley, 2008. "The Probabilistic Lens: High Girth and High Chromatic Number", and Chapter 4.
• J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000.