\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{tikz}


\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{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%
	\address{Aleksei L’vovich Perezhogin  % Контактные данные всех авторов и место работы указываются только на английском языке
		\newline\hphantom{iii} Sobolev Institute of Mathematics,
		\newline\hphantom{iii} pr. Koptyuga, 4,
		\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
	\email{\textcolor{blue}{pereal@math.nsc.ru}}%

\address{Igor Sergeevich Bykov   % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} Novosibirsk State University,
	\newline\hphantom{iii} Pirogova str., 1,
	\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{\textcolor{blue}{igor.s.bykov@yandex.ru}}%


\address{Sergei Vladimirovich Avgustinovich   % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{\textcolor{blue}{avgust@math.nsc.ru}}%

\thanks{\sc Perezhogin, A.L., Bykov, I.S., Avgustinovich, S.V.,
Small length circuits in Eulerian orientations of graphs}
\thanks{\copyright \ 2023 Пережогин А.Л., Быков И.С., Августинович С.В.}
\thanks{\rm Исследование выполнено в рамках государственного задания ИМ СО РАН (проект
№ FWNF-2022-0018)}
\thanks{\it Поступила 1 января 2023 г., опубликована 31 декабря 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} In this paper we investigate estimates for number of 3-, 4- and 5-circuits in eulerian tournaments and 4-circuits in eulerian orientations of complete bipartite graphs and hypercubes.
By using obtained relations, we prove uniqueness (up to isomorphism) of orientations, which reach maximum number of 4-circuits in all graph families mentioned above.
\medskip

\noindent{\bf Keywords:} Eulerian orientation of graph, circuit, tournament, complete bipartite graph, boolean cube.
 \end{quote}
}

\bigskip

\section{Введение}

Ориентацией графа $G$ назовем орграф, получаемый из $G$ заменой каждого ребра $vu$ на ровно одну из дуг $vu$ или $uv$. В статье для широких классов графов изучается число контуров малой длины (3, 4 и 5) в соответствующих эйлеровых ориентациях. Две ориентации произвольного графа G называются изоморфными, если одну из другой можно получить действием какого-либо автоморфизма графа G. Авторам хотелось бы понять, как связаны свойства графа со свойствами его ориентаций, в частности - с количествами контуров в них разной длины. Главный вопрос - при каких условиях упомянутые количества позволяют граф однозначно  определить (с точностью до изоморфизма). Также для нас вдохновляющими были исследования \cite{Kir2,Kir1,Tar}, связывающие тему ориентаций графов с исследованием совершенных структур.
Везде в дальнейшем мы будем иметь дело только с регулярными связными графами четной степени, причем рассматриваемые ориентации будут в основном эйлеровыми, то есть такими, у которых во всех вершинах полустепени исхода и захода одинаковые. У каждой такой ориентации естественно обеспечено существование эйлерова цикла. Ранее внимание исследователей было сосредоточено на перечислении различных ориентаций фиксированных помеченных графов без учета изоморфизма \cite{Mih,Mck,Sch}.




%\section{Определения и обозначения}




Выходящей окрестностью $N^+(v)$ вершины $v$ в ориентации $Т$ графа $G$ будем называть множество вершин, в которые ведут дуги, начинающиеся в $v$. Аналогично определяется входящая окрестность $N^-(v)$. Пусть множество вершин графа $G$ упорядоченно $V(G)={v_1,\ldots,v_n}.$ Для ориентации $T$ графа $G$ определим $d^+(T)=(d^+_1,\ldots,d^+_n)$ и $d^-(T)=(d^-_1,\ldots,d^-_n)$, где $d^+_i=|N^+(v_i)|$ и $d^-_i=|N^-(v_i)|$, $0\le i\le n.$ Тогда для  $T$  определим степенную последовательность
$$d(T)=(d^-_1+d^+_1,\ldots,d^-_n+d^+_n).$$
Заметим, что если $G$ является регулярным графом, то по степенной последовательности его ориентации $T$ легко определяются кортежи $d^+(T)$ и $d^-(T)$.

Ориентация полного графа называется турниром.
Существуют два неизоморфных турнира на трех вершинах. Они же являются ориентациями 3-цикла (Рис. \ref{cicle3}).



	\begin{figure}
		\begin{center}
\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]%
\draw[-latex,thick](0,0)node
        {$$} to[out=60,in=-120] (1,1.73);
\draw[-latex,thick](1,1.73)node
        {$$} to[out=-60,in=120] (2,0);
\draw[-latex,thick](2,0)node
        {$$} to[out=180,in=0] (0,0);
\draw[-latex,thick](3,0)node
        {$$} to[out=60,in=-120] (4,1.73);
\draw[-latex,thick](4,1.73)node
        {$$} to[out=-60,in=120] (5,0);
\draw[-latex,thick](3,0)node
        {$$} to[out=0,in=180] (5,0);
\large

\coordinate [label=above:\textcolor{black}{$a$}] (B) at (1,-0.6);
\coordinate [label=above:\textcolor{black}{$b$}] (B) at (4,-0.6);

\end{tikzpicture}%\hspace{1cm}
			\caption{Типы ориентаций 3-циклов.}\label{cicle3}
		\end{center}
	\end{figure}




Существует 4 попарно неизоморфных турнира на четырех вершинах. Обозначим через $X$ турнир с $d(X)=(-1,-1,+1,+1)$, через $Y^+$ и $Y^-$ турниры с $d(Y^+)=(-1,-1,-1,+3)$ и $d(Y^-)=(-3,+1,+1,+1)$ соответственно, а через $Z$ турнир с $d(Z)=(-3,-1,+1,+3)$ (Рис. \ref{4tur}).


	\begin{figure}
		\begin{center}
\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]%
\draw[-latex,thick](0,0)node
        {$$} to[out=90,in=-90] (0,2);
