В этой публикации я разберу два задачи из теории графов, где одновременно фигурируют лемма Турана и числа Рамсея. Напомню, что лемма Турана в общем виде звучит так.
Наибольшее число ребер у графов, имеющих 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 вершинах покрашены в красный и синий цвета так, что нет одноцветных треугольников...
Определение. Если {а, b} – неориентированное ребро, тогда вершины а и b называются концами или концевыми вершинами ребра {а, b}. Ребро {а, b} называют также инцидентным вершинам а и b. Обратно, говорят, что вершины а и b инцидентны к ребру {а, b}. Пример 1. В неориентированном графе G1 (см. рис. ниже) вершина а инцидентна рёбрам{a, c} и {a, b}, вершина b инцидентна двум рёбрам {a, b} и{b, d}, вершина с инцидентна трём рёбрам {a, c}, {c, d} и {c, е}, вершина d инцидентна трём рёбрам {b, d}, {c, d} и {d, f}, вершина e инцидентна ребру {c, e}, вершина f инцидентна ребру {d, f}...