Notorious bound for Ramsey number for two coloring

By | May 31, 2015

Lemma. If r\ge2, then R\left(r,2\right)=r.

Proof. 꼭짓점이 r인 완전그래프 K_{r}을 생각해보자. 그러면 K_{r}에는 blue로 칠해진 edge가 적어도 한 개가 있거나(K_{2}) 모두 red인 경우거나 둘 중 하나다. 그러므로 R\left(r,2\right)\le r이다.

모두 red로 칠해진 완전그래프 K_{r-1}를 생각해보면 induced subgraph로서 blue로 된 K_{2}는 없고, red로 된 K_{r} 또한 없다. 그러므로 r-1<R\left(r,2\right)이므로 R\left(r,2\right)=r이다.


 

Theorem. If r\ge2 and s\ge2, then

(1)   \begin{equation*} R\left(r,s\right)\le R\left(r-1,s\right)+R\left(r,s-1\right). \end{equation*}

Also, we get a notorious bound

(2)   \begin{equation*} R\left(r,s\right)\le\binom{r+s-2}{r-1}. \end{equation*}

Proof. (1)과 (2)가 동시에 성립한다는 것을 보이기 위해, 그렇지 않는다고 하자. 다시 말해, (1)이 성립하지 않는 r,s>2
존재한다고 하자. 그리고 이런 r,s들 중에서 r+s가 최소가 되도록 잡자.

이제 u=r-1, v=s-1이라 하면, r+s의 최소성에 의하여 R\left(u,s\right),R\left(r,v\right),R\left(u,v\right)는 (1)을 만족해야 한다.

n=R\left(u,s\right)+R\left(r,v\right)라 하자. 이제 K_{n}의 red-blue coloring을 생각하고, v\in V\left(G\right)를 하나 생각해보자. 그리고 v와 연결된 점들을 색깔을 기준으로 분류를 해보자.

    \begin{align*} N_{R} & =\left\{ w\in V:w\ne v,\,\chi\left(\left\{ v,w\right\} \right)=\text{red}\right\} ,\\ N_{B} & =\left\{ w\in V:w\neq v,\,\chi\left(\left\{ v,w\right\} \right)=\text{blue}\right\} \end{align*}

라 정의하자. 그러면 N_{R}\cup N_{B}\cup\left\{ v\right\} =V\left(G\right)이므로, \left|N_{R}\cup N_{B}\right|=\left|N_{R}\right|+\left|N_{B}\right|-1=n-1이다. 그러므로 \left|N_{R}\right|\ge R\left(u,s\right)이거나 \left|N_{B}\right|\ge R\left(r,v\right) 둘 중 하나가 성립해야 한다. 이 사실은 자명하지 않은 사실이므로 증명이 필요하다.

그렇지 않다고 하자. 즉 다시 말해서 \left|N_{R}\right|<R\left(u,s\right)이고 \left|N_{B}\right|<R\left(r,v\right)라 하자. 그런데 램지수는 정수이므로

    \begin{align*} n-1 & =\left|N_{R}\right|+\left|N_{B}\right|\le R\left(u,s\right)-1+R\left(r,v\right)-1\\ & =R\left(u,s\right)+R\left(r,v\right)-2\\ & =n-2 \end{align*}

가 성립해야 하는데, 이는 모순이다.

\left|N_{R}\right|\ge R\left(u,s\right)일 때, 꼭짓점이 N_{R}인 완전그래프를 생각해보자. 그런데, \left|N_{R}\right|\ge R\left(u,s\right)이므로 N_{R}에는 적어도 빨간색으로 색칠된 완전그래프 K_{u}를 포함하고 있더나 또는 파란색으로 색칠된 완전그래프 K_{s}를 포함하고 있다. 만약 v가 처음에 언급한 완전그래프에 포함된다고 가정하면, N_{R}의 정의에 의하여 이는 빨간색으로 색칠된 완전그래프 K_{u+1}=K_{r} 를 갖거나, 파란색으로 색칠된 완전그래프 K_{s}를 가질 것이다.

마찬가지의 원리로 \left|N_{B}\right|\ge R\left(r,v\right)라 하면 N_{B}을 꼭짓점으로 갖는 완전그래프를 생각하자. 그 후 여기에 v를 하나 더 추가해서 완전그래프를 생각해보면 빨간색으로 색칠된 완전그래프 K_{r}을 가지고 있거나, 파란색으로 색칠된 완전그래프 K_{v+1}=K_{s}를 가질 것이다.

그러므로 위 관찰로부터 K_{n}의 색칠된 변에는 빨간색으로 색칠된 K_{r}을 갖거나, 파란색으로 색칠된 K_{s}를 가질 것이다. 이로부터 R\left(r,s\right)\le n이다.

그러므로

    \begin{align*} R\left(r,s\right) & \le n=R\left(u,s\right)+R\left(r,v\right)\\ & \le\binom{u+s-2}{u-1}+\binom{r+v-2}{r-1}\\ & =\binom{r+s-3}{r-2}+\binom{r+s-3}{r-1}\\ & =\binom{r+s-2}{r-1} \end{align*}

이므로 이는 처음에 (1)와 (2)가 성립하지 않는다는 사실에 모순이다.

Leave a Reply

Your email address will not be published. Required fields are marked *