• 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$$