Fundamentals of Ramsey Theory

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

$R(n, n) > (n-1)^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.)

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

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

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

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.

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.

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

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

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

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

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

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

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

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

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

4.1.5(1);

4.1.5(2).

Among any 5 points in general position in the plane there is a convex 4-gon.

There exist 8 points in general position in the plane among which there is no convex 5-gon.

Among any 9 points in general position in the plane there is a convex 5-gon.

Erdős–Szekeres Theorem. For some $n$, among any $n$ points in general position in the plane there is a convex 10-gon. (Cf. Problem 4.4.4.)

The number $R_l(m_1, \ldots , m_k)$ exists for any $m_1, \ldots , m_k$. (This is not obvious!)

$R_l(m_1, \ldots , m_k) \leqslant R_l(R_l(m_1, m_2), m_3, \ldots , m_k)$.

$R_l(m, n) \leqslant R_{l-1}(R_l(m-1, n), R_l(m, n-1)) + 1$.

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

There exists a number $c > 0$ such that $R_3(n, n) \geqslant 2^{cn^2}$.

Find lower bounds on $R_l(\underbrace{n, \ldots , n}_{k})$ analogous to Statements 4.1.5(1, 2) (cf. Problem 4.2.7).

a monochromatic equilateral triangle with side 1 or $\sqrt{3}$?

a monochromatic equilateral triangle with side 1?

a monochromatic triangle with sides $\sqrt{2}$, $\sqrt{6}$, $\pi$?

There exists an $n$ such that for any coloring of the space $\mathbb {R}^{n}$ (for the definition see Ch. 7) in 9 colors there is a rectangle with monochromatic vertices and sides 1 and 2.

Is it true that for any parallelogram $P$ with non-perpendicular sides there exists an $n$ such that for any coloring of the points of the space $\mathbb {R}^{n}$ in 4 colors there is a parallelogram congruent to $P$ with vertices of the same color?

Among any $f(m, m)$ points in the plane there is a convex $m$-gon. (Cf. Problem 4.3.2.)

$f(k, l) \leqslant f(k-1, l) + f(k, l-1) - 1$.

$f(k, l) \leqslant \dbinom {k+l-4}{k-2} + 1$.

$f(k, l) = \dbinom {k+l-4}{k-2} + 1$.

For any coloring of the numbers $1, \ldots , 9$ in 2 colors there is a monochromatic three-term arithmetic progression.

The analogue of the previous part for the numbers $1, \ldots , 8$ is false.

There exists an integer $W$ such that for any coloring of the numbers $1, \ldots , W$ in 2 colors there is either a three-term arithmetic progression of the first color or a four-term one of the second.

There exists an integer $W$ such that for any coloring of the numbers $1, \ldots , W$ in 3 colors there is a monochromatic three-term arithmetic progression.

The same as in the previous part, for $r$ colors.

Van der Waerden’s theorem. For any $k, r$ and any coloring of the positive integers in $r$ colors there is a monochromatic $k$-term arithmetic progression. (Cf. Schur's theorem 4.2.6.)

From any 5 points in the plane one can choose two disjoint pairs of points such that the segment joining the points of the first pair intersects the segment joining the points of the second pair.

The Conway–Gordon–Sachs theorem for linear embeddings. For any 6 points in general position in space there exist two linked triangles with vertices at these points (i.e., such that the union of the sides of the first one intersects the second two-dimensional triangle in exactly one point.) (A set of points in space is said to be in general position if no 4 of them lie in one plane.)

The van Kampen–Flores theorem for linear embeddings. From any 7 points in four-dimensional space one can choose two disjoint triples of points such that the two-dimensional triangles formed by these triples intersect.

$R(T_m, K_n) = (m-1)(n-1) + 1$.

If $m - 1$ divides $n - 1$, then $R(T_m, K_{1,n}) = m + n - 1$.

$R(nK_3, nK_3) \geqslant 5n$.

The edges of a complete graph are colored blue and red. If the graph contains a blue triangle and a red triangle, then among the vertices of these triangles there are five vertices $A, B, O, C, D$ such that the triangle $AOB$ is blue and the triangle $COD$ is red.

$R(nK_3, nK_3) \leqslant 5n + 1$.

$R(2K_3, 2K_3) = 10$.

$R(nK_3, nK_3) = 5n$ for any $n > 1$.