\draw[-latex,thick](0,2)node
        {$$} to[out=0,in=180] (2,2);
\draw[-latex,thick](2,2)node
        {$$} to[out=-90,in=90] (2,0);
\draw[-latex,thick](2,0)node
        {$$} to[out=180,in=0] (0,0);
\draw[-latex,thick](0,0)node
        {$$} to[out=45,in=-135] (2,2);
\draw[-latex,thick](0,2)node
        {$$} to[out=-45,in=135] (2,0);


\draw[-latex,thick](3,0)node
        {$$} to[out=90,in=-90] (3,2);
\draw[-latex,thick](3,2)node
        {$$} to[out=0,in=180] (5,2);
\draw[-latex,thick](5,2)node
        {$$} to[out=-90,in=90] (5,0);
\draw[-latex,thick](3,0)node
        {$$} to[out=0,in=180] (5,0);
\draw[-latex,thick](3,0)node
        {$$} to[out=45,in=-135] (5,2);
\draw[-latex,thick](5,0)node
        {$$} to[out=135,in=-45] (3,2);


\draw[-latex,thick](6,0)node
        {$$} to[out=90,in=-90] (6,2);
\draw[-latex,thick](6,2)node
        {$$} to[out=0,in=180] (8,2);
\draw[-latex,thick](8,2)node
        {$$} to[out=-90,in=90] (8,0);
\draw[-latex,thick](6,0)node
        {$$} to[out=0,in=180] (8,0);
\draw[-latex,thick](8,2)node
        {$$} to[out=-135,in=45] (6,0);
\draw[-latex,thick](6,2)node
        {$$} to[out=-45,in=135] (8,0);

\draw[-latex,thick](9,0)node
        {$$} to[out=90,in=-90] (9,2);
\draw[-latex,thick](11,2)node
        {$$} to[out=180,in=0] (9,2);
\draw[-latex,thick](11,2)node
        {$$} to[out=-90,in=90] (11,0);
\draw[-latex,thick](9,0)node
        {$$} to[out=0,in=180] (11,0);
\draw[-latex,thick](9,0)node
        {$$} to[out=45,in=-135] (11,2);
\draw[-latex,thick](9,2)node
        {$$} to[out=-45,in=135] (11,0);


\large

\coordinate [label=above:\textcolor{black}{$X$}] (B) at (1,-0.6);
\coordinate [label=above:\textcolor{black}{$Y^+$}] (B) at (4,-0.6);
\coordinate [label=above:\textcolor{black}{$Y^-$}] (B) at (7,-0.6);
\coordinate [label=above:\textcolor{black}{$Z$}] (B) at (10,-0.6);

\end{tikzpicture}%\hspace{1cm}
			\caption{Типы 4-турниров.}\label{4tur}
		\end{center}
	\end{figure}


Турнир называется полутранзитивным, если его подтурниры, порожденные множествами $N^+(v)$ и $N^-(v)$ являются транзитивными для всех $v$.

\begin{proposition}\label{pro_tra}
Турнир является полутранзитивным тогда и только тогда, если он свободен от подтурниров типа $Y^+$ и $Y^-$.
\end{proposition}

Существует по четыре типа ориентации 4-цикла (Рис. \ref{cicle4}) и 5-цикла (Рис. \ref{cicle5}).

	\begin{figure}
		\begin{center}
\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]%
\draw[-latex,thick](0,0)node
        {$$} to[out=90,in=-90] (0,2);
\draw[-latex,thick](0,2)node
        {$$} to[out=0,in=180] (2,2);
\draw[-latex,thick](2,2)node
        {$$} to[out=-90,in=90] (2,0);
\draw[-latex,thick](2,0)node
        {$$} to[out=180,in=0] (0,0);
\draw[-latex,thick](3,0)node
        {$$} to[out=90,in=-90] (3,2);
\draw[-latex,thick](3,2)node
        {$$} to[out=0,in=180] (5,2);
\draw[-latex,thick](5,2)node
        {$$} to[out=-90,in=90] (5,0);
\draw[-latex,thick](3,0)node
        {$$} to[out=0,in=180] (5,0);
\draw[-latex,thick](6,0)node
        {$$} to[out=90,in=-90] (6,2);
\draw[-latex,thick](6,2)node
        {$$} to[out=0,in=180] (8,2);
\draw[-latex,thick](8,0)node
        {$$} to[out=90,in=-90] (8,2);
\draw[-latex,thick](6,0)node
        {$$} to[out=0,in=180] (8,0);
\draw[-latex,thick](9,0)node
        {$$} to[out=90,in=-90] (9,2);
\draw[-latex,thick](11,2)node
        {$$} to[out=180,in=0] (9,2);
\draw[-latex,thick](11,2)node
        {$$} to[out=-90,in=90] (11,0);
\draw[-latex,thick](9,0)node
        {$$} to[out=0,in=180] (11,0);
\large

