Числа Рамсея. Примеры

Обозначим r(m,n) — минимальное количество человек в компании, в которой обязательно найдётся либо m попарно знакомых, либо n попарно незнакомых. Задачу о нахождении впервые, вероятно, сформулировали Эрдёш и Секереш, но называются эти значения числами Рамсея, который рассматривал похожую задачу на бесконечных графах.

Известно несколько точных значений: r(3,3)=6, r(3,4)=9, r(4,4)=18, r(3,5)=14 и ещё несколько. О том, что задача необычайно трудна, говорит хотя бы тот факт, что до сих пор неизвестно значение r(5,5). Однако, давайте поговорим о примерах, которые показывают, что r(3,3)>5, r(3,4)>8, r(4,4)>17 и r(3,5)>13.

Интересно, что все примеры можно описать с помощью остатков.

r(3,3)>5. Рассмотрим граф на 5 вершинах, пронумеруем вершины остатками при делении на 5. Соединим две вершины, если разность номеров равна 1. Тут возникли квадратичные вычеты. Графически это 5-угольник.

r(3,4)>8. Рассмотрим граф на 8 вершинах, пронумеруем вершины остатками при делении на 8. Соединим две вершины, если разность номеров равна 1 или 4. И опять возникли квадратичные вычеты! Графически это 8-угольник с проведенными главными диагоналями.

r(4,4)>17. Рассмотрим граф на 17 вершинах, пронумеруем вершины остатками при делении на 17. Соединим две вершины, если разность номеров равна 1, 2, 4, 8. И снова возникли квадратичные вычеты!

r(3,5)>13. Рассмотрим граф на 13 вершинах, пронумеруем вершины остатками при делении на 13. Соединим две вершины, если разность номеров равна или 5. Тут возникли уже кубические вычеты. Но всё равно пример строится с помощью теории чисел.

Хочется подумать, а почему дальше не строится теоретикочисловых примеров. Пусть даже не оптимальных. Да, я знаю про пример Франкла-Вильсона. Но он совсем не оптимальный.