Многоцветное число Рамсея R(3,3,3).

[NL0]

Как доказать, что число Рамсея $R(3,3,3)=17$.

В лоб, попытаться доказать, что среди 17 вершин найдется одноцветный треугольник одного из трех цветов никак не получается. То, что количество вершин нельзя уменьшить -- тем более. Это делается рисованием треугольников или с помощью вспомогательных лемм, теорем?

Зато доказать, что $R(3,3)=6$ получается. Стоит ли писать?

Кстати, а куда ставить ударение в слове клика? Кли'ка или Клика'?

[Xaositect]

Выделите одну вершину из 17 и попробуйте свести задачу к $R(3,3) = 6$.
Кли́ка.

[NL0]

Xaositect в сообщении #1154451 писал(а):

Выделите одну вершину из 17 и попробуйте свести задачу к $R(3,3) = 6$.
Кли́ка.

Спасибо. Давайте использовать синий, красный, зеленый цвета.

Среди 16 ребер из $a_{17}$ вершины найдутся 6 одноцветных ребер, согласно принципу Дирихле. Пусть нашлись 6 синих ребер к вершинам $a_1,a_2,...,a_6$.

Возможны две ситуации :

1) Среди вершин $a_1,a_2,...,a_6$ нет тех, что соединены синими ребрами, тогда найдется красный треугольник или зеленый, так как $R(3,3)=6$.

2) Есть хотя бы одно ребро, соед две вершины из $a_1,a_2,...,a_6$. Тогда $a_{17}$ и эти две вершины образуют синий треугольник.

То есть доказано, получается, что $R(3,3,3)\ge 17$, но как доказать ,что $R(3,3,3)\le 17$?

[Xaositect]

NL0 в сообщении #1154550 писал(а):

То есть доказано, получается, что $R(3,3,3)\ge 17$, но как доказать ,что $R(3,3,3)\le 17$?

Неравенства наоборот. Надо привести явную раскраску 16-вершинного графа, в которой треугольника нет. Там достаточно жесткая конструкция, можете попробовать найти руками. Если лень, в википедии есть: https://en.wikipedia.org/wiki/Ramsey%27 ... .29_.3D_17