\coordinate [label=above:\textcolor{black}{$A$}] (B) at (1,-0.6);
\coordinate [label=above:\textcolor{black}{$B$}] (B) at (4,-0.6);
\coordinate [label=above:\textcolor{black}{$C$}] (B) at (7,-0.6);
\coordinate [label=above:\textcolor{black}{$D$}] (B) at (10,-0.6);

\end{tikzpicture}%\hspace{1cm}
			\caption{Типы ориентаций 4-циклов.}\label{cicle4}
		\end{center}
	\end{figure}


	\begin{figure}
		\begin{center}
\begin{tikzpicture}[thick,scale=1.2,shorten >=2pt]%
\draw[-latex,thick](0.36,0)node
        {$$} to[out=108,in=-72] (0,1.12);
\draw[-latex,thick](0,1.12)node
        {$$} to[out=36,in=-144] (0.95,1.81);
\draw[-latex,thick](0.95,1.81)node
        {$$} to[out=-36,in=144] (1.9,1.12);
\draw[-latex,thick](1.9,1.12)node
        {$$} to[out=-108,in=72] (1.54,0);
\draw[-latex,thick](1.54,0)node
        {$$} to[out=180,in=0] (0.36,0);

\draw[-latex,thick](2.86,0)node
        {$$} to[out=108,in=-72] (2.5,1.12);
\draw[-latex,thick](2.5,1.12)node
        {$$} to[out=36,in=-144] (3.45,1.81);
\draw[-latex,thick](3.45,1.81)node
        {$$} to[out=-36,in=144] (4.4,1.12);
\draw[-latex,thick](4.4,1.12)node
        {$$} to[out=-108,in=72] (4.04,0);
\draw[-latex,thick](2.86,0)node
        {$$} to[out=0,in=180] (4.04,0);

\draw[-latex,thick](5.36,0)node
        {$$} to[out=108,in=-72] (5,1.12);
\draw[-latex,thick](5,1.12)node
        {$$} to[out=36,in=-144] (5.95,1.81);
\draw[-latex,thick](5.95,1.81)node
        {$$} to[out=-36,in=144] (6.9,1.12);
\draw[-latex,thick](6.54,0)node
        {$$} to[out=72,in=-108] (6.9,1.12);
\draw[-latex,thick](5.36,0)node
        {$$} to[out=0,in=180] (6.54,0);

\draw[-latex,thick](7.86,0)node
        {$$} to[out=108,in=-72] (7.5,1.12);
\draw[-latex,thick](8.45,1.81)node
        {$$} to[out=-144,in=36] (7.5,1.12);
\draw[-latex,thick](8.45,1.81)node
        {$$} to[out=-36,in=144] (9.4,1.12);
\draw[-latex,thick](9.4,1.12)node
        {$$} to[out=-108,in=72] (9.04,0);
\draw[-latex,thick](7.86,0)node
        {$$} to[out=0,in=180] (9.04,0);


\large

\coordinate [label=above:\textcolor{black}{$\alpha$}] (B) at (0.95,-0.6);
\coordinate [label=above:\textcolor{black}{$\beta$}] (B) at (3.45,-0.6);
\coordinate [label=above:\textcolor{black}{$\gamma$}] (B) at (5.95,-0.6);
\coordinate [label=above:\textcolor{black}{$\delta$}] (B) at (8.45,-0.6);

\end{tikzpicture}%\hspace{1cm}
			\caption{Типы ориентаций 5-циклов.}\label{cicle5}
		\end{center}
	\end{figure}

Обозначим через $f_\lambda(T)$ количество конфигураций типа $\lambda$ в ориентации $T$ графа $G$. Например, $f_a(X)=2$.


\begin{proposition}
	Для любой ориентации $T$ графа $G$ выполнено
	\begin{equation}
		\label{th1}
		f_D(T) = \sum_{u,v \in V(G)} \binom{|N^+(u) \cap N^+(v)|}{2}.
	\end{equation}
\end{proposition}

Ориентация графа $G$ называется эйлеровой, если в каждой вершине полустепень исхода равна полустепени захода. Для связного графа $G$ существует эйлерова ориентация тогда и только тогда, когда $G$ является эйлеровым.

В разделах 2, 3 и 4 рассматриваются 3-, 4- и 5-циклы в турнирах. Показано, что количества различных ориентаций как 4-циклов, так и 5-циклов в эйлеровых турнирах образуют однопараметрическое множество. Найдены оценки числа 4-контуров. Доказано, что верхняя оценка на число 4-контуров в эйлеровых турнирах достигается на единственном турнире. В разделе 5 аналогичные результаты для 4-циклов получены для эйлеровых ориентаций полного двудольного графа. В разделе 6 получены достижимые оценки на число 4-контуров в эйлеровых ориентациях булева куба четной размерности.











\section{3-циклы в турнирах}


Обозначим через $\Upsilon_{N,d}$ множество всех турниров на $N$ вершинах со степенной последовательностью $d$, а через $\Xi_{2n+1}$ множество всех эйлеровых турниров на $(2n+1)$ вершине.

\begin{proposition}
Для любого турнира $T\in \Upsilon_{N,d}$ выполнено
\begin{eqnarray}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
 \nonumber f_a(T) &=& \binom{N}{3}-\sum_{i=1}^N \binom{d^+_i}{2}, \\
 \label{eq_b} f_b(T) &=&  \sum_{i=1}^N \binom{d^+_i}{2}.
