# Combinatorics (Fall 2010)/Random graphs

## Contents

## 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 be a random variable assuming only nonnegative values. Then, for all ,

- Let be a random variable assuming only nonnegative values. Then, for all ,

**Proof.**Let be the indicator such that It holds that . Since is 0-1 valued, . Therefore,

For any random variable , for an arbitrary non-negative real function , the is a non-negative random variable. Applying Markov's inequality, we directly have that

This trivial application of Markov's inequality gives us a powerful tool for proving tail inequalities. With the function which extracts more information about the random variable, we can prove sharper tail inequalities.

### Variance

**Definition (variance)**- The
**variance**of a random variable is defined as - The
**standard deviation**of random variable is

- The

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 and is

- The

We have the following theorem for the variance of sum.

**Theorem**- For any two random variables and ,
- Generally, for any random variables ,

- For any two random variables and ,

**Proof.**The equation for two variables is directly due to the definition of variance and covariance. The equation for variables can be deduced from the equation for two variables.

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 and ,

- For any two independent random variables and ,

**Proof.**

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

**Theorem**- For any two independent random variables and ,

- For any two independent random variables and ,

**Proof.**

### 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 ,

- For any ,

**Proof.**Observe that Since is a nonnegative random variable, we can apply Markov's inequality, such that

## Erdős–Rényi Random Graphs

Consider a graph which is randomly generated as:

- ;
- , independently with probability .

Such graph is denoted as **. This is called the ****Erdős–Rényi model** or ** model** for random graphs.

Informally, the presence of every edge of is determined by an independent coin flipping (with probability of HEADs ).

### Coloring large-girth graphs

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

**Definition**Let be an undirected graph.

- A
**cycle**of length in is a sequence of distinct vertices such that for all and . - The
**girth**of , dented , is the length of the shortest cycle in .

- A

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 , denoted , is the minimal number of colors which we need to color the vertices of so that no two adjacent vertices have the same color. Formally,

- .

- The

In 1959, Erdős proved the following theorem: for any fixed and , there exists a finite graph with girth at least and chromatic number at least . 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 there exists a graph with and .

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 , denoted , is the size of the largest independent set in . Formally,

- .

- The

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

**Lemma**- For any -vertex graph,
- .

- For any -vertex graph,

**Proof.**- In the optimal coloring, vertices are partitioned into 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 . Therefore, .

The lemma follows.

Therefore, it is sufficient to prove that and .

**Proof of Erdős theorem**Fix . Let be with .

For any length- simple cycle , let be the indicator random variable such that

The number of cycles of length at most in graph is

- .

For any particular length- simple cycle ,

- .

For any , the number of length- simple cycle is . By the linearity of expectation,

- .

Applying Markov's inequality,

Therefore, with high probability the random graph has less than short cycles.

Now we proceed to analyze the independence number. Let , so that

The probability that either of the above events occurs is

Therefore, there exists a graph with less than "short" cycles, i.e., cycles of length at most , and with .

Take each "short" cycle in and remove a vertex from the cycle (and also remove all adjacent edges to the removed vertex). This gives a graph which has no short cycles, hence the girth . And has at least vertices, because at most vertices are removed.

Notice that removing vertices cannot makes grow. It holds that . Thus

- .

The theorem is proved by taking sufficiently large so that this value is greater than .

The proof contains a very simple procedure which for any and *generates* such a graph with and . The procedure is as such:

- Fix some . Choose sufficiently large with , and let .
- Generate a random graph as .
- For each cycle of length at most in , remove a vertex from the cycle.

The resulting graph satisfying that and with high probability.

### Monotone properties

A graph property is a predicate of graph which depends only on the structure of the graph.

**Definition**- Let , where , be the set of all possible graphs on vertices. A
**graph property**is a boolean function which is invariant under permutation of vertices, i.e. whenever is isomorphic to .

- Let , where , be the set of all possible graphs on vertices. A

We are interested in the monotone properties, i.e., those properties that adding edges will not change a graph from having the property to not having the property.

