| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) Нижние и верхние оценки минимального числа ребер в некоторых подграфах графа Джонсона Н. А. Дубининa, Е. А. Неустроеваa, А. М. Райгородскийabcd, Я. К. Шубинa a Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл. b Московский государственный университет имени М. В. Ломоносова c Адыгейский государственный университет, г. Майкоп d Бурятский государственный университет имени Доржи Банзарова, г. Улан-Удэ
Англоязычная версия:
Sbornik: Mathematics, 2024, Volume 215, Issue 5, Pages DOI: https://doi.org/10.4213/sm10021e 
Реферативные базы данных:
     § 1. ВведениеВ настоящей работе мы рассматриваем специальный дистанционный граф $G(n,r,s)$, вершинами которого являются точки в $n$-мерном булевом кубе, у которых ровно $r$ единиц, а ребро между такими вершинами проводится тогда и только тогда, когда скалярное произведение соответствующих векторов равно $s$. Также можно сформулировать данное определение в комбинаторных терминах, а именно, вершинами данного графа являются все возможные $r$-элементные подмножества множества $\mathcal{R}_{n}=\{1,2, \dots, n\}$, а ребро проводится между подмножествами, имеющими ровно $s$ общих элементов. Именно вторым определением мы будем пользоваться в дальнейшем. Граф $G(n,r,s)$ имеет большое значение для теории графов, комбинаторной геометрии и исследования кодов с запрещенными расстояниями. Именно с помощью этих графов П. Франкл и Р. Уилсон установили, что хроматическое число пространства растет экспоненциально с ростом размерности (см. [1]). В 1991 г. Дж. Кан и Г. Калаи использовали результаты Франкла и Уилсона для опровержения классической гипотезы Борсука о том, что всякое ограниченное множество в $\mathbb{R}^{n}$ мощности больше 1 может быть разбито на $n+1$ частей меньшего диаметра (см. [2], [3]). В работах [4]–[7] исследованы некоторые свойства графа $G(n,r,s)$ и схожих с ним по структуре графов. Напомним, что подмножество вершин графа $G$ называется независимым, если никакие две его вершины не связаны ребром. Размер наибольшего независимого подмножества в графе $G$ называется его числом независимости и обозначается $\alpha(G)$. Пусть $W$ – подмножество вершин графа $G=(V, E)$. Обозначим $\rho(W)$ число ребер в подграфе, индуцированном множеством $G$, т.е. Также положим Отметим, что проблема оценивания количества ребер в индуцированных подграфах тесно связана с теорией экспандеров и спектральной теорией графов (см. [8]–[10]). В настоящей работе мы будем рассматривать верхние и нижние асимптотические оценки величины $\rho(l)$ для графов $G(n, 3, 1)$. Напомним, что отношение $f(n) \sim g(n)$ означает $\lim_{n \to \infty} f(n)/g(n)=1$. В работах [11]–[13] был получен следующий результат. Теорема 1. Для серии графов $G(n, 3, 1)$ верны следующие утверждения: 1) если функция $l=l(n)$ такова, что $l=\omega(n), l=o(n^2)$, то $\rho(l) \sim l^2/(2n)$; 2) если функция $l=l(n)$ такова, что $l=\omega(n^2)$, то $\rho(l) \sim 9l^2/(2n)$. Мы сосредоточимся на случае $l=[cn^2]$, который не охвачен предыдущей теоремой. Сформулируем известные результаты и приведем улучшенные верхние и нижние оценки для разных значений $c$. § 2. Известные результатыСначала приведем все известные нижние оценки величины $\rho (l)$, которые могут быть использованы для случая $l \sim cn^2$. Число независимости графа $G(n, 3, 1)$ было найдено Ж. Надем в [14]. Мы будем пользоваться удобной оценкой числа независимости, очевидно следующей из результатов этой работы. Классический способ оценить число ребер в графе с ограниченным числом независимости дает следующая теорема Турана. Теорема 2. Для любого графа $G$ с числом независимости $\alpha$ и любого $l > \alpha$ выполняется неравенство Предложение 1 и теорема 2 влекут следующую простую оценку. Теорема 3. Для последовательности графов $G(n, 3, 1)$ при $l=[cn^2]$ существует функция $g(n)$ такая, что $\rho(l) \geqslant g(n)$ и Хотя в общем случае оценка, полученная при помощи теоремы Турана, неулучшаема, ее можно улучшить для класса графов $G(n, 3, 1)$. Более сильная оценка была получена в работе [11]. Теорема 4. Для последовательности графов $G(n, 3, 1)$ при $l=[cn^2]$ существует функция $g(n)$ такая, что $\rho(l) \geqslant g(n)$ и При росте $c$ результат этой теоремы практически неулучшаем (см. п. 2) теоремы 1), но при малых $c$ оценка, полученная в теореме 4, отрицательна. Результаты, превосходящие оценки из теорем 3 и 4 для малых $c$, были получены в [15]. Теорема 5. Для последовательности графов $G(n, 3, 1)$ и $c \in(1/8,1/4]$ существует функция $g(n)$ такая, что $\rho([cn^2]) \geqslant g(n)$ и Теорема 6. Для последовательности графов $G(n, 3, 1)$ и $c \in(1/4, 1]$ существует функция $g(n)$ такая, что $\rho([cn^2]) \geqslant g(n)$ и Все приведенные выше оценки величины $\rho([cn^2])$ асимптотически равны $f(c)n^3$. Поэтому сравнивать стоит сами функции $f(c)$ в тех точках, где они определены. Обозначим соответствующие функции для оценок из теорем 3–6 как $f_3$, $f_4$, $f_5$, $f_6$. Поведение оценок $f_3$, $f_4$, $f_5$, $f_6$ иллюстрирует рис. 1. Таким образом, при $c < 1/8$ лучший результат дает турановская оценка, при $c \in[1/8,1/4]$ – оценка из теоремы 5, при $c \in(1/4, c_0]$, $c_0 \approx 0.8537$ – оценка из теоремы 6, а при всех остальных $c$ – оценка из теоремы 4. В настоящей работе мы приведем оценку, улучшающую оценку из теоремы 4 при всех $c$, и оценку, улучшающую оценку из теоремы 6 при $c > 1/4$. Обратимся к верхним оценкам. Единственная известная верхняя оценка, которая применима в случае $l \sim cn^2$, следует из доказательства п. 2) теоремы 1. Таким образом, мы имеем следующую оценку. Предложение 2. Для последовательности графов $G(n, 3, 1)$ и любой константы $c>0$ существует функция $g(n)$ такая, что $\rho([cn^2]) \leqslant g(n)$ и § 3. Нижние оценки: формулировки результатов работыТеорема 7. Для последовательности графов $G(n,3,1)$ и любой положительной константы $c$ существует функция $g(n)$ такая, что $\rho([cn^2]) \geqslant g(n)$ и Сопоставим оценке из теоремы 7 функцию $f_7(c)=9c^2/2-3c/2$. Нетрудно заметить, что эта оценка всегда существенно сильнее оценки из теоремы 4 и сильнее других оценок на большем множестве значений $c$, чем оценка из теоремы 4. Для получения этого результата используется следующая лемма, которую мы докажем в § 7. Саму теорему 7 мы докажем в § 6. Лемма 1. В простом графе на $v$ вершинах с $e$ ребрами количество пар ребер, имеющих общую вершину, не превосходит Тем не менее при малых $c$ оценка из теоремы 7 все еще проигрывает оценкам из теорем 3, 5, 6. Для малых значений $c$ тоже получен новый результат. Теорема 8. Для последовательности графов $G(n, 3, 1)$ и $c \in(1/4,1]$ существует функция $g(n)$ такая, что $\rho([cn^2]) \geqslant g(n)$ и Сопоставим оценке из теоремы 8 функцию $f_{8}(c)=c^2-13/1320$. Эта оценка улучшает оценку из теоремы 6 при всех $c > 1/4$. Несмотря на то, что константа улучшена лишь немного, при получении этой оценки был усовершенствован метод, с помощью которого была получена оценка в теореме 6. Теорему 8 мы докажем в § 8. По-прежнему при $c < 1/8$ лучший результат дает турановская оценка, при $c \in[1/8,1/4]$ – оценка из теоремы 5, при $c \in(1/4,c_1]$, $c_1 \approx 0.4219$ – оценка из теоремы 8, а при всех остальных $c$ – оценка из теоремы 7. Поведение новых оценок $f_3$, $f_4$, $f_7$, $f_8$ иллюстрирует рис. 2. § 4. Верхние оценки: формулировки результатов работыТеорема 9. Рассмотрим последовательность графов $G(n, 3, 1)$. Дана константа $c > 0$, которая представлена в виде $c=p/2+q$, где $p$ – целое неотрицательное, а $q$ лежит в промежутке $[0,1/2)$. Тогда существует функция $g(n)$ такая, что $\rho([cn^2]) \leqslant g(n)$ и Заметим, что выполнено равенство