\end{eqnarray}
\end{proposition}
\begin{proof}
Очевидно, что $f_a(T)+f_b(T) = \binom{N}{3}.$  В $i$-ой вершине турнира ровно $\binom{d^+_i}{2}$ пар дуг, выходящих из вершины. Каждая такая пара порождает ровно один 3-цикл типа $b$.
\end{proof}





\begin{corollary}\label{eyl_tre}
Для любого эйлерова турнира $T\in \Xi_{2n+1}$ выполнено
\begin{eqnarray*}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
  f_a(T) &=& \frac{2n+1}{3}\binom{n}{2}, \\
  f_b(T) &=&  (2n+1) \binom{n}{2}.
\end{eqnarray*}
\end{corollary}

Обозначим через $M_a(N)$ наибольшее число 3-контуров в турнире среди всех турниров на $N$ вершинах.

\begin{corollary}
Для любого $n$ выполнено
\begin{eqnarray*}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
  M_a(2n+1) &=& \frac{(2n+1)n(n-1)}{6}, \\
  M_a(2n) &=&  \frac{n(n^2-1)}{3}.
\end{eqnarray*}
\end{corollary}
\begin{proof}
По неравенству Коши--Буняковского сумма (\ref{eq_b}) достигает минимума при $d^+(T)=(n,\ldots,n)$, если $N=2n+1$, и при $d^+(T)=(n-1,\ldots,n-1,n,\ldots,n)$, если $N=2n$. В первом случае искомое равенство получаем из Следствия \ref{eyl_tre}. Во втором случае имеем
$$
  M_a(2n) = \binom{2n}{3}-(n\binom{n-1}{2}+n\binom{n}{2}) =  \frac{n(n^2-1)}{3}.
$$

\end{proof}


\section{4-циклы в турнирах}



\begin{proposition}
Для любого турнира $T$ выполнено
\begin{eqnarray}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
\label{clikax}  f_A(T) &=& f_X(T), \\
\nonumber   f_B(T) &=& f_X(T)+f_Z(T)+3f_{Y^+}(T)+3f_{Y^-}(T), \\
\nonumber   f_C(T) &=& f_X(T)+f_Z(T), \\
\nonumber   f_D(T) &=& f_Z(T).
\end{eqnarray}
\end{proposition}
\begin{proof}
 Полный граф на четырех вершинах содержит три цикла длины 4.
Класс $X$  содержит циклы длины 4 типов $A$, $B$ и $C$. Классы $Y^+$ и $Y^-$ с содержат по три цикла длины 4 типа $B$. Класс $Z$  содержит циклы длины 4 типов $B$, $C$ и $D$.
\end{proof}

\begin{corollary}
Для любого турнира $T$ выполнено $$f_C(T)=f_A(T)+f_D(T).$$
\end{corollary}


Обозначим через $\Upsilon_{N,d}$ множество всех турниров на $N$ вершинах со степенной последовательностью $d$.

\begin{proposition}
Для любого турнира $T\in \Upsilon_{N,d}$ выполнено
\begin{eqnarray}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
\label{clik1}  f_{Y^+}(T)+f_Z(T) &=& \sum_{i=1}^N \binom{d^+_i}{3}, \\
\label{clik2}  f_{Y^-}(T)+f_Z(T) &=& \sum_{i=1}^N \binom{d^-_i}{3}, \\
\label{clik3}  f_X(T)+f_{Y^+}(T) &=& \frac{1}{2}\sum_{i=1}^N (\binom{d^-_i}{2}d^+_i-\binom{d^+_i}{3}), \\
\label{clik4}  f_X(T)+f_{Y^-}(T) &=& \frac{1}{2}\sum_{i=1}^N (\binom{d^+_i}{2}d^-_i-\binom{d^-_i}{3}).
\end{eqnarray}
\end{proposition}
\begin{proof}
Рассмотрим конфигурацию: вершина и три исходящих из нее дуги. С одной стороны, среди 4-клик такая конфигурация входит по одному разу в клики типа $Y^+$ и $Z$. С другой стороны, из $i$-ой вершины выходит $\binom{d^+_i}{3}$ таких конфигураций. Отсюда получаем равенство (\ref{clik1}). Аналогично, рассматривая вершину и три входящих в нее дуги, получаем равенство (\ref{clik2}).

Рассмотрим конфигурацию: вершина, две входящих и одна исходящая из нее дуга. Такая конфигурация встречается два раза в $X$, три раза в $Y^+$ и один раз в $Z$. С другой стороны, из $i$-ой вершины выходит $\binom{d^-_i}{2}d^+_i$ таких конфигураций. Следовательно,
\begin{equation}\label{clik21}
 2f_X(T)+3f_{Y^+}(T)+f_Z(T) = \sum_{i=1}^N \binom{d^-_i}{2}d^+_i.
\end{equation}
Вычитая равенство (\ref{clik1}) из (\ref{clik21}) получаем искомое равенство (\ref{clik3}). Аналогично доказывается равенство (\ref{clik4}).
\end{proof}



\begin{corollary}
Для любого эйлерова турнира $T\in \Xi_{2n+1}$ выполнено
\begin{eqnarray}
\label{clika1} f_{Y^-}(T)&=&f_{Y^+}(T),\\
\nonumber  f_{Y^-}(T)+f_Z(T) &=& (2n+1) \binom{n}{3}, \\
\label{clika2}  f_X(T)+f_{Y^-}(T) &=& (2n+1) \binom{n+1}{3}.
\end{eqnarray}
\end{corollary}
\begin{proof}
(\ref{clika1}) вытекает из равенства правых частей равенств (\ref{clik1}) и (\ref{clik2}) для эйлеровых турниров.
\end{proof}





