По мотивам Турана и Рамсея

[Alexander Evnin]

Задача из последнего конкурса https://www.mathmash.org/contestprob.php?prob=269

Имеется полный граф из 1000 вершин. Каждое его ребро покрашено в красный или синий цвет.
Известно, что в этом графе нет синих треугольников и полных подграфов из 500 вершин, все рёбра которых красные.
Каково наименьшее возможное число синих рёбер в таком графе?

Если бы не не запрещались синие треугольники, то, применив теорему Турана, мы бы получили, что минимальное
число синих рёбер 503.
Но при этом в соответствующем экстремальном графе ровно два синих треугольника (плюс паросочетание из 497 синих рёбер).

Значит, синих рёбер не меньше 504. А что дальше?

[DeBill]

Есть пример на 506: паросочетание из 496 синих ребер, плюс синий восьмиугольник с парой соседних больших диагоналей.
Но вот с оценкой - не очень ясно.
Можно попробовать что-то типа "Пусть есть КУЧА - полный красный подграф на 499 вершинах" (с меньшим, вроде , проще).
Попытка добавить к КУЧЕ вершину из вне кучи, дает: из каждой внешней в кучу идет синее ребро (уже есть 501 синее). Их -на две больше, чем вершин в куче. Значит, в какую -то вершину кучи (в А) входит два синих ребра(и даже - в две, может - ну, или в одну входит три, что однофигственно) (из В и С). Попытка заменить А на В плюс С дает: (тр-ков синих - нет): из В или С есть еще одно синее ребро в кучу (уже стало 503, ибо таких пар - две). Теперь надо два новых ребра куда то воткнуть...Дальше какие то варианты пошли - так что решения исчо нет... Но даже если получится - дурное какое то решение...

[Alexander Evnin]

Их ответ 505.

[DeBill]

Ага!
Вторая попытка...
Пример: пара синих пятиугольников, и паросочетание из 495 синих ребер.
Оценка; Индукция по $n,s$: для всех неотрицательных $s$, если на $2n-s$ вершинах нет синих тр-ков и красных полных подграфов на $n-s$ вершинах. то синих ребер не менее $n+5$
База: $n=5$, $s>0$. Известные школьные задачи: в полном двуцветном графе на 6 вершинах есть либо синий тр-к, либо красный тр-к; в полном двуцветном графе на 9 вершинах есть либо синий тр-к, либо красный полный 4-граф. Поэтому при $s>0$ утверждение истинно (не бывает таких конфигураций). (Для $s=0$: делается шаг индукции как ниже.)
$n=4, s>0$ - ШЗ, для $s=0$ делаем шаг.
$n=3$ - ШЗ
$n\geqslant 5, s\geqslant n-4$ -ШЗ
Шаг:

Если синих ребер не более $n+4$, то суммарная синяя полустепень вершин не превышает $2n+8$. Сумма степеней всех вершин равна $(2n-s)(2n-s-1)$, так что красная полустепень вершин не менее $(2n-s)(2n-s-1)-4n-8$. В среднем на вершину приходится $2n-s-2 -\frac{s+8}{2n-s} >2n-s-3$, если $n-s>4$ (это - в базе). Значит, есть вершина с красной степенью не менее $2n-2$.
Если - в точности $2n-2$, то из нее выходит ровно одно синее ребро. Удалим его (вместе с концами). Из предположения индукции ($n $ уменьшилось на 1, $s$ сохранилось) получим требуемое.
Если эта вершина - степени $2n-1$, то удалим ее , и тож будет хорошо ($n $сохранилось, $s$ увеличилось на 1).
Вааще, можно, навроде, и проще сделать: попросту посмотреть синие степени вершин: если есть степени 0 или 1 - как выше, делается шаг. А если у всех степень не мене 2, то сразу получится что надо - с учетом школьной задачи...

-- 09.09.2018, 07:54 --

Упс, есть дырочка: для $n=4,s=0$ шаг по общей методе (как с неравенством, так и попросту) не проходит: один случай (8 вершин, 8 синих ребер, все синие степени вершин равны 2, нет синих тр-ков и красных полных 4-графов) надо рассматривать отдельно. Ну да легко: Это - либо синий восьмиугольник, либо пара синих чет-ков . И тогда есть красный 4-граф -противоречие.
(Да и вообще, можно было сразу уцепиться за наличие синего нечетного цикла длины не менее 5: отсутствие таких сразу дает сине-двудольность; одна из долей - объема не мене половины - что противоречит отсутствию большого красного полного подграфа. Но что то тут у меня не срослось....)