| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) Оценки числа ребер в подграфах графов Джонсона Е. А. Неустроеваa, А. М. Райгородскийabcd a Московский физико-технический институт (национальный исследовательский университет), Московская облаcть, г. Долгопрудный b Московский государственный университет им. М. В. Ломоносова c Кавказский математический центр, Адыгейский государственный университет, г. Майкоп d Бурятский государственный университет, Институт математики и информатики, г. Улан-Удэ
Англоязычная версия:
Mathematical Notes, 2024, Volume 115, Issue 2, Pages DOI: https://doi.org/10.1134/S0001434624010218 
Реферативные базы данных:
  1. ВведениеВ данной работе мы рассматриваем дистанционные графы – графы, в которых вершинам соответствуют точки в $n$-мерном пространстве, а ребрами связываются вершины, находящиеся на одинаковом фиксированном расстоянии. Графы Джонсона $G(n, r, s)$ могут служить примером дистанционных графов в $\mathbb{R}^n$. Они определяются следующим образом: фиксируется $n$-элементное множество, в качестве вершин выбираются все его $r$-элементные подмножества, а ребрами соединяются вершины, соответствующие подмножествам, пересекающимся по $s$ элементам. Эквивалентным приведенному выше комбинаторному определению является следующее: рассматривается граф, вершинами которого являются точки в $n$-мерном булевом кубе, а ребро между вершинами проводится в том и только том случае, когда скалярное произведение векторов, соответствующих вершинам, равно $s$. Второе определение как раз подчеркивает, что такой граф является дистанционным. Изучение графов Джонсона важно, поскольку эти графы находят применение во многих разделах комбинаторики: они используются в нахождении оценок хроматического числа $n$-мерного пространства (см. [1]–[4]), с их помощью был построен контрпример к гипотезе Борсука (см. [5], [6]). Графы $G(n, r, s)$ используются при изучении кодов с запрещенными расстояниями (cм. [7], [8]), задач теории Рамсея (см. [9]–[11]), а также интерес представляют их спектральные свойства [12]. Напомним, что независимым множеством вершин графа $G$ называется такое подмножество вершин $G$, что никакие две из них не соединены ребром. Размер наибольшего независимого множества вершин графа $G$ называется его числом независимости и обозначается $\alpha(G)$. Мы будем изучать число ребер в индуцированных подграфах графов Джонсона, что важно, например, для теории экспандеров (см. [13], [14]). Обозначим $\rho_G(W)$ число ребер в подграфе графа $G=(V, E) $, индуцированном множеством вершин $W \subset V$. Иными словами,
