Давайте рассмотрим разные случаи,
как могут соотноситься между собой две вершины нашего графа — x и y.
Вот давайте в первом случае будем считать, как говорят, без ограничения общности,
будем считать, что x, одна из двух вершин нашего графа — это 1, 2,
3, а y — это 4, 5, 6.
Ну, что я имею в виду, когда говорю «без ограничения общности»?
Я имею в виду, что я рассмотрел просто две вершины,
которые как троечки не пересекаются вовсе, то есть они, конечно, ребра не образуют,
и при этом у них еще пустое пересечение.
Понятно, что рассмотреть две вот такие вот троечки конкретных,
которые имеют пустое пересечение, это абсолютно то же самое,
как если мы рассмотрим какие-нибудь другие две троечки,
которые имеют пустое пересечение с точки зрения того, сколько у них общих соседей.
Ну, давайте посмотрим, сколько общих соседей у таких троек,
что вот у нас есть 1, 2, 3, и есть 4, 5, 6.
Как посчитать количество общих соседей?
Ну, сосед — это вершина, которая соединена ребром и с вот этой тройкой,
и с вот этой тройкой; то есть это такая тройка элементов,
которая отсюда вычерпывает ровно 1 элемент и отсюда тоже вычерпывает ровно 1 элемент.
Ну, понятно, у нас есть 3 возможности вычерпать отсюда,
3 возможности независимых вычерпать из второй троечки после чего,
чтобы донабрать строящуюся тройку, которая будет как раз вот этим общим соседом,
нужно еще из оставшихся n − 6 вершин, их n − 6 останется...
Ой, извините, только не вершин, элементов, конечно,
из оставшихся n − 6 элементов выбрать один.
Один отсюда произвольный тремя способами, один отсюда тремя
способами и из оставшихся n − 6 элементов, именно элементов еще один.
Итого получаем 9 * (n − 6).
Ну, такое вот замечательное количество.
Так, теперь давайте рассмотрим следующий случай.
Я думаю, понятно, как случаи дальше классифицируются.
Значит, здесь у нас был случай, когда две тройки, две вершины вовсе не пересекались.
Следующий случай без ограничений общности будет выглядеть так: это как раз две
тройки, которые образуют ребро: 1, 2, 3 и 3, 4, 5.
То есть, вот они образуют ребро в нашем графе,
потому что пересекаются ровно по одному общему элементу.
И любая другая пара, образующая ребро, конечно, устроена,
по сути, точно так же, можно просто перенумеровать, если хотите,
элементы исходного множества, и мы попадем вот в эту самую ситуацию.
Так, сколько здесь общих соседей?
Ну, знаете, вообще, считать не очень удобно.
Общие соседи могут быть разные.
Смотрите, как могут быть устроены общие соседи?
С одной стороны, можно взять вот такого общего соседа,
у которого среди его трех элементов присутствует 3,
и добавить к этой 3 какие-то, скажем,
элементы a и b, где сами эти элементы a и b находятся в множестве от 6 до n.
Тогда, конечно, образуется ребро, потому что любая такая тройка и с этой, и с этой
пересекается ровно по элементу 3, а другие два элемента мы выбрали откуда-то извне,
поэтому никакого нового пересечения ни с x, ни с y, конечно же, не возникнет.
То есть, это заведомо некий набор общих соседей по всем a и b.
Сколько таких общих соседей?
Ну, понятное дело, их C из n − 5,
извините, их C из n − 5,
потому что пока задействовано только 5 элементов, и из них взята ровно 3,
их C из n − 5 по 2 — количество способов выбрать вот эти дополнительные a и b,
а 3 вполне себе фиксируемая.
То есть их уже C из n − 5 по 2.
Ну, конечно, бывают другие общие соседи, товарищи.
Какие?
Понятно, какие: наоборот мы можем вот из этих двух элементов
взять какой-нибудь один, из вот этих двух элементов тоже
взять какой-нибудь один, значит, отсюда взяли один,
отсюда взяли один, естественно, получили с этой тройкой пересечение по одному, с этой
тройкой пересечение по одному, и еще один добавили вот отсюда, из 6 и так далее n.
Ну, сколько-то их там получится, а я вам так скажу: давайте будем считать,
что общих соседей уж точно не меньше, чем С из n − 5 по 2.
Да, есть еще какие-то, ну, я их добавлю, будет больше строк.
Если кому-то не нравится этот значок, я могу написать больше строго,
мне лично от этого ну никак не пострадать, ну,
а вы уже смотрите: больше, больше либо равно — это абсолютно не важно.
Я грубо считаю, мне этого все равно хватит.
Мы же потом будем оценивать число независимости и покажем,
что это число сильно меньше, чем вот эта вот, например, величина.
Поэтому то, что там добавляется, мне уже как бы побоку, вот.
Ну, хорошо, значит, вот их по крайней мере C из n − 5 по 2.
Ну, и последний оставшийся случай — это когда x, по сути,
является вершинкой 1, 2, 3, а y — это 2, 3, 4.
То есть эти две вершины пересекаются по двум общим элементам,
и в этом случае нам тоже хочется найти количество общих соседей.
Ну, как можно найти количество общих соседей в этой ситуации?
Значит, ну я не знаю, можно по-разному, конечно, считать.
Опять же, тут есть много разных ситуаций, в которых возникает общий сосед.
Ну можно вот, например, из этих двух элементов выбрать любой, правильно?
То есть, если мы выберем 2, а оставшиеся два элемента будем
выбирать откуда-то извне, ну, нам и хорошо.
Если мы выберем 3 и тоже оставшиеся два элемента будем выбирать откуда-то извне,
то нам тоже вполне себе комфортно.
Ну, можем, наконец, выбрать 1 отсюда,
4 отсюда и один элемент извне, но это какая-то ерунда.
Все, давайте сделаем так: давайте возьмем общего соседа,
который имеет вид i, a, b,
где i — это 2 или 3,
совершенно не важно, а числа a и b по-прежнему находятся в остатке,
то есть лежат в множестве от 5 уже до n.
Понятно, что таких способов зафиксировать Z 2,
во-первых, за счет двух возможностей для выбора числа i,
и надо умножить на все способы фиксации чисел a и b,
то есть получается C из n − 4 по 2.
Ну это вообще колоссальное число.
То есть видно, что на самом деле в зависимости от ситуации,
количество общих соседей все время только росло.
Если в этом случае оно было самое маленькое: 9 (n − 6),
то потом оно оказалось точно больше, чем C из n − 5 по 2, и,
наконец, в третьем случае оно еще больше: оно оказалось точно больше,
чем 2 умножить на C из n − 4 по 2.
Ну даже C из n − 4 по 2 больше, чем C из n − 5 по 2, это в свою очередь, конечно,
больше, ну, по крайней мере, начиная с какого-то момента, чем 9 (n − 6).
Поэтому вывод, который у нас получается — это,
что при достаточно больших n,
ну очень легко сообразить при каких, там, я думаю,
что при n больших 10 это уже верно, значит, при достаточно больших
n каппа от G точно не меньше, чем 9 (n − 6),
это уже с гарантией, что вот это самое маленькое из перечисленных чисел,
а нас как раз интересует наименьшее количество общих соседей.
Вот это вот давайте сейчас запомним, а я через некоторое время сейчас вам расскажу,
как оценивается наоборот сверху число независимости в этом графе,
и мы увидим, что это число независимости меньше, чем даже вот эта оценка
нижняя для каппа от G, и (iii) будет благополучно применен.