Tag Archives: Graph theory

Notorious bound for Ramsey number for two coloring

Lemma. If , then . Proof. 꼭짓점이 인 완전그래프 을 생각해보자. 그러면 에는 blue로 칠해진 edge가 적어도 한 개가 있거나() 모두 red인 경우거나 둘 중 하나다. 그러므로 이다. 모두 red로 칠해진 완전그래프 를 생각해보면 induced subgraph로서 blue로 된 는 없고, red로 된 또한 없다. 그러므로 이므로 이다.   Theorem. If and , then (1)  … Read More »