\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

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

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


\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

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

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 20, № 2, стр. 144--145 (2023) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[\sc Алгебры бинарных изолирующих формул\\ для
теорий модулярных произведений графов]{\large Алгебры бинарных изолирующих формул\\ для
теорий модулярных произведений графов}
\author[Д.Ю. Емельянов]{{\bf \large \textsc{Д.Ю. Емельянов}}\protect\orcidicon{0000-0001-8827-2630}\\ \\
%\textit{(заполняется редактором)}
}%
\address{Emelyanov Dmitry Yurevich  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Novosibirsk State Technical University,
\newline\hphantom{iii} K. Marx, 20,
\newline\hphantom{iii} 630073, Novosibirsk, Russia}%
\email{\textcolor{blue}{dima-pavly@mail.ru}}%

\thanks{\sc Emelyanov, D.Y.,
Algebras of binary isolating formulas for
the theory of modular products of graphs}
\thanks{\copyright \ 2025 Емельянов Д.Ю.}
\thanks{\rm Исследование выполнено за счет гранта Российского научного фонда № 24-21-00096, https://rscf.ru/project/24-21-00096/.}
\thanks{\it Поступила 3 июня 2025 г., опубликована 31 декабря 2025 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} The distribution algebras of binary isolating and semi-isolating formulas are objects that are derived for a given theory, and they indicate the relationships between the binary formulas of the theory. These algebras are useful for classifying theories and determining which algebras correspond to which theories. The article discusses the algebras of binary formulas for modular products and provides Cayley tables for these algebras. On the basis of the constructed tables, theorems are formulated describing all the distribution algebras of binary formulas for theories of modular multiplications of regular polygons among themselves. This concept is a useful tool for understanding the relationships between the binary formulas of a given theory.\medskip

\noindent{\bf Keywords:} algebra of binary isolating formulas, modular product, model theory, Cayley tables.
 \end{quote}
}

\bigskip

\section{Введение}
Эта статья продолжает исследование алгебр распределений
бинарных изолирующих формул {\rm \cite{EmIrk,EmDek, ShS, SuCCMCT, Su08}}: описываются
такие алгебры для теорий унаров, декартовых произведений графов, а также их некоторые обобщения
для полуизолирующих формул.

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

Описание алгебр распределений бинарных изолирующих формул
позволяет классифицировать теории из данного класса по производным
алгебраическим объектам. В настоящей работе предлагается такая
классификация для структур модулярных произведений графов, ограниченных на множества
реализаций фиксированного типа. В теореме \eqref{teor1}
показано, что алгебры подразделяются на две разновидности,
каждая из которых в определенной степени дает возможность
восстановить бинарную структуру данного $1$-типа.

\section{Алгебры бинарных изолирующих формул для теорий модулярных произведений графов}

Модулярные произведения графов представляют собой мощный инструмент для построения новых графов из существующих с помощью специальных операций комбинирования. В таких произведениях вершины нового графа соответствуют парам вершин исходных графов, а рёбра определяются на основе заданных правил смежности. Эта конструкция находит широкое применение в различных областях, включая теорию графов, дискретную математику, теорию кодирования и оптимизацию, позволяя изучать сложные сетевые структуры и их свойства.

Определение модулярного произведения заключается в следующем: для двух графов $G$ и $H$ их модулярное произведение $G \ast H$ имеет множество вершин, равное декартову произведению $V(G) \times V(H)$. Рёбра в новом графе проводятся между парами вершин $(u_1, v_1)$ и $(u_2, v_2)$ тогда и только тогда, когда либо $u_1$ смежна с $u_2$ в $G$ и одновременно $v_1$ смежна с $v_2$ в $H$, либо $u_1$ не смежна с $u_2$ в $G$ и $v_1$ не смежна с $v_2$ в $H$. Это определение делает модулярное произведение универсальным инструментом для анализа комбинаторных свойств графов, так как оно учитывает как совпадения, так и различия в структурах исходных графов.

Одним из ключевых применений модулярных произведений является теория раскраски графов. Хроматическое число модулярного произведения $G \ast H$ тесно связано с хроматическими числами исходных графов, что позволяет использовать эту операцию для решения задач минимизации количества цветов. Например, если оба графа $G$ и $H$ являются двудольными, их модулярное произведение может обладать более сложной структурой, требующей дополнительного анализа для определения точного хроматического числа. Кроме того, модулярные произведения играют важную роль в теории информации и кодировании, где они помогают строить коды, исправляющие ошибки, за счёт моделирования допустимых переходов между кодовыми словами.

