[Graph Theory] Ramsey Theory

Organized patterns must appear in large chaotic system.

엮자면 다 엮을 수 있다.

 

Definition

hypergraph: edge 가 $V(H)$의 subset 인 그래프. 어떻게든 엮어본 vertex들끼리 이어보면 나오는 그래프. 

r-uniform: 모든 edge의 size가 r. 어떻게든 엮어본 그룹 사이즈가 다 r.

complete r-uniform hypergraph: 모든 r-subset 에 edge 들로 구성된 그래프. 어떻게든 엮어본 그룹에 다 edge 있음

Graph 는 2-uniform hypergraphs. 2개의 vertices 사이에 다 edge가 있잖아.

hyper graph is simple: $e \subseteq e'$ 인데 $e, e' \in E(H)$ 가 없는 경우. <????>

 

$K_6$의 예시를 보자. edge coloring 을 하다보면 monochromatic cliques, 그러니까 "같은 색으로 edge를 싹 칠할 수 있는 3짜리 clique를 가진다" 성질을 유지하는 graph의 minimum size 가 6이라는 걸 알 수 있다.

 

Definition

k-coloring: 각 도메인의 element 를 k 개의 색 중 하나로 label. vertex건 edge건 굳이 색이 아니더라도 라벨링으로 매칭

$\binom{S}{r}$: a complete r-uniform hypergraph with the vertex set $S$. set $S$ 에서 r-subset의 family. subset 에서 억지로 엮은 r개짜리 팀들의 그룹.

$binom{S}{r}$의 coloring 에서, $T \subseteq S$, 그러니까 어느 그룹 T는 $i$-homogeneous 하다. r-subset이 모두 같은 색 $i$를 가진다면. 같은 색으로 칠해지는 subset이 있다.

 

Ramsey number $R(p_1, ..., p_k; r)$: $p_1, ..., p_k \in \mathbb{N}$, $\binom {[N]}{r}$의 $k$ coloring 에 대해 size $p_i$짜리 $i$-homogeneous set 을 만족하는 $N$이 존재하고, 그 숫자 중 가장 작은 수.

$p_i$ 는 1이건 2건 3이건... 뭐가 되었건 간에 자연수들이고 우리는 $[N]$개짜리 자연수를 생각한다.

$N$으로 이루어진 그래프가 있을 때, 걔들 중에서 억지로 $r$개씩 묶어줬을 때, $p_i$ 만큼의 size 에 $i$ 색으로 homogeneous 하게 칠해진 subset이 항상 존재한다는 것. 이 중에 가장 작은 그래프를 Ramsey number라고 한다.

 

예를 들어, $R(3,3;2) = 6$. 억지로 2개씩 묶어줬을 때, size 3짜리에 red or blue 색으로 homoegenous 하게 칠해진 subset이 존재하는 그래프 중 가장 작은 사이즈는 6이다.

그래프에서는 어차피 edge가 두 vertex끼리 엮이니까 끝의 2를 생략하고 $R(3,3)$하고 쓴다.

 

Theorem <Ramsey>

$R(p_1, ..., p_k; r)$은 항상 존재한다.

2개씩 묶어주면 어떻게 묶어도 homogeneous 한 set이 발생하게 할 수 있다. 다만 size가 겁나 커질 뿐.

$\textit{Proof}$

이건 시간 나면 할게.

 

Ramsey number 의 upper bound는 무엇일까.

그래프의 2색 색칠 케이스에 국한하자면,

 

Theorem.

$R(p,q) \leq R(p-1, q) + R(p, q-1)$

솔직히 모르겠고

 

Corollary

$R(p,q) \leq \binom{p+1+2}{p-1}$

$\textit{Proof}$

$R(p,q) \leq R(p-1, q) + R(p, q-1) \leq \binom{p+q-3}{p-1} + \binom{p+q-3}{p-2} = \binom{p+q-2}{p-1}$

솔직히 모르겠고

 

Theorem <Erdos-Szekeres, Happy End>

$m \in \mathbb{N}$ 에 대해서, $N = N(m)$인 $N$이 존재한다.

어느 3개의 포인트도 한 라인에 줄지어 있지 않은 평면의 $N$ point짜리 set 들은 convex m-gon <m각형> 을 만드는 m-subset 을 포함한다.

$\textit{Proof}$

2개의 claim 을 살펴보자.

Claim 1. 어느 3개 포인트도 한 라인에 줄지어있지 않은 평면의 5개의 점들을 골라봐. 그 중 4개는 convex quadrilateral. 볼록 사다리꼴이야.

증명은 나중에 할게.

Claim 2. m개 포인트 중에서 4개짜리 subset 들이 볼록 사다리꼴을 만들면 그 $m$개의 포인트들이 convex m-gon 만들어.

증명은 나중에 할게.

 

$N = R(m, 5;4)$라고 치자. $N$개 포인트가 plane에 있다면,

각 4-set, 4개짜리 subset을 convexity에 의해 색칠해보자.

convex quadrilateral, 볼록 사다리꼴을 만드는 애들이면 빨강, 나머지는 파랑으로.

이러면 4-subset 이 모두 파란색이 나오는 5개짜리 팀들은 아무도 없다구.

Ramsey theorem에 따르면 4-subset 이 모두 빨간색인 $m$ 개의 포인트들이 있어야 한단 말이야.

그러면 걔들이 convex m-gon 을 만드는 거지.

그러므로 $R(m,5;4)$ 인 $N$이 존재한다.

 

$N(m)$의 lower bound에 대해서 Erdos-Szekeres 가 증명한 건

$2^{n-2}+1 \leq N(m) \leq \binom{2n-4}{n-2} + 1 \leq 4^n$ 이라는 것.

Suk 이 $N(m) \geq 2^{n+cn^{2/3}logn}$ 인것까지는 밝히긴 했음.

 

Ramsey number 를 일반화 해보면

 

Definition

<graph> Ramseynumber $R(G_1, ..., G_k)$: $E(K_n)$의 모든 $k$-coloring 에 대해서 color $i$로 색칠되는 $G_i$를 포함하게 되는 smallest integer $n$.

$R_k(G) = R(G_1, ..., G_k)$

 

$G_i$ 가 $p_i$ 개의 vertices를 가지고 있고, $G_i$가 $K_{p_i}$의 subgraph라고 치면,

$R(G_1, ..., G_k)$ 는 $R(p_1, ..., p_k)$가 존재한다면 존재하지.

 

Theorem <Chvatal>

T 가 $m$-vertex tree $\Rightarrow$ $R(T, K_n) = (m-1)(n-1)+1$

$textit{Proof}$

나중에 할게.