## Description

Exercise 7.1

In this question, R(m, n) denotes the Ramsey number and we assume that in a group of people, any two people

are either friends or enemies.

i) Show that in a group of five people there are not necessarily either three mutual enemies or three mutual

friends. Hence, R(3, 3) > 5.

(2 Marks)

ii) Show that in a group of 10 people there are either three mutual friends or four mutual enemies, and there

are either three mutual enemies or four mutual friends. This implies R(4, 3) ≤ 10.

(2 Marks)

iii) Use ii) to show that among any group of 20 people there are either four mutual friends or four mutual

enemies. (Actually, R(4, 4) = 18, so this result is not optimal.)1

(2 Marks)

iv) Show that R(2, n) = n for n ∈ N, n ≥ 2.

(1 Mark)

v) Show that R(m, n) ≤ R(m − 1, n) + R(m, n − 1). Hence R(4, 3) ≤ 10.

(2 Marks)

vi) Prove that R(4, 3) ≤ 9 as follows: In a party of size 9, every person has at least four enemies or at least

four friends (by the generalized pigeonhole principle). Consider first the case where there is one person

with four friends and then the case where no one has four friends, i.e., everyone has five or more enemies.

(2 Marks)

vii) Show that R(4, 3) > 8 by giving a suitable example of an 8-member party. Conclude R(4, 3) = 9.

(2 Marks)

Exercise 7.2

At a given party of at least two people, any two participants are either mutual friends or not. Show that there

are two people at such a party that have the same number of friends.

(2 Marks)

Exercise 7.3

Show that if k, n ∈ N with 1 ≤ k ≤ n, then

(

n

k

)

≤

n

k

2

k−1

(2 Marks)

1From http://www.cut-the-knot.org/arithmetic/combinatorics/Ramsey44.shtml: Noga Alon and Michael Krivelevich [The

Princeton Companion to Mathematics, p. 562] present a story of the Ramsey number R(4, 4):

“In the course of an examination of friendship between children some fifty years ago, the Hungarian sociologist Sandor

Szalai observed that among any group of about twenty children he checked he could always find four children any

two of whom were friends, or else four children no two of whom were friends. Despite the temptation to try to draw

sociological conclusions, Szalai realized that this might well be a mathematical phenomenon rather than a sociological

one. Indeed, a brief discussion with the mathematicians Erd¨os, Tur´an, and S´os convinced him this was the case.”

Exercise 7.4

Show that if A and B are events and P is a probability function, then P[A ∩ B] ≥ P[A] + P[B] − 1. This is

known as Bonferroni’s inequality.

(2 Marks)

Exercise 7.5

Use induction to prove the probabilistic inclusion-exclusion principle: Let S be a sample space and A1, . . . , An ⊂

S. Then

P[A1 ∪ A2 ∪ · · · ∪ An] = ∑

1≤i≤n

P(Ai) −

∑

1≤i