Нужно отметить связь модулярных произведений с теорией моделей. В этом контексте вершины и рёбра графов можно рассматривать как модели с определёнными предикатами смежности, а само модулярное произведение -- как результат применения логических операций к этим предикатам. Такой подход позволяет изучать перенос свойств исходных графов, таких как транзитивность или отсутствие треугольников, на их модулярное произведение. Например, если оба графа $G$ и $H$ не содержат треугольников, то при определённых условиях их модулярное произведение $G \ast H$ также будет лишено треугольников.

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


Далее мы рассмотрим алгебры, порождаемые операцией модулярного умножения рёбер в графах полигональной структуры.

При модулярном поизведении ребра на ребро ${H\times H}$ получим две одинаковые алгебры с метками
$\rho_{\nu(p)}=\{0, 1\}$, задающиейся произведениями меток:

\begin{center}
$0 \cdot 0=\{0\}$,

$0 \cdot 1=\{1\}$,

$1 \cdot 1=\{0,1\}$,

$1 \cdot 0=\{1\}$.
\end{center}

Алгебра модулярного произведения графа ребра на треугольник
${H \times T}$ с метками $\rho_{\nu(p)} = {0,1,2,3}$
определяется следующими произведениями меток:

\begin{center}
\begin{tabular}{cc}
$0 \cdot 0 = \{0\}$,& $0 \cdot 1 = \{1\}$, \\
$1 \cdot 0 = \{1\}$,& $1 \cdot 1 = \{0, 2\}$, \\
$1 \cdot 2 = \{0, 1\}$,& $1 \cdot 3 = \{0, 2\}$, \\
$2 \cdot 0 = \{2\}$,& $2 \cdot 1 = \{1, 2\}$, \\
$2 \cdot 2 = \{0, 1\}$,& $2 \cdot 3 = \{1, 3\}$, \\
$3 \cdot 0 = \{3\}$,& $3 \cdot 1 = \{0, 2\}$, \\
$3 \cdot 2 = \{1, 3\}$,& $3 \cdot 3 = \{0, 2\}$.
\end{tabular}
\end{center}

При модулярном произведении графов ребра и квадрата
${ H\times Q}$  получим две одинаковые алгебры с множеством  меток  $\rho_{\nu(p)}=\{0,1,2\}$, которые задаются произведениями меток:

\begin{center}
\begin{tabular}{cc}
$0 \cdot 0 = \{0\}$,&$0 \cdot 1 = \{1\}$, \\
$1 \cdot 0 = \{1\}$,&$1 \cdot 1 = \{0, 2\}$, \\
$1 \cdot 2 = \{1, 3\}$,&$2 \cdot 0 = \{2\}$, \\
$2 \cdot 1 = \{1, 3\}$,&$2 \cdot 2 = \{0, 2\}$.
\end{tabular}
\end{center}

Алгебра для модулярного произведения графов ребра и пятиугольника 
${H\times P}$ с множеством  меток  $\rho_{\nu(p)}=\{0,1,2,3,4,5\}$
задается произведениями меток:

\begin{center}
\begin{tabular}{cc}
$0 \cdot 0 = \{0\}$,& $0 \cdot 1 = \{1\}$, \\
$1 \cdot 0 = \{1\}$,& $1 \cdot 1 = \{0, 2\}$,\\
$1 \cdot 2 = \{1, 3\}$,&$1 \cdot 3 = \{0, 2, 4\}$,\\
$1 \cdot 4 = \{1, 3, 5\}$,&$1 \cdot 5 = \{0, 2, 4\}$,\\
$2 \cdot 0 = \{2\}$,&$2 \cdot 1 = \{1, 3\}$,\\
$2 \cdot 2 = \{0, 2, 4\}$,&$2 \cdot 3 = \{1, 3, 5\}$,\\
$2 \cdot 4 = \{0, 2, 4\}$,&$2 \cdot 5 = \{1, 3, 5\}$,\\
$3 \cdot 0 = \{3\}$,&$3 \cdot 1 = \{0, 2, 4\}$,\\
$3 \cdot 2 = \{1, 3, 5\}$,&$3 \cdot 3 = \{0, 2, 4\}$,\\
$3 \cdot 4 = \{1, 3, 5\}$,&$3 \cdot 5 = \{0, 2, 4\}$,\\
$4 \cdot 0 = \{4\}$,&$4 \cdot 1 = \{1, 3, 5\}$,\\
$4 \cdot 2 = \{0, 2, 4\}$,&$4 \cdot 3 = \{1, 3, 5\}$,\\
$4 \cdot 4 = \{0, 2, 4\}$,&$4 \cdot 5 = \{1, 3, 5\}$,\\
$5 \cdot 0 = \{5\}$,& $5 \cdot 1 = \{0, 2, 4\}$,\\
$5 \cdot 2 = \{1, 3, 5\}$,&$5 \cdot 3 = \{0, 2, 4\}$,\\
$5 \cdot 4 = \{1, 3, 5\}$,&$5 \cdot 5 = \{0, 2, 4\}$.
\end{tabular}
\end{center}