$$
\begin{equation*}
\frac{9c^2}{2}-c+2q\biggl(\frac 12-qr\biggr) =\frac{9c^2}{2}-\frac{p}{2}- q +q -2q^2 = \frac{9c^2}{2}- \frac{p}{2} -2q^2 < \frac{9c^2}{2}.
\end{equation*}
\notag
$$
Таким образом, оценка в теореме 9 при любых значениях константы $c$ будет лучше, чем оценка в предложении 2. Теорему 9 мы докажем в § 9. Также в настоящей работе мы докажем следующую теорему. Теорема 10. Рассмотрим последовательность графов $G(n, 3, 1)$. Дана константа $1/8 \geqslant c > 0$, которая представлена в виде $c=p(1-p)/2$, где $p\in(0,1/2)$. Тогда существует функция $g(n)$ такая, что $\rho([cn^2]) \leqslant g(n)$ и При всех значениях $c\in(0,1/8]$ константа при $n^3$ в теореме 10 будет меньше, чем в теореме 9. Теорему 10 мы докажем в § 10. Однако для случая $1/4> c >1/8$ теорему 10 применить нельзя, а теорема 9 дает слишком большую оценку. Поэтому для этого случая мы рассмотрели конструкцию, которая в некотором смысле похожа на конструкцию из теоремы 10. За счет этой конструкции был получен следующий результат. Теорема 11. Рассмотрим последовательность графов $G(n,3,1)$. Дана константа $1/4 > c > 0$, которая представлена в виде $c=q(1-q)$, где $q\in(0,1/2)$. Тогда существует функция $g(n)$ такая, что $\rho([cn^2]) \leqslant g(n)$ и Для сравнения верхних оценок будем смотреть только на функции $f(c)$, которые являются коэффициентами при $n^3$. Обозначим соответствующие функции для оценок из утверждения 2 и теорем 9–11 как $f_2$, $f_{9}$, $f_{10}$, $f_{11}$. Поведение верхних оценок $f_2$, $f_{9}$, $f_{10}$, $f_{11}$ иллюстрирует рис. 3. § 5. Сравнение оценокСравним новые нижние и верхние оценки между собой. Для всех оценок будем сравнивать только коэффициенты при $n^3$, которые являются функциями от $c$. Сначала рассмотрим случай $c <1/8$. Лучшая нижняя оценка дает нам функцию $f_3(c)= c^2/2$, а лучшая верхняя оценка –
$$
\begin{equation*}
f_{10}=\frac{c^2}{2(1-p)}, \quad\text{где }\ c=\frac{p(1-p)}{2}, \quad p\in\biggl(0,\frac 12\biggr).
\end{equation*}
\notag
$$
Нетрудно видеть, что оценки отличаются в $1-p$ раз, причем при $c \to 0$ выполнено $p \to 0$ и $(1-p) \to 1$. Учитывая, что $p < 1/2$, получаем, что оценки отличаются меньше, чем в два раза для любых $c < 1/8$. Теперь, наоборот, рассмотрим случай “больших” значений $c$, начиная с $c_1 \approx 0.4219$. В этом режиме лучшая нижняя оценка обеспечивает нам функцию $f_7(c)=(9c^2-3c)/2$, а лучшая верхняя оценка –
$$
\begin{equation*}
f_9(c)=\frac{9c^2}{2}-c+2q\biggl(\frac12-q\biggr), \quad\text{где }\ c=\frac{p}{2}+q, \quad 0 \leqslant q < \frac 12.
\end{equation*}
\notag
$$
Разница между данными функциями равна $c/2+2q(1/2-q)$, а также при $c \to \infty$ выполнено $f_7(c) \sim f_9(c)$. Если же смотреть на $c \in [1/8, c_1)$, то лучшие нижние оценки получаются из теорем 5 и 8, а лучшие верхние – из теорем 11 и 9. Зазор получается незначительно больше, чем в предыдущих случаях. Поведение лучших нижних и лучших верхних оценок иллюстрирует рис. 4. § 6. Доказательство теоремы 7Пусть $l(n)=l=[cn^2]$. Для каждого $n$ возьмем подмножество вершин $W_n$ графа $G(n,3,1)$ такое, что $|W_n|=l(n)$. Для каждого элемента $i$ возьмем множество вершин $K_i$ нашего подграфа, которые содержат элемент $i$: Введем обозначение $k_i=|K_i|$. Заметим, что каждая вершина входит ровно в три различных $K_i$, поэтому получаем Данные множества будут пересекаться по вершинам. Но если две вершины нашего графа соединены ребром, то они будут одновременно входить ровно в одно из $K_i$, так как имеют ровно $s$ общих элементов. Тогда мы имеем Оценим снизу количество ребер внутри множества $K_1$. Для этого построим новый граф $F$ на $n-1$ вершинах, которые будут соответствовать элементам $2, 3, \dots, n$ в изначальном графе. Элементы $i$ и $j$ будем соединять ребром в новом графе тогда и только тогда, когда вершина $\{1,i,j\}$ присутствовала в изначальном графе. Таким образом, количество ребер графа $F$ будет равняться $k_1$. Заметим, что если две вершины из $K_1$ были соединены ребром в графе $W_n$, то соответствующие им ребра в графе $F$ не имеют общей вершины. Назовем пару ребер в графе $F$ галочкой, если они имеют общую вершину. Пусть количество галочек в графе $F$ равняется $q$. Тогда выполнено равенство Таким образом, нам требуется оценить максимальное число галочек в графе $F$ с фиксированным числом ребер. Применим лемму 1 к графу $F$. Получаем, что количество галочек в графе $F$ не превосходит Тогда имеем оценку
$$
\begin{equation*}
\rho(K_1) \geqslant C_{k_1}^2-\frac{k_1(n-1)}{2} -\frac{k_1^2}{n-1}= \frac{n-3}{2(n-1)} k_1^2-\frac{n}{2} k_1.
\end{equation*}
\notag
$$
Аналогично получаются оценки для остальных множеств $K_i$, просуммируем их:
$$
\begin{equation*}
\rho (W_n)=\sum_{i=1}^{n}\rho (K_i) \geqslant \sum_{i=1}^{n} \frac{n-3}{2(n-1)} k_i^2-\sum_{i=1}^{n} \frac{n}{2} k_i.
\end{equation*}
\notag
$$
Нам известно, что Первую же сумму оценим по неравенству о средних: Получаем итоговую нижнюю оценку
$$
\begin{equation*}
\rho (W_n) \geqslant \frac{n-3}{2(n-1)} \,\frac{9l^2}{n}-\frac{3ln}{2} \sim \frac{9c^2n^3}{2}- \frac{3cn^3}{2}.
\end{equation*}
\notag
$$
Теорема 7 доказана. § 7. Доказательство леммы 17.1.Проводим доказательство индукцией по количеству вершин. База для $v=1$ очевидна. Для перехода рассмотрим граф $G$ такой, что $V(G)=v$, $E(G)=e$. Причем из всех таких графов выберем тот, в котором количество галочек максимально. Если в данном графе есть изолированная вершина, то уберем ее и применим предположение индукции. Получаем, что количество ребер не больше, чем Сравним данное число с требуемой оценкой:
$$
\begin{equation*}
\begin{gathered} \, \frac{e(v-1)}{2}+\frac{e^2}{v-1} \vee \frac{ev}{2}+\frac{e^2}{v}, \\ \frac{e^2}{v(v-1)} \vee \frac{e}{2}, \\ e \vee \frac{v(v-1)}{2}. \end{gathered}
\end{equation*}
\notag
$$
Правая часть не меньше левой, потому что ребер в графе не более $C_v^2$, поэтому в данном случае переход доказан. Пусть теперь в графе $G$ отсутствуют изолированные вершины. Тогда выберем вершину $a$ наименьшей степени, пусть она соединена с множеством вершин $B=\{b_1, b_2, \dots, b_s\}$. Тогда степень любой вершины в графе не меньше $s$. Докажем, что все вершины множества $B$ имеют максимальную степень, т.е. Пусть это не так. Тогда найдутся несмежные вершины $f$ и $b_i$. Отметим, что вершина $f$ также может принадлежать множеству $B$. Далее уберем ребро между вершинами $a$ и $b_i$, а добавим – между $f$ и $b_i$. Нетрудно видеть, что убранное ребро участвовало ровно в $d(b_i)-1+s-1$ галочках. А после добавления нового ребра появилось еще $d(f)+d(b_i)-1$ галочек. Таким образом, количество галочек увеличится на $d(f)- (s-1) \geqslant s-(s-1) > 0,$ что приводит к противоречию с изначальной максимальностью. Теперь будем выкидывать вершину $b_1$ со всеми ее ребрами. Подсчитаем число галочек, в которых участвуют эти ребра. Количество галочек, выходящих из вершины $b_1$, равняется $C_{v-1}^2$. Также заметим, что любое из остальных ребер участвует ровно в двух галочках с данными ребрами. Поэтому общее число галочек с ребрами из $b_1$ равняется $C_{v-1}^2+2(e-(v-1))$. Далее применяем предположение индукции для графа без вершины $b_1$. Получаем, что общее число галочек не превосходит
$$
\begin{equation*}
\begin{aligned} \, &C_{v-1}^2+2(e-(v-1))+\frac{(e-(v-1))(v-1)}{2}+\frac{(e-(v-1))^2}{v-1} \\ &\qquad =2(e-(v-1))+\frac{(e-1)(v-1)}{2} +\frac{(e-(v-1))^2}{v-1} \\ &\qquad =\frac{(e-1)(v-1)}{2}+\frac{e^2-(v-1)^2}{v-1} \\ &\qquad\leqslant \frac{e(v-1)}{2}+ \frac{e^2}{v-1}= \frac{ev}{2}+\frac{e^2}{v-1}-\frac{e}{2}. \end{aligned}
\end{equation*}
\notag
$$
Заметим, что в первой части перехода мы уже показали, что всегда выполнено неравенство Таким образом, данная оценка не превосходит оценку из утверждения индукции, т.е. в этом случае переход также доказан.Лемма доказана. 7.2.Лемму 1 можно доказать и другим способом, воспользовавшись тем, что графы с фиксированным числом вершин и ребер, имеющие максимального количество галочек, имеют специальный вид. Определение. Квазиполным графом с $v$ вершинами и $e$ ребрами называется граф, в котором вершины $1, 2, \dots, a$ образуют полный подграф, вершина $a+1$ соединена с вершинами $1, \dots, b$, а остальные вершины изолированные, где $a$ и $b$ единственным образом определяются из соотношения Пусть граф $G$ на $v$ вершинах с $e$ ребрами таков, что в нем не меньше галочек, чем в любом другом графе с тем же числом вершин и ребер. В работе [16] было доказано, что такой граф $G$ является или квазиполным, или дополнением к квазиполному. Таким образом, достаточно доказать оценку для этих двух типов графов. Пусть $G$ – квазиполный граф, $e=a(a-1)/2+b$, $0 \leqslant b < a$, в нем вершины $1, \dots, a$ образуют полный подграф, а вершина $a+1$ соединена с вершинами $1, \dots, b$. Число галочек, оба ребра в которых имеют концы в множестве $\{1, \dots, a\}$, равно $a(a- 1)(a-2)/2$. Число галочек, в которых ровно одно ребро инцидентно вершине $a+1$, равно $b(a- 1)$. Наконец, число галочек, в которых оба ребра инцидентны вершине $a+1$, равно $b(b- 1)/2$. Таким образом, суммарное количество галочек в графе $G$ равняется
$$
\begin{equation*}
\begin{aligned} \, &\frac{a(a-1)(a-2)}{2}+b(a-1)+\frac{b(b-1)}{2} \\ &\qquad=\frac{a(a-1)^2}{2}-\frac{a(a-1)}{2}+b(a- 1)+\frac{b(b-1)}{2}. \end{aligned}
\end{equation*}
\notag
$$
Поскольку $b < a$, значение последнего выражения не превосходит
$$
\begin{equation*}
\begin{aligned} \, \frac{a(a-1)^2}{2}+b(a-1) &=(a-1)\biggl(\frac{a(a-1)}{2}+b\biggr) \\ &\leqslant \biggl(\frac{a(a-1)}{2}+b\biggr) \sqrt{a(a-1)+2b}=e\sqrt{2e} \leqslant \frac{ev}{2}+\frac{e^2}{v}, \end{aligned}
\end{equation*}
\notag
$$
что и требовалось доказать. Последний переход выполняется в силу неравенства о средних. Пусть теперь $G$ – дополнение к квазиполному графу. Так как $\overline{G}$ – квазиполный граф, он имеет описанный ранее вид, параметры $a$ и $b$ определяются единственным образом из $v(v-1)/2-e=a(a-1)/2+b$, $0 \leqslant b < a$. Таким образом, граф $G$ имеет следующий вид: в нем вершины с номерами, большими $a+1$, соединены со всеми остальными, вершина с номером $a+1$ соединена со всеми, кроме вершин $1, 2, \dots, b$, а других ребер нет. Вершины из множества $\{1, \dots, b\}$ имеют степень $v-a-1$, вершины из множества $\{b+1, \dots, a\}$ – степень $v-a$, вершина с номером $a+1$ имеет степень $v-b-1$, а все остальные вершины – степень $v-1$. Положим $c=a-b$, $d=v-a-1$. Тогда число вершин равняется $b+c+d+ 1$. Подсчитав суммарную степень вершин, получим Заметим, что из каждой вершины с номером в $\{1, \dots, b\}$ исходит $d(d-1)/2$ галочек, из каждой вершины с номером в множестве $\{b+1, \dots, a\}$ исходит $(d+1)d/2$ галочек, из вершины с номером $a+1$ исходит $(c+d)(c+d-1)/2$ галочек, а из каждой из оставшихся – по $(b+c+d)(b+c+d-1)/2$ галочек. Таким образом, суммарное число галочек равняется
$$
\begin{equation*}
\begin{aligned} \, g &=\frac{1}{2}\bigl(bd(d-1)+cd(d+1)+(c+d)(c+d-1) \\ &\qquad+d(b+c+d)(b+c+d-1)\bigr). \end{aligned}
\end{equation*}
\notag
$$
Необходимо доказать неравенство $g \leqslant ev/2+e^2/v$. После домножения на $4v$ неравенство примет вид $4gv \leqslant 2e(v^2+2e)$. После выражения всех переменных через $b$, $c$, $d$ неравенство примет следующий вид:
$$
\begin{equation*}
\begin{aligned} \, &2(b+c+d+1)\bigl(bd(d-1)+cd(d+1)+(c+d)(c+d-1) \\ &\qquad\qquad+d(b+c+d)(b+c+d-1)\bigr) \\ &\qquad \leqslant \bigl(bd+c(d+1)+(c+d)+d(b+c+d)\bigr) \\ &\qquad\qquad\times\bigl((b+c+d+1)^2+bd+c(d+1)+(c+d)+d(b+c+ d)\bigr). \end{aligned}
\end{equation*}
\notag
$$
После раскрытия скобок и приведения подобных слагаемых останется
$$
\begin{equation*}
\begin{aligned} \, 0 &\leqslant 2b^2c+b^2d^2+7b^2d+2bc^2+2bcd^2+18bcd+6bc+10bd^2+10bd \\ &\qquad + c^2d^2+9c^2d+8c^2+8cd^2+12cd+4c+3d^3+6d^2+3d, \end{aligned}
\end{equation*}
\notag
$$
что верно в силу положительности $b, c, d$. Таким образом, неравенство доказано для обоих случаев. Лемма 1 доказана. § 8. Доказательство теоремы 88.1.Положим $l=[cn^2]$ и рассмотрим произвольное подмножество $L$ вершин графа $G(n, 3, 1)$ такой мощности. Выделим в этом подмножестве максимальное независимое множество $B_1$, его мощность обозначим $\beta_1$. Среди оставшихся вершин графа рассмотрим вершины, каждая из которых соединена ровно с одной вершиной из множества $B_1$. Эти вершины образуют множество $K_1$ мощности $k_1$. Для каждой вершины $a_i \in B_1$, $1\leqslant i \leqslant \beta_1$, рассмотрим $A_i \subset K_1$ – множество всех вершин, лежащих в $K_1$ и соединенных с $a_i$. Множество $A_i$ является кликой, так как если бы там нашлись не инцидентные $b$, $c$, то множество $\{b, c\} \,{\cup}\, B_1 \setminus \{a_i\}$ было бы независимым множеством, мощность которого больше, чем мощность множества $B_1$, чего не может быть. Для различных $i$, $j$ множества $A_i$ и $A_j$ не пересекаются, иначе в множестве $K_1$ нашлась бы вершина, инцидентная двум вершинам из $B_1$. Таким образом, в $K_1$ найдется клика мощности хотя бы $k_1/\beta_1$. Отметим, что каждая вершина из $L\setminus (B_1 \cup K_1)$ соединена хотя бы с двумя вершинами $B_1$. Теперь мы поступим одним из двух способов. Во-первых, мы можем убрать из графа множество $B_1$ со всеми инцидентными ему ребрами. Тогда мы уберем $v_1=\beta_1$ вершин и $e_1=k_1+2(l- \beta_1-k_1)=2l-2\beta_1-k_1$ ребер. Во-вторых, мы можем убрать и множество $B_1$, и клику мощности ровно $[k_1/\beta_1]$ из $K_1$. Тогда получится, что число вершин уменьшится на $v_1=\beta_1 +[{k_1}/{\beta_1}]$, а число ребер – на
$$
\begin{equation*}
\begin{aligned} \, e_1 &=k_1+2(l-\beta_1-k_1)+ \frac{1}{2}\biggl[\frac{k_1}{\beta_1}\biggr] \biggl(\biggl[\frac{k_1}{\beta_1}\biggr]-1\biggr) \\ &=2l-2\beta_1-k_1+ \frac{1}{2}\biggl[\frac{k_1}{\beta_1}\biggr] \biggl(\biggl[\frac{k_1}{\beta_1}\biggr]-1\biggr). \end{aligned}
\end{equation*}
\notag
$$
Повторим это действие еще $T\,{-}\,1$ раз, где $T$ будет определено позднее. Таким образом, на $j$-м шаге мы будем выделять максимальное независимое множество $B_j$ мощности $\beta_j$ и $K_j$ – множество вершин, каждая из которых инцидентна ровно одной вершине из $B_j$, $|K_j|=k_j$. В множестве $K_j$ найдется клика мощности хотя бы $k_j/\beta_j$. Перед $j$-м шагом в графе будет оставаться $l-\sum_{i=1}^{j-1}v_i$ вершин. На $j$-м шаге, аналогично первому шагу, мы будем поступать одним из двух способов. Первый способ – убрать $B_j$, тем самым убирая $v_j=\beta_j$ вершин и $e_j=2\bigl(l-\sum_{i=1}^{j}v_j\bigr)-k_j$ ребер. Второй способ – убрать и множество $B_j$, и клику размера $[{k_j}/{\beta_j}]$. Тогда мы уберем из графа вершины в количестве $v_j=\beta_j+[k_j/\beta_j]$ и ребра в количестве
$$
\begin{equation*}
\begin{aligned} \, e_j &=2\biggl(l-\sum_{i=1}^{j-1}v_i-\beta_j-k_j\biggr)+k_j+ \frac{1}{2}\biggl[\frac{k_j}{\beta_j}\biggr]\biggl(\biggl[\frac{k_j}{\beta_j}\biggr]-1\biggr) \\ &=2\biggl(l-\sum_{i=1}^{j}v_i\biggr)-k_j+\frac{k_j^2}{2\beta_j^2}+ O\biggl(\frac{k_j}{\beta_j}\biggr), \end{aligned}
\end{equation*}
\notag
$$
причем константа $C$, с помощью которой функция $O({k_j}/{\beta_j})$ оценивается как не превосходящая $C({k_j}/{\beta_j})$, не зависит от $j$. Чтобы оценить $T$ – возможное количество шагов, воспользуемся следующей леммой, являющейся переформулировкой леммы 1 из [15]. Лемма 2. Для любого подграфа $H$ графа $G(n, 3, 1)$, его максимального независимого подмножества $B, |B|=\beta$, и $K$ – множества вершин $H$, соединенных ровно с одной вершиной $B, |K|=k$, выполняется неравенство $\beta \leqslant n$ и хотя бы одно из неравенств $\beta+ 2k/\beta \leqslant n$ и $k \leqslant 6\beta$. Таким образом, на каждом шаге из графа удаляется не более $n+6$ вершин и можно положить $T= [l/(n+6)]$. Также заметим, что в силу леммы $k_j/\beta_j=O(n)$. Просуммируем количество извлеченных ребер по $T$ шагам и обозначим эту величину $S$:
$$
\begin{equation*}
\begin{aligned} \, S &=\sum_{i=1}^T e_i=\sum_{i=1}^T \biggl(2\biggl(l-\sum_{j=1}^{i}v_j\biggr)+e_i-2\biggl(l- \sum_{j=1}^{i}v_j\biggr)\biggr) \\ &=2lT-2\sum_{i=1}^{T} \sum_{j=1}^{i}v_j+\sum_{i=1}^{T} \biggl(e_i-2\biggl(l-\sum_{j= 1}^{i}v_j\biggr)\biggr) \\ &=2lT-\sum_{i=1}^T\biggl(2(T-i+1)v_i-e_i+2\biggl(l-\sum_{j=1}^{i}v_j\biggr)\biggr). \end{aligned}
\end{equation*}
\notag
$$
На каждом шаге мы могли поступить одним из двух описанных выше способов: или убрать максимальное независимое множество, или убрать и максимальное независимое множество, и клику. Будем каждый раз выбирать такой способ, чтобы значение слагаемого $2(T-i+1)v_i-e_i+2\bigl(l- \sum_{j=1}^{i}v_j\bigr)$ было как можно меньше. Тогда суммарное число извлеченных ребер будет как можно больше. Будет выполняться следующая оценка:
$$
\begin{equation*}
\begin{aligned} \, S &\geqslant 2lT-\sum_{i=1}^{T}\min\biggl\{2(T-i+1)\beta_i+k_i, 2(T-i+ 1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i-\frac{k_i^2}{2\beta_i^2}\biggr\} \\ &\qquad+O(Tn). \end{aligned}
\end{equation*}
\notag
$$
Следующая серия лемм поможет оценить значение $S$ более точно. Леммы 3 и 4 являются переформулировками лемм 2 и 3 из работы [15], а леммы 5 и 6 их уточняют. В совокупности леммы 2–5 позволяют оценить при всевозможных $T$ значение выражения
$$
\begin{equation*}
\min\biggl\{2(T-i+1)\beta_i+k_i, 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i- \frac{k_i^2}{2\beta_i^2}\biggr\},
\end{equation*}
\notag
$$
причем оценки из лемм 4–6 улучшают результат леммы 3. Поскольку рассуждения выше проводились для произвольного подграфа мощности $l$ графа $G(n, 3, 1)$, применить эти леммы можно сразу для получения оценки величины $\rho(l)$. Напомним, что мы рассматриваем число шагов $T=[l/(n+6)]$ для $l=[cn^2]$, $c \in(1/4,1]$, поэтому шаги с номерами $T$, $T-n/22+1$, $T-n/20+1$, $T-n/4+1$ существуют при достаточно больших $n$. Теперь можно доказать заявленную оценку
$$
\begin{equation*}
\begin{aligned} \, \rho(l) &\geqslant 2lT-\sum_{i=1}^{T-n/4+1}2(T-i)n-\sum_{i=T-n/4+2}^{T- n/20+1} \frac{(2(T-i+1)+n/2)^2}{2} \\ &\qquad-\sum_{i=T-n/20+2}^{T-n/22+1}6(T-i+1)n-48(T-i+1)^2 \\ &\qquad - \sum_{i=T-n/22+2}^{T} \frac{n^2+16n(T-i+1)+4(T-i+1)^2}{10}+O(nT). \end{aligned}
\end{equation*}
\notag
$$
Вычислим по отдельности значение каждой из четырех сумм. Для шагов с $1$ по $T- n/4+1$ значение выражения будет следующим:
$$
\begin{equation*}
\begin{aligned} \, \sum_{i=1}^{T-n/4+1}2(T-i)n &=2n\sum_{j=n/4-1}^{T-1}j= 2n\biggl(\frac{T^2}{2}- \frac{n^2}{32}\biggr)+O(nT) \\ &=nT^2-\frac{n^3}{16}+O(nT). \end{aligned}
\end{equation*}
\notag
$$
Для шагов с номерами от $T-n/4+2$ до $T-n/20+1$ сумма примет следующий вид:
$$
\begin{equation*}
\begin{aligned} \, &\sum_{i=T-n/4+2}^{T-n/20+1} \frac{(2(T-i+1)+n/2)^2}{2} \\ &\qquad= \sum_{j=n/20}^{n/4-1} \frac{(2j+n/2)^2}{2}=\sum_{j= n/20}^{n/4-1}\biggl(2j^2+nj+\frac{n^2}{8}\biggr) \\ &\qquad =\frac{2}{3}\biggl(\frac{n^3}{64}-\frac{n^3}{8000}\biggr)+ \frac{n}{2}\biggl(\frac{n^2}{16}-\frac{n^2}{400}\biggr)+\frac{n^2}{8}\biggl(\frac{n}{4}- \frac{n}{20}\biggr)+O(n^2) \\ &\qquad =n^3 \biggl(\frac{31}{3000}+\frac{3}{100}+\frac{1}{40}\biggr)+O(n^2)). \end{aligned}
\end{equation*}
\notag
$$
Теперь оценим сумму для шагов с $T-n/20+2$ по $T-n/22+1$:
$$
\begin{equation*}
\begin{aligned} \, &\sum_{i=T-n/20+2}^{T-n/22+1}6(T-i+1)n-48(T-i+ 1)^2=\sum_{j=n/22}^{n/20-1}(6nj-48j^2) \\ &\qquad =3n\biggl(\frac{n^2}{400}-\frac{n^2}{484}\biggr)-\frac{48}{3}\biggl(\frac{n^3}{20^3}- \frac{n^3}{22^3}\biggr)+O(n^2). \end{aligned}
\end{equation*}
\notag
$$
Осталось оценить сумму для шагов с номерами с $T-n/22+2$ по $T$:
$$
\begin{equation*}
\begin{aligned} \, &\sum_{i=T-n/22+2}^{T}\frac{n^2+16n(T-i+1)+4(T-i+1)^2}{10} =\sum_{j=1}^{n/22-1}\frac{n^2+16nj+4j^2}{10} \\ &\qquad =\frac{n^3}{220}+\frac{4n^3}{5\cdot 22^2}+\frac{4n^3}{30\cdot 22^3}+O(n^2). \end{aligned}
\end{equation*}
\notag
$$
Вернемся к оценке $\rho(l)$, имея в виду, что $T=[l/(n+6)]$:
$$
\begin{equation*}
\begin{aligned} \, \rho(l) &\geqslant 2lT-nT^2-n^3\biggl(-\frac{1}{16}\biggr)-n^3\biggl(\frac{31}{3000} +\frac{3}{100}+\frac{1}{40}\biggr) \\ &\qquad - n^3\biggl(\frac{3}{400}-\frac{3}{484}-\frac{48}{3\cdot8000}+ \frac{48}{3\cdot22^3}\biggr) \\ &\qquad- n^3\biggl(\frac{1}{220}+\frac{4}{5\cdot 22^2}+\frac{4}{30\cdot 22^3}\biggr)+O(n^2) \\ &=\frac{l^2}{n}-\frac{13n^3}{1320}+O(n^2) \sim n^3\biggl(c^2-\frac{13}{1320}\biggr). \end{aligned}
\end{equation*}
\notag
$$
Таким образом, мы доказали заявленную оценку по модулю лемм, доказательство которых будет приведено ниже. 8.2. Доказательство леммы 5Во-первых, исследуем, когда какое выражение меньше:
$$
\begin{equation*}
\begin{aligned} \, &2(T-i+1)\beta_i+k_i \leqslant 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i- \frac{k_i^2}{2\beta_i^2} \\ &\quad\Longleftrightarrow \quad \frac{k_i^2}{2\beta_i^2} \leqslant 2(T-i+1)\frac{k_i}{\beta_i} \quad\Longleftrightarrow \quad \frac{k_i}{\beta_i} \leqslant 4(T-i+1). \end{aligned}
\end{equation*}
\notag
$$
Теперь оценим значение выражения $2(T-i+1)\beta_i+k_i$ при условии $k_i/\beta_i \leqslant 4(T-i+1)$, а затем оценим величину $2(T-i+1)(\beta_i+k_i/\beta_i)+k_i-k_i^2/(2\beta_i^2)$ при $k_i/\beta_i > 4(T-i+1)$. Нужно доказать, что обе эти оценки не превосходят при любых допустимых значениях $k_i, \beta_i$.В силу леммы 2 выполнено или $\beta_i+2k_i/\beta_i \leqslant n$, или $k_i \leqslant 6\beta_i$. В случае $k_i/\beta_i \leqslant 6$ выполняется что в свою очередь не больше так как
$$
\begin{equation*}
48(T-i+1)^2 \leqslant 4(T-i+1) \quad\Longleftrightarrow \quad T-i+1 \leqslant \frac{n}{12}.
\end{equation*}
\notag
$$
Аналогично, выполняется
$$
\begin{equation*}
\begin{aligned} \, 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i-\frac{k_i^2}{2\beta_i^2} &\leqslant 2(T-i+ 1)n+O(n) \\ &\leqslant 6(T-i+1)n-48(T-i+1)^2+O(n). \end{aligned}
\end{equation*}
\notag
$$
Существенно более интересен случай $\beta_i+2k_i/\beta_i \leqslant n$. Во-первых, заметим, что можно рассматривать только такие $\beta_i$ и $k_i$, для которых $\beta_i+ 2k_i/\beta_i=n$, поскольку если какое-то значение выражения
$$
\begin{equation*}
\min\biggl\{2(T-i+1)\beta_i+k_i, 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i- \frac{k_i^2}{2\beta_i^2}\biggr\}
\end{equation*}
\notag
$$
достигается при $k_i=k$, $\beta_i=\beta$ таких, что $\beta+2k/\beta < n$, то не меньшее значение этого выражения достигается при $\beta_i'=n-2k/\beta$, $k_i'= k\beta_i'/\beta$, но теперь уже $\beta_i'+2k_i'/\beta_i'=n$. Итак,
$$
\begin{equation*}
\begin{aligned} \, 2(T-i+1)\beta_i+k_i &=2(T-i+1)\biggl(n-\frac{2k_i}{\beta_i}\biggr)+ \frac{k_i}{\beta_i}\biggl(n-\frac{2k_i}{\beta_i}\biggr) \\ &= -\frac{2k_i^2}{\beta_i^2}+\frac{k_i}{\beta_i}(n-4(T-i+1))+2n(T-i+1). \end{aligned}
\end{equation*}
\notag
$$
Максимум этой квадратичной по $k_i/\beta_i$ функции достигается при и значение, при котором достигается максимум, не лежит в области определения, так как
$$
\begin{equation*}
\frac{n -4(T-i+1)}{4} \leqslant 4(T-i+1) \quad\Longleftrightarrow\quad i \leqslant T-\frac{n}{20}+1 ,
\end{equation*}
\notag
$$
что противоречит условию леммы. Значит, максимум выражения достигается на границе области определения, а именно при $k_i/\beta_i=4(T-i+1)$, и в точности равен $6(T-i+1)n-48(T-i+1)^2$, что и требовалось доказать. Теперь оценим сверху $2(T-i+1)(\beta_i+k_i/\beta_i)+k_i-k_i^2/(2\beta_i^2)$. Верны следующие равенства:
$$
\begin{equation*}
\begin{aligned} \, &2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i-\frac{k_i^2}{2\beta_i^2} \\ &\qquad =2(T-i+1)\biggl(n-\frac{k_i}{\beta_i}\biggr)+\frac{k_i}{\beta_i} \biggl(n- \frac{2k_i}{\beta_i}\biggr)-\frac{k_i^2}{2\beta_i^2} \\ &\qquad =-\frac{5k_i^2}{2\beta_i^2}+\frac{k_i}{\beta_i}(n-2(T-i+1))+2(T-i+1)n. \end{aligned}
\end{equation*}
\notag
$$
Максимум этой квадратичной по ${k_i}/{\beta_i}$ функции достигается при и значение, при котором достигается максимум, не лежит в области определения, поскольку
$$
\begin{equation*}
\frac{n-2(T-i+1)}{5} > 4(T-i+1) \quad\Longleftrightarrow\quad i > T-\frac{n}{22}+1.
\end{equation*}
\notag
$$
Значит, на самом деле максимум этой функции достигается тоже при $k_i/\beta_i= 4(T-i+1)$ и тоже в точности равен $6(T-i+1)n-48(T-i+1)^2$, что завершает доказательство леммы 5. 8.3. Доказательство леммы 6Как и при доказательстве леммы 5, оценим сверху значение выражения $2(T-i+1)\beta_i+ k_i$ при условии ${k_i}/{\beta_i} \leqslant 4(T-i+1)$ и значение выражения $2(T-i+ 1)(\beta_i+{k_i}/{\beta_i})+k_i-{k_i^2}/(2\beta_i^2)$ при условии ${k_i}/{\beta_i} > 4(T-i+1)$, а также будем считать, что или ${k_i}/{\beta_i} \leqslant n$, или $\beta_i+2k_i/{\beta_i}=n$. В первом случае выполняется
$$
\begin{equation*}
\begin{aligned} \, &\min\biggl\{2(T-i+1)\beta_i+k_i, 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i- \frac{k_i^2}{2\beta_i^2}\biggr\} \\ &\qquad \leqslant 2(T-i+1)n+O(n), \end{aligned}
\end{equation*}
\notag
$$
что не превосходит $(n^2+ 16n(T-i+1)+4(T-i+1)^2)/10+O(n)$, так как
$$
\begin{equation*}
\begin{aligned} \, & 2(T-i+1)n \leqslant \frac{n^2+16n(T-i+1)+4(T-i+1)^2}{10} \\ &\quad\Longleftrightarrow\quad n^2+4(T-i+1)^2 \geqslant 4n(T-i+1). \end{aligned}
\end{equation*}
\notag
$$
Во втором случае при ${k_i}/{\beta_i} \leqslant 4(T-i+1)$ аналогично лемме 4 верна оценка что в свою очередь не больше требуемого, поскольку
$$
\begin{equation*}
\begin{aligned} \, & 6(T-i+1)n-48(T-i+1)^2 \leqslant \frac{n^2+16n(T-i+1)+4(T-i+1)^2}{10} \\ &\quad\Longleftrightarrow\quad n^2+484(T-i+1)^2 \geqslant 44(T-i+1)n. \end{aligned}
\end{equation*}
\notag
$$
При ${k_i}/{\beta_i} > 4(T-i+1)$ максимум выражения
$$
\begin{equation*}
\begin{aligned} \, &2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i-\frac{k_i^2}{2\beta_i^2} \\ &\qquad=-\frac{5k_i^2}{2\beta_i^2}+\frac{k_i}{\beta_i}(n-2(T-i+1))+2(T-i+1)n \end{aligned}
\end{equation*}
\notag
$$
достигается при ${k_i}/{\beta_i}=(n-2(T-i+1))/5$, и значение, при котором достигается максимум, теперь уже лежит в области определения и равняется в точности Таким образом, лемма 6 доказана. § 9. Доказательство теоремы 9Для всех $n$, начиная с некоторого, будем строить подмножество вершин $W_n$ графа $G(n,3,1)$ такое, что $|W_n| \geqslant cn^2$ и
$$
\begin{equation*}
\rho(W_n) \leqslant \frac{9c^2n^3}{2}-cn^3+ 2q\biggl(\frac12-q\biggr)n^3+o(n^3).
\end{equation*}
\notag
$$
Пусть $k$ – наибольшее натуральное число такое, что $2k \leqslant n$. Тогда выполнено $n/2 \geqslant k \geqslant (n-1)/2$. Также будем использовать, что $k \sim n/2$. Пусть $A$ – множество элементов $\{1, 2, \dots, k\}$, а $B$ – множество элементов $\{k+ 1, k+2, \dots, 2k\}$. В качестве вершин для $W_n$ будем брать только те, у которых два элемента принадлежат множеству $A$, а третий элемент – множеству $B$, и наоборот. Заметим, что всего таких вершин существует Такая величина, начиная с некоторого $n$, будет больше, чем $cn^2$.Для каждой пары элементов $1 \leqslant i \leqslant k$, $k+1 \leqslant j \leqslant 2k$ рассмотрим множество вершин $M_{i,j}$ таких, что они содержат элементы $i$, $j$ и любой третий элемент из множества $A$ или $B$. Тогда выполнено $|M_{i,j}|=2k-2$. Будем брать в качестве вершин множества $W_n$ объединение нескольких $M_{i,j}$. Для этого важно заметить, что два таких множества либо не пересекаются, либо имеют ровно один общий элемент, если у них совпадает один индекс. Причем пересечение любых трех множеств $M_{i,j}$ является пустым множеством. Разделим все множества $M_{i,j}$ на $k$ групп. В первую группу будем включать множества $M_{1,k+1}, M_{2, k+2},\dots, M_{k,2k}$. В $i$-ю группу включаем множества вида $M_{j,k+j+i-1}$, где $1 \leqslant j \leqslant k$. Если в данной записи $k+j+i-1 > 2k$, то вычитаем из индекса число $k$, т.е. каждая следующая группа получается циклическим сдвигом второго индекса. Набирать множества $M_{i,j}$ для вершин множества $W_n$ будем по одному, начиная с первой группы, пока мощность их объединения не будет превосходить $cn^2$. Заметим, что с каждым прибавлением количество вершин увеличивается не больше, чем на $2k-2 < n$. Получаем, что число вершин в нашем графе будет равняться $cn^2+o(n^2)$. Пусть мы выбрали множество вершин $W_n$ в качестве объединения всех множеств из первых $a$ групп и еще $b$ первых множеств из $(a+1)$-й группы. Тогда $2b$ индексов будут встречаться $a+1$ раз, а все остальные индексы – $a$ раз. Пусть $T$ – множество пар $(i,j)$, которые были взяты в качестве индексов $M_{i,j}$. Тогда $|T|=ak+b$. Также рассмотрим $P$ – множество всех индексов, которые встречаются $a+1$ раз, и $Q$ – множество всех индексов, которые встречаются $a$ раз. Обратим внимание на то, что $b \leqslant k-1 < n/2$. Заметим, что
$$
\begin{equation*}
|W_n| \geqslant \frac{\sum_{(i,j) \in T} |M_{i,j}|}{2}= \frac{(2k-2)(ak+b)}{2},
\end{equation*}
\notag
$$
потому что каждая взятая вершина содержится не более чем в двух $M_{i,j}$, где $(i,j) \in T$. Отсюда следует, что $a=O(1)$. Подсчитаем точное количество вершин, которое получилось в данном объединении. Будем использовать формулу включений-исключений
$$
\begin{equation*}
\begin{aligned} \, |W_n| &=\sum_{(i,j) \in T} |M_{i,j}| -\sum_{(i,j), (s,w) \in T} |M_{i,j} \cap M_{s,w}| \\ &=(2k-2)(ak+b)-(2k-2b)C_a^2-2bC_{a+1}^2 \sim cn^2. \end{aligned}
\end{equation*}
\notag
$$
Второй переход обусловлен тем, что $|M_{i,j} \cap M_{s,w}|=0$, если $\{i,j\}$ и $\{s,w\}$ не пересекаются. Заметим, что $(2k-2b)C_a^2+2bC_{a+1}^2=o(n^2)$. Отсюда следует, что $ak+b \sim cn= pn/2 +qn$. Ясно, что при $q \neq 0$ начиная с некоторого $n$ выполнено $a=p,$ а также $b=qn+o(n)$. Разберем случай $q=0$. Поймем, что $(2k-2)(ak+b) > cn^2$, при этом $(2k- 2) < n$, а значит, $ak+b > cn=pn/2$. Таким образом, начиная с некоторого $n$ выполнено $a=p$, а также $b=O(1)$. Получаем, что в обоих случаях выполнены равенства $a=p$ и $b=qn+o(n)$. Теперь подсчитаем количество ребер в конструкции $W_n$. Введем обозначение Заметим, что две смежные вершины имеют ровно один общий элемент, а значит, одновременно встречаются ровно в одном множестве $K_i$. Отсюда следует равенство Теперь оценим количество ребер внутри конкретного множества $K_i$. Рассмотрим любое $j$ такое, что $(i,j) \in T$. Нетрудно видеть, что внутри $K_i$ множество $M_{i,j}$ является независимым. При этом любые два множества $M_{i,j}$ и $M_{i,s}$ при $s \neq j$ имеют ровно одну общую вершину, а значит, не имеют общих пар вершин. Отсюда получаем, что количество пар несмежных вершин внутри $K_i$ не менее Получаем оценку
$$
\begin{equation*}
\rho(K_i) \leqslant C_{|K_i|}^2-\sum_{j\colon (i,j) \in T} C_{|M_{i,j}|}^2.
\end{equation*}
\notag
$$
Складывая все такие неравенства, получаем
$$
\begin{equation*}
\rho(W_n)=\sum_{i=1}^{2k} \rho(K_i) \leqslant \sum_{i=1}^{2k} C_{|K_i|}^2-2\sum_{(i,j) \in T} C_{|M_{i,j}|}^2.
\end{equation*}
\notag
$$
Сначала заметим, что
$$
\begin{equation*}
2\sum_{(i,j) \in T} C_{|M_{i,j}|}^2=2(ak+b)C_{2k-2}^2 \sim cn^3.
\end{equation*}
\notag
$$
Далее для каждого элемента оценим сверху количество вершин из $W_n$, которые этот элемент содержат. Возьмем элемент $s \in Q$. Тогда существует ровно $a$ взятых $M_{i,j},$ которые содержат $2k-2$ вершин с элементом $s$. Во всех остальных взятых $M_{i,j}$ вершина с элементом $s$ содержится ровно один раз. Получаем оценку
$$
\begin{equation*}
|K_s| \leqslant (2k-2)a+ak+b-a=3ak+b-3a \leqslant 3ak+b.
\end{equation*}
\notag
$$
Аналогично, для $s \in P$ имеем
$$
\begin{equation*}
\begin{aligned} \, |K_s| &\leqslant (2k-2)(a+1)+ak+b-(a+1)=3ak+2k+b-3a-3 \\ &\leqslant 3ak+2k+b. \end{aligned}
\end{equation*}
\notag
$$
Теперь оценим сумму полностью:
$$
\begin{equation*}
\begin{aligned} \, \sum_{i=1}^{2k} C_{|K_i|}^2 &\leqslant \sum_{i=1}^{2k} \frac{K_i^2}{2} =\sum_{i \in Q} \frac{K_i^2}{2}+\sum_{i \in P} \frac{K_i^2}{2} \\ &\leqslant \frac{(2k-2b)(3ak+b)^2+ 2b(3ak+b+2k)^2}{2} \\ &= \frac{2k(3ak+b)^2+2b \cdot 4k^2+2b \cdot 2(3ak+b) \cdot 2k}{2} \\ &=\frac{18a^2k^3+12abk^2+ 2b^2k+8bk^2 +24abk^2 +8b^2k}{2} \\ &=\frac{18a^2k^3+36abk^2+10b^2k+8bk^2}{2} \\ &= \frac{9(ak+b)^2\cdot 2k+ 8bk^2-8b^2k}{2} \\ &=\frac{9c^2n^3+o(n^3)+8bk(k-b)}{2}. \end{aligned}
\end{equation*}
\notag
$$
Таким образом, получаем нужную оценку
$$
\begin{equation*}
\begin{aligned} \, \rho([cn^2]) &\leqslant \rho(W_n) \leqslant \sum_{i=1}^{2k} C_{|K_i|}^2-2\sum_{(i,j) \in T} C_{|M_{i,j}|}^2 \\ &\leqslant\frac{9c^2n^3}{2}+\frac{8bk(k-b)}{2}-cn^3+o(n^3) \\ &\sim \frac{9c^2n^3}{2}-cn^3+2q\biggl(\frac 12-q\biggr)n^3. \end{aligned}
\end{equation*}
\notag
$$
Теорема 9 доказана. § 10. Доказательство теоремы 10Для всех $n$, начиная с некоторого, будем строить подмножество вершин $W_n$ графа $G(n,3,1)$ такое, что $|W_n| \geqslant [cn^2]$ и $\rho(W_n) \leqslant c^2n^3/(2(1-p))+g(n)$, где $g(n)=o(n^3)$. Пусть $x=[p n]$. Зафиксируем множества $A_{1}=\{1,2,\dots,[x/2]\}$, $A_{2}=\{ x+ 1, \dots,n\} $. Рассмотрим
$$
\begin{equation*}
W_n^{*}=\bigcup_{i\in A_{1}}\bigcup_{j\in A_{2}}\{(2i-1,2i,j)\} .
\end{equation*}
\notag
$$
Найдем мощность $W_n^{*}$. Всего существует $[x/2]$ способов выбрать первые два числа в векторной записи вершины и $n-x$ способов выбрать третье число. Получаем
$$
\begin{equation*}
\begin{aligned} \, |W_n^{*}| &=\biggl[\frac{x}{2}\biggr] (n-x) \geqslant \biggl(\frac{pn}{2}-1\biggr) (n-pn) \\ &\geqslant \frac{p(1-p)}{2} n^{2}-n \geqslant [cn^2]-n. \end{aligned}
\end{equation*}
\notag
$$
Найдем число ребер в данном подграфе. Ребрами соединены те вершины, которые пересекаются ровно по одному элементу, т.е. вершины вида $\{2i_{k}-1, 2i_{k},j\}$ при фиксированном $j$. Всего в множестве $W_n^{*}$ существует $[x/2]$ вершин, имеющих общий элемент $j,$ причем все они попарно соединены ребром. Количество ребер в данной клике равняется
$$
\begin{equation*}
\frac{1}{2} \biggl[\frac{x}{2}\biggr] \biggl(\biggl[\frac{x}{2}\biggr]-1\biggr) \leqslant \frac{1}{2}\,\frac{pn}{2} \biggl(\frac{pn}{2}-1\biggr) \leqslant \frac{p^{2}n^{2}}{8}.
\end{equation*}
\notag
$$
Заметим, что вершины из других клик либо пересекаются по первым двум элементам, либо не пересекаются. Всего количество таких клик (способов выбрать элемент $j$) равно $1-[pn]$. Получаем
$$
\begin{equation*}
\rho(W_n^{*}) \leqslant \frac{p^{2}(1-p)}{8} n^3+o(n^3)=\frac{c^2}{2(1-p)} n^3+o(n^3).
\end{equation*}
\notag
$$
Заметим, что каждый элемент от 1 до $n$ содержится меньше, чем в $n$ вершинах из $W_n^{*}$. Тогда любая вершина вне $W_n^{*}$ смежна меньше, чем с $3n$ вершинами из $W_n^{*}$. Тогда при добавлении $y$ любых вершин к множеству $W_n^{*}$ количество ребер увеличится не больше, чем на $C_y^2+3ny$. Если $|W_n^{*}| \geqslant [cn^2]$, то возьмем это множество в качестве $W_n$, и условие будет выполнено. Иначе построим $W_n$ как объединение $W_n^{*}$ и $y=[cn^2]-|W_n^{*}|$ любых различных вершин вне $W_n^{*}$. Заметим, что $y \leqslant n,$ тогда $C_y^2+3ny=o(n^3)$. Таким образом, Теорема 10 доказана. § 11. Доказательство теоремы 11Выделим в графе $G(n,3,1)$ непересекающиеся множества вершин $S_i$ следующим образом: Тогда $|S_i|=n-2i$. Всего таких множеств будет ровно $m=[n/2]$, поэтому выполнено
$$
\begin{equation*}
\sum_{i=1}^m |S_i|=nm -2 \frac{m(m+1)}{2} \sim \frac{n^2}{4}.
\end{equation*}
\notag
$$
Получаем, что для любой константы $c<1/4$ начиная с некоторого $n$ существует наименьшее натуральное $k \leqslant m$ такое, что Также отсюда следует, что $\sum_{i=1}^k |S_i| \sim cn^2$, так как мощность любого $S_i$ равна $o(n^2)$.Будем рассматривать подмножество вершин $W_n$ графа $G(n,3,1)$ такое, что ПолучаемЕсли положить $c=q(1-q),$ где $q<1/2$, то получится $k \sim qn$. Осталось подсчитать количество ребер в выбранном множестве вершин $W_n$. Введем обозначение Две смежные вершины имеют ровно один общий элемент, а значит, одновременно встречаются ровно в одном множестве $K_i$. Отсюда следует равенство Заметим, что
$$
\begin{equation*}
\begin{gathered} \, |K_1|=|K_2|=n-2,\quad |K_3|=|K_4|=n-3, \quad \dots, \\ |K_{2k-1}|=|K_{2k}|=n-k-1,\quad |K_{2k+1}|=\dots=|K_{n}|=k. \end{gathered}
\end{equation*}
\notag
$$
Также учтем, что все изначальные множества $S_i$ являются независимыми внутри $K_i$. Получаем оценку
$$
\begin{equation*}
\begin{aligned} \, \rho(W_n) &=\sum_{i=1}^{n} \rho(K_i)=\sum_{i=1}^{2k} \rho(K_i)+\sum_{i=2k+1}^{n} \rho(K_i)=\sum_{i=1}^{2k} \rho(K_i)+(n-2k)C_k^2 \\ &\leqslant \sum_{i=1}^{2k} (C_{|K_i|}^2-C_{|S_i|}^2)+ (n-2k)C_k^2 =2 \sum_{i=1}^{k} (C_{n-i-1}^2-C_{n-2i}^2)+(n-2k)C_k^2 \\ & \sim \sum_{i=1}^{k} (n-i-1)^2-\sum_{i=1}^{k} (n-2i)^2+(n-2k)\frac{k^2}{2} \\ &\sim \frac{n^3-(n-k)^3}{3}-\frac{n^3-(n-2k)^3}{6}+(n-2k)\frac{k^2}{2} \\ &\sim n^3 \frac{1-2(1-q)^3+(1-2q)^3+3(1-2q)q^2}{6}\sim n^3 \frac{9q^2-12q^3}{6} \\ &\sim \frac{3q^2-4q^3}{2} n^3. \end{aligned}
\end{equation*}
\notag
$$
Теорема 11 доказана. 
Цитирование в формате AMSBIB
\RBibitem{DubNeuRai24} |
|
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|