Math Problems Vault

Problem 4.2.1

(1)(2)(3)

?

(1)

In the plane, 17 points are marked and every 2 of them are joined by a colored segment: red, yellow, or green. Then there is a monochromatic triangle.

(2)

Come up with 9 points in the plane and a coloring in 3 colors of all the segments joining them for which there is no monochromatic triangle.

(3)

The same as in part (2), for 16 points.

Problem 4.2.2

(1)(2)(3)

The Ramsey number $R(m_1, \ldots , m_k)$ is the smallest positive integer $x$ such that for any coloring of the edges of the graph $K_x$ in $k$ colors, for some $i$ there is an $m_i$ -clique of the $i$ -th color (i.e., $m_i$ vertices pairwise joined by edges of color $i$ ).

?

(1)

$R(m, n, p) \leqslant R(R(m, n), p)$ .

(2)

$R(m_1, m_2, \ldots , m_k) \leqslant R(m_1 - 1, m_2, \ldots , m_k) + R(m_1, m_2 - 1, \ldots , m_k) + \ldots + R(m_1, m_2, \ldots , m_k - 1)$ .

(3)

Find a bound on $R(m_1, m_2, \ldots , m_k)$ in terms of multinomial coefficients.

For more details, see [w2] and [Ga].

Problem 4.2.3

If the edges of the graph $K_{31}$ are colored blue, white, and red so that there is neither a blue 4-clique, nor a white 3-clique, nor a red 3-clique, then 14, 15, or 16 blue edges issue from each vertex.

?

Problem 4.2.4

Theorem. For every integer $m > 0$ there exists $M > 0$ such that for every prime $p > M$ the congruence $x^m + y^m \equiv z^m \pmod{p}$ has a solution in nonzero residues modulo $p$ . (You will be able to prove this theorem after solving the next two problems.)

?

Problem 4.2.5

The congruence $x^m + y^m \equiv z^m \pmod{p}$ has a solution in nonzero residues modulo $p$ for

?

(1)

$m = 2$ , $p = 89$ ;

(2)

$m = 3$ , $p = 89$ ;

(3)

$m = 4$ , $p = 83$ ;

(4)

$m = 3$ , $p = 97$ ;

(5)

$m = 9$ , $p = 97$ .

Problem 4.2.6

Schur’s theorem. For any coloring of the positive integers in finitely many colors there is a monochromatic solution of the equation $x + y = z$ .

More precisely, for every integer $k > 0$ there exists an integer $r > 0$ such that for any coloring of the first $r$ positive integers in $k$ colors there is a monochromatic solution of the equation $x + y = z$ .

?

Problem 4.2.7

(1)(2)

The Ramsey number $R(m_1, \ldots , m_k)$ is the smallest positive integer $x$ such that for any coloring of the edges of the graph $K_x$ in $k$ colors, for some $i$ there is an $m_i$ -clique of the $i$ -th color (i.e., $m_i$ vertices pairwise joined by edges of color $i$ ).

Find lower bounds on $R(\underbrace{n, \ldots , n}_{k})$ analogous to the statements

?

(1)

4.1.5(1);

(2)

4.1.5(2).