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

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

I’m TAing a combinatorics course this semester, and as a result I’ve been reading a few books on the subject recently. I’ve in particular been reading Alon and Spencer’s book on the probabilistic method. In this post, I’d like to highlight one of the examples I learned from it; there is a paper by Alon and Frankl where the material originates.

Let {\mathcal{F} \subset 2^{[n]}} be a family of subsets of {[n] \stackrel{\mathrm{def}}{=} \left\{1, 2, \dots, n\right\}}. We let {d(\mathcal{F})} be the number of disjoint pairs of {\mathcal{F}}: that is, the number of pairs {(A, A') \in \mathcal{F}^2} with {A \cap A' = \emptyset}.

Clearly we have

\displaystyle d(\mathcal{F}) \leq \left\lvert \mathcal{F}\right\rvert^2,

and a natural question is whether this inequality can be substantially improved if {|\mathcal{F}|} is large.

If {n} is even, and we take

\displaystyle \mathcal{F} = \left\{A: A \subset \left\{1, 2, \dots, n/2\right\} \ \text{or} A \subset \left\{n/2 +1 , \dots, n\right\}\right\},

then {| \mathcal{F}| = 2^{n/2 + 1}} while

\displaystyle d(\mathcal{F}) \geq 2 ( 2^{n/2} . 2^{n/2})) = 2^{1+n},

by choosing pairs such that one element is contained in {\left\{1, 2, \dots, n/2\right\}} and the other in {\left\{n/2, \dots, n\right\}}, or vice versa. In particular, we find that d(\mathcal{F}) = \Omega( |\mathcal{F}|^2).

Nonetheless, if {|\mathcal{F}|} grows sufficiently fast, then we have:

Theorem 1 (Alon and Frankl) If we require {|\mathcal{F}| \geq 2^{(1/2 + \delta) n}} for {\delta >0}, then

\displaystyle d(\mathcal{F}) = o( |\mathcal{F}|^2)

as {n \rightarrow \infty}. (more…)