Теории Рамсея — математическая задача, которая ставит математиков в тупик (хоть прогресс и есть) уже почти столетие. Это сложная область, занимающаяся вопросами порядка в кажущихся случайными структурах. Но исследователи из Калифорнийского университета в Сан-Диего разгадали давнюю проблему: r (4,t). Теория Рамсея сводится к поиску скрытой организации в графах — совокупностях точек, соединенных линиями. Теория утверждает, что если граф достаточно велик, то он будет содержать определенный вид порядка — либо группу точек, полностью соединенных линиями (клика), либо группу без связей...

В этой публикации я разберу два задачи из теории графов, где одновременно фигурируют лемма Турана и числа Рамсея. Напомню, что лемма Турана в общем виде звучит так. Наибольшее число ребер у графов, имеющих v вершин и у которого нет n попарно соединённых вершин равно ex(v,n)=(n-2)(v^2-r^2)/(2n-2)+r(r-1)/2, где r - остаток при делении v на (n-1). Числом Рамсея r(m,n) называется минимальное количество человек в компании, в которой обязательно найдётся либо m попарно знакомых, либо n попарно незнакомых. Задача 1. Ребра графа на 300 вершинах покрашены в красный и синий цвета так, что нет одноцветных треугольников...