Question 1:
Show that in any group of 6 people there will always be a subgroup of 3 people who are pairwise acquainted or a subgroup of 3 people who are pairwise strangers.
Solution 1:
Let be a group of 6 people. Suppose that the people known to A are seated in room Y and the people NOT known to A are seated in room Z; A is not in either room. Then, there are necessarily at least 3 people in either room Y or in room Z; (a) Suppose B, C, D to be in room Y. Either these 3 people are mutual strangers (and so the given theorem is true), or, at least two of them (say, B and C) know each other. In the latter case, A, B and C form a group of 3 mutual acquaintances — and again, the theorem is true. (b) In (a), replace room Y by Z and interchange the notion of ‘”acquaintances” and “strangers”‘.
Question 2:
Show that in any group of 10 people there is always (a) a subgroup of 3 mutual strangers or a subgroup of 4 mutual acquaintances, and (b) a subgroup of 3 mutual acquaintances or a subgroup of 4 mutual strangers.
Solution 2:
(a) Let A be one of the ten people; the remaining 9 people can be assigned to two rooms: those who are known to A are in room Y and those who are not known to A are in room Z. Either room Y has at least 6 people or room Z has at least 6 people. For, (i) suppose room Y has at least 6 people. Then, by previous problem number 1, there is either a subgroup of 3 mutual acquaintances or a subgroup of 3 mutual strangers (thus, the theorem is true) in this room. In the former case, A and these 3 people constitute 4 mutual acquaintances (ii) Suppose room Z has at least 4 people. Either these 4 people know one another or at least 2 of them, say B and C, do not know each other. In the former case, we have a subgroup of 4 mutual acquaintances. In the latter case A, B and C constitute 3 mutual strangers.
(b) In the previous scenario, let people who are strangers become acquaintances, and let people who are acquaintances pretend they are strangers. The situation is symmetric.
Question 3:
Show that in any subgroup of 20 people there will always be either a subgroup of 4 mutual acquaintances or a subgroup of 4 mutual strangers.
Solution 3:
Suppose A is one of these 20 people. People known to A are in room Y and people not known to A are room Z. Either room Y has at least 10 people or room Z has at least 10 people. (i) If Y has at least 10 people, then by part B of problem number 2 here, there is either a subgroup of 3 mutual acquaintances or a subgroup of 4 mutual strangers — as asserted — in this room. In the former case, A and these mutual acquaintances will form a subgroup of 4 mutual acquaintances. (ii) Switch ‘”acquaintances” and “strangers”‘ in (i).
Question 4:
Let p and q be 2 positive integers. A positive integer r is said to have the (p,q) – Ramsey property, if in any group of r people either there is a subgroup of p people known to one another or there is a subgroup of q people not known to one another. {By Ramsey’s theorem, all sufficiently large integers r have the (p,q)-Ramsey property.} The smallest r with the (p,q)-Ramsey property is called the Ramsey number R(p,q). Show that (a) R(p,q) = R (q,p). (b) , and (c) R(p,2)=p.
Solution 4:
(a) By parts (b) of the previous three questions, we have proved part a of the proof here.
(b) This is obvious.
(c) In any group of p people, if all of them are not known to one another, there will be at least 2 people who do not know each other.
Question 5:
Prove that .
Solution 5:
Question 1 and its proof in this blog article imply that .
To prove that , it is sufficient to consider a seating arrangement of 5 people about a round table in which each person knows only the 2 people on either side. In such a situation, there is no set of 3 mutual acquaintances and no set of 3 people not known to one another.
Question 6:
Show that if m and n are integers both greater than 2, then
.
(this recursive inequality gives a non-sharp upper bound for R(m,n)).
Solution 6:
Let ,
and
. Consider a group
of r people. Let L be the set of people known to person 1 and M be the set of people NOT known to person 1. The two sets together have
people, so either L has at least p people or M has at least q people. (a) If L has
people, then, by definition, it contains a subset of
people known to one another or it contains a subset of n people unknown to one another. In the former case, the
people and person 1 constitute m people known to one another.
Thus, in their case, a group of people necessarily includes m mutual acquaintances or n mutual strangers. That is,
.
(b) By the usual symmetry argument, the same conclusion follows when M contains q people.
Question 7:
(Remark: A pretty property of Ramsey numbers related to combinatorics).
Show that if m and n are integers greater than 1, then — a non-recursive upper bound.
Solution 7:
When , or
, (i) holds with equality (see problem 4 in this blog article). The proof is by induction on
. As we have just seen, the result is true when
. Assume the result true for
. Then,
and
Now, Pascal’s identity gives:
so that
But, from the previous question and its solution, we get
PS: As Richard Feynman, used to say, you will have to “piddle” with smallish problems as particular cases of these questions in order to get a grip over theory or formal language of this introduction.
PS: Additionally, you can refer to any basic Combinatorics text like Brualdi, or Alan Tucker or even Schaum Series outline ( V K Balakrishnan).