随机算法 (Fall 2011)/Random Graphs

From EtoneWiki
Jump to: navigation, search

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

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 .

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 .

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
.

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 .

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 ,

.