Problem involving Ramsey's theorem

113 Views Asked by At

Prove that among $ 9 $ people, there are $ 3 $ who know each other or $ 4 $ who do not know each other.

I began by trying to prove $ R_9 \rightarrow R_3, R_4 $. Let $ S $ be a set of $ 9 $ points in the plane, no three of which are collinear. Let the lines joining these points be coloured either red or blue (red denotes a relation, blue denotes none). Consider any one of the points and the $8$ line segments joining this point (say $ P $) with the other points on the plane. By the pigeon-hole principle, at least $4$ of them are either red or blue. WLOG assume four red lines meet the other points at $A$, $B$, $C$ and $D$ respectively. Consider the lines joining these points. If all of them are blue, then we have a blue $K_4$. If one of them is red, then we have a red $K_3$.

Is my reasoning correct?

I'm quite new to Ramsey's theorem and I'm still a high school sophomore so please answer accordingly so I can comprehend.

1

There are 1 best solutions below

2
On

The one problem with your proof is your use of WLOG (without loss of generality) in saying "WLOG assume four red lines meet the other points...".

In this problem, the red and blue colors play different roles, so assuming that red is the dominant color on lines out of $P$ is a loss of generality. You would not be able to reproduce the same argument in the case where $P$ has four blue lines to $A$, $B$, $C$, and $D$. In that case, it's perfectly possible to color the lines between $A$, $B$, $C$, and $D$ without creating either a blue $K_4$ or a red $K_3$ using those four points and the original point alone. Even assuming that $P$ has five blue lines out of it is not enough!

To make the proof work, you need to exploit the asymmetry of the problem. Let $r$ be the number of red lines out of $P$, and let $b$ be the number of blue lines out of $P$. I suggest splitting the problem into cases as follows:

  1. $r \ge 4$.
  2. $b \ge 6$.
  3. $r=3$ and $b=5$.

One of these has to happen: we have $r+b = 8$, so either $r \ge 4$, or $r=3$ (making $b=5$) or $r \le 2$ (making $b \ge 6$).

You've handled the first case already, and the second case is not too much harder. In the third case, we seem to get stuck; however, you can show that the third case can't possibly hold for every choice of $P$: one of the points must fall into either case 1 or case 2. If you do, that will complete the proof.