\begin{proposition}
Для любого турнира $T\in \Upsilon_{N,d}$ выполнено
\begin{eqnarray*}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
  &&0 \le  f_{Y^+}(T)  \le  \sum_{i=1}^N M_a(d^+_i), \\
  &&0 \le  f_{Y^-}(T)  \le  \sum_{i=1}^N M_a(d^-_i).
\end{eqnarray*}
\end{proposition}
\begin{proof}
Вершина турнира и концы трех исходящих из этой вершины дуг образуют в турнире 4-клику типа $Y^+$ тогда и только тогда, когда концы этих трех дуг образуют 3-контур. Следовательно, 4-клик типа $Y^+$ с истоком в $i$-ой вершине не может быть больше, чем $M_a(d^+_i)$. Аналогично с 4-кликами типа $Y^-$.
\end{proof}


\begin{corollary}\label{eq_y}
Для любого эйлерова турнира $T\in \Xi_{2n+1}$ выполнено
\begin{equation*}
 0 \le  f_{Y^-}(T)=f_{Y^+}(T)  \le  (2n+1)M_a(n).
\end{equation*}
\end{corollary}

Из равенств (\ref{clikax}) и (\ref{clika2}) и Следствия \ref{eq_y} получаем следующие оценки на число 4-контуров в эйлеровых турнирах.
\begin{corollary}
Для любого эйлерова турнира $T\in \Xi_{2n+1}$ выполнено
\begin{equation}\label{eq_X}
 (2n+1) \binom{n+1}{3}-(2n+1)M_a(n) \le  f_{A}(T)  \le  (2n+1) \binom{n+1}{3}.
\end{equation}
\end{corollary}

Для любого $n\le 6$ в $\Xi_{2n+1}$ мы нашли турниры, достигающие нижней оценки \eqref{eq_X}.






\begin{theorem}
Для любого $n$ существует и единственный с точностью до изоморфизма эйлеров турнир $T\in \Xi_{2n+1}$, для которого
\begin{equation}\label{polutra}
f_{A}(T)  =  (2n+1) \binom{n+1}{3}.
\end{equation}
\end{theorem}
\begin{proof}
Равенство (\ref{polutra}) достигается в случае, когда $f_{Y^-}(T)=f_{Y^+}(T)=0$. Следовательно, по Предложению \ref{pro_tra} достаточно доказать, что эйлеров полутранзитивный турнир единственный. Действительно, рассмотрим какой-либо эйлеров полутранзитивный турнир $Т$ порядка  $(2n+1)$. Выберем какую-то его вершину $v$ и припишем ей метку $0$. Все вершины из $N^+(v)$ имеют естественное упорядочение в соответствии с тем транзитивным подтурниром, который они порождают. Занумеруем их числами от 1 до $n$ так, чтобы дуги шли от меньших номеров к большим. Аналогично поступим с вершинами из $N^-(v)$, занумеровав их от $(n+1)$ до $2n$. Пусть $j>i$. Докажем, что в турнире Т дуга из вершины с номером $i$ идет в вершину с номером $j$ тогда и только тогда, когда выполняется условие           $|j-i|<(n+1)$. Если оба числа $i$ и $j$ одновременно принадлежат $N^+(v)$ или $N^-(v)$, то соотношение выполняется автоматически. Если же они принадлежат разным множествам, то нам поможет индуктивное рассуждение. Заметим, что для вершины $v$, имеющей метку 0, условие выполнено по построению. Вершина с меткой n уже насыщена входящими дугами (начиная с этого места мы пользуемся только эйлеровостью графа), значит все оставшиеся ее дуги - исходящие. Аналогично можно восстановить все исходящие дуги из вершины с меткой $2n$. Переходя от метки $i$ к метке $(i+n)\bmod{(2n+1)}$ мы обойдем все вершины графа и убедимся в том, что условие везде выполнено. Таким образом, полутранзитивный турнир  восстанавливается однозначно и, следовательно, он единственный. Заметим, данный турнир имеет циклическую группу автоморфизмов, то есть  является
циркулянтом.
\end{proof}



\section{5-циклы в турнирах}

\begin{proposition}
Для любого турнира $T\in \Upsilon_{N,d}$ выполнено
\begin{eqnarray}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
\label{5cicle1}  f_\beta(T)+f_\gamma(T)+2f_\delta(T) &=& (N-3)(N-4)\sum_{i=1}^N \binom{d^+_i}{2}, \\
\label{5cicle2}  f_\delta(T)-f_\alpha(T) &=& (N-3)(N-4)(\sum_{i=1}^N \binom{d^+_i}{2}-\frac{3}{5}\binom{N}{3}).
\end{eqnarray}
\end{proposition}
\begin{proof}
Вершина с двумя выходящими из нее дугами встречается по одному разу в 5-циклах типа $\beta$ и $\gamma$, и по два раза в циклах типа $\delta$. С другой стороны, $i$-ая вершина входит в качестве такой вершины в $(N-3)(N-4)\binom{d^+_i}{2}$ различных 5-циклов. Следовательно, верно (\ref{5cicle1}).

Нетрудно видеть, что
\begin{equation}\label{5cicle3}
  f_\alpha(T)+f_\beta(T)+f_\gamma(T)+f_\delta(T)=12\binom{N}{5}.