**Definition**- A graph property is
**monotone**if for any , both on vertices, having property implies having property .

- A graph property is

By seeing the property as a function mapping a set of edges to a numerical value in , a monotone property is just a monotonically increasing set function.

Some examples of monotone graph properties:

- Hamiltonian;
- -clique;
- contains a subgraph isomorphic to some ;
- non-planar;
- chromatic number (i.e., not -colorable);
- girth .

From the last two properties, you can see another reason that the Erdős theorem is unintuitive.

Some examples of **non-**monotone graph properties:

- Eulerian;
- contains an
*induced*subgraph isomorphic to some ;

For all monotone graph properties, we have the following theorem.

**Theorem**- Let be a monotone graph property. Suppose , , and . Then
- .

- Let be a monotone graph property. Suppose , , and . Then

Although the statement in the theorem looks very natural, it is difficult to evaluate the probability that a random graph has some property. However, the theorem can be very easily proved by using the idea of coupling, a proof technique in probability theory which compare two unrelated random variables by forcing them to be related.

**Proof.**For any , let be independently and uniformly distributed over the continuous interval . Let if and only if and let if and only if .

It is obvious that and . For any , means that , which implies that . Thus, .

Since is monotone, implies . Thus,

- .

### Threshold phenomenon

One of the most fascinating phenomenon of random graphs is that for so many natural graph properties, the random graph suddenly changes from almost always not having the property to almost always having the property as grows in a very small range.

A monotone graph property is said to have the **threshold** if

- when , as (also called almost always does not have ); and
- when , as (also called almost always has ).

The classic method for proving the threshold is the so-called second moment method (Chebyshev's inequality).

**Theorem**- The threshold for a random graph to contain a 4-clique is .

We formulate the problem as such. For any -subset of vertices , let be the indicator random variable such that

Let be the total number of 4-cliques in .

It is sufficient to prove the following lemma.

**Lemma**- If , then as .
- If , then as .

**Proof.**The first claim is proved by the first moment (expectation and Markov's inequality) and the second claim is proved by the second moment method (Chebyshev's inequality).

Every 4-clique has 6 edges, thus for any ,

- .

By the linearity of expectation,

- .

Applying Markov's inequality

- , if .

The first claim is proved.

To prove the second claim, it is equivalent to show that if . By the Chebyshev's inequality,

- ,

where the variance is computed as

- .

For any ,

- . Thus the first term of above formula is .

We now compute the covariances. For any that :

- Case.1: , so and do not share any edges. and are independent, thus .
- Case.2: , so and share an edge. Since , there are pairs of such and .

- since there are 11 edges in the union of two 4-cliques that share a common edge. The contribution of these pairs is .

- Case.2: , so and share a triangle. Since , there are pairs of such and . By the same argument,

- since there are 9 edges in the union of two 4-cliques that share a triangle. The contribution of these pairs is .

Putting all these together,

And

- ,

which is if . The second claim is also proved.

The above theorem can be generalized to any "balanced" subgraphs.

**Definition**- The
**density**of a graph , denoted , is defined as . - A graph is
**balanced**if for all subgraphs of .

- The

Cliques are balanced, because for any . The threshold for 4-clique is a direct corollary of the following general theorem.

**Theorem (Erdős–Rényi 1960)**- Let be a balanced graph with vertices and edges. The threshold for the property that a random graph contains a (not necessarily induced) subgraph isomorphic to is .

**Sketch of proof.**For any , let indicate whether (the subgraph of induced by ) contain a subgraph . Then

- , since there are at most ways to match the substructure.

Note that does not depend on . Thus, . Let be the number of -subgraphs.

- .

By Markov's inequality, which is when .

By Chebyshev's inequality, where

- .

The first term .

For the covariances, only if for . Note that implies that . And for balanced , the number of edges of interest in and is . Thus, . And,

Therefore, when ,

- .

## Small World Networks

Read the introduction of Kleinberg's paper (listed in the references).

## 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.