2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Многоцветное число Рамсея R(3,3,3).
Сообщение25.09.2016, 02:25 
Как доказать, что число Рамсея $R(3,3,3)=17$.

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

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

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

 
 
 
 Re: Многоцветное число Рамсея R(3,3,3).
Сообщение25.09.2016, 09:54 
Аватара пользователя
Выделите одну вершину из 17 и попробуйте свести задачу к $R(3,3) = 6$.
Кли́ка.

 
 
 
 Re: Многоцветное число Рамсея R(3,3,3).
Сообщение25.09.2016, 18:25 
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$?

 
 
 
 Re: Многоцветное число Рамсея R(3,3,3).
Сообщение25.09.2016, 18:55 
Аватара пользователя
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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group