\end{equation}
Из равенств (\ref{5cicle1}) и (\ref{5cicle3}) следует (\ref{5cicle2}).
\end{proof}

\begin{theorem}
Для любого эйлерова турнира $T\in \Xi_{2n+1}$ выполнено
\begin{eqnarray}
\label{551}  f_\delta(T)-f_\alpha(T) &=& \frac{1}{5}(2n+1)(2n-3)n(n-1)(n-3), \\
\label{552}  f_{\beta}(T)+3f_{\delta}(T) &=& \frac{1}{2}(2n+1)(2n-3)^2n(n-1), \\
\label{553}  f_\gamma(T)-f_\delta(T) &=& \frac{1}{2}(2n+1)(2n-3)n(n-1).
\end{eqnarray}
\end{theorem}
\begin{proof}
Равенство (\ref{551}) совпадает с (\ref{5cicle2}) в случае эйлеровых ориентаций. Для доказательства (\ref{552})  рассмотрим цепь из трех дуг, ориентированную так, что две внутренние вершины являются истоком и стоком. Такая конфигурация встречается три раза в 5-цикле типа $\delta$ и один раз в цикле типа $\beta$. С другой стороны, общее число 5-циклов с такой конфигураций можно посчитать следующим образом. Выберем дугу $(2n+1)n$ способами. Выберем по одной дуге из исходящих из начала и входящих в конец выбранной дуги $(n-1)^2$ способами. Среди выбранных таким образом цепей длины 3 встретятся замкнутые. Их $f_b(T)$ штук. Остается выбрать последнюю вершину 5-цикла $(2n-3)$ способами. Таким образом, из Следствия \ref{eyl_tre} имеем
\begin{eqnarray*}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
  f_{\beta}(T)+3f_{\delta}(T) &=& ((2n+1)n(n-1)^2-f_b(T))(2n-3) \\
   &=& \frac{1}{2}(2n+1)(2n-3)^2n(n-1).
\end{eqnarray*}
Равенство (\ref{553}) вытекает из (\ref{5cicle1}) и (\ref{552}).
\end{proof}













\section{4-циклы в ориентациях полных двудольных графов}

Обозначим через $\Theta_{N,d}$ множество всех ориентаций полного двудольного графа $K_{N,N}$ со степенной последовательностью $d$, а через $\Theta_{2n}$ все эйлеровы ориентации графа $K_{2n,2n}$.

\begin{proposition}
Для любой ориентации  $E\in \Theta_{N,d}$ выполнено
\begin{eqnarray}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
\label{4cicle2dol}  f_B(E)+f_C(E)+2f_D(E) &=& (N-1)\sum_{i=1}^{2N} \binom{d^+_i}{2}, \\
\label{4cicle2dol1}  f_A(E)-f_D(E) &=& \binom{N}{2}^2-(N-1)\sum_{i=1}^{2N} \binom{d^+_i}{2}.
\end{eqnarray}
\end{proposition}
\begin{proof}
Вершина с двумя выходящими из нее дугами встречается по одному разу в 4-циклах типа $B$ и $C$, и по два раза в циклах типа $D$. С другой стороны, $i$-ая вершина входит в качестве такой вершины в $(N-1)\binom{d^+_i}{2}$ различных 4-циклов. Следовательно, верно (\ref{4cicle2dol}).

Нетрудно видеть, что
\begin{equation}\label{4cicle2dol2}
  f_A(E)+f_B(E)+f_C(E)+f_D(E)= \binom{N}{2}^2.
\end{equation}
Из равенств (\ref{4cicle2dol}) и (\ref{4cicle2dol2}) следует (\ref{4cicle2dol1}).
\end{proof}

\begin{corollary}
\label{2dolSled}
Для любой эйлеровой ориентации  $E\in \Theta_{2n}$ выполнено
\begin{eqnarray*}
  f_A(E) - f_D(E) &=& n^2(2n-1), \\
  f_B(E)+4f_D(E) &=& 4n^2(n-1)^2, \\
  f_C(E)-2f_D(E) &=& 2n^2(n-1).
\end{eqnarray*}
\end{corollary}
\begin{proof}
Рассмотрим цепь из трех дуг, ориентированную так, что две внутренние вершины являются истоком и стоком. Такая конфигурация встречается четыре раза в 4-цикле типа $D$ и один раз в цикле типа $B$. С другой стороны, общее число 4-циклов с такой конфигураций можно посчитать следующим образом. Выберем дугу $4n^2$ способами. Выберем по одной дуге из исходящих из начала и входящих в конец выбранной дуги $(n-1)^2$ способами. Эти три дуги единственным образом замыкаются в 4-цикл.
\end{proof}


\begin{theorem}
	\label{bip7}
	Для любой эйлеровой ориентации $E \in \Theta_{2n}$ выполнено
	\begin{equation*}
		f_A(E) \leq n^4.
	\end{equation*}
