Math Problems Vault

Problem 4.1.1

?

(1)

Among five people there may be neither three pairwise acquainted nor three pairwise unacquainted people.

(2)

Among any six people there are either three pairwise acquainted or three pairwise unacquainted people.

(3)

Among any ten people there are either four pairwise acquainted or three pairwise unacquainted people.

(4)

Among any nine people there are either four pairwise acquainted or three pairwise unacquainted people.

(5)

Among eight people there may be neither three pairwise acquainted nor four pairwise unacquainted people.

(6)

Among any 18 people there are either 4 pairwise acquainted or 4 pairwise unacquainted people.

(7)

Among any 14 people there are either 5 pairwise acquainted or 3 pairwise unacquainted people.

The Ramsey number $R(m, n)$ is the smallest positive integer $x$ such that any of the following equivalent conditions holds:

among any $x$ people there are either $m$ pairwise acquainted or $n$ pairwise unacquainted people;
every graph with $x$ vertices contains either an $m$ -clique or an $n$ -anticlique;
for every coloring of the edges of the graph $K_x$ in blue and red there is either a blue $m$ -clique or a red $n$ -clique.

For example, it is obvious that $R(1, n) = 1$ and $R(2, n) = n$ for every $n$ . In Problem 4.1.1 it is proved that $R(3,3) = 6$ , $R(3,4) = 9$ , $R(4,4) \leqslant 18$ and $R(3,5) \leqslant 14$ . But it is not obvious that such a number exists for all $m, n$ .

Problem 4.1.2

(1)(2)(3)(4)

?

(1)

If the numbers $R(m-1, n)$ and $R(m, n-1)$ exist, then the number $R(m, n)$ exists and $R(m, n) \leqslant R(m-1, n) + R(m, n-1)$ .

This statement is usually written briefly in the form `` $R(m, n) \leqslant R(m-1, n) + R(m, n-1)$ ''. In what follows, similar statements are written only in the brief form.

(2)

$R(m, n) \leqslant \binom {m+n-2}{m-1}$ .

(3)

$R(m, n) \leqslant R(m-1, n) + R(m, n-1) - 1$ if the numbers $R(m-1, n)$ and $R(m, n-1)$ are even.

(4)

$R(5,5) \leqslant 62$ .

Problem 4.1.3

(1)(2)

?

(1)

If a graph with 13 vertices contains neither a triangle nor a 5-anticlique, then the degree of each vertex equals 4.

(2)

If a graph with 18 vertices contains neither a triangle nor a 6-anticlique, then the degree of each vertex equals 5.

Remark.

?

To avoid a vicious circle, when solving this and other problems do not use without proof either the equality $R(3,6) = 18$ or any other facts that you cannot prove.

Problem 4.1.4

(1)(2)

?

(1)

$R(4,4) \geqslant 18$ ;

(2)

$R(3,5) \geqslant 14$ .

Problem 4.1.5

?

(1)

$R(n, n) > (n-1)^2$ .

(2)

Erdős’s theorem. $R(n, n) > n2^{(n-3)/2}$ for all sufficiently large $n$ . (More precisely, Erdős's theorem states that $R(n, n) \gtrsim n2^{n/2}/e$ . The symbol $\gtrsim$ is defined in Sec. 6.1.)

(3)

If $\binom {r}{n} < 2^{\binom {n}{2}-1}$ , then $R(n, n) > r$ .

(4)

If $\binom {r}{n} < s2^{\binom {n}{2}-1}$ , then $R(n, n) > r - s$ .

(5)

$R(n, n) > r - \binom {r}{n}2^{1-\binom {n}{2}}$ for every $r$ .

Problem 4.1.6

In any tournament with $4^n$ vertices one can choose vertices $A_1, \ldots , A_n$ so that every edge between them is directed from the larger index to the smaller one.

?

Problem 4.1.7

For any coloring of the edges of the graph $K_n$ in two colors, it contains a Hamiltonian cycle consisting of two monochromatic paths (the colors of the paths may be either the same or different).

?