| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях) Еще раз о разреженных вершинных полуграфах в графах без треугольников А. А. Разборовab a University of Chicago, Chicago, USA b Математический институт им. В. А. Стеклова Российской академии наук, г. Москва
Англоязычная версия:
Sbornik: Mathematics, 2022, Volume 213, Issue 1, Pages DOI: https://doi.org/10.1070/SM9615 
Реферативные базы данных:
     § 1. ВведениеЗа свою долгую жизнь П. Эрдёш многократно (см. [8]–[10]) обращался к ряду вопросов, объединенных одной общей темой: насколько граф без треугольников может быть далек от того, чтобы оказаться двудольным. Один из них – задача о пятиугольниках – был полностью разрешен в [16], [14]. Другой вопрос состоит в том, каково может быть наибольшее возможное $\ell_1$-расстояние (в данном случае просто число удаляемых ребер) от графа без треугольников до класса двудольных графов? Он изучался в [5], [7], [1]. Настоящая работа посвящена третьему вопросу – гипотезе о вершинных полуграфах, который иногда называют одним из самых любимых вопросов Эрдёша (см. [19]). Всегда ли можно в заданном графе $G$ без треугольников удалить половину вершин так, чтобы реберная плотность ${|E(G)|}/(2|V(G)|^2)$ стала ${\leqslant}\,1/25$? В этом направлении имеются и более свежие работы [6], [18]–[20], однако вопрос остается открытым. В настоящей работе мы улучшаем некоторые из результатов указанных публикаций, а также предлагаем новые результаты. Зададим граф $G$ без треугольников на $n$ вершинах и обозначим через $\beta(G)$ наименьшее число ребер в его вершинных полуграфах, нормированное1 числом $n^2$. Гипотеза о вершинных полуграфах Эрдёша гласит, что $\beta(G)\leqslant 1/{50}$ для всякого графа $G$ без треугольников. Оценка $\beta(G)\leqslant 1/{16}$ очевидна (она достигается на случайном полуграфе); в работе [6] показано, что $\beta(G)\leqslant 1/{30}$, а в [18] оценка улучшена до $\beta(G)\leqslant 1/{36}$. Число ${27}/{1024}$ здесь отнюдь не произвольно: оно показывает, чего можно достичь методами определенного класса, причем граф Клебша является экстремальным примером для получающейся в результате экстремальной задачи. Ниже мы скажем об этом больше. Предположительно экстремальными примерами для гипотезы о вершинных полуграфах являются пятиугольник $C_5$ и граф Петерсена. Первый, кроме того, не содержит индуцированных паросочетаний размера $2$. Теорема 1.2. Гипотеза о вершинных полуграфах верна для любого графа без треугольников и без индуцированных паросочетаний размера $2$. Прежде чем двинуться дальше, обсудим доказательства этих двух теорем вкратце, поскольку они приводят к потенциально интересным понятиям и вопросам. Отступление о подсчете четырехугольниковЧерез $\rho=\rho(G)$ и $C_4=C_4(G)$ обозначим соответственно реберную плотность в графе $G$ и плотность четырехугольников (копий графа $C_4$) в нем. Эти величины вычисляются в смысле алгебр флагов или пределов графов: сначала $G$ заменяется своим бесконечным раздутием (так что, в частности, копии пути $P_3$ в $G$ и даже отдельные ребра вносят вклад в $C_4(G)$). Эти две величины имеют основополагающее значение в теории квазислучайных графов: $C_4\geqslant 3\rho^4$, причем возрастающая последовательность графов с одинаковыми значениями $\rho(G)$ квазислучайна тогда и только тогда, когда это неравенство в пределе обращается в равенство (см. [4]). Для графов без треугольников данную оценку легко улучшить до Это количественное уточнение утверждения о том, что графы без треугольников не являются квазислучайными. Естественно поэтому спросить: каково наименьшее значение величины $C_4(G)$ как функции от $\rho(G)$? В некотором смысле данный вопрос двойствен вопросам Эрдёша. Последние в том или ином виде заключаются в том, насколько граф без треугольников может быть далек от двудольности. Вопрос о четырехугольниках, напротив, состоит в том, насколько граф без треугольников должен быть далек от квазислучайности?Мы предполагаем, что в общем виде этот вопрос чрезвычайно труден. Однако, как было показано еще в [5; § 2], он очень тесно связан с гипотезами Эрдёша. В нашем контексте несложный анализ (части) рассуждения Кривелевича, дополненный непосредственным усреднением, дает следующее утверждение. Теперь обе оценки на $\beta(G)$ вытекают из следующего утверждения. Теорема 1.4. 1. Для любого графа $G$ без треугольников 2. Для любого графа $G$ без треугольников и без индуцированных паросочетаний размера $2$ Эта теорема доказывается с помощью вычислений средней сложности в алгебрах флагов. Вторая оценка точна при $\rho=2/5$, как и должно быть, поскольку пятиугольник $C_5$ (предположительно) является экстремальным примером для гипотезы о вершинных полуграфах. Оценка из первого неравенства лучше тривиальной оценки (1) при $0.257\leqslant\rho \leqslant 0.366$. Эта оценка точна при $\rho=5/16$. Экстремальным примером служит граф Клебша, причем, по-видимому, это единственное нетривиальное значение величины $\rho(G)$, для которого известно точное решение задачи о четырехугольниках. Заметим теперь, что наша оценка $\beta(G)\leqslant {27}/{1024}$ точна при довольно естественном ограничении гипотезы Эрдёша. А именно, многие предшествующие результаты, включая предложение 1.3, основаны на следующей простой конструкции. Возьмем ребро $e\in E(G)$. Оно естественным образом делит множество $V(G)$ на три части. Всем этим частям некоторым образом припишем общие веса, которые затем равномерно распределим внутри каждой части. Тогда значение ${27}/{1024}$ в гипотезе о вершинных полуграфах является наилучшим значением, достижимым таким способом, причем граф Клебша опять оказывается экстремальным примером. Вернемся к обзору оставшихся результатов. Гипотеза о вершинных полуграфах очевидна при $\rho(G)\leqslant 4/25$ (здесь еще раз оказывается полезным случайный полуграф). П. Киваш и Б. Судаков (см. [19]) ослабили это условие до $\rho(G)\leqslant 1/6$. Теорема 1.5. Гипотеза о вершинных полуграфах верна для всякого графа $G$ без треугольников, для которого выполнено соотношение На основе этой теоремы доказывается следующая Теорема 1.6. Гипотеза о вершинных полуграфах верна для всякого сильно регулярного графа без треугольников. Многое было сделано в отношении критического значения $\rho=2/5$. В [18; теорема 3] гипотеза доказана для регулярных графов $G$ без треугольников с условием $\rho(G)\geqslant 2/5$, а в [19] требование регулярности снято. С. Норин и Л. Епремян (см. [20]) улучшили этот результат, ослабив предположение $\rho(G)\geqslant 2/5$ до $\rho(G)\geqslant 2/5-\gamma$, где $\gamma>0$ – (вычислимая) константа. Если заменить $\rho(G)$ (нормированной) наименьшей степенью $\delta(G)$, то оценка на $\gamma$ значительно улучшается и гипотеза о вершинных полуграфах оказывается верной при $\delta(G)\geqslant 5/{14}$ (см. [20]). Теорема 1.7. Пусть $\alpha(G)$ – нормированное (числом $n$) число независимости графа $G$ без треугольников. Допустим, что $\alpha(G)\geqslant 3/8$. Тогда Следствие 1.8. Гипотеза о вершинных полуграфах выполняется для любого графа без треугольников с (нормированной) наибольшей степенью $\geqslant 2/5$. Заметим, что, в отличие от предшествующих результатов, мы не требуем, чтобы все вершины имели большу́ю степень (даже в среднем), а только чтобы одна. Кроме того, теорема 1.7 покрывает и случай графа Петерсена, поскольку его (ненормированное) число независимости равно $4$. С другой стороны, мы не смогли распространить ее на открытую окрестность числа $2/5$ подобно результатам предыдущих исследований. И последнее, оба предположительно экстремальных примера (цикл на пяти вершинах и граф Петерсена) имеют обхват $5$. Теорема 1.9. Гипотеза о вершинных полуграфах выполняется для всех графов обхвата $\geqslant 5$ без треугольников. Оставшаяся часть работы организована следующим образом. В § 2 даются все нужные определения. В § 3 еще раз сформулированы наши результаты, главным образом из соображений удобства. Доказательствам посвящен § 4, а § 5 завершает статью рядом замечаний и открытых вопросов. § 2. Предварительные рассмотренияЕсли не сказано иного, любой граф $G$ в настоящей работе считается конечным, простым и не содержащим треугольников. Через $N_G(v)$ обозначается окрестность вершины $v$, а $n$ всегда обозначает число вершин. Если множества вершин $X$ и $Y$ не пересекаются, то через $E(X,Y)$ мы обозначим множество ребер с одним концом в $X$, а другим в $Y$; аналогично $E(X)$ обозначает множество ребер, порожденное множеством $X$. Вершинным полуграфом (или просто полуграфом) в графе $G$ с $n$ вершинами называется функция $\mu\colon V(G)\longrightarrow[0,1]$ такая, что $\sum_{v\in V(G)}\mu(v)=n/2$. Положим при этом
