Randomized Algorithms (Spring 2010)/The probabilistic method
The Basic Idea
Counting or sampling
- Circuit complexity
Theorem (Shannon)
|
- Ramsey number
Recall the Ramsey theorem which states that in a meeting of at least six people, there are either three people knowing each other or three people not knowing each other. In graph theoretical terms, this means that no matter how we color the edges of [math]\displaystyle{ K_6 }[/math] (the complete graph on six vertices), there must be a monochromatic [math]\displaystyle{ K_3 }[/math] (a triangle whose edges have the same color).
Generally, the Ramsey number [math]\displaystyle{ R(k,\ell) }[/math] is the smallest integer [math]\displaystyle{ n }[/math] such that in any two-coloring of the edges of a complete graph on [math]\displaystyle{ n }[/math] vertices [math]\displaystyle{ K_n }[/math] by red and blue, either there is a red [math]\displaystyle{ K_k }[/math] or there is a blue [math]\displaystyle{ K_\ell }[/math].
Ramsey showed in 1929 that [math]\displaystyle{ R(k,\ell) }[/math] is finite for any [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math]. It is extremely hard to compute the exact value of [math]\displaystyle{ R(k,\ell) }[/math]. Here we give a lower bound of [math]\displaystyle{ R(k,k) }[/math] by the probabilistic method.
Theorem (Erdős 1947)
|
Proof: Consider a random two-coloring of edges of [math]\displaystyle{ K_n }[/math] obtained as follows:
- For each edge of [math]\displaystyle{ K_n }[/math], independently flip a fair coin to decide the color of the edge.
For any fixed set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ k }[/math] vertices, let [math]\displaystyle{ \mathcal{E}_S }[/math] be the event that the [math]\displaystyle{ K_k }[/math] subgraph induced by [math]\displaystyle{ S }[/math] is monochromatic. There are [math]\displaystyle{ {k\choose 2} }[/math] many edges in [math]\displaystyle{ K_k }[/math], therefore
- [math]\displaystyle{ \Pr[\mathcal{E}_S]=2\cdot 2^{-{k\choose 2}}=2^{1-{k\choose 2}}. }[/math]
Since there are [math]\displaystyle{ {n\choose k} }[/math] possible choices of [math]\displaystyle{ S }[/math], by the union bound
- [math]\displaystyle{ \Pr[\exists S, \mathcal{E}_S]\le {n\choose k}\cdot\Pr[\mathcal{E}_S]={n\choose k}\cdot 2^{1-{k\choose 2}}. }[/math]
Due to the assumption, [math]\displaystyle{ {n\choose k}\cdot 2^{1-{k\choose 2}}\lt 1 }[/math], thus there exists a two coloring that none of [math]\displaystyle{ \mathcal{E}_S }[/math] occurs, which means there is no monochromatic [math]\displaystyle{ K_k }[/math] subgraph.
[math]\displaystyle{ \square }[/math]
For [math]\displaystyle{ k\ge 3 }[/math] and we take [math]\displaystyle{ n=\lfloor2^{k/2}\rfloor }[/math], then
- [math]\displaystyle{ \begin{align} {n\choose k}\cdot 2^{1-{k\choose 2}} &\lt \frac{n^k}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\ &\le \frac{2^{k^2/2}}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\ &= \frac{2^{1+\frac{k}{2}}}{k!}\\ &\lt 1. \end{align} }[/math]
By the above theorem, there exists a two-coloring of [math]\displaystyle{ K_n }[/math] that there is no monochromatic [math]\displaystyle{ K_k }[/math]. Therefore, the Ramsey number [math]\displaystyle{ R(k,k)\gt \lfloor2^{k/2}\rfloor }[/math] for all [math]\displaystyle{ k\ge 3 }[/math].
Note that for sufficiently large [math]\displaystyle{ k }[/math], if [math]\displaystyle{ n= \lfloor 2^{k/2}\rfloor }[/math], then the probability that there exists a monochromatic [math]\displaystyle{ K_k }[/math] is bounded by
- [math]\displaystyle{ {n\choose k}\cdot 2^{1-{k\choose 2}} \lt \frac{2^{1+\frac{k}{2}}}{k!} \ll 1, }[/math]
which means that a random two-coloring of [math]\displaystyle{ K_n }[/math] is very likely not to contain a monochromatic [math]\displaystyle{ K_{2\log n} }[/math]. This gives us a very simple randomized algorithm for finding a two-coloring of [math]\displaystyle{ K_n }[/math] without monochromatic [math]\displaystyle{ K_{2\log n} }[/math].
- Blocking number
Let [math]\displaystyle{ S }[/math] be a set. Let [math]\displaystyle{ 2^{S}=\{A\mid A\subseteq S\} }[/math] be the power set of [math]\displaystyle{ S }[/math], and let [math]\displaystyle{ {S\choose k}=\{A\mid A\subseteq S\mbox{ and }|A|=k\} }[/math] be the [math]\displaystyle{ k }[/math]-uniform of [math]\displaystyle{ S }[/math].
We call [math]\displaystyle{ \mathcal{F} }[/math] a set family (or a set system) with ground set [math]\displaystyle{ S }[/math] if [math]\displaystyle{ \mathcal{F}\subseteq 2^{S} }[/math]. The members of [math]\displaystyle{ \mathcal{F} }[/math] are subsets of [math]\displaystyle{ S }[/math].
Given a set family [math]\displaystyle{ \mathcal{F} }[/math] with ground set [math]\displaystyle{ S }[/math], a set [math]\displaystyle{ T\subseteq S }[/math] is a blocking set of [math]\displaystyle{ \mathcal{F} }[/math] if all [math]\displaystyle{ A\in\mathcal{F} }[/math] have [math]\displaystyle{ A\cap T\neq \emptyset }[/math], i.e. [math]\displaystyle{ T }[/math] intersects (blocks) all member set of [math]\displaystyle{ \mathcal{F} }[/math].
Theorem
|
Proof: Let [math]\displaystyle{ \tau=\left\lceil\frac{n\ln m}{k}\right\rceil }[/math]. Let [math]\displaystyle{ T }[/math] be a set chosen uniformly at random from [math]\displaystyle{ {S\choose \tau} }[/math]. We show that [math]\displaystyle{ T }[/math] is a blocking set of [math]\displaystyle{ \mathcal{F} }[/math] with a probability >0.
Fix any [math]\displaystyle{ A\in\mathcal{F} }[/math]. Recall that [math]\displaystyle{ \mathcal{F}\subseteq{S\choose k} }[/math], thus [math]\displaystyle{ |A|=k }[/math]. And
- [math]\displaystyle{ \begin{align} \Pr[A\cap T=\emptyset] &= \frac{\left|{S-T\choose \tau}\right|}{\left|{S\choose \tau}\right|}\\ &= \frac{{n-k\choose \tau}}{{n\choose\tau}}\\ &= \frac{(n-k)\cdot(n-k-1)\cdots(n-k-\tau+1)}{n\cdot(n-1)\cdots(n-\tau+1)}\\ &\lt \left(1-\frac{k}{n}\right)^{\tau}\\ &\le \exp\left(-\frac{k\tau}{n}\right)\\ &\le \frac{1}{m}. \end{align} }[/math]
By the union bound, the probability that there exists an [math]\displaystyle{ A\in\mathcal{F} }[/math] that misses [math]\displaystyle{ T }[/math]
- [math]\displaystyle{ \Pr[\exists A\in\mathcal{F}, A\cap T=\emptyset]\le m\Pr[A\cap T=\emptyset]\lt m\cdot\frac{1}{m}=1. }[/math]
Thus, the probability that [math]\displaystyle{ T }[/math] is a blocking set
- [math]\displaystyle{ \Pr[\forall A\in\mathcal{F}, A\cap T\neq\emptyset]\gt 0. }[/math]
There exists a blocking set of size [math]\displaystyle{ \tau=\left\lceil\frac{n\ln m}{k}\right\rceil }[/math].
[math]\displaystyle{ \square }[/math]
Linearity of expectation
Theorem
|
Theorem
|
Alterations
- Independent sets
Theorem
|
- Dominating sets
Theorem
|
- Intersecting families
The Erdős-Ko-Rado theorem
Theorem (Erdős-Ko-Rado 1961)
|
Proof (due to Katona 1972).
- Two-coloring of hypergraphs
Theorem (Erdős 1963)
|
Theorem (Radhakrishnan and Srinivasan 2000)
|