\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{tikz}

\usetikzlibrary{calc,positioning}

\tikzstyle{every node}=[circle, draw, fill=black!50,
inner sep=0pt, minimum width=4pt]

\tikzstyle{red node}=[circle, draw, fill=red!80,
inner sep=0pt, minimum width=4pt]

\tikzstyle{green node}=[circle, draw, fill=green!50,
inner sep=0pt, minimum width=4pt]
\tikzstyle{blue node}=[circle, draw, fill=blue!50,
inner sep=0pt, minimum width=4pt]
\tikzstyle{yellow node}=[circle, draw, fill=yellow!50,
inner sep=0pt, minimum width=4pt]

\tikzstyle{blue box}=[rectangle, minimum height=0.3cm,draw, fill=blue!50,
inner sep=0pt, minimum width=0.3cm]
\tikzstyle{red box}=[rectangle, minimum height=0.3cm, draw, fill=red!50,
inner sep=0pt, minimum width=0.3cm]

\RequirePackage[all]{xy}

\def\udcs{???.?} %Здесь автор определяет УДК своей работы
\def\mscs{??X??} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}
\newtheorem{comment}{Замечание}

\def\x{X}
\def\a{a}
\def\L{\mathcal{L}}
\def\A{\mathcal{A}}
\def\Lg{\L_\Gamma}
\def\NN{\mathbb{N}}
\def\simp{\mathfrak{S}}
\def\loop{\mathfrak{L}}

