2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Многоцветное число Рамсея R(3,3,3).
Сообщение25.09.2016, 02:25 


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

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

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

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

 Профиль  
                  
 
 Re: Многоцветное число Рамсея R(3,3,3).
Сообщение25.09.2016, 09:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Многоцветное число Рамсея R(3,3,3).
Сообщение25.09.2016, 18:25 


13/02/16
129
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 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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