Show that in any group of 9 people there is always a subgroup of 3 mutual strangers or a subgroup of 4 mutual acquaintances.

Question

Show that in any group of 9 people there is always a subgroup of 3 mutual strangers or a subgroup of 4 mutual acquaintances.

I know that this is an application of Ramsey's Theorem, but I'm not sure how to tackle the proof.

Answer 1

As you noticed (and TorsionSquid pointed out) this exersice gives an upper bound for $\mathcal{R}(3,4)$. It happens to be the exact value of $\mathcal{R}(3,4)$. In order to see that, you have to demonstrate a red,blue-coloured $K_{8}$ without a red $K_{4}$ or a blue $K_{3}$.

Sketch of Solution:
The idea of the solution is to take a $K_{9}$ so that each person corresponds to a vertex, color the edge joining $A$ and $B$ red if $A$ and $B$ know each other, and blue if they do not and show that there will always be a red $K_{4}$ or a blue $K_{3}$.

Now, notice that there exists a vertex $V$ so that either (i) at least six of the edges adjacent to $V$ are red, or (ii) at least four of the edges adjacent to $V$ are blue.

In the first case donate $A$ the six-element set of their endpoints. (Does this reminds you something?) There is either a blue triangle, or red triangle on $A$ (why?) and we are done (why?).

In the second case donate $B$ the four-element set of their endpoints. If all edges on $B$ are red, then we are done. If there exists a blue edge on $B$ then this will form a blue triangle, together with $V$.