\newenvironment{network}%
{\catcode`"=12\begin{xy}<1ex,0ex>:}%
	{\end{xy}\catcode`"=13}
\def\nnNode"#1"(#2)#3{\POS(#2)*#3="#1"}
\def\nnLink"#1,#2"#3{\POS"#1"\ar #3 "#2"}


\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
{
	\vbox{
		\noindent\logo
		\hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }
		
		\vspace{5mm}
		
		\begin{center}
			{\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
			{\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
			{\large Siberian Electronic Mathematical Reports} \\[1mm]
			{\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
			%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
			%     {\small Sobolev Institute of Mathematics SB RAS}
		\end{center}
		\vspace{-3mm}
		\noindent
		\begin{tabular}{c}
			\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
			\hline\hline
		\end{tabular}
		
		\vspace{1mm}
		{\flushleft\it Том 16, стр. 144--144 (2019) \hspace{65mm}{\rm\small УДК \udcs}}
		\newline
		{\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
	}%\vbox
}

\begin{document}
\renewcommand{\refname}{References}
	
	
\thispagestyle{empty}
	
\title[Ненетеровы графы]{О графах, не являющихся нетеровыми по уравнениям}
\author{{И.М. БУЧИНСКИЙ, А.В. ТРЕЙЕР}}
\address{Ivan Mikhailovich Buchinskiy  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Omsk branch of Sobolev Institute of Mathematics,
\newline\hphantom{iii} Pevtsova street, 13,
\newline\hphantom{iii} 644043, Omsk, Russia}
\email{buchvan@mail.ru} 

\address{Alexander Viktorovich Treyer  % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} Omsk branch of Sobolev Institute of Mathematics,
	\newline\hphantom{iii} Pevtsova street, 13,
	\newline\hphantom{iii} 644043, Omsk, Russia}
\email{alexander.treyer@gmail.com} 

\semrtop \vspace{1cm}
\maketitle {\small	
	\begin{quote}
		\noindent{\sc Abstract. } The goal of the paper is to describe all equationally noetherian graphs in terms of forbidden subgraphs for the categories of simple graphs and graphs with loops. \medskip
		
		\noindent{\bf Keywords:} simple graphs, graphs with loops, graph groups, equationally noetherian, one variable equations.
	\end{quote}
}
	
\section{Введение}

Исследованием решений уравнений над различными алгебраическими системами занимается направление математики с названием <<Универсальная алгебраическая геометрия>>. Существует немало работ, посвященных этой тематике. Достаточно большой список таких статей и теоретическую основу по универсальной алгебраической геометрии можно найти в монографии \cite{Mon}. Настоящая работа также относится к этому направлению исследований.

Важным свойством алгебраических систем, с точки зрения алгебраической геометрии, является свойство нётеровости по уравнениям. Алгебраическая система является нётеровой по уравнениям, если любая система уравнений от конечного набора переменных над этой алгебраической системой эквивалентна некоторой своей конечной подсистеме. Для краткости изложения, иногда мы будем пользоваться термином <<нётеров граф>>, подразумевая под этим граф, являющийся нётеровым по уравнениям.

Нётеровы алгебраические системы достаточно удобны для описания решений систем уравнений над ними. В этом случае существует общий теоретический подход, позволяющий взглянуть на алгебраические множества с разных точек зрения. Описание этого подхода можно найти в параграфе <<Объединяющие теоремы для нётеровых по уравнениям алгебраических систем>> из \cite{Mon}, а также в работе \cite{Remeslen1}. Список нётеровых по уравнениям алгебраических систем достаточно широк. В этом списке, в частности, содержатся все конечные алгебраические системы, абелевы группы, линейные группы, гиперболические группы без кручения \cite{Mon}, свободные разрешимые группы произвольных ступеней разрешимости и рангов \cite{Romanovskiy}. Список ненётеровых алгебраических систем тоже достаточно большой. К примеру, ненётеровыми являются сплетения неабелевой группы и бесконечной группы \cite{BMRom}, бесконечная прямая степень неабелевой группы или полугруппы \cite{ShahShevl}, есть примеры двуступенно нильпотентных групп и конечнопорожденных центрально-метабелевых групп, не являющихся нётеровыми по уравнениям \cite{Romanovskiy}. Далее рассмотрим примеры нётеровых и ненётеровых графов более детально.

Пусть $\L = \{E(x,y), =^{(2)}\}$ --- язык теории графов, где $E(x,y)$ предикат соседства вершин $x$ и $y$, а $=^{(2)}$ --- бинарный предикат равенства для вершин графа. Так как мы рассматриваем системы уравнений от конечного набора переменных и язык $\L$ не содержит констант, то в языке $\L$ все графы являются нётеровыми в силу того, что в этом языке не существует бесконечных систем уравнений. Таким образом, вопрос нётеровости для графов имеет смысл рассматривать для языка $\L$, расширенного некоторым набором констант. Поэтому для произвольного графа $\Gamma$ мы будем рассматривать уравнения в языке $\Lg = \L \cup V(\Gamma)$. Уравнения, заданные в языке с множеством констант, расширенным всеми элементами алгебраической системы, называются диофантовыми уравнениями. В статье мы работаем только с диофантовыми уравнениями над графами.

Известно, что нётеровыми по уравнениям являются все локально конечные графы, то есть графы, степень любой вершины которых конечна. Этот факт достаточно просто обосновать, используя {\it лемму \ref{lemma:kotov}}, доказанную в \cite{KotovArticle}. В то же время, среди не локально конечных графов есть много графов, являющихся нётеровыми. В частности, непосредственно проверяется с помощью {\it леммы \ref{lemma:kotov}} из параграфа \ref{sec:reduction}, что любой граф, содержащий конечное количество вершин бесконечной степени, является нётеровым. Но также существуют и графы, являющиеся нётеровыми по уравнениям, в которых есть бесконечное число вершин бесконечной степени. С другой стороны отметим, что бесконечная клика $K$ в категории простых графов ненётерова по уравнениям.

В статье мы будем рассматривать графы в двух категориях. Первая категория --- это простые графы, то есть ненаправленные графы без кратных ребер и петель. Вторая категория --- это ненаправленные графы без кратных ребер, но с петлями, то есть для любой вершины $v$ графа этой категории мы считаем, что пара $(v,v)$ является ребром. Первую категорию графов будем обозначать символом $\simp$, а вторую --- $\loop$. Эти две категории используют один и тот же язык теории графов $\L$, поэтому любая система уравнений может быть рассмотрена и в категории $\simp$, и в категории $\loop$. Всюду далее в статье под словом ``граф'' мы понимаем либо граф из категории $\simp$, либо граф из категории $\loop$. Большинство полученных результатов статьи верны сразу для двух категорий, и, в этом случае, мы не указываем категорию графов, для которой этот результат верен. Где же это необходимо, мы явно указываем категорию $\simp$ или $\loop$.

Основной проблемой, решаемой в статье, является описание всех нётеровых по уравнениям графов в указанных выше категориях. Эта задача решается в {\it теореме \ref{theorem:nonnoether}} из параграфа \ref{sec:nonnoetherian} на языке запрещенных подграфов для класса нётеровых графов.

Авторы выражают благодарность рецензенту за ценные замечания к работе.


\section{Предварительные сведения}

Неориентированным графом называется пара множеств $(V, E)$, где $V$ --- непустое множество вершин, а $E$ --- множество неупорядоченных пар элементов из $V$, называемых ребрами. Все используемые нами в этой статье стандартные определения из теории графов, такие как вложение графов, подграф, индуцированный подграф, можно найти в книге \cite{DistelGraphs}. 

Введём используемые нами понятия алгебраической геометрии над алгебраическими системами, следуя монографии \cite{Mon}. Несмотря на то, что эти понятия носят универсальный характер, мы приведем их в адаптации на язык теории графов.

Язык $\L = \{E^{(2)}, =^{(2)}\}$ назовем языком графов. Произвольный граф является алгебраической системой над языком $\L$. Пусть $\Gamma$ --- неориентированный граф. Расширение языка $\L$ множеством вершин графа $\Gamma$: $\Lg = \L \cup V(\Gamma)$, назовем языком графов с константами из $\Gamma$. Утверждение о том, что вершины $u$ и $v$ смежны, записывается в виде уравнения $E(u, v)$ языка $\Lg$. Отметим, что для всякого простого графа уравнение $E(x, x)$ всегда ложно, в то время как для графов с петлями оно всегда истинно. Язык  $\Lg$ допускает только шесть видов уравнений: $E(x,y), x = y, E(x,c), x=c, E(c_1,c_2), c_1=c_2$, где $x,y$ --- неизвестные, $c, c_1,c_2$ --- константы. Любое множество таких уравнений называется системой уравнений языка $\Lg$.

Точка $\a \in \Gamma^n$ называется решением уравнения $s(\x)$ языка $\Lg$ от $n$ переменных $\x = \{x_1, \ldots, x_n\}$ над графом $\Gamma$, если $\Gamma \models s(\a)$. Точка $\a \in \Gamma^n$ называется решением системы уравнений $S(\x)$ над графом $\Gamma$, если $\a$ является решением каждого уравнения системы $S(\x)$. Множество всех решений системы уравнений $S(\x)$ называется алгебраическим множеством над $\Gamma$ и обозначается через $V_{\Gamma}(S(\x))$.
	
Две системы уравнений $S_1(\x)$ и $S_2(\x)$ языка $\L$ называются эквивалентными над графом $\Gamma$, если их множества решений совпадают. Граф $\Gamma$ называется нётеровым по уравнениям, если для любого целого положительного $n$ любая система уравнений $S(\x)$ от $n$ переменных $\x$ эквивалентна своей некоторой конечной подсистеме $S_0(\x) \subseteq S(\x)$. Данное условие можно ослабить, введя понятие нётеровости графа от фиксированного числа переменных. Будем говорить, что граф $\Gamma$ нётеров по уравнениям от $n$ переменных, если любая система уравнений $S(\x)$ от $n$ переменных $\x$ эквивалентна своей некоторой конечной подсистеме $S_0(\x) \subseteq S(\x)$, то есть является нётеровой. 

Уравнения, состоящие только из констант: $E(c_1,c_2), c_1=c_2$, либо всегда ложны, либо всегда истинны. Системы таких уравнений можно заменить одним заведомо ложным или истинным уравнением вида $c_1 = c_2$. Поэтому мы не будем рассматривать системы уравнений, содержащие бесконечное количество уравнений, состоящих только из констант.
	
	
\section{Уравнения от одной переменной над графами}\label{sec:reduction}	
	
В \cite{KotovArticle} представлена лемма, которая является критерием ненётеровости по уравнениям для алгебраических систем. В оригинальной формулировке леммы есть ограничение на язык алгебраической системы: он не должен содержать предикатных символов. Однако это ограничение не является существенным, и доказательство леммы без каких-либо изменений верно для произвольной алгебраической системы. Приведем формулировку этой леммы и ее доказательство для произвольной алгебраической системы.

\begin{lemma}\label{lemma:kotov}
	Алгебраическая система $\A = \langle A, \L \rangle$ не является нётеровой по уравнениям тогда и только тогда, когда найдутся последовательность элементов $(\a_i)_{i \in \NN}$, $\a_i \in A^n$, и последовательность уравнений $(s_i(\x))_{i \in \NN}, \ \x = \{x_1, \ldots, x_n\}$ языка $\L$, для которых выполнено следующее условие:
	\begin{equation}\label{conditions_kotov}
		\A \not \models s_i(\a_i) \text{ для всех } i \in \NN \text{ и } \A \models s_j(\a_i) \text{ для всех } j < i.
	\end{equation}
\end{lemma}	

\begin{proof}
	<<$\Rightarrow$>> Пусть алгебраическая система $\A$ не является нётеровой по уравнениям, тогда, по определению, найдётся система уравнений $S(\x)$, не эквивалентная никакой своей конечной подсистеме. Покажем по индукции существование искомых последовательностей. 
	В качестве $a_0$ выберем любой элемент из $A^n \setminus V_\A(S(\x))$, а в качестве $s_0(\x)$ – такое уравнение системы $S(\x)$, что $a_0 \not \in V_\A(s_0(\x))$. Далее, положим $a_1$ равным какому-нибудь элементу из $V_\A(s_0(\x)) \setminus V_\A(S(\x))$, а в качестве $s_1(\x)$ выберем любое уравнение из $S(\x)$, для которого $a_1 \not \in V_\A(s_1(\x))$. И так далее. Пусть $a_0, a_1, \ldots, a_m$ и $s_0(\x), s_1(\x), \ldots, s_m(\x)$ с требуемыми свойствами уже построены. В качестве $a_{m + 1}$ выберем любой элемент из $V_\A(s_0(\x), s_1(\x), \ldots, s_m(\x)) \setminus V_\A(S(\x))$. Такой элемент всегда найдётся, так как $S(\x)$ не эквивалентна никакой своей конечной подсистеме, а в качестве $s_{m + 1}(\x)$ выберем любое уравнение, для которого $a_{m + 1} \not \in V_\A(s_{m + 1}(\x))$.
	
	<<$\Leftarrow$>> Рассмотрим систему уравнений $S(\x) = (s_i(\x))_{i \in \NN}$. Несложно заметить, что $a_i \not \in V_\A(S(\x))$ для любого $i$, но для любой конечной подсистемы $S_0(\x) = (s_i(\x))_{i \in I}$ элемент $a_{max I + 1}$ принадлежит $V_\A(S_0(\x))$.
\end{proof}

Будем говорить, что последовательности уравнений и элементов удовлетворяют {\it лемме \ref{lemma:kotov}}, если для них выполнено условие \ref{conditions_kotov} из {\it леммы \ref{lemma:kotov}}.

Отметим, что из доказательства {\it леммы \ref{lemma:kotov}} следует ещё и такое утверждение:

\begin{corollary}\label{cor:kotov}
	В любой ненётеровой системе уравнений $S(\x)$ от $n$ переменных $\x = \{x_1, \ldots, x_n\}$ над алгебраической системой $\A$ существует бесконечная подсистема уравнений $S' = \{s_1(\x), \ldots, s_i(\x), \ldots\}$ и последовательность элементов $(\a_i)_{i \in \NN}$, $\a_i \in A^n$, для которых выполнены условия {\it леммы \ref{lemma:kotov}}, то есть система $S'$ не является нётеровой по уравнениям. Кроме того, любая бесконечная подсистема $S'' \subset S'$ и соответствующая ей подпоследовательность элементов $(\a'_j)_{j \in \NN} \subset (\a_i)_{i \in \NN}$ тоже удовлетворяют {\it лемме \ref{lemma:kotov}}, то есть не является нётеровой по уравнениям.
\end{corollary}

На основе вышеприведенных результатов сформулируем следующее предложение:

\begin{proposition}\label{state:onevariable}
	Пусть $\L = \{P_1^{(2)}, P_2^{(2)}, \ldots, P_m^{(2)}\}$ --- язык с конечным числом бинарных предикатных символов и $S$ --- бесконечная система уравнений языка $\L$ от конечного множества переменных $\x$, не содержащая бесконечных подсистем уравнений, состоящих только из констант. Тогда существует бесконечная подсистема уравнений $S^1 \subset S$ от одной переменной из множества $\x$.
\end{proposition}

\begin{proof}
	Пусть $\x = \{x_1, \ldots, x_n \}$ и $S = S^c \cup S' \cup S^{x_1} \cup \ldots \cup S^{x_n}$, где подсистема $S^{x_i}$ содержит уравнения только от одной переменной $x_i$, $i = 1, \ldots,n$, $S'$ содержит уравнения только без констант, $S^c$ содержит уравнения только с константами. Так как количество неизвестных конечно, то подсистема $S'$ конечна. $S^c$ конечна по условию. Отсюда следует, что по крайней мере какая-то из подсистем $S^{x_i}, \ i = 1, \ldots, n$ является бесконечной. 
\end{proof}

Отметим, что предложение выше истинно для графов по той причине, что в их языке $\Lg$ есть лишь конечное число типов уравнений.

В \cite{BMR} для групп сформулирована следующая проблема:

\textbf{Проблема 1.} Пусть группа $G = \langle G, \L_{gr, G} \rangle$ нётерова по уравнениям от одной переменной. Следует ли отсюда, что группа $G$ нётерова по уравнениям?

В \cite{KotovArticle} приведен пример алгебраических систем, которые являются нётеровыми по уравнениям от $n$ переменных, но не являются нётеровыми по уравнениям от $n+1$ переменных. Для алгебраической системы с конечным числом бинарных предикатных символов имеет место следующая теорема, которая дает положительный ответ на проблему 1 для таких алгебраических систем.

\begin{theorem}\label{theorem:onevariable-nonnoether}
	Пусть $\A = \langle A, \L \rangle$ --- алгебраическая система языка $\L = \{P_1^{(2)}, P_2^{(2)},\\
	 \ldots, P_m^{(2)}\}$ с конечным числом бинарных предикатных символов, не являющаяся нётеровой в языке с константами $\L_{\A} = \L \; \cup \; A$. Тогда существуют такой предикат $P_k$ языка $\L$ и последовательность элементов $(a_i)_{i \in \NN}$, что для уравнений $(P_k(x, b_i))_{i \in \NN}$ и последовательности $(a_i)_{i \in \NN}$, выполнены условия {\it леммы \ref{lemma:kotov}}, то есть $\A$ не является нётеровой по уравнениям от одной переменной.
\end{theorem}

\begin{proof}
	Так как $\A$ не является нётеровой по уравнениям, то, по {\it следствию \ref{cor:kotov}}, существуют последовательности уравнений $S(\x)$ и элементов $(a_i)_{i \in \NN}$, удовлетворяющие {\it лемме \ref{lemma:kotov}}. По {\it предложению \ref{state:onevariable}}, существует бесконечная подсистема уравнений $S'\subseteq S$ от одной переменной $x$. Тогда $S'(x) = \{ x = c_i | i \in I_0\} \cup \bigcup_{j=1}^m \{P_j(x,b_i^j) | i \in I_j\}$. По {\it следствию \ref{cor:kotov}}, подсистема $S'$ также ненётерова, поэтому в ней не может быть уравнений вида $x = c$. С другой стороны, для некоторого $k \in \{1, 2, \ldots, m\}$ множество $I_k$ бесконечно. Тогда, по {\it следствию \ref{cor:kotov}}, для системы уравнений $S'' = (P_k(x, b_i^k))_{i \in I_k}$ также выполнены условия {\it леммы \ref{lemma:kotov}}.
\end{proof}


\section{Графы, не являющиеся нётеровыми по уравнениям}\label{sec:nonnoetherian}

В этом параграфе мы опишем все нётеровы графы в категориях $\simp$ и $\loop$. Начнем с определения совершенно ненётерового графа, играющего важную роль в данном описании.

\begin{definition}\label{def:sov-nonnoether}
	Граф $\Gamma$ будем называть совершенно ненётеровым, если он содержит бесконечную последовательность попарно различных вершин \\
	$a_1, b_1, a_2, b_2, \ldots, a_n, b_n, \ldots$ такую, что каждая из вершин $a_i$ соединена ребрами со всеми вершинами $b_j$ при $j < i$, но не соединена ребром с вершиной $b_i$. 
\end{definition}

Вершины $a_i$ и $b_i$ совершенно ненётерового графа в дальнейшем для красоты письма будем называть {\it парными вершинами}. Граф, приведенный на следующем рисунке, назовем {\it базисным ненётеровым} графом и обозначим через $B$:

\begin{center}
	\begin{tikzpicture}[thick,scale=1, every node/.style={scale=1}]
		\path (-1,0) node[red node][label=180:$a_1$] (a1) {};
		\path (1,0) node[red node][label=0:$b_1$] (b1) {};
		\path (-1,-1) node[red node][label=180:$a_2$] (a2) {};
		\path (1,-1) node[red node][label=0:$b_2$] (b2) {};
		\path (-1,-2) node[red node][label=180:$a_3$] (a3) {};
		\path (1,-2) node[red node][label=0:$b_3$] (b3) {};
		\path (-0.5,-3) node[][label=180:\rotatebox{130}{$\ddots$}] (ldots1) {};
		\path (1.5,-3) node[][label=180:\rotatebox{130}{$\ddots$}] (rdots1) {};
		\path (-1,-4) node[red node][label=180:$a_n$] (an) {};
		\path (1,-4) node[red node][label=0:$b_n$] (bn) {};
		\path (-0.5,-5) node[][label=180:\rotatebox{130}{$\ddots$}] (ldots2) {};
		\path (1.5,-5) node[][label=180:\rotatebox{130}{$\ddots$}] (rdots2) {};
		\draw (a2) -- (b1);
		\draw (a3) -- (b1);
		\draw (a3) -- (b2);
		\draw (an) -- (b1);
		\draw (an) -- (b2);
		\draw (an) -- (b3);
	\end{tikzpicture}
\end{center}

Очевидно, что граф $B$ совершенно ненётеров. Далее приведем несколько замечаний о совершенно ненётеровых графах.

\begin{comment}\label{comment:sov-nonnoether}
	Каждый совершенно ненётеров граф $\Gamma$ не является нётеровым по уравнениям в языке $\Lg$: последовательности уравнений $S = \{E(x, b_i)\}_{i \in \NN}$ и вершин $A = \{a_i\}_{i \in \NN}$, где каждая вершина $a_i$ смежна со всеми вершинами $b_j$ при $j < i$ и не смежна с $b_i$, удовлетворяют условиям {\it леммы \ref{lemma:kotov}} в графе $\Gamma$.
\end{comment}

\begin{comment}\label{comment:k-nonnoether}
	Если мы отождествим все парные вершины базисного ненётерова графа, то получим счетную клику $K$, которая не является совершенно ненётеровым графом. Действительно, обозначим через $c_i$ результат отождествления вершин $a_i$ и $b_i$ графа $B$. Тогда, в силу смежности вершины $b_j$ со всеми вершинами $a_i$ при $j < i$, полученная вершина $c_j$ будет смежна со всеми $c_i$. Отсюда следует, что счетная клика $K$ в категории $\simp$ ненётерова, так как $E(c_i, c_i)$ ложно в категории простых графов $\simp$. Наоборот, в категории $\loop$ счетная клика является нётеровой в силу истинности уравнений вида $E(c_i, c_i)$ в этой категории.
\end{comment}



\begin{comment}
	Любой граф, содержащий в качестве индуцированного подграфа ненётеров граф, ненётеров по уравнениям. Действительно, по {\it теореме \ref{theorem:onevariable-nonnoether}}, в произвольном ненётеровом графе $\Gamma$ существуют последовательности уравнений $(E(x,b_i))_{i \in \NN}$ и вершин $(a_i)_{i \in \NN}$ таких, что $\Gamma \not \models E(a_i,b_i)$ для всех $i$ и $\Gamma \models E(a_i,b_j)$ для всех $i > j$. Пусть $\Gamma$ индуцированный подграф графа $H$. По определению индуцированного подграфа, $E_\Gamma(u,v) = E_H(u,v)$. Значит последовательности уравнений $(E(x,b_i))_{i \in \NN}$ и вершин $(a_i)_{i \in \NN}$ удовлетворяют условиям {\it леммы \ref{lemma:kotov}} в графе $H$.
\end{comment}

Граф, содержащий счетную клику $K$ в качестве индуцированного подграфа будем называть {\it надкликой}. Следующая ключевая лемма показывает, что если граф ненётеров и не является кликой, то он совершенно ненётеров.

\begin{lemma}\label{lemma:predtheorem-nonnoether}
	Пусть $\Gamma$ - произвольный ненётеров граф, либо из категории $\simp$, либо из $\loop$. Тогда если $\Gamma$ не является надкликой, то он совершенно ненётеров.
\end{lemma}

\begin{proof}	 
	 Пусть граф $\Gamma$ ненётеров по уравнениям, но не является надкликой. Тогда, по {\it теореме \ref{theorem:onevariable-nonnoether}}, существуют последовательности вершин $(a_i)_{i \in \NN}$ и уравнений $S(x) = (E(x,b_i))_{i \in \NN}$ такие, что $\Gamma \not \models E(a_i,b_i)$ для всех $i \in \NN$, и $\Gamma \models E(a_i,b_j)$ для всех $i > j$. 
	 
	 Обозначим через $I_c = \{i \in \NN | a_i = b_i\}$ множество индексов, для которых вершины $a_i$, $b_i$ совпадают. В силу {\it замечания \ref{comment:k-nonnoether}} имеем, что раз $\Gamma$ не является надкликой, то множество $I_c$ конечно. Тогда, в силу {\it следствия \ref{cor:kotov}}, существует бесконечная подсистема уравнений $(E(x, b_i))_{i \not \in I_c}$ и подпоследовательность вершин $(a_i)_{i \not \in I_c}$, которые удовлетворяют условиям {\it леммы \ref{lemma:kotov}}. Поэтому далее будем считать, что $I_c$ --- пустое множество.	 
	 Заметим, что если все вершины $a_i, b_j, \ i \neq j \in \NN$, попарно различны в графе $\Gamma$, то $\Gamma$ совершенно ненётеров и, следовательно, он ненётеров по уравнениям. Пусть теперь не все из вершин $a_i,b_j$, где $i, j \in \NN $, попарно различны. 
 
	По множеству вершин $\{a_i, b_i | i \in \NN \}$ графа $\Gamma$ построим граф $\Gamma_{lev}$ следующим образом: паре вершин $a_i, b_i$ графа $\Gamma$ соответствует вершина $c_i$ графа $\Gamma_{lev}$, и вершины $c_i, c_j$ графа $\Gamma_{lev}$ смежны в том и только в том случае, когда $a_i$ совпадает с $b_j$ или $a_j$ совпадает с $b_i$ в графе $\Gamma$. 
	 
	Во-первых, заметим, что $b_i$ не может совпадать с $b_j$ для любых $i,j \in \NN$, так как в системе $S$ нет одинаковых уравнений. Во-вторых, $a_i$ не может совпадать с $a_j$, в силу смежности $a_j$ с $b_i$ и несмежности $a_i$ с $b_i$ для любых $i < j$. Следовательно, степень любой вершины графа $\Gamma_{lev}$ не больше $2$. Из этого следует (см., например, \cite{DistelGraphs}, Глава 5. <<Раскраска>>), что любой конечный подграф графа $\Gamma_{lev}$ может быть раскрашен не более чем тремя цветами. Следующая теорема из \cite{Erdos} по сути является адаптацией теоремы компактности Гёделя-Мальцева для раскрасок графов:

\begin{theorem}\label{theorem:erdos} Пусть $k$ --- натуральное число и пусть граф $G$ имеет свойство, что каждый его конечный подграф может быть раскрашен $k$ цветами. Тогда и сам граф $G$ допускает раскраску $k$ цветами.
\end{theorem}
	 
	 Таким образом, по {\it теореме \ref{theorem:erdos}}, все вершины бесконечного графа $\Gamma_{lev}$ можно раскрасить не более чем тремя цветами. Выберем бесконечное множество вершин одного цвета в графе $\Gamma_{lev}$ и заметим, что в индуцированном подграфе $\Gamma_{lev}^c$ на этих вершинах нет ребер. Значит, все вершины $\{a_i,b_i\}$ графа $\Gamma$, соответствующие вершинам графа $\Gamma_{lev}^c$, попарно различны. Следовательно, граф $\Gamma$ совершенно ненётеров.
\end{proof}

Подытоживая результаты {\it замечаний \ref{comment:sov-nonnoether}}, \ref{comment:k-nonnoether} и {\it леммы \ref{lemma:predtheorem-nonnoether}}, мы получаем критерий нётеровости графов в категориях простых графов $\simp$ и неориентированных графов с петлями $\loop$, сформулированный на языке запрещённых подграфов:

\begin{theorem}\label{theorem:nonnoether}
	Справедливы следующие утверждения:
	
	\begin{list}{}{}
		\item 1. Граф из категории $\simp$ ненётеров по уравнениям тогда и только тогда, когда он либо совершенно ненётеров, либо является надкликой.
		\item 2. Граф из категории $\loop$ ненётеров по уравнениям тогда и только тогда, когда он совершенно ненётеров.
	\end{list}
\end{theorem}

Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003.

\bigskip
	
	\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

		\bibitem{Mon} Daniyarova E., Miasnikov A., Remeslennikov V.,
		{\it Algebraic geometry over algebraic systems},
		Publishing House of SB RAS, Novosibirsk, (2016), 243 p.

		\bibitem{Remeslen1} Daniyarova E., Miasnikov A., Remeslennikov V.,
		{\it Unification theorems in algebraic geometry},
		Algebra and Discrete Mathematics. {\bf 1}, (2008), 80-112.

		\bibitem{Remeslen2} Daniyarova E.U., Miasnikov A.G., Remeslennikov V.N.,
		{\it Algebraic geometry over algebraic systems. II. Foundations},
		Fundament. and app. math. \textbf{17}:1, (2012), 65-106. (in Russian).

		\bibitem{BMRom} Baumslag G., Myasnikov A., Roman'kov V.,
		{\it Two theorems about Equationally noetherian groups},
		J. Algebra. {\bf 194}, (1997), 654-664.
		
		\bibitem{BMR} Baumslag G., Myasnikov A., Remeslennikov V.,
		{\it Algebraic geometry over groups I: Algebraic sets
		and ideal theory}, J. Algebra. {\bf 219}, (1999), 16-79.
		
		\bibitem{ShahShevl} Shahriyary M., Shevlyakov A.,
		{\it Direct products, varieties, and compactness conditions},
		Groups Complexity Cryptology. {\bf 9}:2, (2017), 159–166.
		
		\bibitem{Romanovskiy} Gupta Ch.K., Romanovskii N.S.,
		{\it The property of being equationally Noetherian for some soluble groups},
		Algebra and Logic. \textbf{46}:1, (2007),  46–59.
		
		\bibitem{KotovArticle} Kotov M.V.,
		{\it Several remarks on equationally Noetherian property},
		Herald of Omsk University. {\bf 2}, (2013), 24-28. (in Russian).
	
		\bibitem{DistelGraphs} Diestel R.,
		{\it Graph theory},
		Novosibirsk: Institute of Mathematics Publishing House, 2002.
		
		\bibitem{Erdos} deBruijn N. G., Erdos P., A colour problem for infinite graphs and a problem in the theory of relations, Kon. Ned. Akad. Wetensch. Proc. {\bf A54}, (1951), 371-373.
		
	\end{thebibliography}
	
\end{document}

