Random Graphs and the Probabilistic Method...
In analysis of Random Graphs, we are especially interested in testing whether the observed graph has a given property. The technique known as the Probabilistic Method is often used in proofs of these properties. The basic idea is simple and elegant : To prove the existence of an object with certain properties, we demonstrate a sample space of objects in which the probability is positive that a randomly selected object has required properties.
For example, we can demonstrate a outline of simple proof of the following theorem :
Let K_n be a complete graph (having n vertices and (n \over 2) eges) and let K_k be a complete subgraph in K_n , with k vertices.
If (n \over 2)2^{-(k \over 2)+1) \lt 1 then it is possible to color the edges of K_n with two colors so that it has no monochromatic K_k subgraph
There are 2^(n \over 2) possible coloring of edges of K_n using two colors, so the probability of each coloring, choosed uniformly at random is 2^-(n \over 2). There are (n \over k) different k-vertex cliques of K_n. If we assume that A_i is the event that the clique i is monochromatic, then is we color the first edge in i, the remaining (k \over 2) edges must be of the same color. Therefore, the probability of this coloring is Pr(A_i) = 2^-(k \over 2)+1. We can use unior bound to determine that probability of all possible A_i events is less than (n \over k)2^-(k \over 2)+1 that is less than 1, meaning that the inverse probability (of picking the coloring without monochromatic k-vertex clique) is greater than 0, wich means that there exists a coloring with no monochromatic k-vertex clique.
So, we have proved that such graph exists, without explicitly constructing one, which is a reason that the probabilistic method proofs are known as a nonconstructive proofs.
todo : convert tex formulas into gifs...
For example, we can demonstrate a outline of simple proof of the following theorem :
Let K_n be a complete graph (having n vertices and (n \over 2) eges) and let K_k be a complete subgraph in K_n , with k vertices.
If (n \over 2)2^{-(k \over 2)+1) \lt 1 then it is possible to color the edges of K_n with two colors so that it has no monochromatic K_k subgraph
There are 2^(n \over 2) possible coloring of edges of K_n using two colors, so the probability of each coloring, choosed uniformly at random is 2^-(n \over 2). There are (n \over k) different k-vertex cliques of K_n. If we assume that A_i is the event that the clique i is monochromatic, then is we color the first edge in i, the remaining (k \over 2) edges must be of the same color. Therefore, the probability of this coloring is Pr(A_i) = 2^-(k \over 2)+1. We can use unior bound to determine that probability of all possible A_i events is less than (n \over k)2^-(k \over 2)+1 that is less than 1, meaning that the inverse probability (of picking the coloring without monochromatic k-vertex clique) is greater than 0, wich means that there exists a coloring with no monochromatic k-vertex clique.
So, we have proved that such graph exists, without explicitly constructing one, which is a reason that the probabilistic method proofs are known as a nonconstructive proofs.
todo : convert tex formulas into gifs...
0 Comments:
Post a Comment
<< Home