Лемма Турана в общем виде звучит так.
Наибольшее число ребер у графов, имеющих v вершин и у которого нет n попарно соединённых вершин равно
ex(v,n)=(n-2)(v^2-r^2)/(2n-2)+r(r-1)/2,
где r - остаток при делении v на (n-1).
Доказательство для случая, когда n=3, можно найти здесь.
В формулировке речь идёт про неориентированные графы, но лемма применима и в некоторых задачах про ориентированные графы.
Вот, например, задача, предложенная на 36 Уральском турнире юных математиков
На конгресс приехало 100 ученых, каждый из которых сделал доклад. В конце каждый заявил, что ему понравилось ровно 75 докладов, сделанных его коллегами. Докажите, что найдутся трое, каждому из которых понравились доклады двух других.
Всего дуг (ориентированных ребер) в графе 75*100=7500. Всего ребер в полном неориентированном графе 100*99/2=4950. Значит, хотя бы 2550 ребер имеют направление в обе стороны. Но по лемме Турана, если в графе больше [100^2/4]=2500 ребер, то в нем есть три вершины, попарно соединённые рёбрами.
На Московской математической олимпиаде в 1994 была предложена следующая задача.
Каждый из 1994 депутатов парламента дал пощечину ровно одному своему коллеге. Докажите, что можно составить парламентскую комиссию из 665 человек, члены которой не выясняли отношения указанными выше способом.
В книге, изданной МЦНМО, про московские олимпиады написано несколько решений этой задачи, но нет использующего лемму Турана.
Рассмотрим граф, в котором две вершины-депутата соединены ребром в том и только в том случае, когда никто из них не дал пощечин друг другу. Рёбер в нашем графе не меньше, чем 1994*1993/2-1994=1985027 (не меньше из-за того, что пары депутатов могли дать пощёчину друг другу, и тогда две пощёчины дают одно ребро). А в графе, где нет 665 попарно соединённых вершин, ребер не меньше, чем
ex(1994,665)=(665-2)(1994^2-2^2)/(2*665-2)+2*1/2=1985023.
Аналогично решается и задача с 6-го Уральского турнира юных математиков.
22 школьника участвовали в съезде юных писателей. После съезда каждый из них прочитал произведения трех юных писателей, побывавших на съезде. Докажите, что из делегатов съезда можно составить комиссию из четырех человек так, что в комиссии никто не читал произведения остальных ее членов.
Ещё одну задачу про орграфы, связанную с леммой Турана можно найти тут.
