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