September 25, 2012

The first and second moment methods

Posted by Akhil Mathew under combinatorics | Tags: , , |
Leave a Comment 

As I mentioned earlier, I’ve been reading a little about the probabilistic method, especially in combinatorics and related fields, as a result of a course I’m TAing. This material is certainly fundamental to a lot of mathematics and computer science, but I’ve never really studied probability. I’ve been trying to change that. The material in this post is from Alon and Spencer’s The Probabilistic Method.

 

1. First moments

For the purposes of the probabilistic method, we often want to show that a certain event is possible, which is done by showing that it occurs with positive probability as the outcome of a random process. Let {X} be a nonnegative random variable on a probability space {\Omega}. A basic observation is that:

\displaystyle \mathbb{P}(X \geq \mathbb{E}( X)) > 0.

that is, a random variable takes at least its expectation value with positive probability. This alone is sufficient to obtain many interesting results.

Example: Let’s go back to the problem of bounding below the Ramsey numbers. Consider a random 2-coloring of the edges of the graph {K_N}, and let {X} be the random variable which outputs the number of monochromatic {k}-cliques, and {Y = N - X}. We note that if we remove one vertex from {K_N} from each monochromatic edge, we get a 2-colored complete graph with {Y} vertices and no {k}-cliques. (more…)

 

September 18, 2012

Ramsey theory and the probabilistic method

Posted by Akhil Mathew under combinatorics | Tags: , , |
Leave a Comment 

Let {A_i, 1 \leq i \leq n} be a collection of events in a probability space {\Omega}. There are two situations under which we can conclude that

\displaystyle \bigcup A_i \neq \Omega.

  1. {\sum \mathbb{P}(A_i) < 1}.
  2. The {A_i} are independent of each other. In this case, the {\overline{A_i} } are independent and {\mathbb{P} ( \bigcap \overline{A_i}) = \prod \mathbb{P}(\overline{A_i}) >0}.

There are a number of probabilistic arguments in combinatorics which can be made from the first situation alone. One of the original examples is the problem of bounding below the Ramsey numbers {R(k, k)}. By definition, {R(k, k)} is large enough such that any 2-coloring of the edges on a complete graph {K_{R(k, k)}} contains a monochromatic {k}-clique {K_k}.

In order to show that {R(k, k)} must be larger than some value {n}, one chooses a random 2-coloring (with both colors equally likely and the coloring of each edge independent) on the edges of a {K_n}. For each {k}-subset {A \subset [n]}, let {E_A} be the event that {A} is monochromatic under this 2-coloring, so that

\displaystyle \mathbb{P}(E_A) = 2^{1-\binom{k}{2}}.

If {\bigcup_{A: |A| = k} E_A } is a proper subset of the probability space, then there is a 2-coloring of {K_n} with no monochromatic {k}-clique. In particular, if

\displaystyle \sum_{A: |A| = k} \mathbb{P}(E_A) = \binom{n}{k} 2^{1-\binom{k}{2}} < 1,

then we can conclude that there is a 2-coloring of {K_n} without a monochromatic {K_k}, so that {n < R(k, k)}. One concludes the following lower bound:

Theorem 1 (Erdös) If {\binom{n}{k} 2^{1-\binom{k}{2}} < 1}, then {R(k, k) > n}.

 

In such arguments, the individual “bad” events (say, the {E_A}) had small probability, and to show that they did not together exhaust the entire probability space, one used the relatively crude bound {\mathbb{P}( \bigcup A_i) \leq \sum \mathbb{P}(A_i)}: that is, we used the first of the above two conditions at the beginning of this post. In practice, the events {A_i} are not independent, but a large proportion of them are, and that might suggest the use of a “hybrid” of the two strategies. (more…)