244
правки
Изменения
Нет описания правки
# Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
# Докажите, что если связный граф $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
# Найдите $R(3, 4)$
# Докажите, что $R(n, 3) \le (n^2+3)/2$
# Найдите $R(3, 3, 3)$
# На плоскости даны 6 точек, никакие 3 из которых не лежат на одной прямой и все попарные расстояния между которыми различны. Рассмотрим все треугольники с вершинами в этих точках. Докажите, что найдется отрезок, который в одном из этих треугольников является наибольшей стороной, а в другом - наименьшей.
# Обобщение теоремы Шура. Докажите, что для любого натурального $k$ найдется такое $n$, что в любой раскраске чисел от 1 до $n$ в $k$ цветов найдутся различные $x$ и $y$, такие что $x$, $y$ и $x+y$ раскрашены в один цвет.
# Докажите, что из 5 точек на плоскости, никакие три из которых не лежат на одной прямой, можно выбрать 4, являющихся вершинами выпуклого четырехугольника.
# Докажите, что для любого $n$ найдется $N$, такое что из любых $N$ точек, никакие 3 из которых не лежат на одной прямой, можно выбрать вершины выпуклого $n$-угольника.
# Докажите, что для любого $n$ найдется такое простое $p$, что существуют натуральные числа $x$, $y$ и $z$, что $x^n+y^n=z^n \pmod p$.
# Докажите усиление теоремы Эрдёша: $R(k, k) \ge \frac{2^{k/2}\cdot k}{e\sqrt{2}}
# Докажите, что для любого достаточно большого $s$ выполнено $R(k, k) \ge s - {s \choose k}\cdot 2^{1-{k \сhoose 2}}$
# Докажите, что в любой перестановке $n$ элементов найдется возрастающая последовательность из $\sqrt{n}$ элементов или убывающая последовательнтсть из $\sqrt{n}$ элементов.
# Теорема Ван дер Вардена. Докажите, что для любых $n$ и $k$ найдется такое $W(n, k)$, что если числа от $1$ до $W(n, k)$ покрасить в $k$ цветов, то найдется арифметическая прогрессия длины $n$, покрашенная в один цвет.
# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что найдутся четыре вершины прямоугольника со сторонами, параллельными осям координат, которые покрашены в один цвет.
# Все клетки бесконечного листа клетчатой бумаги раскрасили в $n$ цветов. Докажите, что для любых $k$ и $l$ найдутся $k$ строк и $l$ столбцов, что все $kl$ их клеток пересечения покрашены в один и тот же цвет.
# $P_k$ - путь длины $k-1$ (содержащий $k$ вершин и $k-1$ ребро). Найдите $R(P_3, P_3)$.
# Найдите $R(P_4, P_4)$
# Завершите доказательство теоремы Хватала, показав, что $R(T_m, K_n) \ge (n-1)(m-1)+1$
