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

Задача 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

Обозначим через $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).

?

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