Ramsay's theorem problem Here is a problem from my lecture notes: > How many people can we invite to a party if we want for every arbitrary group of three people to exist: a pair that are acquainted with each other and a pair that are not. **The answer is: 5 people.** I want to know how does this come out of Ramsay's theorem.

This is exactly one less than the Ramsey number $R(3,3)$. To see this, create a graph whose nodes are the people attending a party. If two people are acquainted with one another, we color the edge between their nodes blue. If they are strangers, then we color the edge between them red. Restating the question, this means that in any induced subgraph on $3$ vertices, we want at least one blue edge and at least one red edge. In other words, this is saying that such a graph on $5$ vertices exists, but a graph on $6$ vertices does not. One can construct such a graph on $5$ vertices after some trial and error, and to see that $6$ is impossible is a nice application of the pidgeonhole principle.

(It is one less than the Ramsey number since the Ramsey number is the first number for which this is impossible)