| Математический сборник |
|
|
|
|
|
Логическая сложность свойства наличия индуцированного подграфа, изоморфного данному, для некоторых семейств графов М. Е. Жуковскийab, Е. Д. Кудрявцевc, М. В. Макаровc, А. С. Шлычковаc a Лаборатория продвинутой комбинаторики и сетевых приложений, Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл. b Московский центр фундаментальной и прикладной математики c Московский физико-технический институт (национальный исследовательский университет), г. Долгопрудный, Московская обл.
Англоязычная версия:
Sbornik: Mathematics, 2021, Volume 212, Issue 4, Pages DOI: https://doi.org/10.1070/SM9259 
Реферативные базы данных:
     § 1. ВведениеРассмотрим логику первого порядка (см. [1]–[3]) $\mathscr{F}$ над множеством конечных графов с сигнатурой, состоящей из двух предикатных символов $\sim, =$, обозначающих смежность вершин и равенство соответственно (оба предиката имеют арность 2). Под свойствами графов мы будем подразумевать такие множества графов, что любой класс изоморфизма либо принадлежит множеству целиком, либо вообще его не пересекает. Иными словами, если граф $G$ обладает некоторым свойством, то и любой изоморфный ему граф тоже обладает этим свойством. Будем говорить, что предложение $\varphi$ выражает свойство графов $\mathscr{C}$, если истинность предложения равносильна обладанию свойством. Иными словами, для любого графа $G$ выполнено
