Randomized Algorithms (Spring 2010)/The probabilistic method

The Basic Idea

Counting or sampling

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] vertices with two colors so that there is no monochromatic [math]\displaystyle{ K_k }[/math] subgraph.

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].

Theorem Let [math]\displaystyle{ \mathcal{F}\subseteq{[n]\choose k} }[/math] and let [math]\displaystyle{ m=|\mathcal{F}| }[/math]. [math]\displaystyle{ \mathcal{F} }[/math] has a blocking set of size [math]\displaystyle{ \left\lceil\frac{n\ln m}{k}\right\rceil }[/math]. That is, there exists a set [math]\displaystyle{ T\subseteq[n] }[/math] of size [math]\displaystyle{ \left\lceil\frac{n\ln m}{k}\right\rceil }[/math] such that [math]\displaystyle{ T }[/math] intersects all [math]\displaystyle{ S\in\mathcal{E} }[/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.