10. Ramsey Theory

• In any party of six people, either at least three of them are mutual strangers or at least three of them are mutual acquaintances.
• Color edges of $$K_6$$ with 2 colors, there must be monochromatic $$K_3$$.

Define $$R(k, l)$$ as the smallest integer satisfying: if $$n \geqslant R(k, l)$$, for any 2-coloring of $$K_n$$ there exists a red $$K_k$$ or a blue $$K_l$$.

Ramsey Theorem

Ramsey Theorem: $$R(k, l)$$ is finite.

• $$R(3, 3) = 6$$
• $$R(k, 2) = k, R(2, l) = l$$ (why?)
• $$R(k, l) \leqslant R(k, l-1) + R(k-1, l)$$ (why?)

Take $$n = R(k, l-1) + R(k-1, l)$$ and an arbitrary node $$v$$, split $$n-1$$ nodes into two sets $$S$$ and $$T$$, where edges between $$v$$ and $$S$$ are blue, edges between $$v$$ and $$T$$ are red. Then discuss on the size of $$|S|$$ and $$|T|$$:

• $$|S| \geqslant R(k, l-1)$$: either $$K_k \subseteq S$$ or $$K_{l-1} \subseteq S$$, in the latter case $$K_l \subseteq S \cup \lbrace v \rbrace$$.
• $$|T| \geqslant R(k-1, l)$$: either $$K_{k-1} \subseteq T$$ or $$K_l \subseteq T$$, in the former case $$K_k \subseteq T \cup \lbrace v \rbrace$$.

Upper Bound

By induction using $$R(k,l) \leqslant R(k,l-1) + R(k-1,l)$$, we can conclude that $R(k,l) \leqslant {k+l-2 \choose k-1}$

therefore $$R(k,l)$$ is finite and we complete the proof of Ramsey Theorem.

Lower Bound

For a uniformly and independently random 2-coloring of $$K_n$$, each edge is red/blue with probability $$1 / 2$$.

Associate each $$k$$-size subset of $$[n]$$ $$S$$ with an event $$A_S$$ defined as $$S$$ is a monochromatic $$K_k$$, we know that $Pr[A_S] = \dfrac{2}{2^{{k \choose 2}}} = 2^{1-{k \choose 2}}$

For any subset $$S$$ and $$T$$, $$A_S$$ and $$A_T$$ are dependent if $$|S \cap T| \geqslant 2$$. Therefore the max degree in the dependency graph is (choose the $$2$$ nodes in both sets first and choose other $$k-2$$ nodes) $d \leqslant {k \choose 2}{n-2 \choose k-2} \leqslant {k \choose 2}{n \choose k-2}$

For some $$n = ck2^{k / 2}$$ with constant $$c$$, $e 2^{1-{k \choose 2}} (d+1) \leqslant 1$

and by Lovasz Local Lemma, $$Pr\left[ \bigwedge\limits_{S \in {[n] \choose k}} \overline{A_S} \right] > 0$$, thus we know that $R(k,k) \geqslant n = \Omega(k 2^{k / 2})$

$\Omega(k 2^{k / 2}) \leqslant R(k, k) \leqslant {2k-2 \choose k-1} = O \left( \dfrac{4^k}{\sqrt{k}} \right)$

Multicolor

Similarly, define $$R(r; k_1, k_2, \dots, k_r)$$: if $$n \geqslant R(r; k_1, k_2, \dots, k_r)$$, for any $$r$$-coloring of $$K_n$$, there exists a monochromatic $$k_i$$-clique with color $$i$$.

The mixing color trick:

$R(r; k_1, \dots, k_{r-2}, k_{r-1}, k_r) \leqslant R(r-1; k_1, \dots, k_{r-2}, R(2; k_{r-1}, k_r))$

Ramsey Theorem: $$R(r; k_1, k_2, \dots, k_r)$$ is finite.

Hypergraph

If $$n \geqslant R_t(r; k_1, k_2, \dots, k_r)$$, then for any $$r$$-coloring of $${[n] \choose t}$$ there exists a monochromatic $${S \choose t}$$ with color $$i$$ and $$|S| = k_i$$ for smoe $$i$$.

A complete $$t$$-uniform hypergraph $${[n] \choose t}$$

$$r$$-coloring function $$f: {[n] \choose t} \rightarrow \lbrace 1, 2, \dots, r \rbrace$$

Partition of Set Family

If $$n \geqslant R_t(r; k_1, k_2, \dots, k_r)$$, then for any $$r$$-partition of $${[n] \choose t} = C_1 \cup \dots \cup C_r$$, there exists an $$S \subseteq [n]$$ such that $$|S| = k_i$$ and $${S \choose t} \subseteq C_i$$ for some $$i$$.

Erdos-Rado partition arrow $$n \rightarrow (k_1, k_2, \dots, k_r)^t$$

Theorem by Ramsey:

• $$R_t(r; k_1, k_2, \dots, k_r)$$ is finite.
• $$R_t(r; k) \overset{\Delta}{=} R_t(r; k, \dots, k)$$ is finite.

Happy Ending Problem

Any 5 points in the plane with no three on a line, has a subset of 4 points that form a convex quadrilateral.

Theorem (Erdos-Szekeres 1935): $$\forall m \geqslant 3$$, $$\exists N(m)$$ such that any set of $$n \geqslant N(m)$$ points in the plane with no three on a line, contains $$m$$ points that are the vertices of a convex $$m$$-gon. （凸$$m$$边形）

A convex polygon:

• The line between any two nodes in the polygon is completely in the polygon.
• No vertice is covered by the triangles formed by other three vertices.

Result: $$N(m) = R_3(2; m, m)$$ (why?)

For any set of points in the plane with no 3 on a line, denoted as $$X$$, $$|X| \geqslant N(m)$$. For all $$f: {X \choose 3} \rightarrow \lbrace 0, 1 \rbrace$$, $$\exists S \subseteq X$$, $$|S| = m$$ that there is a monochromatic $${S \choose 3}$$.

We claim that $$S$$ is a convex $$m$$-gon. (why?) For all $$a, b, c \in X$$, define $$\Delta_{abc}$$ as the # of points in triangle $$abc$$. $f(\lbrace a, b, c \rbrace) = |\Delta_{abc}| \bmod 2$

In this case, if there is point $$d$$ in triangle $$abc$$, then we have $f(abc) = f(abd) + f(acd) + f(bcd) + 1$ which is impossible because $${S \choose 3}$$ cannot be monochromatic if this equation holds.

Data Structures

• Data universe $$[N]$$
• Key $$x \in [N]$$
• Data set $$S \in {[N] \choose n}$$

Problem: is $$x \in S$$?

Solution: sorted table as data structure

Complexity: $$\geqslant \log_2 n$$ memory accesses in the worst case

Theorem (Yao 1981): If $$N \geqslant 2n$$, on sorted table, any search algorithm requires $$\Omega(\log n)$$ accesses in the worst-case.

Proof by induction on $$n$$ using equation （具体看讲义） $1 + \log \dfrac{n}{2} = \log n$