\end{theorem}
\begin{proof}
	Из следствия \ref{2dolSled} имеем, что максимальное значение $f_A(E)$ достигается при максимуме $f_D(E)$.
	Найдем верхнюю оценку для $f_D(E)$ для произвольной ориентации $E$.
	
	Для каждой пары вершин $u,v$ ориентации $E$ очевидны оценки:
	\begin{equation}\dfrac{числит}{знамен}
		\label{bip8}
		0 \leq |N^+(u) \cap N^+(v)| \leq n.
	\end{equation}
	Заметим, что
	\begin{equation*}
		\sum_{u,v \in VK_{2n, 2n}} |N^+(u) \cap N^+(v)| = 4n\binom{n}{2},
	\end{equation*}
	так как каждая вершина графа вносит вклад $\binom{n}{2}$ в эту сумму.
	Из предложения \ref{th1} следует, что для максимизации $f_D(E)$ необходимо максимизировать
	\begin{equation}
		\label{bip9}
		\sum_{u,v \in VK_{2n, 2n}} |N^+(u) \cap N^+(v)|^2.
	\end{equation}
	Максимум выражения (\ref{bip9}) при ограничениях (\ref{bip8}) достигается, если среди мощностей всех пар пересечений выходящих окрестностей $n$ встречается $4\binom{n}{2}$ раз, а остальные мощности равны $0$.
	Отсюда следует, что
	\begin{equation*}
		f_D(E) \leq 4\binom{n}{2}^2.
	\end{equation*}
	
	Теперь вновь используя следствие \ref{2dolSled}, связывающее $f_A(E)$ и $f_D(E)$, получаем искомую оценку.
\end{proof}


\begin{theorem}
	Для любого $n$ существует и единственная с точностью до изоморфизма ориентация $E\in \Theta_{2n}$, для которой
	\begin{equation*}
		f_{A}(E) = n^4.
	\end{equation*}
\end{theorem}
\begin{proof}
	Из доказательства теоремы \ref{bip7} следует что оценка может достигаться только в случае, если множество вершин двудольного графа удастся разбить на 4 подмножества $S_1$, $S_2$, $S_3$, $S_4$, внутри которых для каждой вершины $v$ множество $N^+(v)$ одно и то же.
	Такая ориентация строится однозначно с точностью до изоморфизма следующим образом.
	
	Пусть $S_1$, $S_2$, $S_3$, $S_4$ - разбиение $4n$ вершин пустого графа $G$ на 4 множества одинаковой мощности $n$.
	Добавим в граф $G$ дуги:
	\begin{eqnarray*}
		% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
		\{(u,v)\ |\ u \in S_1, v \in S_2\}, \\
		\{(u,v)\ |\ u \in S_2, v \in S_3\}, \\
		\{(u,v)\ |\ u \in S_3, v \in S_4\}, \\
		\{(u,v)\ |\ u \in S_4, v \in S_1\}.
	\end{eqnarray*}
	Нетрудно видеть, что получившийся граф $G$ --- двудольный с долями $S_1 \cup S_3$ и $S_2 \cup S_4$.
	Пересечение окрестностей имеет мощность $n$ для вершин из одного множества и мощность $0$ в противном случае.
	Значит, на графе $G$ искомая оценка достигнута.
\end{proof}






\section{4-циклы в ориентациях гиперкубов}
Обозначим через $\Phi_{N,d}$ множество всех ориентаций графа $N$-мерного гиперкуба $Q_N$ со степенной последовательностью $d$, а через $\Phi_{2n}$ все эйлеровы ориентации графа $Q_{2n}$.

\begin{proposition}
	Для любой ориентации  $E\in \Phi_{N,d}$ выполнено
	\begin{eqnarray}
		% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
		\label{4cicleQ}  f_B(E)+f_C(E)+2f_D(E) &=& \sum_{i=1}^{2^N} \binom{d^+_i}{2}, \\
		\label{4cicleQ1}  f_A(E)-f_D(E) &=& 2^{N-2}\binom{N}{2}- \sum_{i=1}^{2^N} \binom{d^+_i}{2}.
	\end{eqnarray}
\end{proposition}

\begin{proof}
	Вершина с двумя выходящими из нее дугами встречается по одному разу в 4-циклах типа $B$ и $C$, и по два раза в циклах типа $D$. С другой стороны, $i$-ая вершина входит в качестве такой вершины в $\binom{d^+_i}{2}$ различных 4-циклов. Следовательно, верно (\ref{4cicleQ}).
	
	Нетрудно видеть, что
	\begin{equation}\label{4cicleQ2}
		f_A(E)+f_B(E)+f_C(E)+f_D(E)= 2^{N-2}\binom{N}{2}.
	\end{equation}
	Из равенств (\ref{4cicleQ}) и (\ref{4cicleQ2}) следует (\ref{4cicleQ1}).
\end{proof}
	
\begin{corollary}
	Для любой эйлеровой ориентации  $E\in \Psi_{2n}$ выполнено
	\begin{eqnarray*}
		% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
		f_B(E)+f_C(E)+2f_D(E) &=& 2^{2n} \binom{n}{2}, \\
		f_A(E)-f_D(E) &=& 2^{2n-2} n.
	\end{eqnarray*}
\end{corollary}

\begin{corollary}
	\label{4cicleQ3}
	Для любой эйлеровой ориентации  $E\in \Psi_{2n}$ выполнено
	\begin{eqnarray*}
		2^{2n-2} n \leq	f_A(E) \leq 2^{2n-2} n^2.
	\end{eqnarray*}
\end{corollary}

\begin{theorem}
	Для любого $n$ существует ориентация $E\in \Phi_{2n}$, для которой
	\begin{equation*}
			f_A(E) = 2^{2n-2}n.
	\end{equation*}
