combinatorics- persons in group

Question

Let $$ n = \binom {k + b-2}{k-1} \text{ and }k, b\ge 2 $$ Prove that in each group of at least n persons there is k person is familiar with everybody or there are b persons two did not know each other.

Answer 1

Let $P(k,b)$ be the assertion in the problem. Suppose that $P(k-1,b)$ and $P(k,b-1)$ are true, and let $S$ be a set of

$$n=\binom{k+n-2}{k-1}=\binom{k+n-3}{k-2}+\binom{k+n-3}{k-1}$$

people. Fix $p\in S$, and let $S_0=S\setminus\{p\}$. Let $S_1$ be the set of people in $S_0$ whom $p$ knows, and let $S_2=S_0\setminus S_1$. Then

$$|S_1|\ge\binom{k+b-3}{k-2}\qquad\text{or}\qquad|S_2|\ge\binom{k+b-3}{k-1}\;.$$

If $|S_1|\ge\binom{k+b-3}{k-2}$, either there are $b$ members of $S_1$ who are mutual strangers, or there are $k-1$ members of $S_1$ who know one another, and those $k-1$ together with $p$ form a set of $k$ who know one another. If $|S_2|>\binom{k+b-3}{k-1}$, either there are $k$ members of $S_2$ who know one another, or there are $b-1$ who are mutual strangers, and together with $p$ they form a set of $b$ mutual strangers. Thus, $S$ contains either a set of $k$ mutual acquaintances or a set of $b$ mutual strangers, and $P(k,b)$ holds.

$P(2,2)$ is clearly true, and it’s also clear that for any $k$ and $b$, $P(k,b)$ holds if and only if $P(b,k)$ holds. The statement of the problem disallows $P(1,2)$ and $P(2,1)$, but there’s no good reason for this, and the statements are true, since a set of one person is rather vacuously both a set of mutual acquaintances and a set of mutual strangers. (A set fails to be either of these if and only if it contains two people who know each other and two people who don’t, and this is certainly not the case for a singleton set.) In fact, $P(n,1)$ and $P(1,n)$ are similarly true for all $n\in\Bbb Z^+$.

The result now follows by induction on $k+b$. Suppose that $m\ge 3$, and $P(k,b)$ holds for all $k,b\in\Bbb Z^+$ such that $k+b<m$. We just saw that $P(m-1,1)$ and $P(1,m-1)$ hold. By the argument given above, $P(m-b,b)$ follows from $P(m-b-1,b)$ and $P(m-b-1,b-1)$ for $2\le b\le m-2$, which hold by the induction hypothesis, so $P(k,b)$ holds for all $k,b\in\Bbb Z^+$ such that $k+b=m$.

This problem is essentially the two-color case of Ramsey’s theorem.