Банк задач по математике

Задача 4.1.1

?

(1)

Среди пяти человек может не найтись ни трёх попарно знакомых, ни трёх попарно незнакомых.

(2)

Среди любых шести человек найдётся либо трое попарно знакомых, либо трое попарно незнакомых.

(3)

Среди любых десяти человек найдётся либо четверо попарно знакомых, либо трое попарно незнакомых.

(4)

Среди любых девяти человек найдётся либо четверо попарно знакомых, либо трое попарно незнакомых.

(5)

Среди восьми человек может не найтись ни трёх попарно знакомых, ни четверых попарно незнакомых.

(6)

Среди любых 18 человек найдётся либо 4 попарно знакомых, либо 4 попарно незнакомых.

(7)

Среди любых 14 человек найдётся либо 5 попарно знакомых, либо 3 попарно незнакомых.

Числом Рамсея $R(m, n)$ называется минимальное из таких целых положительных чисел $x$ , что выполнено любое из следующих эквивалентных условий:

среди любых $x$ человек найдётся либо $m$ попарно знакомых, либо $n$ попарно незнакомых;
в любом графе с $x$ вершинами найдётся либо $m$ -клика, либо $n$ -антиклика;
для любой раскраски рёбер графа $K_x$ в синий и красный цвета найдётся либо синяя $m$ -клика, либо красная $n$ -клика.

Например, очевидно, что $R(1, n) = 1$ и $R(2, n) = n$ для любого $n$ . В задаче 4.1.1 доказано, что $R(3,3) = 6$ , $R(3,4) = 9$ , $R(4,4) \leqslant 18$ и $R(3,5) \leqslant 14$ . Но не очевидно, что такое число существует для любых $m, n$ .

Задача 4.1.2

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

?

(1)

Если числа $R(m-1, n)$ и $R(m, n-1)$ существуют, то число $R(m, n)$ существует и $R(m, n) \leqslant R(m-1, n) + R(m, n-1)$ .

Это утверждение обычно коротко записывают в виде « $R(m, n) \leqslant R(m-1, n) + R(m, n-1)$ ». Далее аналогичные утверждения записываются только в кратком виде.

(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$ , если числа $R(m-1, n)$ и $R(m, n-1)$ чётны.

(4)

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

Задача 4.1.3

(1)(2)

?

(1)

Если в графе с 13 вершинами нет ни треугольника, ни 5-антиклики, то степень каждой вершины равна 4.

(2)

Если в графе с 18 вершинами нет ни треугольника, ни 6-антиклики, то степень каждой вершины равна 5.

Примечание.

?

Во избежание порочного круга, при решении этой и других задач не используйте без доказательства ни равенства $R(3,6) = 18$ , ни других фактов, которые не умеете доказывать.

Задача 4.1.4

(1)(2)

?

(1)

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

(2)

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

Задача 4.1.5

?

(1)

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

(2)

Теорема Эрдёша. $R(n, n) > n2^{(n-3)/2}$ начиная с некоторого $n$ . (Более точно, теорема Эрдёша утверждает, что $R(n, n) \gtrsim n2^{n/2}/e$ . Знак $\gtrsim$ определён в п. 6.1.)

(3)

Если $\binom {r}{n} < 2^{\binom {n}{2}-1}$ , то $R(n, n) > r$ .

(4)

Если $\binom {r}{n} < s2^{\binom {n}{2}-1}$ , то $R(n, n) > r - s$ .

(5)

$R(n, n) > r - \binom {r}{n}2^{1-\binom {n}{2}}$ для любого $r$ .

Задача 4.1.6

В любом турнире с $4^n$ вершинами можно выбрать вершины $A_1, \ldots , A_n$ так, чтобы каждое ребро между ними было направлено от большего номера к меньшему.

?

Задача 4.1.7

При любой раскраске рёбер графа $K_n$ в два цвета в нём найдётся гамильтонов цикл, состоящий из двух одноцветных путей (цвета путей могут быть и одинаковы, и различны).

?

Двухцветные числа Рамсея