$$
\begin{equation*}
G\models\varphi\quad\Longleftrightarrow\quad G\in\mathscr{C}.
\end{equation*}
\notag
$$
В этой работе мы будем рассматривать свойство графов $\mathscr{C}[F]$ содержать индуцированный подграф, изоморфный данному графу $F$ (граф $H$ называется индуцированным подграфом графа $G$, если множество вершин графа $H$ является подмножеством множества вершин графа $G$, а множество ребер индуцировано этим множеством вершин, т.е. любые две вершины $u,v$ графа $H$ смежны в $H$ тогда и только тогда, когда они смежны в $G$). Такие свойства представляют большой интерес как c теоретической точки зрения, так и для различных приложений. Отметим отдельно, что если бы свойство $\mathscr{C}[K_{\ell}]$ ($K_{\ell}$ – это полный граф на $\ell$ вершинах) проверялось бы за $n^{o(\ell)}$ для $n$-вершинных графов, то неверна была бы гипотеза об экспоненциальном времени (см. [4]). Наш интерес к рассмотрению свойств $\mathscr{C}[F]$ в контексте логической сложности обусловлен именно временн\’ой сложностью проверки этого свойства. Более формально, для графа $F$ обозначим через $D[F]$ минимальную кванторную глубину (под кванторной глубиной формулы подразумевается наибольшая длина последовательности вложенных кванторов в этой формуле; строгое определение см., например, в [2], [3]) предложения из $\mathscr{F}$, выражающего свойство $\mathscr{C}[F]$. Например, формула
$$
\begin{equation*}
\exists\, x_1\, \exists\, x_2\, \exists\, x_3 \quad( x_1 \sim x_2 \land x_2 \sim x_3 \land x_1 \nsim x_3 \land x_1\neq x_3)
\end{equation*}
\notag
$$
записывает свойство содержать подграф, изоморфный $P_3$ (здесь и далее $P_{\ell}$ – это простой путь на $\ell$ вершинах), и имеет глубину 3. Поэтому $D[P_3] \leqslant 3$. Очевидно, для любого графа $F$ на $\ell$ вершинах существует тривиальная запись свойства $\mathscr{C}[F]$ с помощью формулы первого порядка, утверждающей существование $\ell$ различных вершин с заданными инцидентностями. Поэтому $D[F] \leqslant \ell$. Так как истинность формулы глубины $r$ на $n$-вершинном графе можно проверить за $O(n^r)$ (см. [3]), то и определить принадлежность $n$-вершинного графа множеству $\mathscr{C}[F]$ можно за $O(n^{D[F]})$. Этот факт мотивирует интерес к нахождению величины $D[F]$ для произвольного графа $F$. Заметим, что, насколько нам известно, наилучшей верхней оценкой на сложность проверки $\mathscr{C}[F]$ в общем случае (для произвольного графа $F$ на $\ell$ вершинах) является $O(n^{\omega\ell/3+O(1)})$ (см. [5], [6]), где $\omega\in[2,2.373)$ – экспонента быстрого перемножения матриц (см. [7]). Заметим, что $O(1)$ в показателе, разумеется, не зависит от $\ell$. Возникает естественный вопрос, а существуют ли графы $F$ на $\ell$ вершинах, для которых $D[F]<\omega\ell/3$? К сожалению, этот вопрос остается открытым. Возможность положительного ответа обусловлена наилучшей известной нижней оценкой на $D[F]$ в общем случае (см. [8]):
$$
\begin{equation}
D[F]\geqslant\max\biggl\{\biggl\lfloor\frac{1}{2}\ell-2\log_2\ell+3\biggr\rfloor, \chi(F),\frac{e(F)}{\ell}+2\biggr\},
\end{equation}
\tag{1.1}
$$
где $\chi(F)$ – хроматическое число графа $F$, а $e(F)$ – количество ребер графа $F$. Действительно, легко видеть, что максимум из этих трех величин равен первой для почти всех графов (имеется в виду равномерное распределение на множестве всех графов, заданных на множестве вершин $\{1,\dots,\ell\}$, или, иными словами, биномиальный случайный граф $G(\ell,{1}/{2})$). Так, количество ребер в случайном графе сконцентрировано около среднего $C_\ell^2/2$, а хроматическое число близко к ${\ell}/(2\log_2\ell)$ (см. [9]). Тем не менее до настоящей работы был известен пример лишь одного графа (с точностью до реберного дополнения), для которого $D[F]$ меньше количества вершин графа $F$. Заметим, что задачи нахождения $D(F)$ и $D(\overline{F})$ (где $\overline{F}$ – реберное дополнение графа $F$) равносильны (т.е. $D(F)=D(\overline{F})$), так как если в формуле первого порядка, определяющей $\mathscr{C}[F]$, добавить отрицание перед каждым предикатом смежности, то полученная формула будет определять $\mathscr{C}[\overline{F}]$. Итак, из работы [8] известно, что для всех графов $F$ с количеством вершин $\ell\leqslant 4$ выполнено $D[F]=\ell$ тогда и только тогда, когда граф $F$ отличен от paw-граф (paw-граф – это треугольник с дополнительным ребром, исходящим из одной из вершин треугольника к четвертой вершине) и от его реберного дополнения (т.е. от дизъюнктного объединения вершины и $P_3$). Для этих двух “исключительных” графов на четырех вершинах $D[F]=3$. Заметим, наконец, что из (1.1), в частности, следует, что $D[K_{\ell}]=\ell$, так как $\chi(K_{\ell})=\ell$. Подробнее об истории этой задачи и о других смежных результатах можно прочитать, например, в [8], [10], [11]. В настоящей работе мы, во-первых, доказали, что существуют графы любого размера $\ell$, не меньшего 4, для которых $D[F]\leqslant \ell-1$. Более того, таких графов достаточно много: подобный граф $F$ можно получить из произвольного графа, добавив к нему дизъюнктно вершину и $P_3$. Кроме того, мы значительно расширили класс графов, для которых $D[F]=\ell$. Наконец, мы установили, что для всех графов на пяти вершинах $D[F]\geqslant 4.$ Поэтому если и существует граф $F$ на $\ell$ вершинах с $D[F]\leqslant \ell-2$, то $\ell\geqslant 6$. Формулировки описанных результатов и некоторые обсуждения приведены в § 2. В § 3 описан основной инструмент получения нижних оценок величины $D[F]$, который мы использовали. Параграфы 4–6 содержат доказательства результатов. А § 7 посвящен обсуждению открытых вопросов. § 2. Основные результатыНиже $A\sqcup B$ обозначает дизъюнктное объединение графов $A$ и $B$, $mA$ обозначает дизъюнктное объединение $m$ изоморфных копий графа $A$, а $K_1$ – граф без ребер, состоящий из всего одной вершины. Наконец, всюду ниже, как и выше, $\ell$ – количество вершин графа $F$. Теорема 1. Пусть $H$ – произвольный граф, $F= P_3\sqcup K_1\sqcup H$. Тогда $D[F] \leqslant \ell-1$. К сожалению, нам не удалось доказать, что эту оценку нельзя улучшить ни для каких графов $F$ обозначенного вида. Тем не менее если $H$ – пустой граф, то полученная оценка точна. Заметим, что, во-первых, граф из теоремы 2 является дизъюнктным объединением двудольных графов, а во-вторых, при удалении из него хотя бы одного ребра, получается граф, являющийся реберным дополнением к полному многодольному (с одной долей размера 2 и остальными размера 1). Поэтому в некотором смысле граф из теоремы 2 является наиболее простым дизъюнктным объединением различных двудольных графов. В случае же, если двудольные графы изоморфны, утверждение теоремы сразу становится неверным, а верен тривиальный результат $D[F]=\ell$. Более того, это верно даже для объединения одинаковых многодольных графов. Теорема 3. Пусть $n_1,\dots,n_k$ – натуральные числа, $\ell=m\sum_{i=1}^{k} n_k$, $F=mK_{n_1, \dots, n_k}$ – дизъюнктное объединение $m$ графов, изоморфных полному многодольному графу $K_{n_1, \dots, n_k}$ на $k$ долях, размеры которых равны $n_1, \dots, n_k$. Тогда выполнено равенство $D[F]=\ell$. Заметим, наконец, что теорема 1 позволяет лишь строить примеры графов $F$ на $\ell$ вершинах, для которых $D[F]\leqslant \ell-1$, но мы до сих пор не знаем, существуют ли графы $F$, для которых $D[F]\leqslant \ell-2$. Как было сказано во введении, для любого графа $F$ на не более чем четырех вершинах $D[F]\geqslant\ell-1$. Мы доказали, что то же самое верно и для графов на пяти вершинах, т.е. если $D[F]\leqslant \ell-2$, то $\ell\geqslant 6$. § 3. Игра Эренфойхта–ФраиссеОсновным средством в доказательстве теорем 2–4 служит теорема А. Эренфойхта, доказанная в 1960 г. в [12]. В этом параграфе мы сформулируем ее частный случай для графов. Прежде всего определим игру Эренфойхта–Фраиссе на двух графах $G,H$ с количеством раундов, равным $r$ (см., например, [1]–[3], [8], [9]). В каждом раунде Новатор выбирает ровно одну вершину в любом из графов, отличную от уже выбранных (если такая существует – иначе игра заканчивается). Консерватор следом в том же раунде должен выбрать вершину в другом графе, тоже отличную от уже выбранных. Если Консерватор не может этого сделать, то проигрывает. Если в каждом из графов хотя бы $r$ вершин (или одинаковое число вершин), то к концу игры выбраны вершины $x_1,\dots,x_r$ и $y_1,\dots,y_r$ в графах $G$ и $H$ соответственно (если в графах менее $r$ вершин, то выбрано меньшее число вершин, но это лишь меняет обозначение числа вершин и не влияет на дальнейшее описание, поэтому мы будем считать, что выбрано по $r$ вершин в каждом графе). Консерватор побеждает тогда и только тогда, когда отображение, переводящее $x_i$ в $y_i$, является изоморфизмом графов индуцированных на множества $\{x_1,\dots,x_r\}$ и $\{y_1,\dots,y_r\}$ (т.е. $x_i\sim x_j$ в $G$ тогда и только тогда, когда $y_i\sim y_j$ в $H$). Теорема 5 (А. Эренфойхт, см. [12]). Для любых двух графов $G$, $H$ и любого $r\in\mathbb{N}$ Консерватор имеет выигрышную стратегию в игре Эренфойхта–Фраиссе на графах $G,H$ в $r$ раундах тогда и только тогда, когда для любого предложения $\varphi\in\mathscr{F}$ кванторной глубины не более $r$ либо на $G$ и $H$ предложение $\varphi$ истинно, либо на обоих графах ложно. Теперь поясним, как эту теорему можно применять для получения нижних оценок величины $D[F]$. Предположим, что граф $G$ содержит индуцированный подграф, изоморфный $F$, а $H$ не содержит. Пусть, кроме того, Консерватор побеждает в игре на графах $G$ и $H$ в $r$ раундах. Тогда в силу теоремы 5 $D[F]\geqslant r+1$. Действительно, если бы существовала формула глубины $r$, выражающая свойство $\mathscr{C}[F]$, то тогда бы она различала графы $G$ и $H$, а это противоречило бы теореме. § 4. Графы, для которых существует запись эффективнее тривиальной4.1. Доказательство теоремы 1Пронумеруем вершины графа $H$ следующим образом: $h_1, \dots, h_m$. Составим формулу глубины $m+3$, выражающую существование подграфа, изоморфного $F$. Для этого рассмотрим следующие вспомогательные предикаты. Во-первых, предикат
$$
\begin{equation*}
P_H(x_1, \dots, x_m):=\biggl[\bigwedge_{i<j\colon h_i\sim h_j} (x_i\sim x_j)\biggr] \wedge\biggl[\bigwedge_{i<j\colon h_i\nsim h_j}(x_i\nsim x_j \land x_i \neq x_j)\biggr]
\end{equation*}
\notag
$$
является истинным тогда и только тогда, когда индуцированный подграф на вершинах $x_1, \dots, x_m$ изоморфен графу $H$, причем отображение, переводящее $x_i$ в $h_i$, является изоморфизмом. Во-вторых, предикат
$$
\begin{equation*}
P_0(x_1, \dots, x_{m+3}):=P_H(x_4, \dots, x_{m+3}) \land\biggl[\bigwedge_{i=1}^{3} \bigwedge_{j=i+ 1}^{m+3} (x_i \neq x_j \land x_i \nsim x_j)\biggr]
\end{equation*}
\notag
$$
является истинным тогда и только тогда, когда вершины $x_1$, $x_2$, $x_3$ не смежны ни друг с другом, ни с $x_4, \dots, x_{m+3}$, а последние индуцируют $H$, причем $x_{3+i}\,{\mapsto}\, h_i$ – изоморфизм. Кроме того, предикат
$$
\begin{equation*}
\begin{aligned} \, &P_1(x_1, \dots, x_{m+3}):=P_H(x_4, \dots, x_{m+3}) \land x_1 \sim x_2 \\ &\qquad\qquad \land \biggl[\bigwedge_{j=3}^{m+3}(x_1 \neq x_j \land x_1 \nsim x_j)\biggr] \land \biggl[\bigwedge_{i=2,3} \bigwedge_{j=i+1}^{m+3} (x_i \neq x_j \land x_i \nsim x_j)\biggr] \end{aligned}
\end{equation*}
\notag
$$
является истинным в той же ситуации, что и $P_0$, за исключением того, что вершины $x_1$, $x_2$ должны быть смежны. А для истинности предиката
$$
\begin{equation*}
\begin{aligned} \, & P_2(x_1, \dots, x_{m+3}):=P_H(x_4, \dots, x_{m+3}) \land x_1 \sim x_2 \land x_2 \sim x_3 \land x_1\neq x_3\land x_1\nsim x_3 \\ &\qquad\qquad\land\biggl[\bigwedge_{i=1}^3\bigwedge_{j=4}^{m+3}(x_i \neq x_j \land x_i \nsim x_j)\biggr] \end{aligned}
\end{equation*}
\notag
$$
должны быть смежны $x_1$ с $x_2$ и $x_2$ с $x_3$. Тогда искомая формула имеет вид
$$
\begin{equation*}
\begin{aligned} \, &\varphi=\exists\, x_5 \dots \exists\, x_{m+4}\,\exists\, x_1 \quad \Bigl([\exists\, x_3 \exists\, x_4\ P_0(x_1, x_3, x_4, x_5, \dots, x_{m+4})] \\ &\qquad\qquad\land \bigl[\exists\, x_2\ \bigl([\exists\, x_4 \ P_1(x_1, x_2, x_4, x_5, \dots, x_{m+ 4})] \\ &\qquad\qquad \land [\exists\, x_3 \ P_2(x_1, x_2, x_3, x_5, \dots, x_{m+4})]\bigr)\bigr] \Bigr). \end{aligned}
\end{equation*}
\notag
$$
Действительно, пусть сперва $G\in\mathscr{C}[F]$. Пронумеруем вершины индуцированного подграфа $\widetilde F$, изоморфного $F$, в $G$ числами от $1$ до $m+4$ таким образом, что $1\sim 2$, $2\sim 3$, $4$ – изолированная вершина в $\widetilde F$ и отображение $h_i\mapsto i+4$ – изоморфизм графов $H$ и $F_0$. Тогда, очевидно, истинность формулы $\varphi$ следует из того, что становятся истинны все предикаты в ней при подстановке $x_i=i$. С другой стороны, предположим, что $G\models\varphi$. Укажем такую нумерацию некоторых вершин $G$ числами от $1$ до $m+4$, что подграф на занумерованных вершинах изоморфен $F$. Пусть истинность формулы $\varphi$ обеспечивается истинностью предикатов $P_0$, $P_1$ и $P_2$ на наборах вершин $(x_1,y_1,y_2,x_5,\dots,x_{m+4})$, $(x_1,x_2,x_4,x_5,\dots,x_{m+4})$ и $(x_1,x_2,x_3,x_5,\dots,x_{m+4})$ соответственно. Пронумеруем вершины $x_5,\dots,x_{m+4}$ числами $5, \dots, m+4$ соответственно. Заметим, что вершина $x_2$ не совпадает ни с $y_1$, ни с $y_2$, так как она смежна с $x_1$. Возможны 3 случая. 1. Вершина $x_2$ смежна ровно с одной вершиной из $y_1$, $y_2$. Не умаляя общности, пусть $y_1\sim x_2$. Тогда оставшиеся четыре номера $1$, $2$, $3$, $4$ получат вершины $x_1$, $x_2$, $y_1$, $y_2$ соответственно. 2. Вершина $x_2$ не смежна ни с одной вершиной из $y_1$, $y_2$. Тогда вершина $x_3$ отлична как от $y_1$, так и от $y_2$. Если $x_3$ не смежна с вершиной $y_i$ для некоторого $i \in \{ 1, 2 \}$, то присвоим номера 1, 2, 3, 4 вершинам $x_1$, $x_2$, $x_3$, $y_i$ соответственно. Иначе ($x_3 \sim y_1$, $x_3 \sim y_2$) эти номера получат вершины $y_1$, $x_3$, $y_2$, $x_1$. 3. Вершина $x_2\sim y_1$, $x_2\sim y_2$. Тогда вершина $x_4$ отлична как от $y_1$, так и от $y_2$. Если для некоторого $i \in \{ 1, 2\}$ $x_4 \nsim y_i$, то номера 1, 2, 3, 4 получат вершины $x_1$, $x_2$, $y_i$, $x_4$ соответственно. Иначе ($y_1 \sim x_4$, $y_2 \sim x_4$) – вершины $y_1$, $x_4$, $y_2$, $x_1$ соответственно. 4.2. Доказательство теоремы 2В силу теоремы 1 достаточно показать, что $D[F] \geqslant m+2$. Для этого достаточно построить пару графов $G$, $G'$ таких, что $G\in\mathscr{C}[F]$, $G'\notin\mathscr{C}[F]$ и у Консерватора есть выигрышная стратегия в игре Эренфойхта–Фраиссе на графах $G$, $G'$ в $m+1$ раунде. Обозначим через $G_m$ граф с множеством вершин $\{1,\dots,2m+4\}$, у которого множество ребер описывается следующим образом:
$$
\begin{equation*}
\begin{gathered} \, 1 \sim 2,\qquad 2 \sim 3, \qquad 3 \sim 4, \\ 2i+3\sim 2i+4,\qquad i\in\{1,\dots,m\}. \end{gathered}
\end{equation*}
\notag
$$
Иными словами, $G_m=P_4\sqcup mP_2$. Обозначим $\mathscr{A}_i=\{2i+3,2i+4\}$, $i\in\{1,\dots,m\}$, $\mathscr{B}=\{1,2,3,4\}$. Будем рассматривать $G:=G_m$ и $G':=G_{m-1}$. Нетрудно понять, что действительно $G\in\mathscr{C}[F]$, $G'\notin\mathscr{C}[F]$. Осталось доказать, что у Консерватора есть выигрышная стратегия в игре Эренфойхта–Фраиссе на графах $G$, $G'$ в $m+1$ раундах. Сначала опишем эту стратегию для первых $m-1$ раундов. В первом раунде Новатор выбирает либо вершину из $\mathscr{A}_i$ для некоторого $i\in\{1,\dots,m\}$, либо вершину из $\mathscr{B}$. В первом случае Консерватор выбирает в другом графе вершину из $\mathscr{A}_1$. Во втором случае Консерватор выбирает вершину, равную вершине, выбранной Новатором. Пусть к началу раунда $r\in\{2,\dots,m-1\}$ выбраны вершины $x_1,\dots,x_{r-1}$ в $G$ и вершины $x_1',\dots,x_{r-1}'$ в $G'$. Пусть, кроме того, выполнены следующие условия $(r-1).1$ и $(r-1).2$, где Заметим сразу, что выполнение этих условий гарантирует победу Консерватора в $\mu$ раундах. Очевидно, какую бы вершину ($x_r$ в $G$ или $x_r'$ в $G'$) ни выбрал бы Новатор, Консерватор сможет выбрать такую вершину ($x_r'$ в $G'$ или $x_r$ в $G$), что будут выполнены условия $r.1$, $r.2$. Итак, пусть сыграно $m-1$ раундов. Если хотя бы в двух из них была выбрана вершина из $\mathscr{B}$, то, очевидно, Консерватор сможет в двух последних раундах играть так, что будут выполнены условия $(m+1).1$, $(m+1).2$, и тем самым победить. Если ровно в одном раунде была выбрана вершина из $\mathscr{B}$, то Консерватор сможет в раунде $m$ выбрать такую вершину, что выполнены условия $m.1$, $m.2$. Если в раунде $m$ Новатор выбрал вершину из $\mathscr{B}$, то Консерватор сможет и в раунде $m+1$ выбрать такую вершину, что выполнены условия $(m+1).1$, $(m+1).2$. Поэтому будем предполагать, что в раунде $m$ Новатор выбрал вершину вне $\mathscr{B}$. Кроме того, будем предполагать, что Новатор выбрал вершину в $G$ (иначе, опять же, в раундах $m$ и $m+1$ Консерватор сможет выбрать такие вершины, что выполнены условия $(m+1).1$, $(m+1).2$). Тогда в раунде $m+1$ Новатору не выгодно выбирать вершину из $\mathscr{B}$, так как в этом случае Консерватор сможет просто выбрать ту же самую вершину. Не выгодно Новатору и выбирать вершину из некоторого $\mathscr{A}_s$, в котором уже выбрана некоторая вершина $x_i$, так как в этом случае Консерватор просто выберет вершину из того $\mathscr{A}_{s'}$, в котором лежит $x_i'$. Если же Новатор выберет вершину из единственного множества $\mathscr{A}_s$, в котором еще не выбрано ни одной вершины $x_i$, то Консерватор выберет вершину из $\mathscr{B}$, которая не смежна с единственной вершиной, выбранной в $\mathscr{B}$, и победит. Пусть, наконец, все $x_i$, $i\in\{1,\dots,m-1\}$, лежат вне $\mathscr{B}$. Если в раунде $m$ Новатор выберет вершину из $\mathscr{B}$, то Консерватор выбирает такую же вершину и, очевидно, сможет победить в раунде $m+1$, так как в графе $G'$ существует по крайней мере еще одна вершина (из $\mathscr{B}$), которая не смежна ни с одной из $x_1',\dots,x_m'$. Если в раунде $m$ Новатор выберет вершину (скажем, в $G$) из некоторого $\mathscr{A}_s$, в котором уже выбрана некоторая вершина $x_i$, $i\in\{1,\dots,m-1\}$, то Консерватор должен выбрать вершину $x_m'$ из того $\mathscr{A}_{s'}$, в котором лежит $x_i'$. Очевидно, в раунде $m+1$ Консерватор победит, так как если даже Новатор выберет вершину из единственного оставшегося нетронутым $\mathscr{A}_s$, то Консерватор выберет произвольную вершину из $\mathscr{B}$. Наконец, если в раунде $m$ Новатор выберет вершину (скажем, в $G$) из $\mathscr{A}_s$, которому не принадлежит ни одна вершина $x_i$, $i\in\{1,\dots,m-1\}$, то Консерватор выберет вершину $x_m'=1\in\mathscr{B}$. Так как в каждом графе – у каждой выбранной вершины, не смежной с другими выбранными, есть ровно один сосед, – у каждой выбранной вершины, имеющей соседа среди выбранных, нет других соседей, – ни у какой пары выбранных вершин нет общего соседа, – есть вершина, не смежная ни с одной из выбранных, то Консерватор сможет победить в последнем раунде. § 5. Графы, для которых не существует записи эффективнее тривиальнойДля доказательства теоремы 3 достаточно построить два графа $G, G'$ такие, что $G\in\mathscr{C}[F]$, $G'\notin\mathscr{C}[F]$ и у Консерватора есть выигрышная стратегия в игре Эренфойхта–Фраиссе на графах $G,G'$ в $\ell-1$ раундах. Будем для удобства считать, что $n_1\leqslant\dots\leqslant n_k$. Напомним, что $\ell=m(n_1+\dots+n_k)$. Определим почти многодольный граф $G^m_{\ell, k}$ как граф на множестве вершин $V:=\{ (i, j, h) \mid 1 \leqslant i \leqslant\ell, 1 \leqslant j \leqslant k, 1 \leqslant h \leqslant m \}$ и с множеством ребер
$$
\begin{equation*}
E:=\bigl\{ \{(i_1, j_1, h), (i_2, j_2, h)\} \mid i_1 \neq i_2, \,j_1 \neq j_2 \bigr\} \cup \bigl\{\{ (i, j_1, h_1), (i, j_2, h_2)\} \mid h_1 \neq h_2\bigr\}.
\end{equation*}
\notag
$$
Для вершины $(i, j, h)$ будем называть $i$ классом, $j$ – долей, а $h$ – частью этой вершины, при этом будем говорить, что вершины $(i_1,j_1,h_1)$, $(i_2,j_2,h_2)$ находятся в одной доле, если номера их долей и частей совпадают (т.е. $j_1=j_2$, $h_1=h_2$). Заметим, что если инвертировать все ребра в этом графе между вершинами с одинаковым классом, то получится дизъюнктное объединение $m$ полных $k$-дольных графов $mK_{\ell, \dots, \ell}$, в связи с чем вторую координату каждой вершины мы назвали ее долей. Положим $G=G^m_{\ell, k}$, $G'=G^m_{\ell-1, k}$. Докажем, что это нужные нам графы. Разобьем доказательство на несколько утверждений. Доказательство. Пронумеруем все вершины (числами от 1 до $\ell$) и компоненты (числами от 1 до $m$) графа $mK_{n_1, \dots, n_k}$, а также доли каждой компоненты числами от $1$ до $k$. Тогда вершине с номером $i$ из компоненты $h$ этого графа из доли с номером $j$ сопоставим вершину $(i, j, h)$ графа $G$. Это и будет искомое вложение. Утверждение доказано. Далее мы предположим, что $F$ вкладывается в $G'$. Условимся, что везде, где речь будет идти о доле образа вершины из $F$ при таком вложении, будет иметься в виду доля графа $G'$, в которой лежит этот образ. Соответственно, когда будет упоминаться доля вершины из $F$, будет иметься в виду доля графа $F$. Утверждение 2. Пусть $n_k>1$, $k\geqslant 2$. Если граф $G'$ содержит индуцированный подграф, изоморфный $F$, то не существует двух вершин $v$, $w$, лежащих в разных компонентах графа $F$ таких, что их образы лежат в одной части, но в разных долях графа $G'$. Доказательство. Предположим, что такая пара вершин $v, w$ нашлась. Обозначим через $v'$, $w'$ их образы.
Так как $w$, $v$ лежат в разных компонентах, $w' \nsim v'$. Значит, классы $v'$ и $w'$ совпадают. Выберем $w_0$ такую, что $w_0$, $w$ лежат в одной компоненте связности, но разных долях. Тогда $w_0 \sim w$. Рассмотрим ее образ $w'_0$. Если $w'_0$ лежит в отличной от $v'$ части, то тогда так как $w'_0 \sim w'$, то классы $w'_0$, $w'$ совпадают. Но тогда классы $v'$, $w'_0$ совпадают и $v' \sim w'_0$. Противоречие. Значит, $w'_0$ лежит в одной части с $v'$. Если доли $w'_0$ и $v'$ различны, то так как $v' \nsim w'_0$, классы $w'_0$, $v'$ совпадают. Но тогда классы $w'$, $w'_0$ совпадают и либо $w'=w'_0$, либо $w' \nsim w'_0$. Противоречие. Значит, $w'_0$ лежит в одной доле с $v'$. Меняя в этом рассуждении $w'$ и $v'$ местами, получаем, что в $F$ существует $v_0$ с образом $v'_0$, лежащая в одной компоненте с $v$, но в разных с ней долях, и $v'_0$ лежит в одной части и одной доле с $w'$. Тогда так как $v'_0$, $w'_0$ лежат в разных долях одной части и не соединены ребром, то их класс совпадает. Так как $n_k > 1$, то в одной компоненте связности $F$ есть хотя бы три вершины. Значит, существует вершина $v_1$ из одной компоненты с $v$, $v_0$. При этом так как $v$, $v_0$ из разных долей, $v_1$ соединена хотя бы с одной из них. Пусть, не умаляя общности, это $v$. Пусть $v'_1$ – образ $v_1$. Так как $w'_0$, $w'$ имеют разные классы и в долях, в которых лежат $w'_0$, $w'$, эти классы заняты отличными от $v'_1$ вершинами, то если $v'_1$ принадлежит одной части с ними, то она смежна и с $w'$, чего не может быть. Значит, $v'_1$ лежит в другой части. Но так как $v'_1 \sim v'$, она имеет один класс с $v'$ и, следовательно, с $w'$. Значит, $v'_1 \sim w'$. Противоречие. Утверждение доказано. Утверждение 3. Пусть $n_k>1$, $k\geqslant 2$. Тогда граф $G'$ не содержит индуцированный подграф, изоморфный $F$. Доказательство. Предположим противное: $G'\,{\in}\,\mathscr{C}[F]$, и рассмотрим некоторое вложение $F$ (как индуцированного подграфа) в $G'$.
Докажем сперва, что в любой компоненте $F$ найдутся две вершины, образы которых лежат в одной части, но в разных долях графа $G'$. Рассмотрим произвольную компоненту $F$. Так как $n_k > 1$, то найдутся две вершины $v_1$, $v_2$, лежащие в одной доле в этой компоненте, и $v_0$, лежащая в отдельной доле от $v_1$, $v_2$ в той же компоненте. Тогда $v_1 \nsim v_2$, $v_1 \sim v_0$, $v_2 \sim v_0$. Предположим, что все образы $v_0$, $v_1$, $v_2$ – $v'_0$, $v'_1$, $v'_2$ соответственно – лежат в разных частях графа $G'$. Тогда классы $v_0$, $v_1$ и $v_0$, $v_2$ должны совпадать. Но тогда $v_1 \sim v_2$. Противоречие. Предположим, что какие-то два образа лежат в одной части, а третий – в другой. Если они соединены ребром, то они обязаны лежать в разных долях и нужное доказано. Иначе образы из одной части – это $v'_1$, $v'_2$. Тогда классы $v'_0$, $v'_1$ и $v'_0$, $v'_2$ совпадают и, следовательно, $v'_1$, $v'_2$ лежат в разных долях, что и требовалось. Наконец, если все три образа лежат в одной части, то $v'_0$, $v'_1$ должны лежать в разных долях. Значит, для любой компоненты $F$ можно выделить хотя бы одну часть графа $G'$, в двух разных долях которой лежат образы вершин этой компоненты. Но тогда согласно утверждению 2 образ любой вершины из любой другой компоненты $F$, лежащий в этой части, должен лежать сразу в двух долях, чего не может быть. Значит, в этой части могут лежать только образы этой компоненты. Так как компонент столько же, сколько частей, каждая компонента $F$ вложена целиком в одну часть $G'$. Рассмотрим произвольную компоненту $F$. Так как вершины из разных долей этой компоненты соединены ребром, то их образы не могут лежать в одной доле. Так как долей в рассматриваемой компоненте $F$ столько же, сколько в одной части в $G'$, то образ каждой доли лежит ровно в одной доле. Предположим теперь, что какие-то два образа $v'_1$, $v'_2$ вершин $v_1$, $v_2$ из рассматриваемой компоненты графа $F$ имеют один класс. Тогда $v'_1 \nsim v'_2$ и лежат в разных долях. Значит $v_1 \nsim v_2$, откуда $v_1$, $v_2$ лежат в одной доле $H$. Но тогда их образы тоже должны лежать в одной доле – противоречие. Следовательно, образы всех вершин рассматриваемой компоненты графа $F$ имеют попарно различные классы. Наконец, образы вершин из разных частей не могут иметь совпадающего класса, так как иначе, поскольку они лежат в разных частях, они были бы смежны. Следовательно, образы различных вершин из $F$ имеют разные классы в $G'$. Но классов всего $\ell-1$ – меньше, чем вершин. Противоречие. Следовательно, $G'\notin\mathscr{C}[F]$. Утверждение доказано. Утверждение 4. Для любых $\ell \geqslant 2$, $m \geqslant 1$, $k \geqslant 1$ у Консерватора есть выигрышная стратегия в игре Эренфойхта–Фраиссе на графах $G$ и $G'$ в $\ell-1$ раундах. Доказательство. Будем строить функцию $f\colon 1,\dots,\ell \to1,\dots,\ell-1$, переводящую классы вершин графа $G$ в классы вершин графа $G'$. Вначале все значения функции не определены.
Пусть Новатор в некотором раунде выбрал вершину $(i, j, h)$ в одном из графов $G$, $G'$ такую, что в этом графе нет другой выбранной вершины с этим же классом. Тогда пусть $i'$ – такой класс вершины в другом графе, что в нем тоже нет выбранной вершины с классом $i'$. Такой всегда найдется, так как классов в графах $G$, $G'$ хотя бы $\ell-1$, а раундов всего $\ell-1$. Консерватор выберет вершину $(i', j, h)$. Если Новатор делал ход в графе $G$, то определим $f(i)=i'$, и $f(i')=i$ иначе. Если же Новатор в этом раунде выбрал вершину $(i, j, h)$ такую, что в том же графе уже есть выбранные вершины с таким же классом, то либо корректно определена $i':=f(i)$ (при условии, что Новатор выбирал вершину в графе $G$), либо корректно определена $i':=f^{-1}(i)$ (при условии, что Новатор выбирал вершину в графе $G'$). Тогда Консерватор выбирает вершину $(i', j, h)$ в другом графе. При описанной стратегии совпадение номеров классов (долей, частей) выбранных вершин в $G$ равносильно совпадению номеров классов (долей, частей) соответствующих выбранных вершин в $G'$. Поэтому индуцированные подграфы на выбранных вершинах по окончании игры будут изоморфны. Утверждение доказано. В силу утверждений 1, 3 и 4 при $k\geqslant 2$ и $n_k > 1$ теорема 3 доказана. При $k=1$ $F=mn_1 K_1$, т.е. является пустым графом. В этом случае $D[F]=D[\overline{F}]=\ell$ (см. [8]). Наконец, при $k\geqslant 2$ и $n_k=1$ граф $F$ равен дизъюнктному объединению полных графов: $F=mK_k$. Так как $D[F]=D[\overline{F}]$ и $\overline{F}$ – полный многодольный граф, то при $m>1$ $D[F]=\ell$ по уже доказанному (при $k \geqslant 2$ $\overline{F}$ попадает под уже рассмотренный случай, если $m > 1$). А при $m=1$ $F$ – полный граф, для которого также верно $D[F]=\ell$. Теорема 3 полностью доказана. § 6. Графы на пяти вершинахНапомним сперва, что для любого графа $F$ на $\ell$ вершинах и реберного дополнения $\overline{F}$ к нему выполнено $D[F]=D[\overline{F}]$. Поэтому в силу (1.1)
$$
\begin{equation*}
D[F]\geqslant\frac{\max\{e(F),C_\ell^2-e(F)\}}{\ell}+2.
\end{equation*}
\notag
$$
В частности, для любого графа $F$ на пяти вершинах и числом ребер, отличным от $5$, выполнено $D[F]\geqslant{6}/{5}+2$, а значит, $D[F]\geqslant 4$. Осталось проверить справедливость этого неравенства для всех графов с ровно пятью ребрами. Принимая во внимание то, что нам не нужно рассматривать реберные дополнения, мы можем ограничиться следующими четырьмя графами: 1) простой цикл на пяти вершинах $C_5$; 2) граф $G_{4,1}$, равный объединению простого цикла на четырех вершинах и ребра, исходящего из одной из вершин цикла к пятой вершине; 3) граф $K_1\sqcup K_{2,1,1}$, равный дизъюнктному объединению diamond-граф (т.е. полного графа на четырех вершинах без ребра или, иными словами, полного трехдольного графа с долями размера 2, 1, 1) и вершины; 4) граф $G_{3,1,1}$, равный объединению треугольника и двух непересекающихся по вершинам ребер, одно из которых соединяет одну вершину треугольника с четвертой вершиной графа, а второе соединяет другую вершину треугольника с пятой вершиной графа. 6.1. Граф $C_5$Итак, докажем сперва, что $D[C_5]\geqslant 4$. Для этого рассмотрим графы $G=C_5\sqcup C_6$ и $H=C_6\sqcup C_6$. Очевидно, $G\in\mathscr{C}[C_5]$, а $H\notin\mathscr{C}[C_5]$. Осталось доказать, что Консерватор выигрывает в игре Эренфойхта–Фраиссе на графах $G$, $H$ в трех раундах. Если Новатор в первом раунде отметил вершину в одном из $C_6$, то дальнейшая стратегия Консерватора очевидна. Если же Новатор в первом раунде выбрал некоторую вершину $C_5$, то Консерватор в том же раунде должен выбрать произвольную вершину графа $H$. Очевидно, Новатору не выгодно во втором раунде выбирать вершину в одной из двух компонент, ни одна из вершин которых не выбрана в первом раунде. Предположим сначала, что Новатор выбрал еще одну вершину $C_5$. Тогда Консерватор выбирает в “своем” $C_6$ вершину, лежащую от выбранной на расстоянии, равном расстоянию между выбранными вершинами в $C_5$ (под расстоянием подразумевается количество ребер в наикратчайшем простом пути, соединяющем рассматриваемые вершины). Очевидно, Консерватор сможет победить в третьем раунде. Пусть, наконец, во втором раунде Новатор выбрал вершину из $C_6$ в $H$, в котором Консерватором уже выбрана одна вершина. Тогда от предыдущей ситуации отличается лишь случай, в котором Новатор выбирает вершину, находящуюся на расстоянии 3 от уже выбранной. В этом случае Консерватор должен выбрать вершину в $C_6\subset G$. Так как у обеих пар вершин нет общей соседней вершины, а все остальные варианты смежности третьей вершины с ними присутствуют, то в третьем раунде Консерватор сможет победить. 6.2. Граф $G_{4,1}$На рис. 1, a изображены графы $G$ и $H$, полученные из $C_4$ и $C_5$ соответственно добавлением непересекающихся ребер к каждой из вершин циклов. Очевидно, $G$ содержит индуцированный подграф, изоморфный $F=G_{4,1}$, а $H$ – нет. Докажем, что у Консерватора есть выигрышная стратегия в игре Эренфойхта–Фраиссе на графах $G$, $H$ в трех раундах. Для победы Консерватору достаточно просто “повторять” ходы Новатора, а именно обеспечить выполнение следующих двух условий: 1) выбирать вершины степени 1 тогда и только тогда, когда Новатор в том же раунде выбирает вершины степени 1, и выбирать вершины цикла тогда и только тогда, когда Новатор в том же раунде выбирает вершины цикла; 2) во втором раунде выбирать вершину, находящуюся от первой на том же расстоянии, что и две соответствующие вершины в графе, выбранном во втором раунде Новатором. Очевидно, Консерватор сможет в первых двух раундах следовать условию 1), а во втором раунде следовать условию 2). Тогда, как легко видеть, в третьем раунде он сможет победить. 6.3. Граф $K_1\sqcup K_{2,1,1}$Заметим, что diamond-граф $K_{2,1,1}$ является полным многодольным, а значит, как мы установили в § 5, существуют такие графы $G$, $H$, что $G\in\mathscr{C}[K_{2,1,1}]$, $H\notin\mathscr{C}[K_{2,1,1}]$ и Консерватор выигрывает в игре Эренфойхта–Фраиссе на графах $G$, $H$ в трех раундах. Осталось заметить, что отсюда очевидно вытекает, что, во-первых, $2G\in\mathscr{C}[K_1\sqcup K_{2,1,1}]$, $2H\notin\mathscr{C}[K_1\sqcup K_{2,1,1}]$, а во-вторых, Консерватор выигрывает в игре Эренфойхта–Фраиссе на графах $2G$, $2H$ в трех раундах. 6.4. Граф $G_{3,1,1}$На рис. 1, b изображены графы $G$ и $H$, полученные из $K_4\sqcup C_4$ и $K_3\sqcup K_3$ соответственно добавлением ребер между “соответствующими” вершинами компонент, а затем рассмотрением дизъюнктных объединений двух копий каждого из полученных графов. Очевидно, $G$ содержит индуцированный подграф, изоморфный $F=G_{3,1,1}$, а $H$ – нет. Пусть граф $G^*$ получен из графа $G$ добавлением вершины $x^*$, смежной со всеми вершинами $G$, а $H^*$ – из $H$ добавлением вершины $y^*$, смежной со всеми вершинами $H$. Разумеется, для этих графов верно то же самое: $G^*\in\mathscr{C}[F]$, $H^*\notin\mathscr{C}[F]$. Докажем, что у Консерватора есть выигрышная стратегия в игре Эренфойхта–Фраиссе на графах $G^*$, $H^*$ в трех раундах. Ниже мы будем говорить, что пара вершин $(u,v)$ некоторого графа $A$ обладает свойством расширения, если в графе $A$ найдутся четыре другие вершины $z_1$, $z_2$, $z_3$, $z_4$, состоящие в разных отношениях смежности с $u$, $v$, т.е. $u\nsim z_1$, $v\nsim z_1$; $u\sim z_2$, $v\nsim z_2$; $u\nsim z_3$, $v\sim z_3$; $u\sim z_4$, $v\sim z_4$. Разумеется, если в первых двух раундах игры выбраны вершины $x_1$, $x_2$ в $G$ и $y_1$, $y_2$ в $H$ (либо $x_1\sim x_2$, $y_1\sim y_2$, либо $x_1\nsim x_2$, $y_1\nsim y_2$), то если обе пары $(x_1,x_2)$ и $(y_1,y_2)$ обладают свойством расширения, то Консерватор сможет выиграть в третьем раунде. Опишем теперь выигрышную стратегию Консерватора. Для победы Консерватору достаточно просто обеспечить выполнение следующих двух условий: 1) для каждого $i\in\{1,2\}$ в раунде $i$ в $G^*$ выбрана вершина $x^*$ тогда и только тогда, когда в том же раунде в $H^*$ выбрана вершина $y^*$; 2) если в первых двух раундах не выбрана ни вершина $x^*$, ни вершина $y^*$ (т.е. выбраны вершины $x_1$, $x_2$ в $G$ и $y_1$, $y_2$ в $H$), то $x_1\sim x_2$ тогда и только тогда, когда $y_1\sim y_2$. Очевидно, Консерватор сможет в первых двух раундах следовать обоим условиям. Если при этом хотя бы в одном раунде выбраны вершины $x^*$, $y^*$, то Новатор в том раунде просто потерял ход, так как эти вершины смежны со всеми остальными, и дальнейшая стратегия Консерватора очевидна. Если же вершины $x^*$, $y^*$ не выбраны, то обе пары $(x_1,x_2)$ и $(y_1,y_2)$ обладают свойством расширения, а значит, у Консерватора есть выигрышная стратегия в третьем раунде (действительно, в силу существования вершин $x^*$, $y^*$, а также в силу того, что оба графа $G$ и $H$ состоят из двух компонент связности, достаточно проверить, что у любых двух вершин в $G$ и в $H$ есть сосед только первой и сосед только второй, а это легко проверяется). § 7. Открытые вопросыХотя теорема 1 показывает, что существуют сколь угодно большие графы, для которых $D[F] < \ell$, остается открытым вопрос, существуют ли графы, у которых $D[F] < \ell-1$. Вполне возможно, что существует граф $F$ на шести вершинах, для которого $D[F]=4$ (аналогично рассуждению в § 6 из (1.1) незамедлительно следует что графа на шести вершинах с $D[F]<4$ не существует). Хочется высказать еще более смелое предположение о существовании такого $\alpha<1$ и графов $F$ сколь угодно большого размера, для которых $D[F]\leqslant\alpha \ell$. С точки зрения вклада в задачу о временно́й сложности проверки $\mathscr{C}[F]$ хочется доказать, что $\alpha$ может быть меньше чем ${\omega}/{3}$. Наконец, возникает вопрос, можно ли обобщить теорему 3, используя похожую технику, для более широкого класса графов? Например, для некоторых дизъюнктных объединений полных многодольных неизоморфных графов или, скажем, для графов, состоящих из независимых множеств $I_1,\dots,I_k$ размера хотя бы 2 таких, что между любыми двумя множествами смежности одинаковы (для любых различных $i,j\in\{1,\dots,k\}$ либо каждая вершина $I_i$ смежна с каждой вершиной $I_j$, либо между $I_i$ и $I_j$ вообще нет ребер). 
Цитирование в формате AMSBIB
\RBibitem{ZhuKudMak21} |
|
||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|