Randomized Algorithms (Spring 2010)/The probabilistic method

The Basic Idea

Counting or sampling

Circuit complexity

A boolean function is a function is the form [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math].

Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled [math]\displaystyle{ x_1, x_2, \ldots , x_n }[/math]. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in P can be computed by a circuit with polynomially many gates. Thus, if we can find a function in NP that cannot be computed by any circuit with polynomially many gates, then NP[math]\displaystyle{ \neq }[/math]P.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

Theorem (Shannon 1949) 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].

Proof: There are [math]\displaystyle{ 2^{2^n} }[/math] boolean functions [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math].

Fix an integer [math]\displaystyle{ t }[/math], we then count the number of circuits with [math]\displaystyle{ t }[/math] gates. By the De Morgan's laws, we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable [math]\displaystyle{ x_i }[/math], an inverted input variable [math]\displaystyle{ \neg x_i }[/math], or the output of another gate; thus, there are at most [math]\displaystyle{ 2+2n+t-1 }[/math] possible gate inputs. It follows that the number of circuits with [math]\displaystyle{ t }[/math] gates is at most [math]\displaystyle{ 2^t(t+2n+1)^{2t} }[/math].

Uniformly choose a boolean function [math]\displaystyle{ f }[/math] at random. Note that each circuit can compute one boolean function (the converse is not true). The probability that [math]\displaystyle{ f }[/math] can be computed by a circuit with [math]\displaystyle{ t }[/math] gates is at most

[math]\displaystyle{ \frac{2^t(t+2n+1)^{2t}}{2^{2^n}}. }[/math]

If [math]\displaystyle{ t=2^n/3n }[/math], then

[math]\displaystyle{ \frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)\lt 1. }[/math]

Therefore, there exists a boolean function [math]\displaystyle{ f }[/math] which cannot be computed by any circuits with [math]\displaystyle{ 2^n/3n }[/math] gates.

[math]\displaystyle{ \square }[/math]

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but almost all boolean functions have exponentially large circuit complexity.

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

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

The theorem also hints us to a randomized algorithm. In order to make the algorithm efficient, we relax the size of [math]\displaystyle{ T }[/math] to [math]\displaystyle{ \tau=\frac{2n\ln m}{k} }[/math]. Uniformly choose [math]\displaystyle{ \tau }[/math] elements from [math]\displaystyle{ S }[/math] to form the set [math]\displaystyle{ T }[/math], by the above analysis, the probability that [math]\displaystyle{ T }[/math] is NOT a blocking set is at most

[math]\displaystyle{ m\exp\left(-\frac{n\tau}{k}\right)=m\exp(-2\ln m)=\frac{1}{m}. }[/math]

Thus, a blocking set is found with high probability.

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.