При модулярном произведении графов ребра и шестиугольника
${ H\times Q}$  получим две одинаковые алгебры с множеством  меток  $\rho_{\nu(p)}=\{0,1,2\}$, которые задаются следующей
таблицей:
\begin{center}
\begin{tabular}{cc}
$0 \cdot 0 = \{0\}$,&$0 \cdot 1 = \{1\}$, \\
$1 \cdot 0 = \{1\}$,&$1 \cdot 1 = \{0, 2\}$, \\
$1 \cdot 2 = \{1, 3\}$,&$2 \cdot 0 = \{2\}$, \\
$2 \cdot 1 = \{1, 3\}$,&$2 \cdot 2 = \{0, 2\}$.
\end{tabular}
\end{center}


Алгебру для модулярного произведения графов
${ H\times G}$  обозначим через  $\mathfrak{M_o}$ с метками
$\{1,2,3, \dots, n\}$, где $n$ --- нечетное число, равное диаметру
полученного при умножении графа. Получим две одинаковые алгебры, которые задаются следующей
таблицей:

\begin{center}
\begin{tabular}{ccc}
$0 \cdot 0 = \{0\}$ & $0 \cdot 1 = \{1\}$ & $0 \cdot 2 = \{2\}$ \\
$1 \cdot 0 = \{1\}$ & $1 \cdot 1 = \{0, 2\}$ & $1 \cdot 2 = \{1, 3\}$ \\
$1 \cdot 3 = \{0, 2\}$ & $2 \cdot 0 = \{2\}$ & $2 \cdot 1 = \{1, 3\}$ \\
$2 \cdot 2 = \{0, 2, 4\}$ & $2 \cdot 3 = \{1, 3, 5\}$ & $3 \cdot 0 = \{3\}$ \\
$3 \cdot 1 = \{0, 2, 4\}$ & $3 \cdot 2 = \{1, 3, 5\}$ & $3 \cdot 3 = \{0, 2, 4, 6\}$ \\
$4 \cdot 0 = \{4\}$ & $4 \cdot 1 = \{1, 3, 5\}$ & $4 \cdot 2 = \{0, 2, 4, 6\}$ \\
$4 \cdot 3 = \{1, 3, 5, \ldots, n-1\}$ & $4 \cdot 4 = \{0, 2, 4, \ldots, n\}$ & \\
$\vdots$ & $\vdots$ &  $\vdots$\\
$n \cdot 0 = \{n\}$ & $n \cdot 1 = \{1, 3, 5, \ldots, n-1\}$ & $n \cdot 2 = \{0, 2, 4, \ldots, n\}$ \\
$n \cdot 3 = \{1, 3, 5, \ldots, n-1\}$ & $n \cdot 4 = \{0, 2, 4, \ldots, n\}$ & $\ldots$\\
& $n \cdot n = \{0, 2, 4, \ldots, n\}$&
\end{tabular}
\end{center}

