Elementary problems in Ramsey number theory for RMO

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 \{ A, B, C, D, E, F\} 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) R(p,1)=1, 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 R(3,3)=6.

Solution 5:

Question 1 and its proof in this blog article imply that R(3,3) \leq 6.

To prove that R(3,3)>5, 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

R(m,n) \leq R(m-1,n) + R(m,n-1).

(this recursive inequality gives a non-sharp upper bound for R(m,n)).

Solution 6:

Let p \equiv R(m-1,n), q=R(m,n-1) and r \equiv p + q. Consider a group \{ 1,2, 3, \ldots, r\} 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 r-1 people, so either L has at least p people or M has at least q people. (a) If L has p \equiv R(m-1,n) people, then, by definition, it contains a subset of (m-1) people known to one another or it contains a subset of n people unknown to one another. In the former case, the (m-1) people and person 1 constitute m people known to one another.

Thus, in their case, a group of R(m-1,n) + R(m,n-1) people necessarily includes m mutual acquaintances or n mutual strangers. That is, R(m,n) \leq R(m-1,n) + R(m,n-1).

(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 R(m,n) \leq { {m+n-2} \choose {m-1}} — a non-recursive upper bound.

Solution 7:

When m=2, or n=2, (i) holds with equality (see problem 4 in this blog article). The proof is by induction on k=m+n. As we have just seen, the result is true when k=4. Assume the result true for k-1. Then,

R(m-1,n) \leq {{m+n-3} \choose {m-2}}  and R(m,n-1) \leq {{m+n-3} \choose {m-1}}

Now, Pascal’s identity gives:

{{m+n-3} \choose {m-2}} + {{m+n-3} \choose {m-1}} = {{m+n-2}} \choose {m-1} so that R(m-1,n) + R(m,n-1) \leq {{m+n-2}} \choose {m-1}

But, from the previous question and its solution, we get R(m,n) \leq R(m-1,n) + R(m, n-1)

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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.