Randomized Algorithms (Spring 2010)/The probabilistic method

The Basic Idea

Counting or sampling

Ramsey number

Theorem If [math]\displaystyle{ {n\choose k}\cdot 2^{1-{k\choose 2}}\lt 1 }[/math] then it is possible to color the edges of [math]\displaystyle{ K_n }[/math] with two colors so that there is no monochromatic [math]\displaystyle{ K_k }[/math] subgraph.

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]

Note that 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]

Circuit complexity

Theorem (Shannon) There is a boolean function [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math] with circuit complexity greater than [math]\displaystyle{ \frac{2^n}{3n} }[/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 Given a set family [math]\displaystyle{ \mathcal{F}\subseteq{S\choose k} }[/math], where [math]\displaystyle{ m=|\mathcal{F}| }[/math] and [math]\displaystyle{ n=|S| }[/math], [math]\displaystyle{ \mathcal{F} }[/math] has a blocking set of size [math]\displaystyle{ \left\lceil\frac{n\ln m}{k}\right\rceil }[/math].

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 Given an undirected graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges, there is a cut of size at least [math]\displaystyle{ \frac{m}{2} }[/math].

Theorem For any set of [math]\displaystyle{ m }[/math] clauses, there is a truth assignment that satisfies at least [math]\displaystyle{ \frac{m}{2} }[/math] clauses.

Alterations

Independent sets

Theorem Let [math]\displaystyle{ G(V,E) }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices with [math]\displaystyle{ m }[/math] edges. Then [math]\displaystyle{ G }[/math] has an independent set with at least [math]\displaystyle{ \frac{n^2}{4m} }[/math] vertices.

Dominating sets

Theorem Let [math]\displaystyle{ G(V,E) }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices, with minimum degree [math]\displaystyle{ \delta\gt 1 }[/math] edges. Then [math]\displaystyle{ G }[/math] has a dominating set of at most [math]\displaystyle{ \frac{n(1+\ln(\delta+1))}{\delta+1} }[/math] vertices.

Intersecting families

The Erdős-Ko-Rado theorem

Theorem (Erdős-Ko-Rado 1961) Let [math]\displaystyle{ \mathcal{F}\subseteq{S\choose k} }[/math], where [math]\displaystyle{ |S|=n }[/math] and [math]\displaystyle{ n\ge 2k }[/math]. If [math]\displaystyle{ \mathcal{F} }[/math] is an intersecting family then [math]\displaystyle{ |\mathcal{F}|\le{n-1\choose k-1} }[/math].

Proof (due to Katona 1972).

Two-coloring of hypergraphs

Theorem (Erdős 1963) Let [math]\displaystyle{ \mathcal{F}\subseteq{S\choose k} }[/math]. If [math]\displaystyle{ |\mathcal{F}|\le 2^{k-1} }[/math], then [math]\displaystyle{ \mathcal{F} }[/math] is two-colorable.

Theorem (Radhakrishnan and Srinivasan 2000) Let [math]\displaystyle{ \mathcal{F}\subseteq{S\choose k} }[/math]. If [math]\displaystyle{ |\mathcal{F}|=o(2^k\sqrt{k/\ln k}) }[/math], then [math]\displaystyle{ \mathcal{F} }[/math] is two-colorable.