Алгебру для модулярного произведения графов
${ H\times G}$  обозначим через  $\mathfrak{M_e}$ с метками
$\{1,2,3, \dots, n\}$, где $n$ --- четное число, равное диаметру
полученного при умножении графа. Получим две одинаковые алгебры, которые задаются следующей
таблицей:
\begin{center}
\begin{tabular}{ccc}
$0 \cdot 0 = \{0\}$ & $0 \cdot 1 = \{1\}$ & $0 \cdot 2 = \{2\}$ \\
$1 \cdot 0 = \{1\}$ & $1 \cdot 1 = \{0, 2\}$ & $1 \cdot 2 = \{1, 3\}$ \\
$1 \cdot 3 = \{0, 2\}$ & $2 \cdot 0 = \{2\}$ & $2 \cdot 1 = \{1, 3\}$ \\
$2 \cdot 2 = \{0, 2, 4\}$ & $2 \cdot 3 = \{1, 3, 5\}$ & $3 \cdot 0 = \{3\}$ \\
$3 \cdot 1 = \{0, 2, 4\}$ & $3 \cdot 2 = \{1, 3, 5\}$ & $3 \cdot 3 = \{0, 2, 4, 6\}$ \\
$4 \cdot 0 = \{4\}$ & $4 \cdot 1 = \{1, 3, 5\}$ & $4 \cdot 2 = \{0, 2, 4, 6\}$ \\
$4 \cdot 3 = \{1, 3, 5, \ldots, n-1\}$ & $4 \cdot 4 = \{0, 2, 4, \ldots, n\}$ & \\
$\vdots$ & $\vdots$ &  $\vdots$\\
$n \cdot 0 = \{n\}$ & $n \cdot 1 = \{1, 3, 5, \ldots, n\}$ & $n \cdot 2 = \{0, 2, 4, \ldots, n-1\}$ \\
$n \cdot 3 = \{1, 3, 5, \ldots, n\}$ & $n \cdot 4 = \{0, 2, 4, \ldots, n-1\}$ &  $\ldots$\\
 &$n \cdot n = \{0, 2, 4, \ldots, n-1\}$ &
\end{tabular}
\end{center}


\begin{theorem} \label{teor1}
 Если $T$ --- теория модулярного произведения графов, $\mathfrak{M}$ --- алгебра бинарных изолирующих формул теории $T$, то агебра $\mathfrak{M}$ изоморфна алгебре $\mathfrak{M_o}$ или $\mathfrak{M_e}$.
\end{theorem}

Примеры производных графов при модулярном произведении с их таблицами Кэлли можно посмотреть на сайте https://graph-product.ru/. Данные были рассчитаны с помощью написанной мной программы.

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


\bibitem{EmIrk} Емельянов Д.Ю. Об алгебрах распределений бинарных формул теорий унаров //
Известия Иркутского государственного университета. Серия
Математика. 2016. Т.~17. С.~23--36.

\bibitem{Em19} Емельянов Д.Ю. Алгебры бинарных изолирующих формул для теорий симплексов //
Algebra and Model Theory 11. Collection of papers. Novosibirsk~:
Edition of NSTU, 2017, pp. 66--74.

\bibitem{EmDek} Емельянов Д.Ю. Алгебры бинарных изолирующих формул для
теорий декартовых произведений графов // Algebra and model theory
12. Collection of papers, Novosibirsk~: NSTU Publisher, 2019.
С.~21--31.

\bibitem{Em05} Емельянов Д.Ю. Алгебры распределений бинарных формул для теорий архимедовых
тел // Известия Иркутского государственного университета. Серия
Математика. 2019. Т.~28. С.~36--52.

\bibitem{Em06} Емельянов Д.Ю., Судоплатов С.В. Структура алгебр бинарных формул полигонометрических теорий с условием симметрии // Siberian Electronic Mathematical Reports.
2020. Vol. 17. P. 1--20.

\bibitem{EmSuC} Д. Ю. Емельянов, Б. Кулпешов, С. В. Судоплатов {\it  Алгебры бинарных формул : монография}. - Новосибирск : Изд-во НГТУ, 2023. - 330 с. - ISBN 978-5-7782-5028-4. - DOI: 10.17212/978-5-7782-5028-4.

\bibitem{Gena} \textit{Graph symmetry: algebraic methods and applications}, eds. Hahn G., Sabidussi G.,
Springer, 1997, vol.~497, 418~p.

\bibitem{Ha}{\em Харари Ф.} Теория графов~/ Ф.~Харари.~--- М.~: Едиториал УРСС,
2003.~--- 300~с.

\bibitem{ShS} Shulepov I.V., Sudoplatov S.V. Algebras of distributions
for isolating formulas of a complete theory // Siberian Electronic
Mathematical Reports. 2014. Vol.~11. P.~380--407.

\bibitem{Su08} Sudoplatov S.V. Hypergraphs of prime models
and distributions of countable models of small theories //
J.~Math. Sciences. 2010. Vol.~169, No.~5. P.~680--695.
https://doi.org/10.1007/s10958-010-0069-9

\bibitem{Su122} Sudoplatov S.V. Algebras of distributions for semi-isolating formulas of a
complete theory // Siberian Electronic Mathematical Reports. 2014.
Vol.~11. P.~408--433.

\bibitem{SuCCMCT} Sudoplatov S.V. Classification of countable models of
complete theories. Part~1, Novosibirsk~: NSTU Publisher, 2018.
376~p.

\end{thebibliography}
\end{document}