$$
\begin{equation*}
\begin{gathered} \, \beta(G,\mu) \stackrel{\mathrm{def}}{=} \frac 1{n^2}\sum_{(u,v)\in E(G)}\mu(u)\mu(v), \\ \beta(G) \stackrel{\mathrm{def}}{=} \min(\beta(G,\mu)\mid \mu\ \text{есть полуграф в}\ G). \end{gathered}
\end{equation*}
\notag
$$
Из соображений выпуклости легко видеть, что при четном $n$ этот минимум достигается на $0{-}1$-полуграфе; в таком случае мы также используем обозначение $\beta(G,A)$, где $A \in \binom{V(G)}{n/2}$. Если же $n$ нечетно, то минимум достигается на почти $0{-}1$-полуграфе $\mu$, т.е. когда $\mu(v_0)=1/2$ для единственной вершины $v_0$ и $\mu(v)\in \{0,1\}$ для прочих вершин. Однако, как мы увидим далее, аналитическое выражение выше чрезвычайно удобно в конкретных конструкциях. Гипотеза 2.1 (Эрдёша о вершинных полуграфах). $\beta(G)\leqslant 1/{50}$ для любого графа $G$ без треугольников. Через $\rho(G)$ и $C_4(G)$ обозначим соответственно реберную плотность и плотность четырехугольников, определяемые в согласии с формализмом алгебр флагов. То есть полагаем
$$
\begin{equation*}
\rho(G)\stackrel{\mathrm{def}}{=} \frac{2|E(G)|}{n^2},
\end{equation*}
\notag
$$
а чтобы вычислить $C_4(G)$, выберем вершины $\boldsymbol{v_i}\in V(G)$, где $i\in [4]$, случайно, равномерно и независимо в совокупности (при этом возможны повторы), построим граф на множестве $[4]$ со множеством ребер $\{(i,j)\in \binom{[4]}{2}\bigm|(\boldsymbol{v_i}, \boldsymbol{v_j})\in E(G)\}$ и примем за $C_4(G)$ вероятность того, что этот граф изоморфен $C_4$. Для вершины $v\in V(G)$ обозначим через ее относительную степень, а через
$$
\begin{equation*}
\Delta(G)\stackrel{\mathrm{def}}{=}\max(e(v)\mid v\in V(G))
\end{equation*}
\notag
$$
– наибольшую степень, тоже относительную. Аналогично,
$$
\begin{equation*}
\alpha(G) \stackrel{\mathrm{def}}{=} \max\biggl(\frac{|A|}{n}\biggm|A\ \text{является независимым множеством}\biggr)
\end{equation*}
\notag
$$
обозначает относительное число независимости. Можно, не ограничивая общности, считать, что $\alpha(G)\leqslant 1/2$, ибо иначе гипотеза 2.1 очевидна. Таким образом,
$$
\begin{equation}
\rho(G) \leqslant \Delta(G) \leqslant \alpha(G) \leqslant \frac12.
\end{equation}
\tag{2}
$$
Для множеств вершин $A,B,C,D,E,\dots$ буквами $p_a,p_b,p_c,\dots$ будем обозначать их плотности: Через $\rho_{xy}$ (при $x\neq y \in \{a,b,c,d,\dots\}$ и $X \cap Y = \varnothing$) обозначим нормированную плотность ребер между множествами $X$ и $Y$:
$$
\begin{equation*}
\rho_{xy} \stackrel{\mathrm{def}}{=} \frac{2|E(X,Y)|}{n^2};
\end{equation*}
\notag
$$
и аналогично
$$
\begin{equation*}
\rho_{x} \stackrel{\mathrm{def}}{=} \frac{|E(X)|}{n^2}.
\end{equation*}
\notag
$$
Наконец, для $v\not\in X$ положим
$$
\begin{equation*}
e_X(v) \stackrel{\mathrm{def}}{=} \frac{|N_G(v)\cap X|}{n}.
\end{equation*}
\notag
$$
§ 3. РезультатыВ этом параграфе собраны наши основные результаты, сформулированные в § 1. Теорема 3.1. a) Для любого графа $G$ без треугольников (оценка точна для графа Клебша). b) Для любого графа $G$ без треугольников и без индуцированных паросочетаний размера $2$ (оценка точна для $C_5$).Теорема 3.3. Гипотеза 2.1 верна для всякого графа без треугольников и без индуцированных паросочетаний размера $2$. Теорема 3.4. Гипотеза 2.1 верна для всякого графа без треугольников, для которого выполнено неравенство Напомним, что регулярный граф $G$ без треугольников является сильно регулярным, если число $|N_G(v)\cap N_G(w)|$ принимает одно и то же значение $c$ для всех пар $(v,w)$ различных несмежных вершин. Теорема 3.5. Гипотеза 2.1 верна для всякого сильно регулярного графа без треугольников. Теорема 3.6. Для любого графа $G$ без треугольников такого, что $\alpha(G)\geqslant 3/8$, имеет место неравенство Следствие 3.7. Гипотеза 2.1 верна для всякого такого графа $G$ без треугольников, что $\alpha(G)\geqslant 2/5$. Теорема 3.8. Гипотеза 2.1 верна для всякого графа обхвата $\geqslant 5$ без треугольников. § 4. ДоказательстваВ этом параграфе мы доказываем все наши результаты. Некоторые из доказательств, особенно в п. 4.1 и п. 4.3, существенно опираются на символьные вычисления в системе Maple. Соответствующий рабочий лист наряду с некоторыми вспомогательными материалами можно найти по ссылке http://people.cs.uchicago.edu/razborov/files/halves.zip 4.1. Вычисления в алгебре флаговВ этом пункте мы докажем теорему 3.1. Как было замечено в § 2, наши обозначения для конечных графов согласуются с формализмом алгебр флагов, вследствие чего достаточно доказать неравенства (где $M_4$ обозначает паросочетание с двумя ребрами) в теории графов без треугольников, а затем применить их к бесконечному (сбалансированному) раздутию графа $G$.Для этого мы выполняем непосредственное вычисление в алгебрах флагов, используя неравенство Коши–Буняковского–Шварца. Поскольку достаточно много подобных вычислений уже имеется в литературе (с неформальными пояснениями разной степени подробности), то наше доказательство мы проводим достаточно лаконично, строго следуя обозначениям работы [21]. Начнем с неравенства (3). Для него нужно рассматривать графы без треугольников на восьми вершинах. Имеем
$$
\begin{equation*}
|\mathcal M_8|=410, \qquad |\mathcal F_6^{\sigma_i}|=d_i,\quad\text{где }\ d_1=110,\quad d_2=81,\quad d_3=67,\quad d_4= 46,
\end{equation*}
\notag
$$
а типы $\sigma_i$ показаны на рис. 1 (за исключением $\sigma_4$, это те же типы, которые задействованы в [15]). Мы нумеруем флаги $\mathcal F_6^{\sigma_i}$ достаточно произвольным образом, так что $\mathcal F_6^{\sigma_i} = \{F_1^{\sigma_i},\dots, F_{d_i}^{\sigma_i}\}$, и предъявляем положительно полуопределенные матрицы $Q_i$ размера $d_i\times d_i$ с рациональными коэффициентами, для которых
$$
\begin{equation}
\sum_{i=1}^4 \sum_{j_1,j_2=1}^{d_i} [\![Q_i(j_1,j_2)F_{j_1}^{\sigma_i} F_{j_2}^{\sigma_i}]\!]_{\sigma_i} \ll_8 C_4-\frac 32\rho^2+\frac{81}{256}\rho,
\end{equation}
\tag{5}
$$
где $\ll_8$ обозначает покоэффициентное сравнение после приведения обеих частей неравенства к виду линейных комбинаций элементов множества $\mathcal M_8$. Здесь остается лишь заметить, что матрицы $Q_i$ являются вырожденными, а их коранги $d_i-\operatorname{rk}(Q_i)$ равняются $2$, $2$, $5$ и $4$ соответственно. Это отражает тот факт, что граф Клебша $G_{\mathrm{Clebsch}}$ является экстремальной конфигурацией для неравенства (5) и дает отличную проверку корректности наших вычислений. Поэтому каждый строгий гомоморфизм $\sigma_i\to G_{\mathrm{Clebsch}}$ порождает элемент из ядра матрицы $Q_i$. Само вычисление вынесено в http://people.cs.uchicago.edu/razborov/files/halves.zip. Неравенство (4) доказывается аналогично, но на этот раз нам нужны графы лишь на шести вершинах; с другой стороны, вместо $\sigma_3$ требуется тип $E$. Имеем
$$
\begin{equation*}
|\mathcal M_6|=38,\qquad |\mathcal F_6^{\sigma_i}|=d_i,\quad\text{где }\ d_1=12,\quad d_2=10,\quad d_4 =7,
\end{equation*}
\notag
$$
а также $|\mathcal M_4^E|=10$. Вычисление имеет вид
$$
\begin{equation*}
\begin{aligned} \, &\sum_{j_1,j_2=1}^{10}[\![R_E(j_1,j_2)F_{j_1}^{E} F_{j_2}^{E}]\!]_{E} + \sum_{i\in \{1,2,4\}} \sum_{j_1,j_2=1}^{d_i} [\![R_i(j_1,j_2)F_{j_1}^{\sigma_i} F_{j_2}^{\sigma_i}]\!]_{\sigma_i} \\ &\qquad \ll_6 C_4+2M_4-\frac 32\rho^2+\frac{6}{25}\rho. \end{aligned}
\end{equation*}
\notag
$$
Множитель $2$ перед $M_4$ достаточно произволен; мы не пытались найти его оптимальное значение. Поскольку это неравенство обращается в равенство для $C_5$, матрицы $R_E$, $R_1$, $R_2$ и $R_4$ тоже должны быть вырожденными; и действительно, их коранги суть $1$, $1$, $1$ и $3$ соответственно. Теорема 3.1 доказана. 4.2. Абсолютные верхние границы для $\beta(G)$В этом пункте мы докажем теоремы 3.2 и 3.3. Как уже упоминалось, они немедленно следуют из теоремы 3.1 и предложения 1.3, так что остается лишь доказать последнее. Ниже приведена незначительная переформулировка части рассуждений М. Кривелевича (см. [18]), включенная сюда для полноты изложения. Начнем с рассмотрения отдельного ребра $(v_1,v_2)\in E(G)$. Положим
$$
\begin{equation*}
A_i\stackrel{\mathrm{def}}{=} N_G(v_i),\qquad e_i\stackrel{\mathrm{def}}{=} e(v_i)\quad (= p_{a_i});
\end{equation*}
\notag
$$
напомним, что $e_i\leqslant1/2$ по неравенству (2). Пусть
$$
\begin{equation*}
p_i\stackrel{\mathrm{def}}{=} \frac{1/2-e_i}{1-e_1-e_2},
\end{equation*}
\notag
$$
так что $p_1\,{+}\,p_2\,{=}\,1$, $B\stackrel{\mathrm{def}}{=} V(G)\,{\setminus}\, (A_1\cup A_2)$. Для $i=1,2$ определим полуграф $\mu_i$ так:
$$
\begin{equation*}
\mu_i(v)\stackrel{\mathrm{def}}{=} \begin{cases} 1, & \text{если}\ v\in A_i, \\ p_i, & \text{если}\ v\in B, \\ 0, & \text{если}\ v\in A_{3-i}. \end{cases}
\end{equation*}
\notag
$$
Тогда
$$
\begin{equation}
2\beta(G) \leqslant 2\beta(G,\mu_1) =p_1\rho_{a_1,b} +p_1^2\rho_b,
\end{equation}
\tag{6}
$$
$$
\begin{equation}
2\beta(G) \leqslant 2\beta(G,\mu_2) =p_2\rho_{a_2,b} +p_2^2\rho_b.
\end{equation}
\tag{7}
$$
Умножая $i$-е неравенство на $p_{3-i}$, а затем складывая полученные результаты, получаем
$$
\begin{equation*}
2\beta(G) \leqslant p_1p_2(\rho_{a_1b} + \rho_{a_2b} +\rho_{b}) = p_1p_2(\rho-\rho_{a_1a_2}) \leqslant \frac 14(\rho- C_4^E(v_1,v_2)),
\end{equation*}
\notag
$$
где величину $\rho_{a_1a_2}$ мы обозначили через $C_4^E(v_1,v_2)$, чтобы подчеркнуть, что это вклад ребра $(v_1,v_2)$ в значение $C_4(G)$. Наконец, усредняя по всем ребрам, имеем
$$
\begin{equation*}
2\rho\beta(G) \leqslant \frac 14[\![\rho-C^4_E]\!]_{E} = \frac 14\biggl(\rho^2 - \frac 23C_4\biggr),
\end{equation*}
\notag
$$
т.е. в точности предложение 1.3. 4.3. Разреженные графыВ этом пункте мы докажем теорему 3.4. Как и в работе [19], анализ распадается на два случая: $\Delta(G)\geqslant 1/4$ и $\Delta(G)\leqslant 1/4$. Для первого случая достаточно следующего варианта предложения 1.3. Доказательство. Выберем вершину $v\in V(G)$, для которой выполняется условие $e(v)=\Delta$($\stackrel{\mathrm{def}}{=} \Delta(G)$), и положим $A\stackrel{\mathrm{def}}{=}\,N_G(v)$ (так что $p_a=\Delta$) и $B=N_G(v)\setminus A$. Построим следующие вершинные полуграфы $\mu_0$ и $\mu_1$:
$$
\begin{equation*}
\mu_0(w) \stackrel{\mathrm{def}}{=} \begin{cases} 0, &\text{если}\ w\in A, \\ \dfrac 1{2(1-\Delta)}, &\text{если}\ w\in B, \end{cases} \qquad \mu_1(w) \stackrel{\mathrm{def}}{=} \begin{cases} 1,&\text{если}\ w\in A, \\ \dfrac{1/2-\Delta}{1-\Delta},&\text{если}\ w\in B. \end{cases}
\end{equation*}
\notag
$$
Тогда
$$
\begin{equation}
2\beta(G) \leqslant 2\beta(G,\mu_0)= \frac{\rho_b}{4(1-\Delta)^2},
\end{equation}
\tag{8}
$$
$$
\begin{equation}
2\beta(G) \leqslant 2\beta(G,\mu_1)=\frac{1/2-\Delta}{1-\Delta}\rho_{ab} + \biggl(\frac{1/2-\Delta}{1-\Delta}\biggr)^2\rho_b.
\end{equation}
\tag{9}
$$
Умножая неравенство (9) на $1-2\Delta$ и прибавляя его к (8), получаем
$$
\begin{equation*}
4(1-\Delta)\beta(G) \leqslant \frac{1-2\Delta}{2(1-\Delta)}(\rho_{ab}+\rho_b) = \frac{1-2\Delta}{2(1-\Delta)}\rho(G).
\end{equation*}
\notag
$$
Лемма доказана. Далее, функция $(1-2\Delta)/(8(1-\Delta^2))$ убывает при $\Delta\in [1/4,1/2]$, поэтому $\Delta(G)\geqslant 1/4$ влечет $\beta(G)\leqslant {\rho(G)}/{9}$, но тогда теорема 3.4 следует в силу $\rho_0\leqslant 9/{50}$. Случай, когда $\Delta(G)\leqslant 1/4$, труднее. Как и в доказательстве предложения 1.3, рассмотрим сначала отдельное ребро $(v_1,v_2)\in E(G)$ (но на этот раз мы станем выбирать его не случайно, а определенным далее способом). Вновь используем обозначения $e_i$, $A_i$, $B$ и $p_i$ из названного доказательства, так что по-прежнему будем иметь оценки (6) и (7). Однако теперь условие $\Delta(G)\leqslant 1/4$ позволяет построить еще один вершинный полуграф
$$
\begin{equation*}
\mu_0(G) \stackrel{\mathrm{def}}{=} \begin{cases} 1,&\text{если}\ v\in A_1\cup A_2, \\ q,&\text{если}\ v\in B, \end{cases}
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
p_0\stackrel{\mathrm{def}}{=} \frac{1/2-e_1-e_2}{1-e_1-e_2}.
\end{equation*}
\notag
$$
Это приводит еще к одной оценке:
$$
\begin{equation}
2\beta(G) \leqslant \rho_{a_1a_2} + p_0(\rho_{a_1b} + \rho_{a_2b}) + p_0^2\rho_b.
\end{equation}
\tag{10}
$$
Теперь найдем неотрицательные коэффициенты $\alpha_0$, $\alpha_1$ и $\alpha_2$, умножая на которые неравенства (10), (6) и (7) соответственно, а затем складывая результаты, мы уравняем коэффициенты при $\rho_{a_1b}$ и $\rho_{a_1a_2}$, а также при $\rho_{a_2b}$ и $\rho_b$. Для этого положим
$$
\begin{equation*}
\begin{aligned} \, \alpha_0 &\stackrel{\mathrm{def}}{=} (1-2e_1)^2(1-2e_2), \\ \alpha_1 &\stackrel{\mathrm{def}}{=} (1-2e_1)(1-2e_2), \\ \alpha_2 &\stackrel{\mathrm{def}}{=} 2(1-2e_1)e_2. \end{aligned}
\end{equation*}
\notag
$$
Тогда (см. рабочий лист Maple)
$$
\begin{equation*}
\begin{aligned} \, &4(1-2e_1)(1-e_1-e_2+2e_1e_2)\beta(G) \\ &\qquad\leqslant \alpha_0(\rho_{a_1a_2}+\rho_{a_1b}) + \gamma(\rho_{a_2b}+\rho_b) \\ &\qquad = (\alpha_0-\gamma)(\rho_{a_1a_2}+\rho_{a_1b}) + \gamma(\rho_{a_1a_2}+\rho_{a_1b} +\rho_{a_2b}+\rho_b ) \\ &\qquad = (\alpha_0-\gamma)(\rho_{a_1a_2}+\rho_{a_1b})+ \gamma\rho, \end{aligned}
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
\gamma\stackrel{\mathrm{def}}{=} \frac{(1-2e_1)(1-2e_2)(1-4e_1+4e_1^2+4e_1e_2)}{2(1-e_1-e_2)}.
\end{equation*}
\notag
$$
Отметим, что
$$
\begin{equation*}
\alpha_0-\gamma = \frac{(1-2e_1)(1-2e_2)(1-2e_1-2e_2)}{2(1-e_1-e_2)} \geqslant 0,
\end{equation*}
\notag
$$
ибо $e_1,e_2\leqslant \Delta(G)\leqslant 1/4$. Поэтому нам нужна оценка сверху на $\rho_{a_1a_2}+\rho_{a_1b}$. Теперь, чтобы получить таковую, мы определим $v_1$ и $v_2$. В качестве $v_1$ возьмем вершину наибольшей степени, так что $e_1=\Delta$. За $v_2$ примем вершину наибольшей степени во множестве $N_G(v_1)$. Последний выбор дает оценку $\rho_{a_1a_2} + \rho_{a_1b}\leqslant 2\Delta e_2$, поскольку $\rho_{a_1a_2}+\rho_{a_1b}$ есть просто общая плотность ребер, инцидентных $A_1$. Подводя итог, приходим к оценке
$$
\begin{equation*}
\begin{aligned} \, \beta(G) &\leqslant f(\rho,\Delta,e_2) \\ &\stackrel{\mathrm{def}}{=} \frac{(1-2e_2)(4\Delta^2\rho-4\Delta^2e_2+ 4\Delta\rho e_2-4\Delta e_2^2-4\Delta\rho +2\Delta e_2+\rho)}{8(1+2\Delta e_2-\Delta -e_2)(1-\Delta-e_2)}. \end{aligned}
\end{equation*}
\notag
$$
Напомним также, что у нас есть ограничения
$$
\begin{equation*}
0\leqslant \rho, \qquad e_2 \leqslant \Delta \leqslant \frac14.
\end{equation*}
\notag
$$
Данная задача оптимизации несколько неудобна для полного анализа, т.е. чтобы аналитически оценить $\beta(G)$ через $\rho(G)$. Вместо этого мы вычислим
$$
\begin{equation*}
\frac 1{50} - f(\rho,\Delta,e_2) = \frac{Q(\rho,\Delta,e_2)}{200(1-\Delta-e_2) (1-\Delta-e_2+2\Delta(e_2))},
\end{equation*}
\notag
$$
где $Q$ есть некоторый многочлен. Нашей целью будет показать, что из $\rho\leqslant \rho_0$ следует $Q(\rho,\Delta,e_2)\geqslant 0$. Заметим, что $Q(\rho_0,\rho_0,\rho_0)=0$ и что степени $\rho$, $\Delta$ и $e_2$ в $Q$ суть $1$, $2$ и $3$ соответственно. Сначала получаем
$$
\begin{equation*}
\frac{\partial Q}{\partial \rho} = -25(1-2e_2)(4\Delta^2+4\Delta e_2-4\Delta+1) \leqslant -25(1-2e_2)(1-2\Delta)^2 \leqslant 0.
\end{equation*}
\notag
$$
Поэтому достаточно показать, что
$$
\begin{equation*}
Q_1(\Delta,e_2) \stackrel{\mathrm{def}}{=} Q(\min(\rho_0,\Delta),\Delta,e_2) \geqslant 0.
\end{equation*}
\notag
$$
Функция $Q_1$ больше не гладкая по $\Delta$, но остается кубическим многочленом по $e_2$. Разберем два случая: $e_2\leqslant\rho_0$ и $e_2\geqslant\rho_0$. Если $e_2\leqslant\rho_0$, то рассмотрим коэффициенты Тейлора в точке $e_2=\rho_0$:
$$
\begin{equation*}
\frac 1{r!}\,\frac{\partial^r Q_1(\Delta,e_2)}{(\partial e_2)^r}\bigg|_{e_2=\rho_0}, \qquad r=0,1,2,3.
\end{equation*}
\notag
$$
Тогда оказывается (см. рабочий лист Maple), что они неотрицательны при четных $r$ и отрицательны при нечетных $r$. Отсюда вытекает требуемое неравенство $Q_1(\Delta,e_2)\geqslant 0$. Во втором случае, когда $e_2\geqslant \rho_0$, мы также имеем $\Delta\geqslant \rho_0$, а поэтому $Q_1(\Delta,e_2)=Q(\rho_0,\Delta, e_2)$ является квадратичным многочленом по $\Delta\in [e_2,1/4]$. Следует заметить, что эта функция может быть как выпуклой, так и вогнутой. Но в любом случае требуемое неравенство $Q_1(\Delta,e_2)\geqslant 0$ следует из
$$
\begin{equation*}
Q_1(e_2,e_2)\geqslant 0, \qquad Q_1\biggl(\frac14,e_2\biggr)\geqslant 0, \qquad \frac{\partial Q_1}{\partial \Delta}\bigg|_{\Delta=e_2}\geqslant 0.
\end{equation*}
\notag
$$
Теорема 3.4 доказана. 4.4. Сильно регулярный случайВ этом пункте мы докажем теорему 3.5. Общие сведения о сильно регулярных графах без треугольников (далее СРГБТ) приводятся по [2]. Кроме полных двудольных графов $K_{n,n}$ (для которых гипотеза Эрдёша верна тривиальным образом), известны семь примеров СРГБТ, среди которых цикл $C_5$ и графы Петерсена и Клебша являются самыми маленькими. Очевидные параметры СРГБТ $G$ суть $n$, $k$ (степень вершины) и $c$ (число общих соседей у пары различных несмежных вершин). Они удовлетворяют соотношению Здесь и далее мы полагаем, что граф $G$ отличен от $K_{n,n}$ и от $C_5$. Тогда число $s\stackrel{\mathrm{def}}{=} \sqrt{c^2+4(k-c)}$ является целым, а единственное положительное собственное значение матрицы смежности, отличное от $k$, есть $q\stackrel{\mathrm{def}}{=} (s-c)/2$. Это число тоже целое, причем Более того, имеем поэтому $k$ и $n$ суть рациональные функции величин $c$ и $q$. В частности, вычисление дает
$$
\begin{equation*}
\rho(G) = \frac kn = \frac{c(qc+q^2+c)}{(qc+q^2+2c+q)(qc+q^2+ c-q)}\stackrel{\mathrm{def}}{=} Q(q,c).
\end{equation*}
\notag
$$
Проанализируем полученное выражение. Во-первых,
$$
\begin{equation*}
\frac{\partial Q}{\partial c} = \frac{q(q+1)(c^2q^2+2cq^3+q^4+c^2q-q^3-c^2-2qc)} {(qc+q^2+2c+q)^2(qc+q^2+c-q)^2} \geqslant 0,
\end{equation*}
\notag
$$
а значит, $Q$ возрастает по $c$. Далее, пусть
$$
\begin{equation*}
Q_1(q) \stackrel{\mathrm{def}}{=} Q(q,q(q+1)) = \frac{q^2+3q+1}{q(q+3)^2}
\end{equation*}
\notag
$$
(что соответствует так называемым графам Крейна). Тогда поэтому $Q_1(q)$ убывает. Так как $Q_1(4)={29}/{196}<\rho_0$, доказательство теоремы 3.5 сводится к трем случаям $q = 1,2,3$: для всех остальных достаточно теоремы 3.4. При $q=1$ получаем или граф Петерсена ($c=1$), или граф Клебша ($c= 2$). Гипотеза 2.1 для графа Клебша подтверждается вершинным полуграфом $(N_G(u)\cup N_G(v)) \setminus \{u,v\}$, где $(u,v)$ – произвольное ребро. При $q=2$ имеем $Q(2,1)={7}/{50}<\rho_0$ (это граф Хофмана–Синглтона), поэтому достаточно рассмотреть случаи, когда $2\leqslant c\leqslant 6$. Хорошо известные “арифметические условия” исключают $c\in \{3,5\}$ (см. [2; таблица 1]), а три других случая точно соответствуют оставшимся известным СРГБТ: графам Гевирца, $M_{22}$ и Хигмана–Симса (единственным графам для соответствующих значений $c$ и $q$; см. [12], [3], [11]). В графе Гевирца возьмем четыре вершины $u_1$, $u_2$, $u_3$, $u_4$, порождающие индуцированное паросочетание с двумя ребрами, и рассмотрим вершинный полуграф (см. рабочий лист Maple), порожденный множеством
$$
\begin{equation*}
\bigcup_{i=1}^4 N_G(u_i)\setminus \{u_1,u_2,u_3,u_4\}.
\end{equation*}
\notag
$$
В нем $51$ ребро, что доказывает оценку $\beta(G)\leqslant 0.017$. Если $G$ – граф $M_{22}$, то аналогичным образом полагаем
$$
\begin{equation*}
A\stackrel{\mathrm{def}}{=} \bigcup_{i=1}^3 N_G(u_i)\setminus \{u_1,u_2,u_3\},
\end{equation*}
\notag
$$
где $(u_1,u_2)\in E(G)$ и $u_3\notin N_G(u_1)\cup N_G(u_2)$. Тогда $|A|=38$ и $|E(A)|=109$. Более того, найдется вершина $v\notin A$, для которой $|N_G(v)\cap A|=9$. Добавив к подграфу, индуцированному множеством $A$, “половину” вершины $v$, получаем полуграф, доказывающий неравенство $\beta(G)\leqslant 0.0192$. Для графа Хигмана–Симса мы строим специальный вершинный полуграф, на котором достигается значение $\beta(G)\leqslant 1/{50}-10^{-4}$. Он был найден простой оптимизационной программой, примечательным образом наводящей на мысль, что эта оценка на самом деле точна. Если это так (мы не пытались строго обосновать данное утверждение), то граф Хигмана–Симса очень близко подходит к границе в гипотезе Эрдёша. Наконец, при $q=3$ имеем $Q(3,11)={583}/{3350}<\rho_0$. Поэтому остается рассмотреть лишь случай $q=3$, $c=12$, т.е. гипотетический $57$-регулярный граф Крейна на $324$ вершинах. Простым решением будет заметить, что такого графа, как известно (см. [13], [17]), не существует. Позволим себе, однако, набросать иное рассуждение, принадлежащее А. Гжесику и Я. Волецу (не опубликовано), которое, по нашему мнению, более поучительно и может представлять самостоятельный интерес. Как уже было отмечено, из оценки (10) можно убрать величину $\rho_b$, воспользовавшись тождеством $\rho=\rho_{a_1a_2}+\rho_{a_1b}+\rho_{a_2b}+\rho_b$. Если известно еще, что граф $G$ регулярный, то $p_0=(1/2-2\rho)/(1-2\rho)$, и величину $\rho_{a_ib}$ также можно устранить, используя равенство $\rho_{a_ib}+\rho_{a_1a_2}=2\rho^2$. Подставляя все это в неравенство (10) и усредняя по всевозможным выборам ребра $(v_1,v_2)$, как в п. 4.2, приходим к оценке
$$
\begin{equation}
\beta(G) \leqslant \frac{(2/3)C_4+\rho^2(1-4\rho)}{8\rho(1-2\rho)^2},
\end{equation}
\tag{12}
$$
имеющей место для любого регулярного графа $G$ (без треугольников). Если $G$ также является сильно регулярным, то величину $C_4(G)$ легко вычислить: (как мы помним из § 2, в $C_4(G)$ учтены и вырожденные циклы тоже). Подставляя это выражение в неравенство (12), получаем
$$
\begin{equation*}
\beta(G) \leqslant \frac{c(cq+q^2-c)}{8q(q+1)(c+q)(c+q-1)}.
\end{equation*}
\notag
$$
В частности, при $q=3$ и $c=12$ имеем $\beta(G)\leqslant {11}/{560}$. Теорема 3.5 доказана. 4.5. Графы с большим числом независимостиВ этом пункте мы докажем теорему 3.6; как было отмечено в § 1, при $\alpha\geqslant 2/5$ она является обобщением нескольких известных результатов. Будет удобно предполагать, что число $n$ четно: этого всегда можно добиться, заменив каждую вершину двумя неразличимыми вершинами. Пусть $A\subseteq V(G)$ – такое независимое множество, что $p_a=\alpha\geqslant 3/8$. Построим большее множество $B\supseteq A$, рекурсивно добавляя к нему вершины, привносящие лишь немного новых ребер. Точнее, мы применяем следующий простой алгоритм:
$$
\begin{equation*}
\begin{aligned} \, &B:=A \\ &\textbf{пока }|B|<\frac n2\textbf{ и }\exists\, v\not\in B \ \biggl(e_B(v)\leqslant \frac12-\alpha\biggr) \\ &\textbf{выполнять } B:=B\cup \{v\}. \end{aligned}
\end{equation*}
\notag
$$
Если алгоритм завершается вследствие достижения множеством $B$ размера $n/2$, то $\beta(G,B) \leqslant (1/2-\alpha)^2$, где правая часть $\leqslant (\alpha/2)(1/2-\alpha)$ в силу неравенства $\alpha\geqslant 3/8>1/3$, и все доказано. Поэтому без ограничения общности можно считать, что алгоритм останавливается, когда требуемой вершины $v$ не существует. Таким образом, построено множество $B$, для которого
$$
\begin{equation}
\begin{cases} p_b\in \biggl[\alpha,\dfrac12\biggr], \\ \rho_b \leqslant 2\biggl(\dfrac 12-\alpha\biggr)(p_b-\alpha), \\ \forall\, v\not\in B\ \biggl(e_B(v)>\dfrac 12-\alpha\biggr). \end{cases}
\end{equation}
\tag{13}
$$
Пусть
$$
\begin{equation*}
C\stackrel{\mathrm{def}}{=} \biggl\{v\not\in B\biggm| e_B(v)> \frac{p_b}{2}\biggr\}.
\end{equation*}
\notag
$$
Тогда множество $C$ независимое (так как у любых двух вершин из $C$ есть общий сосед в $B$). Отсюда получаем $p_c\leqslant \alpha$ по определению $\alpha(G)$. Это позволяет выбрать такое множество вершин $D$, не пересекающееся ни с $B$, ни с $C$, что $p_d=1-\alpha-p_b$. Теперь рассмотрим два случая, различающиеся тем, найдется ли в $B$ вершина, у которой много соседей в $D$, или нет. Случай 1: существует вершина $v\in B$ такая, что $e_D(v)\geqslant 1/2-p_b$. Произвольно выберем $E\subseteq N_G(v)\cap D$ со свойством $p_e=1/2-p_b$; заметим, что это множество $E\subseteq N_G(v)$ независимое. Далее, для каждого $v\in E$ имеем $e_B(v)\leqslant {p_b}/2$ в силу $E\subseteq D$. Тогда (обратите внимание на отсутствие множителя $2$ в последнем слагаемом)
$$
\begin{equation*}
2\beta(G, B\cup E) \leqslant 2\biggl(\frac 12 - \alpha\biggr)(p_b-\alpha) +p_b\biggl(\frac 12-p_b\biggr).
\end{equation*}
\notag
$$
Правая часть (вогнутая квадратичная функция величины $p_b$ с максимумом в точке $p_b=3/4-\alpha$) не превосходит $\alpha$, так как мы предположили, что $\alpha\geqslant 3/8$. Значит, поскольку $p_b\geqslant\alpha$, можно положить $p_b:=\alpha$, чем завершается анализ случая 1. Случай 2: для всех $v\in B$ имеет место $e_D(v)\leqslant 1/2-p_b$. Этот случай немного сложнее. Сначала зафиксируем некоторую вершину $v_0\in B$ (впоследствии мы будем усреднять по ее выбору). Пусть $E\stackrel{\mathrm{def}}{=} N_G(v_0)\,{\cap}\, D$ (так что $p_e\leqslant 1/2-p_b$) и $F\stackrel{\mathrm{def}}{=} D\,{\setminus}\, N_G(v_0)$; таким образом, $D= E\stackrel. \cup F$, причем множество $E$ независимое. Рассмотрим вершинный полуграф
$$
\begin{equation*}
\mu(v) \stackrel{\mathrm{def}}{=} \begin{cases} 1,& \text{если}\ v\in B\cup E, \\ p,& \text{если}\ v\in F, \\ 0& \text{во всех прочих случаях,} \end{cases}
\end{equation*}
\notag
$$
где Тогда
$$
\begin{equation*}
2\beta(G,\mu) =\rho_b+\rho_{be}+p\rho_{bf}+p\rho_{ef}+p^2\rho_f.
\end{equation*}
\notag
$$
Оценка на $\rho_b$ дается неравенством (13), и мы получаем $\rho_{bf} \leqslant p_bp_f$; множитель $2$ отсутствует по тем же причинам, что и выше. Для $\rho_{ef}$ используем тривиальную оценку $\rho_{ef}\leqslant 2p_ep_f$, и, наконец, имеем $\rho_f\leqslant {p_f^2}/{2}$ просто потому, что в $G$ нет треугольников. Подставляя все это в формулу выше (и пока не трогая $\rho_{be}$), получаем
$$
\begin{equation}
\begin{aligned} \, \notag 2\beta(G,\mu) & \leqslant 2\biggl(\frac 12-\alpha\biggr)(p_b-\alpha) + \rho_{be} + p_b\biggl(\frac 12-p_b-p_e\biggr) \\ \notag &\qquad +2p_e\biggl(\frac 12-p_b-p_e\biggr) + \frac 12\biggl(\frac 12 -p_b-p_e\biggr)^2 \\ & =2\biggl(\frac 12-\alpha\biggr)(p_b-\alpha) + \frac 12 \biggl(\frac 12-p_b-p_e\biggr)\biggl(\frac 12+p_b+3p_e\biggr)+ \rho_{be}. \end{aligned}
\end{equation}
\tag{14}
$$
В этой оценке лишь величины $p_e$ и $\rho_{be}$ зависят от выбора $v_0\in B$, и теперь мы сделаем этот выбор случайным. Оценка (14) вогнута по $p_e$, поэтому можно просто заменить величину $p_e$ ее математическим ожиданием ${\rho_{bd}}/{2p_b}$. Что касается $\rho_{be}$, то выберем $\boldsymbol w\in D$ случайно и равномерно; тогда стандартное рассуждение с подсчетом двумя способами дает
$$
\begin{equation*}
\mathbf E[\rho_{be}] = \frac{2p_d}{p_b}\mathbf E[e_B(\boldsymbol w)^2].
\end{equation*}
\notag
$$
Однако нам также известно, что
$$
\begin{equation*}
\frac 12-\alpha \leqslant e_B(\boldsymbol w) \leqslant \frac{p_b}{2},
\end{equation*}
\notag
$$
где первое неравенство получается из (13), а второе следует из того, что $D\cap C = \varnothing$. Более того,
$$
\begin{equation*}
\mathbf E[e_B(\boldsymbol w)] = \frac{\rho_{bd}}{2p_d}.
\end{equation*}
\notag
$$
Оценивая второй момент обычным образом, получаем
$$
\begin{equation*}
\mathbf E[e_B(\boldsymbol w)^2] \leqslant \frac{\rho_{bd}}{2p_d} \biggl(\frac12-\alpha+\frac{p_b}{2}\biggr) - \frac{p_b}2\biggl(\frac 12-\alpha\biggr).
\end{equation*}
\notag
$$
Наконец, подставляя все найденное здесь в (14), имеем
$$
\begin{equation*}
\begin{aligned} \, &\beta \leqslant Q(\alpha,p_b,\rho_{bd}) \\ &\stackrel{\mathrm{def}}{=} \frac{8\alpha^2p_b^2-24\alpha p_b^3 - 4p_b^4+ 4\alpha p_b^2 - 8\alpha p_b\rho_{bd}+12p_b^3-4p_b^2 \rho_{bd} -3p_b^2 +6p_b\rho_{bd} -3\rho_{bd}^2}{16p_b^2} \end{aligned}
\end{equation*}
\notag
$$
(см. рабочий лист Maple). Функция $Q$ квадратичная и вогнутая по $\rho_{bd}$, причем, как и ранее, $\rho_{bd}\leqslant p_bp_d= p_b(1-\alpha-p_b)$ в силу того, что $D \cap C = \varnothing$. Более того,
$$
\begin{equation*}
\left.\frac{\partial Q}{\partial \rho_{bd}}\right|_{\rho_{bd}=p_bp_d} = \frac{p_b-\alpha}{8p_b}\geqslant 0.
\end{equation*}
\notag
$$
Следовательно,
$$
\begin{equation*}
\begin{aligned} \, Q(\alpha,p_b,\rho_{bd})&\leqslant Q(\alpha,p_b,p_b(1-\alpha-p_b)) \\ &= \frac{13}{16}\alpha^2 - \frac 98\alpha p_b-\frac 3{16}p_b^2 - \frac 14\alpha +\frac 12p_b \stackrel{\mathrm{def}}{=} Q_1(\alpha,p_b). \end{aligned}
\end{equation*}
\notag
$$
Наконец, функция $Q_1$ квадратичная и вогнутая по $p_b$ и
$$
\begin{equation*}
\frac{\partial Q_1}{\partial p_b}\bigg|_{p_b=\alpha} = \frac{1-3\alpha}2<0
\end{equation*}
\notag
$$
(так как $\alpha\geqslant 3/8$). Поскольку $p_b\geqslant \alpha$, получаем
$$
\begin{equation*}
Q_1(\alpha,p_b)\leqslant Q_1(\alpha,\alpha) =\frac{\alpha}{2}\biggl(\frac12-\alpha\biggr).
\end{equation*}
\notag
$$
Теорема 3.6 доказана. 4.6. Графы обхвата ${\geqslant}\,5$В этом пункте докажем теорему 3.8, причем именно в этом доказательстве мы обратимся к мощностям рассматриваемых множеств вместо их плотностей. Причина в том, что условие на обхват не выдерживает раздутия графа, что делает язык плотностей неестественным. Итак, фиксируем такой граф $G$ без треугольников, что $g(G)\geqslant 5$, $|V(G)|=n$, и берем вершину $v_0\in V(G)$ наибольшей степени $k$. Можно считать, что $k\leqslant (n-1)/2$ (иначе утверждение тривиально), а также что $G$ является минимальным контрпримером к гипотезе Эрдёша, т.е. что $\beta(G^\ast)\leqslant1/{50}$ для каждого собственного порожденного подграфа $G^\ast$ графа $G$. Положим
$$
\begin{equation*}
A\stackrel{\mathrm{def}}{=} N_G(v_0), \qquad B\stackrel{\mathrm{def}}{=} V(G)\setminus (\{v_0\}\cup A).
\end{equation*}
\notag
$$
Тогда из $g(G)\geqslant 5$ вытекает, что Теперь применим предположение о минимальности к порожденному подграфу $G|_B$. Это дает функцию $\nu\colon B\longrightarrow[0,1]$ такую, что
$$
\begin{equation}
\begin{cases} \displaystyle \sum_{v\in B} \nu(v) = \frac{n-k-1}2, \\ \displaystyle \sum_{(u,v)\in E(B)} \nu(u)\nu(v) \leqslant \frac{(n-k-1)^2}{50}. \end{cases}
\end{equation}
\tag{16}
$$
Используем ее для определения вершинного полуграфа $\mu$ во всем графе $G$ следующим образом:
$$
\begin{equation*}
\mu(v) \stackrel{\mathrm{def}}{=} \begin{cases} 0&\text{при}\ v=v_0, \\ 1&\text{при}\ v\in A, \\ p\nu(v)&\text{при}\ v\in B, \end{cases}
\end{equation*}
\notag
$$
где Тогда имеем
$$
\begin{equation}
\beta(G,\mu) \leqslant \frac 1{n^2}\biggl(\frac{(n-2k)^2}{50} + \sum_{(u,v)\in E(A,B)}\mu(u)\mu(v)\biggr).
\end{equation}
\tag{17}
$$
Мы задействуем два разных метода оценки суммы $\sum_{(u,v)\in E(A,B)}\mu(u)\mu(v)$. Прежде всего, в силу (15) имеем
$$
\begin{equation*}
\sum_{(u,v)\in E(A,B)}\mu(u)\mu(v) \leqslant \sum_{v\in B} \mu(v)=\frac n2-k,
\end{equation*}
\notag
$$
откуда получаем
$$
\begin{equation}
\begin{aligned} \, \notag \beta(G,\mu) & \leqslant \frac 1{n^2} \biggl(\frac{(n-2k)^2}{50} + \frac n2-k\biggr) \\ & = \frac 1{50} - \frac 1{5n^2} \biggl(n(4k-25) +50k-4k^2\biggr). \end{aligned}
\end{equation}
\tag{18}
$$
Теперь рассмотрим два случая. Случай 1: $k\geqslant 7$. В данном случае, поскольку $n\geqslant 2k+1$, имеем
$$
\begin{equation*}
n(4k-25) +50k-4k^2\geqslant (2k+1)(4k-25) +50k-4k^2 = 4k^2+4k-25\geqslant 0,
\end{equation*}
\notag
$$
чего в силу (18) достаточно. Случай 2: $k\leqslant 6$. Теперь то же самое условие $n(4k\,{-}\,25)\,{+}\,50k\,{-}\,4k^2\,{<}\,0$ (которое можно считать выполненным без ограничения общности) дает новую нижнюю оценку на $n$:
$$
\begin{equation}
n\geqslant \biggl\lceil {\frac{2k(25-2k)}{25-4k}}\biggr\rceil.
\end{equation}
\tag{19}
$$
Чтобы ограничить $n$ сверху, мы оценим сумму $\sum_{(u,v)\in E(A,B)}\mu(u)\mu(v)$ числом $(k-1)k$ просто потому, что степень каждой вершины из $A$ не превосходит $k$ и все они смежны с $v_0\not\in B$. Таким образом,
$$
\begin{equation*}
\beta(G,\mu) \leqslant \frac 1{n^2} \biggl(\frac{(n-2k)^2}{50} + (k-1)k\biggr) =\frac 1{50} -\frac k{25n^2}(2n+25-27k).
\end{equation*}
\notag
$$
Поэтому можно также считать, что
$$
\begin{equation}
n \leqslant \biggl\lceil \frac{27}2(k-1) \biggr\rceil,
\end{equation}
\tag{20}
$$
чем сразу исключается случай $k=1$. Далее, неравенства (19) и (20) исключают случай $k=6$, что оставляет возможными лишь значения $k=2,3,4,5$ и $80$ допустимых значений пары $(k,n)$. Вместо того чтобы пытаться завершить анализ вручную, используем другую стратегию. А именно, мы запишем результаты наших рассуждений в виде “сырых” (причем рекурсивных) оценок, не пытаясь их упростить, а затем просто загрузим эти формулы в систему Maple для завершения работы. Для начала через
$$
\begin{equation*}
C\stackrel{\mathrm{def}}{=} V(G)\setminus (A\cup N_G(A))
\end{equation*}
\notag
$$
обозначим множество вершин, находящихся на расстоянии $\geqslant 3$ от $v_0$; заметим, что Пусть $R(3,u)$, где $u \neq 3$, – число Рамсея; мы используем лишь следующие хорошо известные небольшие значения этих чисел:
$$
\begin{equation*}
\begin{gathered} \, R(3,0)=0,\qquad R(3,1)=1,\qquad R(3,2)=3, \\ R(3,3)=6,\qquad R(3,4) = 9,\qquad R(3,5)=14. \end{gathered}
\end{equation*}
\notag
$$
Для каждого такого $u\in [ 0,\lceil n/2\,{-}\,k \rceil]$, что $R(3,u) \leqslant n\,{-}\,k\,{-}\,1$ ($=|B|$), мы получим отдельную оценку $\beta(G)\leqslant \beta_u$, а затем возьмем минимум по всевозможным значениям $u$. Пока же зададимся некоторым $u$ с указанными свойствами. Выберем подмножество $B_u\in \binom{B}{R(3,u)}$ с тем лишь ограничением, чтобы оно содержало как можно больше вершин из $C$. Тогда имеем
$$
\begin{equation}
|E(A, B_u)| = |B_u\setminus C| = R(3,u) \dot{-} |C| \leqslant R(3,u) \dot{-} (n-k^2-1),
\end{equation}
\tag{21}
$$
где $x \dot{-} y\stackrel{\mathrm{def}}{=} \max(0,x-y)$. Наконец, пусть $B_u'\subseteq B_u$ – независимое подмножество размера $u$, существующее в силу определения чисел Рамсея. Дальнейший анализ распадается еще на два случая. Случай 2.1: $u=\lceil n/2-k\rceil$. При четном $n$ возьмем полуграф $A\cup B_u'$. Если же $n$ нечетно, то можно без ограничения общности считать, что $B_u'\cap N_G(A) \neq \varnothing$ (ибо иначе все доказано). Пусть $\mu$ – полуграф, получающийся из $A\cup B_u'$ удалением “половины” вершины из множества $B_u'\cap N_G(A)$; это сберегает нам “половину” ребра. У нас есть две различные оценки на $|E(A, B_u')|$: одна следует из неравенства (21), но, с другой стороны, как и прежде, имеется тривиальная оценка $|E(A,B_u')| \leqslant n/2-k\leqslant u$, вытекающая из (15). В итоге
$$
\begin{equation}
\begin{gathered} \, \beta(G) \leqslant \beta_u\stackrel{\mathrm{def}}{=} \frac 1{n^2}\biggl(\min(u, R(3,u)- (n-k^2-1)) \dot{-} \frac 12 (n\bmod 2)\biggr), \\ u = \biggl\lceil \frac n2-k \biggr\rceil. \end{gathered}
\end{equation}
\tag{22}
$$
Подчеркнем, что эта оценка имеет смысл лишь при $R(3,\lceil n/2-k \rceil)\leqslant n-k-1$. Случай 2.2: $u<\lceil n/2-k\rceil$. В этом случае имеем2
$$
\begin{equation}
\beta(G) \leqslant \beta_u \stackrel{\mathrm{def}}{=} \gamma(k,n,k+u, \min(u, R(3,u) \dot{-} (n-k^2-1))),
\end{equation}
\tag{23}
$$
где функция $\gamma(k,n,t,e)$ (при $t\leqslant n/2$) отражает происходящее следующим образом:
$$
\begin{equation*}
\gamma(k,n,t,e) \stackrel{\mathrm{def}}{=} \max_{G,A} \min_{\mu|_A\equiv 1} \beta(G,\mu), \qquad t\leqslant \biggl\lfloor\frac n2 \biggr\rfloor.
\end{equation*}
\notag
$$
Здесь $G$ пробегает все графы с $n$ вершинами, для которых $\Delta(G)\leqslant k$, $A$ пробегает все множества вершин такие, что $|A|=t$ и $|E(A)|\leqslant e$, а $\mu$ пробегает все вершинные полуграфы, содержащие $A$. Остается получить достаточно хорошие (для наших целей) рекурсивные оценки на $\gamma$. Прежде всего, если $n$ четно и $t=n/2$, то ясно, что
$$
\begin{equation}
\gamma\biggl(k,n,\frac n2,e\biggr) = \frac e{n^2}, \qquad n\ \text{четное}.
\end{equation}
\tag{24}
$$
Далее, допустим, что $n$ нечетно и $t=(n-1)/2$. Возьмем наихудшие значения $G$ и $A$ и обозначим через $e^\ast\leqslant e$ число ребер в $G|_A$. Тогда в $|E(A, V(G)\setminus A)|$ будет не больше $kt-2e^\ast$ ребер. Поэтому найдется вершина $v\not\in A$, для которой
$$
\begin{equation}
|N_G(V)\cap A| \leqslant \biggl\lfloor\frac{kt-2e^\ast}{n-t}\biggr\rfloor.
\end{equation}
\tag{25}
$$
Добавляя к $A$ “половину” этой вершины, мы заключаем, что
$$
\begin{equation}
\gamma(k,n,t,e) \leqslant \max_{0\leqslant e^\ast\leqslant e} \frac 1{n^2} \biggl(e^\ast +\frac 12\biggl\lfloor \frac{kt-2e^\ast}{n-t}\biggr\rfloor\biggr), \qquad n\ \text{нечетное}, \quad t = \frac{n-1}2.
\end{equation}
\tag{26}
$$
Аналогично, при меньших значениях $t$ применим рекурсию, полагая $A:= A \cup \{v\}$, где $v$ – вершина, удовлетворяющая условию (25). Это дает нам
$$
\begin{equation}
\gamma(k,n,t,e) \leqslant \gamma\biggl(k,n,t+1,\max_{0\leqslant e^\ast\leqslant e}\biggl(e^\ast+ \biggl\lfloor \frac{kt-2e^\ast}{n-t}\biggr\rfloor\biggr), \qquad t< \biggl\lfloor \frac n2\biggr\rfloor.
\end{equation}
\tag{27}
$$
На этом заканчивается описание $\beta_u$ для случая 2.2. Теперь “основная формула” выглядит так:
$$
\begin{equation}
\beta(G) \leqslant \min\biggl\{\beta_u\biggm| 0\leqslant u\leqslant \biggl\lceil \frac n2-k\biggr\rceil \land R(3,u)\leqslant n-k-1\biggr\}.
\end{equation}
\tag{28}
$$
Неравенств (28), (22) и (23) вместе с рекурсивными оценками (24), (26) и (27) на вспомогательную функцию $\gamma$ достаточно, чтобы завершить анализ $80$ остающихся случаев (см. подробности в рабочем листе Maple). Теорема 3.8 доказана. § 5. ЗаключениеВ настоящей работе мы установили несколько частных результатов, касающихся гипотезы Эрдёша о вершинных полуграфах. Хотя они еще сильнее увеличивают правдоподобие гипотезы, она остается открытым вопросом. То же верно и для последней из гипотез Эрдёша в данной области: показать, что любой граф без треугольников на $n$ вершинах можно превратить в двудольный, удалив не более ${n^2}/{25}$ ребер. В качестве промежуточной и, вероятно, более доступной цели мы бы предложили распространить теорему 3.6 на окрестность критического значения $\alpha = 2/5$, т.е. доказать гипотезу о вершинных полуграфах для таких графов $G$ без треугольников, что $\alpha(G)\geqslant 2/5-\varepsilon$ при некотором фиксированном $\varepsilon>0$. Как отмечалось выше, подобные улучшения известны для наименьшей степени и для средней степени (см. [18], [19]). Мы выделили экстремальную задачу нахождения наименьшей плотности четырехугольников в графах без треугольников с заданной реберной плотностью и дали ее приложения к задаче о разреженном вершинном полуграфе. Поскольку эту величину можно рассматривать (на самом деле в весьма точном смысле) как меру неслучайности в графе, быть может, она сама по себе заслуживает изучения. БлагодарностиЯ хочу выразить признательность Анджею Гжесику и Яну Волецу, указавшим работы [13], [17] и сообщившим мне альтернативное рассуждение, набросок которого приведен в конце п. 4.4.
Цитирование в формате AMSBIB
\RBibitem{Raz22} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|