Задача Рамсея

Широко известна следующая головоломка.

Доказать, что среди любых шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. Указанную ситуацию можно описать графом G с шестью вершинами, представляющими людей; смежность двух вершин соответствует знакомству. Требуется показать, что в G найдутся либо три попарно смежные, либо три попарно несмежные вершины.

ДополнениеG графа G имеет в качестве множества вершин множество V(G), две вершины в G смежны тогда и только тогда, когда они не смежны в G. На рис. в графе G нет треугольников, а в графе G их ровно два.Самодополнительный граф- это граф, изоморфный своему дополнению . Примеры таких графов приведены на рисунке.

В полном графе Кркаждая пара его р вершин смежна. Таким образом, графKp имеет (P2) ребер и является регулярным степениp-1. ГрафK₃—треугольник. Графы !Кр—вполне несвязные(или регулярные степени 0).

В этих терминах головоломку можно сформулировать так:

Теорема.Если G-граф с шестью вершинами, то либо G, либо !G содержит, треугольник.

Доказательство. Пусть v — произвольная вершина графа G, имеющего шесть вершин. Так как вершина v с любой из остальных пяти вершин смежна или в G, или в G, то, не теряя общности, можно предположить, что вершины u1,u2,u3 смежны с v в G. Если какие-либо две из вершин u1,u2,u3,смежныв G, то вместе с v они образуют треугольник. Если никакие две из них не смежны в G, то в графе G вершины u1,u2,u3 образуют треугольник.

Обобщая теорему, естественно поставить вопрос: каково наименьшее целое число r(m,n), для которого каждый граф с r(m,n) вершинами содержит Кmили Kn

Числа r (m,n) называютсячислами Рамсея. Ясно, что r (m,n) = r(n,m). Задача, связанная с нахождением чисел Рамсея, остается нерешенной, хотя известна простая верхняя оценка, полученная Эрдёшем и Секерешем :

r(m,n)(m+n-2, m-1)

Постановка этой задачи вытекает из теоремы Рамсея. Бесконечный граф имеет бесконечное множество вершин и не содержит кратных ребер и петель. Рамсей доказал (на языке теории множеств), что каждый бесконечный граф содержит #0 попарно смежных вершин или #0 попарно несмежных вершин.

Все известные числа Рамсея приведены в табл.

2 3 4 5 6 7

2 2 3 4 5 6 7

3 3 6 9 14 18 23

4 4 9 18