The Probabilistic Method: An Introduction

The motivation of the probabilistic method is to show the existence of an object. The basic idea is to show that there is greater than zero probability for that object in a probability space $S$. There are various methods such as the argument with expectation and derandomization. We will talk about them in future sections.
 

a complete graph $K_n$

In this post we explore how to make a basic argument about the existence of an object (using the concept that showing positive probability implies existence). The object we are about to existence of is the k-clique that has no monochromatic edge-coloring (i.e. its edges are not all of a single color). Recall that a complete graph $K_n$ is a graph where all its vertices are connected to every other vertex.

a sketch of two-coloring of edges of $K_5$, monochromatic $K_3$ and non-monochromatic $K_3$

---

Theorem 1: If $\binom{n}{k}2^{-\binom{k}{2}+1}<1$ then it is possible to two-color the edges of a complete graph $K_n$ such that its subgraph $K_k$'s edges have no monochromatic coloring.
 
Don't worry about this term $\binom{n}{k}2^{-\binom{k}{2}+1}<1$ for now, it will make sense very soon. First, let's begin with a quick warm-up:

• How many edges does $K_n$ have?

See answers

$\binom{n}{2} = \frac{n(n-1)}{2} $

 
Here are some questions to think about to work toward the proof:

• How many possible colorings are there for the $\binom{n}{2}$ edges?
• How many subgraphs $K_k$ of $K_n$?
• Let $A_i$ be the event that $i$ is monochromatic. What is the $\mathbb{P}[A_i]$?

See answers

- $2^{\binom{n}{2}} $ possible colorings
- $ \binom{n}{k}$
- $ \mathbb{P}[A_i] = 2^{-\binom{k}{2}+1}$

 

---

End of quiz time.
 
Putting all these together, we have:
$\mathbb{P}[A_i] = 2^{-\binom{k}{2}+1}$
 
By union bound:
$ \mathbb{P}[ \cup_{i=1}^{\binom{n}{k}}A_i] \leq \sum_{i=1}^{ \binom{n}{k}}\mathbb{P}[A_i] = \binom{n}{k} \cdot 2^{- \binom{k}{2} + 1}$
 
By assumption of the theorem, $1- \binom{n}{k} \cdot 2^{- \binom{k}{2} + 1} > 0._{\,⬜}$
 
This proof shows the existence of a non-monochromatic $K_k$, given a two-coloring of the edges of $K_n$ and $\binom{n}{k}2^{-\binom{k}{2}+1}<1$. In the future, we will look at more sophisticated arguments using the Expectation Argument.
 

---

MU: 6.1