Элементы дискретной математики в задачах

Глава 4

Основы теории Рамсея

[29/90%]

Показать

LaTeX

Показать LaTeX

Содержание

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

4.2 · Многоцветные числа Рамсея

4.3 · Числа Рамсея для гиперграфов

4.4 · Результаты рамсеевского типа

4.5 · Числа Рамсея для подграфов

4.1 · Двухцветные числа Рамсея[7/100%]

Задача 4.1.1

(1)(2)(3)(4)(5)(6)(7)

Происхождение: Изложено по оригинальному источнику

(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)(2)(3)(4)(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$ в два цвета в нём найдётся гамильтонов цикл, состоящий из двух одноцветных путей (цвета путей могут быть и одинаковы, и различны).

Происхождение: Изложено по оригинальному источнику

4.2 · Многоцветные числа Рамсея[7/86%]

Задача 4.2.1

(1)(2)(3)

Происхождение: Изложено по оригинальному источнику

(1)

На плоскости отметили 17 точек и соединили каждые 2 из них цветным отрезком: красным, жёлтым или зелёным. Тогда есть одноцветный треугольник.

(2)

Придумайте 9 точек на плоскости и раскраску в 3 цвета всех соединяющих их отрезков, для которой нет одноцветного треугольника.

(3)

То же, что в п. (2), для 16 точек.

Числом Рамсея $R(m_1, \ldots , m_k)$ называется минимальное из таких целых положительных чисел $x$ , что для любой раскраски рёбер графа $K_x$ в $k$ цветов для некоторого $i$ найдётся $m_i$ -клика $i$ -го цвета (т.е. $m_i$ вершин, попарно соединённых рёбрами цвета $i$ ).

Например, очевидно, что $R(1, m, n) = 1$ и $R(2, m, n) = R(m, n)$ для любых $m, n$ . В задаче 4.2.1 доказано, что $R(3,3,3) \leqslant 17$ , $\geqslant 10$ и $\geqslant 17$ . Но не очевидно, что такое число существует для любых $m_1, \ldots , m_k$ .

Задача 4.2.2

(1)(2)(3)

Происхождение: Изложено по оригинальному источнику

(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)

Найдите оценку на $R(m_1, m_2, \ldots , m_k)$ через полиномиальные коэффициенты.

Подробнее см. [w2] и [Ga].

Задача 4.2.3

Если рёбра графа $K_{31}$ раскрашены в синий, белый и красный цвета так, что нет ни синей 4-клики, ни белой 3-клики, ни красной 3-клики, то из каждой вершины выходит 14, 15 или 16 синих рёбер.

Происхождение: Изложено по оригинальному источнику

Задача 4.2.4

Теорема. Для любого целого $m > 0$ существует такое $M > 0$ , что для любого простого числа $p > M$ сравнение $x^m + y^m \equiv z^m \pmod{p}$ имеет решение в ненулевых вычетах по модулю $p$ . (Доказать эту теорему вы сможете после решения двух следующих задач.)

Происхождение: Изложено по оригинальному источнику

Задача 4.2.5

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

Сравнение $x^m + y^m \equiv z^m \pmod{p}$ имеет решение в ненулевых вычетах по модулю $p$ для

Происхождение: Изложено по оригинальному источнику

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

Задача 4.2.6

Теорема Шура. Для любой раскраски натурального ряда в конечное число цветов найдётся одноцветное решение уравнения $x + y = z$ .

Более точно, для любого целого $k > 0$ существует такое целое $r > 0$ , что для любой раскраски первых $r$ натуральных чисел в $k$ цветов найдётся одноцветное решение уравнения $x + y = z$ .

Происхождение: Изложено по оригинальному источнику

Задача 4.2.7

(1)(2)

Найдите нижние оценки на $R(\underbrace{n, \ldots , n}_{k})$ , аналогичные утверждениям

Происхождение: Изложено по оригинальному источнику

(1)

4.1.5(1);

(2)

4.1.5(2).

4.3 · Числа Рамсея для гиперграфов[4/100%]

Задача 4.3.1

Среди любых четырёх из 8000 студентов можно выбрать слаженную тройку (т.е. тройку, составляющую слаженную команду на олимпиаду по программированию). Докажите, что можно выбрать 5 студентов, любая тройка из которых является слаженной.

Происхождение: Изложено по оригинальному источнику

Задача 4.3.2

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

Происхождение: Изложено по оригинальному источнику

(1)

Среди любых 5 точек общего положения на плоскости найдётся выпуклый 4-угольник.

(2)

Найдётся 8 точек общего положения на плоскости, среди которых нет выпуклого 5-угольника.

(3)

Среди любых 9 точек общего положения на плоскости найдётся выпуклый 5-угольник.

(4)

Теорема Эрдёша–Секереша. Для некоторого $n$ среди любых $n$ точек общего положения на плоскости найдётся выпуклый 10-угольник. (Ср. с задачей 4.4.4.)

Числом Рамсея для гиперграфов $R_l(m_1, \ldots , m_k)$ , $m_1, \ldots , m_k \geqslant l$ , называется минимальное из таких целых положительных чисел $x$ , что для любой раскраски всех $l$ -элементных подмножеств $x$ -элементного множества в $k$ цветов найдутся $i$ и подмножество размера $m_i$ , у которого все $l$ -элементные подмножества покрашены в $i$ -й цвет. («Число Рамсея для гиперграфов» --- единый термин, определённый выше; знание термина «гиперграф» не нужно для его понимания.)

Например, очевидно, что $R_2(m_1, \ldots , m_k) = R(m_1, \ldots , m_k)$ и $R_3(3, n) = n$ . В задаче 4.3.1 требуется доказать, что $R_3(5,4) \leqslant 8\, 000$ . А при решении задачи 4.3.2(4) требуется доказать, что $R_3(10,10)$ или $R_4(5,10)$ существует.

Задача 4.3.3

(1)(2)(3)

Происхождение: Изложено по оригинальному источнику

(1)

Число $R_l(m_1, \ldots , m_k)$ существует для любых $m_1, \ldots , m_k$ . (Это не очевидно!)

(2)

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

(3)

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

Задача 4.3.4

(1)(2)(3)

Происхождение: Изложено по оригинальному источнику

(1)

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

(2)

Найдётся такое число $c > 0$ , что $R_3(n, n) \geqslant 2^{cn^2}$ .

(3)

Найдите нижние оценки на $R_l(\underbrace{n, \ldots , n}_{k})$ , аналогичные утверждениям 4.1.5(1, 2) (ср. с задачей 4.2.7).

Известно, что $R_l(\underbrace{n, \ldots , n}_{r^{2r}+1}) \geqslant (l-1)r^{r^{\cdots^{r}}}$ (степенная башня высотой $n$ ).

4.4 · Результаты рамсеевского типа[6/83%]

Задача 4.4.1

(1)(2)(3)

Верно ли, что для любой раскраски точек плоскости в два цвета найдётся

Происхождение: Изложено по оригинальному источнику

(1)

одноцветный равносторонний треугольник со стороной 1 или $\sqrt{3}$ ?

(2)

одноцветный равносторонний треугольник со стороной 1?

(3)

одноцветный треугольник со сторонами $\sqrt{2}$ , $\sqrt{6}$ , $\pi$ ?

Задача 4.4.2

При любой раскраске точек плоскости в три цвета найдутся две точки одного цвета на расстоянии 1.

Происхождение: Изложено по оригинальному источнику

Задача 4.4.3

(1)(2)

Происхождение: Изложено по оригинальному источнику

(1)

Найдётся такое $n$ , что для любой раскраски пространства $\mathbb {R}^{n}$ (определение см. в гл. 7) в 9 цветов найдётся прямоугольник с одноцветными вершинами и сторонами 1 и 2.

(2)

Верно ли, что для любого параллелограмма $P$ с неперпендикулярными сторонами найдётся такое $n$ , что для любой раскраски точек пространства $\mathbb {R}^{n}$ в 4 цвета найдётся равный $P$ параллелограмм с вершинами одного цвета?

Задача 4.4.4

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

Назовём $m$ -чашкой ( $m$ -шапкой) подмножество из $m$ точек графика выпуклой вниз (вверх) функции. Обозначим через $f(k, l)$ минимальное число $n$ , такое что среди любых $n$ точек на плоскости, имеющих разные абсциссы, и никакие три из которых не лежат на прямой, есть либо $k$ -чашка, либо $l$ -шапка. (Не очевидно, что такое число существует. Поэтому о формулах из этой задачи справедливо замечание, аналогичное сделанному в задаче 4.1.2(1).)

Происхождение: Изложено по оригинальному источнику

(1)

Среди любых $f(m, m)$ точек на плоскости найдётся выпуклый $m$ -угольник. (Ср. с задачей 4.3.2.)

(2)

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

(3)

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

(4)

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

Задача 4.4.5

(1)(2)(3)(4)(5)(6)

Происхождение: Изложено по оригинальному источнику

(1)

При любой раскраске чисел $1, \ldots , 9$ в 2 цвета найдётся одноцветная трёхчленная арифметическая прогрессия.

(2)

Аналог предыдущего пункта для чисел $1, \ldots , 8$ неверен.

(3)

Существует такое целое $W$ , что при любой раскраске чисел $1, \ldots , W$ в 2 цвета найдётся либо трёхчленная арифметическая прогрессия первого цвета, либо четырёхчленная --- второго.

(4)

Существует такое целое $W$ , что при любой раскраске чисел $1, \ldots , W$ в 3 цвета найдётся одноцветная трёхчленная арифметическая прогрессия.

(5)

То же, что в предыдущем пункте, для $r$ цветов.

(6)

Теорема ван дер Вардена. Для любых $k, r$ при любой раскраске натурального ряда в $r$ цветов найдётся одноцветная $k$ -членная арифметическая прогрессия. (Ср. с теоремой Шура 4.2.6.)

Задача 4.4.6

(1)(2)(3)

Происхождение: Изложено по оригинальному источнику

(1)

Из любых 5 точек на плоскости можно выбрать две такие непересекающиеся пары точек, что отрезок, соединяющий точки в первой паре, пересекает отрезок, соединяющий точки во второй паре.

(2)

Теорема Конвея–Гордона–Закса для линейных вложений. Для любых 6 точек общего положения в пространстве найдутся два зацепленных треугольника с вершинами в этих точках (т.е. таких, что объединение сторон первого пересекает второй двумерный треугольник в единственной точке.) (Набор точек в пространстве называется набором общего положения, если никакие 4 из них не лежат в одной плоскости.)

(3)

Теорема ван Кампена–Флореса для линейных вложений. Из любых 7 точек в четырёхмерном пространстве можно выбрать две такие непересекающиеся тройки точек, что образованные этими тройками двумерные треугольники пересекаются.

Подробнее см. [Gra].

4.5 · Числа Рамсея для подграфов[5/80%]

Задача 4.5.1

Для любых графов $G$ и $H$ существует целое положительное число $x$ , для которого при любой раскраске рёбер графа $K_x$ в два цвета найдётся либо подграф первого цвета, изоморфный $G$ , либо подграф второго цвета, изоморфный $H$ .

Наименьшее из таких чисел $x$ обозначается $R(G, H)$ .

Происхождение: Изложено по оригинальному источнику

Задача 4.5.2

$R(G, H) \geqslant (\chi (G) - 1)(c(H) - 1) + 1$ , где $\chi (G)$ --- хроматическое число графа $G$ , $c(H)$ --- число вершин в наибольшей компоненте связности.

Происхождение: Изложено по оригинальному источнику

Задача 4.5.3

(1)(2)

Обозначим через $T_m$ дерево на $m$ вершинах.

Происхождение: Изложено по оригинальному источнику

(1)

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

(2)

Если $m - 1$ делит $n - 1$ , то $R(T_m, K_{1,n}) = m + n - 1$ .

Задача 4.5.4

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

Обозначим через $nK_3$ граф из $n$ непересекающихся (по вершинам) треугольников.

Происхождение: Изложено по оригинальному источнику

(1)

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

(2)

Рёбра полного графа раскрашены в синий и красный цвета. Если в графе есть синий и красный треугольники, то среди вершин этих треугольников есть пять вершин $A, B, O, C, D$ , для которых треугольник $AOB$ синий, а треугольник $COD$ красный.

(3)

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

(4)

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

(5)

$R(nK_3, nK_3) = 5n$ для любого $n > 1$ .

Задача 4.5.5

Найдите $R(K_3, C_n)$ , где $C_n$ --- цикл с $n$ вершинами (см. п. 2.1).

Происхождение: Изложено по оригинальному источнику