\end{theorem}
\begin{proof}
	Приведём пример такой ориентации.
	Рассмотрим ориентацию в $Q_{2n}$ получаемую возведением контура $C$ длины 4 (цикла типа $A$) в степень $n$.
	
	Посчитаем количество экземпляров $C$ в получившейся ориентации.
	Для каждого из $n$ направлений в получившемся торе будем иметь $2^{2n-2}$ контуров $C$ фиксированноо направления.
	
	Нетрудно видеть, что если цикл длины 4 образован рёбрами различных экземпляров $C$, то противоположные рёбра в таком цикле сонаправлены, а значит, тип рассматриваемого цикла не $A$.
\end{proof}

\begin{theorem}
	Для любого $n$ существует и единственная с точностью до изоморфизма ориентация $E\in \Phi_{2n}$, для которой
	\begin{equation*}
		f_A(E) = 2^{2n-2}n^2.
	\end{equation*}
\end{theorem}
\begin{proof}
	Для достижимости верхней оценки в Следствии \ref{4cicleQ3} достаточно получить ориентацию, не содержащую 4-циклов типа $B$ и $C$.
	Заметим, что если хотя бы одна пара противоположных рёбер в цикле сонаправлена, то данный цикл имеет тип либо $B$, либо $C$.
	Таким образом, необходимо построить ориентацию $Q_{2n}$, в которой в каждом 4-цикле противоположные рёбра ориентированы навстречу друг другу.
	Такая ориентация строится однозначно с точностью до изоморфизма следующим образом.
	
	Разобъём все $2n$ направлений в кубе на два равномощных множества $R_1$ и $R_2$.
	Теперь для всех вершин $Q_{2n}$ чётного веса полагаем, что все исходящие дуги имеют направления из $R_1$, а входящие --- направления из $R_2$.
	Для всех вершин $Q_{2n}$ нечётного веса напротив: все исходящие дуги имеют направления из $R_2$, а входящие --- направления из $R_1$.
	Нетрудно видеть, что в такой ориентации рёбра одного направления в каждом 4-цикле будут ориентированы навстречу друг другу.
\end{proof}

\section{Заключение}


В заключение хотелось бы обратить внимание читателя на ряд вопросов и гипотез, возникающих в результате проведенного исследования.
Две ориентации произвольного графа G называются $k$-эквивалентными, если одну из другой можно получить в результате последовательной замены ориентаций на противоположные в контурах длины $k$. Понятно, что для эквивалентности необходимо совпадение полустепеней исхода и захода во всех верщинах той и другой ориентации. Если не ограничивать себя контурами фиксированной длины, то отмеченное условие становится и достаточным для эквивалентности, в чем нетрудно убедиться.
Изучая число контуров малой длины мы исходим из того соображения, что для $k$-эквивалентности ориентаций необходимо существование хотя бы одного $k$-контура в каждой из них. Чем больше контуров, тем выше вероятность эквивалентности. Скажем, для сильно связных турниров известно (\cite{Chi}, Теорема 9.29), что каждый из них содержит контуры всех длин от 3 до порядка турнира. Однако неизвестно, будут ли $k$-эквивалентны любые два из них, имеющие одинаковые наборы полустепеней. Также небезынтересно, является ли полным инвариантом произвольного турнира спектр типов его циклов всех возможных длин. Проведенные исследования подтверждают данную гипотезу для малых порядков. Компьютерные эксперименты также показали, что нижняя оценка для числа 4-контуров для всех трех рассмотренных нами классов ориентаций достигается сразу на нескольких примерах.


%Пусть
%\begin{equation}\label{f1}
% A=B.
%\end{equation}






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

\bibitem{Kir2}
Kireeva T.~E.,
\href{http://doi.org/10.17377/semi.2017.14.060}{\it Orientation spectra of cubic graphs}, Siber. Electr. Math. Reports. 14 (2017) , 703–709. %[Russian, English abstract]

\bibitem{Kir1}
Kireeva T.~E.,
\href{http://doi.org/10.17377/semi.2018.15.111}{\it Perfect orientation colorings of cubic graphs}, Siber. Electr. Math. Reports. 15 (2018) , 1353-1360. %[Russian, English abstract]

\bibitem{Tar}
 Taranenko A.~A., \href{http://doi.org/10.1016/j.laa.2020.08.012}{\it
Algebraic properties of perfect structures}.
Linear Algebra Appl. 607 (2020), 286-306.


%\bibitem{Deb}
%DeBiasio, L., K\"{u}hn, D., Molla, T., Osthus, D. and Taylor, A.   \href{https://doi.org/10.1137/140974675}{\it  Arbitrary orientations of Hamilton cycles in digraphs}.  SIAM J. Discrete Math. 29 (2015), no. 3, 1553-1584.

\bibitem{Mih}
 Mihail, M.,  Winkler, P., \href{https://doi.org/10.1007/BF01940872}{\it On the number of Eulerian orientations of a graph}, Algorithmica, 16 (1996) 402–414.

\bibitem{Mck}
McKay B. D., \textit{Applications of a technique for labelled enumeration}, Congressus Numerantium. 49 (1983) 207-221.

\bibitem{Sch}
 Schrijver, A., \href{https://doi.org/10.1007/BF02579193} { \it Bounds on the number of Eulerian orientations}, Combinatorica, 3 (1983)
375–380.

\bibitem{Chi}
Hsu, L.-H., Lin, C.-K., \href{https://doi.org/10.1201/9781420044829}{\it Graph Theory and Interconnection Networks}; CRC Press: Boca Raton, FL, USA, 2008.

\end{thebibliography}
\end{document}