$$
\begin{equation*}
\rho_G(W)=\bigl|\{ (x, y) \in E\mid x, y \in W\}\bigr|.
\end{equation*}
\notag
$$
Также положим В серии работ Шубина [15] и Пушнякова [16], [17] получен следующий результат для графов $G(n, 3, 1)$. Теорема 1. Для серии графов $G(n, 3, 1)$ верны следующие утверждения: 1) если функция $l=l(n)$ такова, что $n=o(l), l=o(n^2)$, то 2) если функция $l=l(n)$ такова, что $n^2=o(l)$, то Видно, что в теореме 1 не исследованы случаи, когда $l=O(n)$ и $l=O(n^2)$. В настоящей работе мы сосредоточились на изучении второго случая и исследуем граф $G(n, 3, 1)$ и $\rho_{G(n, 3, 1)}(l)$ при $l=[cn^2]$ для $c \in [0, 1]$. Отметим, что в общем случае задача для графов $G(n, r, s)$ также исследовалась в работах Пушнякова, Шубина и Дубинина [15]–[18]. 2. Известные результатыПрежде всего заметим, что в работе [9] Надем найдено число независимости графа $G(n, 3, 1)$. Утверждение 1 [9]. Справделиво равенство Помимо этих точных значений будем использовать следующую удобную оценку. Классическая теорема Турана дает способ получить оценку числа ребер в графе с известным ограничением числа независимости. Теорема 2. Для любого графа $G$ с числом независимости $\alpha$ и любого $l > \alpha$ выполняется неравенство В силу оценки числа независимости графа $G(n, 3, 1)$, приведенной в утверждении 2, следующая теорема является простым следствием теоремы Турана, поскольку число независимости графа не меньше, чем число независимости любого его индуцированного подграфа. В общем случае оценка, полученная при помощи теоремы Турана, неулучшаема, но, воспользовавшись спецификой рассматриваего графа, ее можно улучшить. Значительное улучшение было сделано Шубиным в работе [15], где была доказана Понятно, что если в теореме 4 величина $ c $ очень большая, то оценка из теоремы 4 практически неулучшаема (ср. п. 2 из теоремы 1). Однако при $c$ близких к нулю эта оценка теряет смысл, становясь отрицательной. В следующем пункте мы приведем результаты, которые для многих $c \in [0, 1]$ улучшают теоремы 3 и 4. 3. Формулировки результатов работыЗаметим, что все упомянутые оценки $\rho_{G(n, 3, 1)}([cn^2])$ имеют вид $(1+o(1))f(c)n^3$. Поэтому сравнивать стоит сами функции $f(c)$ в тех точках $[0, 1]$, где они определены. Оценка из теоремы 3 дает $f_1(c)={c^2}/{2}$. Улучшение, зафиксированное в теореме 4, дает $f_2(c)={9c^2}/{2}-3c$. Наконец, теорема 5 добавляет к сравнению
$$
\begin{equation*}
f_3(c)=\frac{c^2}{2}+\frac{4}{3}\biggl(\frac{c-1/8}{2}\biggl)^{3/2},
\end{equation*}
\notag
$$
а теорема 6 дает $f_4(c)=c^2-1/96$. Проиллюстрируем поведение оценок графиком (рис. 1). Получается, что оценки из теорем 5, 6 опережают оценку Турана при всех $c \in (1/8, 1]$. Оценка из теоремы 6 при $c \geqslant 1/4$ действительно лучше, чем оценка в теореме 5, причем в точке $c=1/4$ имеем $f_3(c)=f_4(c)= 5/96$. Влоть до $c \approx 0.8537$ новые оценки опережают оценку Шубина. При больших значениях параметра эта оценка значительно опережает новые. 4. Доказательства теорем 5, 6Начало доказательства обеих теорем будет одинаковым. Положим $l=[cn^2]$. Возьмем произвольное подмножество $L$ вершин графа $G(n, 3, 1)$ мощности $l$. Выделим в нем $B_1$ – максимальное независимое множество, его мощность обозначим $\beta_1$. Из оставшихся вершин рассмотрим те, каждая из которых смежна ровно с одной вершиной $B_1$. Они образуют множество $K_1$ мощности $k_1$. Отметим, что каждая вершина из $L \setminus(B_1 \cup K_1)$ смежна хотя бы с двумя вершинами из $B_1$. Между вершинами из $B_1$ и вершинами из $K_1$ проведено ровно $k_1$ ребер, между вершинами из $B_1$ и вершинами из $L \setminus (B_1 \cup K_1)$ – хотя бы $2(l-\beta_1-k_1$) ребер. Уберем из графа множество $B_1$ со всеми инцидентными ему ребрами, которых не менее чем $2(l-\beta_1)-k_1$. Повторим это действие еще $T-1$ раз, где $T$ мы выберем позднее. Получается, на $i$-м шаге выделяем максимальное независимое множество $B_{i}$ мощности $\beta_{i}$ и $K_{i}$ – множество вершин, каждая из которых связана ровно с одной вершиной из $B_{i}$, $|K_i|= k_{i}$. Перед $i$-м шагом в подграфе будет оставаться $l-\sum_{j=1}^{i-1}\beta_j$ вершин. На самом $i$-м шаге извлечем из графа хотя бы $2(l-\sum_{j=1}^{i}\beta_j)-k_i$ ребер. Просуммируем количества извлеченных ребер по $T$ шагам. Получим
$$
\begin{equation*}
\begin{aligned} \, & \sum_{i=1}^{T}\biggl(2\biggl(l-\sum_{j=1}^{i}\beta_j\biggr)-k_i\biggr)= 2lT-2\cdot\sum_{i=1}^{T}\sum_{j=1}^{i}\beta_j-\sum_{i=1}^{T} k_i \\ &\qquad =2lT-\sum_{i=1}^{T}\bigl(2(T-i+1) \beta_i+k_i\bigr). \end{aligned}
\end{equation*}
\notag
$$
Заметим, что $\beta_i \leqslant \alpha(G(n, 3, 1)) \leqslant n$, поэтому $l/n$ шагов точно могло быть, но большее число не гарантируется. После $T$ шагов в графе осталось не менее $l-nT$ вершин. Для оценки числа ребер на этих вершинах применим теорему 3. Положим
$$
\begin{equation*}
t=t(l-nT)= \begin{cases} \dfrac{n}{2}\biggl[\dfrac{l-nT}{n}\biggr]\biggl(\biggl[\dfrac{l-nT}{n}\biggr]-1\biggr), &\text{если }\ l-nT > n, \\ 0, & \text{если }\ l-nT \leqslant n. \end{cases}
\end{equation*}
\notag
$$
Значит,
$$
\begin{equation*}
\rho_{G(n, 3, 1)}(l) \geqslant (1+o(1))\biggl(t+2lT-\sum_{i=1}^{T}\bigl(2(T-i+1) \beta_i+ k_i\bigr)\biggl).
\end{equation*}
\notag
$$
Заметим, что $T \leqslant l/n=O(n)$. Тогда верно Действительно, в случае $l-nT > n$ выполняется неравенство
$$
\begin{equation*}
\begin{aligned} \, t &\geqslant \frac{n}{2}\biggl(\frac{l-nT}{n}-1\biggr)\biggl(\frac{l-nT}{n}-2\biggr) \\ &=\frac{(l-nT)^2}{2n}- \frac{3(l-nT)}{2}+n=\frac{(l-nT)^2}{2n}+O(n^2). \end{aligned}
\end{equation*}
\notag
$$
В случае же $l-nT \leqslant n$ выполняется Таким образом, предыдущую оценку можно записать в виде
$$
\begin{equation*}
\rho_{G(n, 3, 1)}(l) \geqslant (1+o(1))\biggl(\frac{(l-nT)^2}{2n}+2lT-\sum_{i= 1}^{T}\bigl(2(T-i+1) \beta_i+k_i\bigr)\biggl)+O(n^2).
\end{equation*}
\notag
$$
Теперь найдем связь между $k_i$ и $\beta_i$ для прозвольного $i$. Лемма 1. Для любого $i \in [1,\dots, T]$ выполняется или $\beta_i+2k_i/\beta_i \leqslant n$, или $k_i \leqslant 6\beta_i$. Доказательство. Поскольку в $B_i$ – максимальном независимом множестве – $\beta_i$ вершин, а в множестве вершин, связанных с ним по одному ребру, $k_i$ элементов, в $B_i$ найдется вершина $v$, связанная с по крайней мере ${k_i}/{\beta_i}$ вершинами из $K_i$. Пуcть вершины из $K_i$, с которыми соединена $v$, – это $v_1, v_2, \dots, v_d$, $d \geqslant k_i/\beta_i$.
Заметим, что различные вершины $v_i$ и $v_j$ обязательно должны быть связаны ребром, иначе можно было бы заменить в максимальном независимом множестве $v$ на $v_i$ и $v_j$ и тем самым его увеличить, что противоречит его максимальности. Таким образом, $v, v_1, \dots, v_d$ образуют клику. Если $d+1 \leqslant 7$, то ${k_i}/{\beta_i} \leqslant d \leqslant 6$, т.е. $k_i \leqslant 6\beta_i$. В противном случае найденная клика содержит хотя бы $8$ вершин, значит, имеет вид “звезды”: без ограничения общности, все ее вершины имеют вид $\{1, 2k, 2k+1\}$, где $k=1, 2, \dots, d+1$. Последнее утверждение является несложным упражнением, которое решается путем перебора нескольких случаев. В $B_i$ лежат вершины, не соединенные ни с вершинами из клики, ни между собой. Рассмотрим такую вершину $u=\{a, b, c\}$, $a < b < c$. Если все три элемента из $\{1, 2, \dots, 2d+3\}$ и $a=1$, то найдется вершина клики, пересекающаяся с $u$ только по 1, т.е. соединенная c ней ребром. Если, опять же, все элементы из $\{1, 2, \dots, 2d+ 3\}$, $a \neq 1$, то найдется вершина клики, пересекающаяся с $u$ по одному элементу, т.е. соединенная с ней ребром. По той же причине среди $\{a, b, c\}$ не может быть ровно одного элемента из $\{1, 2, \dots, 2d+3\}$. Если ровно $2$ элемента тройки ${a, b, c}$ из множества $\{1, 2, \dots, 2d+3\}$, $a \neq 1$, то это $a=2k$, $b=2k+1$, при этом $c > 2d+3$. У всех таких троек должны быть разные элементы $c$, так как если у двух троек один и тот же элемент $c$, то они или совпадают, или пересекаются только по нему, т.е. связаны ребром. Пусть вершин такого типа $\gamma$. Оставшиеся вершины не связаны между собой, а элементы, из которых они состоят, образуют подмножество $\{1, 2, \dots, n\}$ размера $n-2d-3-\gamma$, а значит, по утверждению 2 этих вершин не более $n-2d-3-\gamma$. Посчитаем теперь все вершины $B_i$, кроме $v$. Мы знаем, что $\beta_i-1 \leqslant \gamma+n- 2d-3-\gamma$, откуда следует, что $\beta_i+2d+2 \leqslant n$, т.е. $\beta_i+ 2k_i/\beta_i \leqslant n$, что и требовалось. Теперь оценим величины $2(T-i+1)\beta_i+k_i$ сверху, принимая во внимание ограничение $T \leqslant l/n$ и результат предыдущей леммы. Доказательство. Обозначим $A=2(T-i-1)\beta_i+k_i$.
Из леммы 1 при фиксированном $\beta_i$ выполняется или $k_i \leqslant 6\beta_i$, или $k_i \leqslant (n\beta_i-\beta_i^2)/2$. В первом случае
$$
\begin{equation*}
A \leqslant 2(T-i+4)\beta_i \leqslant 2(T-i)n+O(n) \leqslant \frac{(2(T-i+1)+n/2)^2}{2}+O(n).
\end{equation*}
\notag
$$
Во втором случае
$$
\begin{equation*}
A \leqslant-\frac{\beta_i^2}{2}+\beta_i\biggl(2(T-i+1)+\frac{n}{2}\biggr) \leqslant \frac{(2(T-i+1)+n/2)^2}{2}.
\end{equation*}
\notag
$$
Последний переход сделан на основе того, что максимум квадратичной по $\beta_i$ функции достигается при $\beta_i=2(T-i+1)+n/2$.
Мы получили требуемую оценку. Доказательство. Отличие будет состоять в том, что при $i \leqslant T-n/4+1$ будет выполнено неравенство $2(T-i+1)+n/2 \geqslant n$, т.е. или оптимальное значение $\beta_i$ не может достигаться в силу утверждения 2, или $n$ – оптимальное значение. В любом случае максимум выражения $- \beta_i^2/2+\beta_i(2(T-i+1)+n/2)$ будет достигаться при максимальном возможном допустимом $\beta_i=n$, т.е. будет справедлива оценка что и требовалось. Завершим доказательство теоремы 5. Доказательство. Как уже было доказано,
$$
\begin{equation*}
\rho_{G(n, 3, 1)}(l) \geqslant (1+o(1))\biggl(\frac{(l-nT)^2}{2n}+2lT-\sum_{i= 1}^{T}\bigl(2(T-i+1) \beta_i+k_i\bigr)\biggl)+O(n^2).
\end{equation*}
\notag
$$
Воспользуемся оценкой из леммы 2. Таким образом,
$$
\begin{equation*}
\begin{aligned} \, &\rho_{G(n, 3, 1)}(l) \\ &\qquad\geqslant (1+o(1))\biggl(\frac{(l-nT)^2}{2n}+2lT-\sum_{i= 1}^{T}\frac{(2(T-i+1)+n/2)^2}{2}+T\cdot O(n)\biggl)+O(n^2) \\ &\qquad=(1+o(1))\biggl(2lT+\frac{l^2}{2n}-lT+\frac{nT^2}{2} \\ &\qquad\qquad -2\sum_{i=1}^{T} (T-i+1)^2- n\sum_{i=1}^{T} (T-i+1)-\frac{Tn^2}{8}\biggl)+O(n^2) \\ &\qquad=(1+o(1))\biggl(lT+\frac{l^2}{2n}+\frac{nT^2}{2}-2\sum_{i=1}^{T}i^2-n\sum_{i= 1}^{T} i-\frac{Tn^2}{8}\biggl)+O(n^2) \\ &\qquad=(1+o(1))\biggl(\frac{l^2}{2n}+lT+\frac{nT^2}{2}-\frac{T(T\,{+}\,1)(2T\,{+}\,1)}{3}- \frac{nT(T\,{+}\,1)}{2}-\frac{Tn^2}{8}\biggl)+O(n^2) \\ &\qquad=(1+o(1))\biggl(\frac{l^2}{2n}+lT+\frac{nT^2}{2}-\frac{2T^3}{3}-\frac{nT^2}{2}- \frac{Tn^2}{8}-T^2-\frac{nT}{2}\biggl)+O(n^2) \\ &\qquad=(1+o(1))\biggl(- \frac{2T^3}{3}+T\biggl(l-\frac{n^2}{8}\biggr)+\frac{l^2}{2n} \biggl)+ O(n^2). \end{aligned}
\end{equation*}
\notag
$$
Осталось подобрать оптимальное количество шагов.
Максимум выражения
$$
\begin{equation*}
- \frac{2T^3}{3}+T\biggl(l-\frac{n^2}8\biggr)+\frac{l^2}{2n}
\end{equation*}
\notag
$$
будет достигаться в нуле его производной по $T$, т.е. при $T=\sqrt{(l- n^2/8)2}$. Асимтотически такие же, как и при максимуме, значения будут достигаться при $T\sim \sqrt{(l-n^2/8)/2}$ и, в частности, при $T=[\sqrt{(l-n^2/8)/2}]-1$.
Проверим, что подобранное значение допустимо при достаточно больших $n$, т.е. во-первых, $l \geqslant n^2/8$ и, во-вторых,
$$
\begin{equation*}
\biggl[\sqrt{\frac{l-n^2/8}{2}}\biggr]-1 \leqslant \frac{l}{n}.
\end{equation*}
\notag
$$
Первое выполняется, поскольку $l=[cn^2]$ и $c > 1/8$. Второе же условие следует из Подставляя $l=[cn^2]$, получим
$$
\begin{equation*}
\frac{[cn^2]^2}{n^2}-\frac{[cn^2]-n^2/8}{2} \geqslant 0,
\end{equation*}
\notag
$$
что равносильно $16[cn^2]^2-8n^2[cn^2]+n^4 \geqslant 0$. Последнее верно, поскольку
$$
\begin{equation*}
\begin{aligned} \, 16[cn^2]^2-8n^2[cn^2]+n^4 &=16(cn^2+O(1))^2-8n^2(cn^2+O(1))+n^4 \\ &=n^4(16c^2- 8c+1)+ O(n^2)=n^4(4c-1)^2+O(n^2) \geqslant 0, \end{aligned}
\end{equation*}
\notag
$$
где последнее неравенство выполнено для достаточно больших $n$ при $c \neq 1/4$.
В случае $c=1/4$ при достаточно больших $n$ будет выполняться цепочка неравенств
$$
\begin{equation*}
\biggl[\sqrt{\frac{[cn^2]-n^2/8}{2}}\biggr]-1 \leqslant \biggl[\sqrt{\frac{n^2/4-n^2/8}{2}}\biggr]-1 \leqslant \frac{n}{4}-1 \leqslant \frac{[cn^2]}{n},
\end{equation*}
\notag
$$
что доказывает допустимость выбора $T$ в оставшемся случае.
Таким образом, оптимален выбор $T \sim n\sqrt{(c-1/8)/2}$, что дает оценку
$$
\begin{equation*}
\begin{aligned} \, \rho_{G(n, 3, 1)}(l) &\geqslant (1+o(1))\biggl(-\frac{2}{3}\biggl(\frac{c- 1/8}{2}\biggr)^{3/2}+\biggl(\frac{c- 1/8}{2}\biggr)^{1/2}\biggl(c-\frac{1}{8}\biggr)+\frac{c^2}{2}\biggl)n^3+ O(n^2) \\ &=(1+o(1))\biggl(\frac{c^2}{2}+\frac{4}{3}\biggl(\frac{c- 1/8}{2}\biggr)^{3/2}\biggl)n^3 , \end{aligned}
\end{equation*}
\notag
$$
что и требовалось. Теперь завершим доказательство теоремы 6. Отличие от предыдущего доказательства будет заключаться в том, что при достаточно большом количестве шагов часть слагаемых вида $2(T-i- 1)\beta_i-k_i$ благодаря лемме 3 можно оценить сильнее, чем ранее. Доказательство. Теперь рассматриваем случай $c \in (1/4, 1]$, $l=[cn^2]$.
Будем подбирать $T$ таким образом, чтобы выполнялось неравенство $n/4 < T \leqslant l/n$. В силу доказанного выше верна оценка
$$
\begin{equation*}
\rho_{G(n, 3, 1)}(l) \geqslant (1+o(1))\biggl(\frac{(l-nT)^2}{2n}+2lT-\sum_{i= 1}^{T}\bigl(2(T-i+1) \beta_i+k_i\bigr)\biggl)+O(n^2).
\end{equation*}
\notag
$$
Так как выполняется неравенство $n/4 < T$, мы можем разбить слагаемые на две части: $1 \leqslant i \leqslant [T-n/4+1]$ и $ [T-n/4+2] \leqslant i$. Слагаемые, соответствующие первой группе шагов, оценим с помощью леммы 3, а слагаемые, соответствующие второй группе шагов, – с помощью леммы 2. Получаем следующую оценку:
$$
\begin{equation*}
\begin{aligned} \, &\rho_{G(n, 3, 1)}(l) \geqslant (1+o(1))\biggl(2lT+\frac{l^2}{2n}-lT+\frac{nT^2}{2}- \sum_{i=1}^{[T-n/4+1]}(2n(T-i)+O(n)) \\ &\qquad\qquad -\sum_{i=[T-n/4+ 2]}^{T}\frac{(2(T-i+1)+n/2)^{2}}{2}+O(nT)\biggl)+O(n^2) \\ &\qquad=(1+o(1))\biggl(lT+\frac{l^2}{2n}+\frac{nT^2}{2}-\sum_{j=\lceil n/4\rceil- 1}^{T-1}(2nj+O(n)) \\ &\qquad\qquad -\sum_{i=[T-n/4+2]}^{T}\frac{(2(T-i+1)+n/2)^2}{2}+O(n^2)\biggl) \\ &\qquad=(1+o(1))\biggl(lT+\frac{l^2}{2n}+\frac{nT^2}{2}-nT^2+ n\cdot\biggl(\frac{n}{4}\biggr)^2-\sum_{j=1}^{\lceil n/4\rceil-1}\frac{(2j+ n/2)^{2}}{2}+O(n^2)\biggl) \\ &\qquad=(1+o(1))\biggl(lT+\frac{l^2}{2n}-\frac{nT^2}{2}+\frac{n^3}{16} - \frac{2}{3}\cdot\biggl(\frac{n}{4}\biggr)^3-\frac{n}{2}\cdot\biggl(\frac{n}{4}\biggr)^2- \frac{n}{4}\cdot\frac{n^2}{8}+O(n^2)\biggl) \\ &\qquad=(1+o(1))\biggl(lT+\frac{l^2}{2n}-\frac{nT^2}{2} -\frac{n^3}{96}+O(n^2)\biggl). \end{aligned}
\end{equation*}
\notag
$$
Подберем теперь оптимальное значение параметра $T$. Максимум достигается в нуле производной квадратичной по $T$ функции, т.е. при $T=l/n > n/4$. Целое $T= [l/n]$ при достаточно больших $n$ тоже будет больше $n/4$ и даст асимптотически такую же оценку. Подставляя $l=[cn^2]$, получим требуемое: 
Цитирование в формате AMSBIB
\RBibitem{NeuRai24} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|