\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}{Предложение}
\newtheorem{remark}{Remark}

\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 УДК 519.177 \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ 05C50 }
  }%\vbox
}



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


\thispagestyle{empty}

\title[\sc On reduction for eigenfunctions of graphs]{\large On reduction for eigenfunctions of graphs}
\author[A. Valyuzhenich]{{\bf \large \textsc{A. Valyuzhenich}}\protect\orcidicon{0000-0002-0582-6595}\\ \\
\textit{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%
\address{Alexandr Valyuzhenich  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Chelyabinsk State University,
\newline\hphantom{iii} Brat’ev Kashirinyh st., 129,
\newline\hphantom{iii} 454021, Chelyabinsk, Russia}%
\email{\textcolor{blue}{graphkiper@mail.ru}}%

\thanks{\sc Valyuzhenich, A.,
On reduction for eigenfunctions of graphs}
\thanks{\copyright \ 2023 Valyuzhenich A}
\thanks{\rm This work was funded by the Russian Science Foundation under grant 22-21-20018}
\thanks{\it Поступила 1 января 2023 г., опубликована 31 декабря 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract.} In this work, we prove a general version of the reduction lemmas for eigenfunctions of graphs admitting involutive automorphisms of a special type.\medskip

\noindent{\bf Keywords:} eigenfunctions of graphs, involutive automorphism.
 \end{quote}
}

\bigskip

\section{Introduction}\label{Sec:Intro}
Recently, for the eigenspaces of the Hamming and Johnson graphs, reduction lemmas were established (see \cite[Lemma 1]{V17} and \cite[Lemma 1]{VMV18}).
In \cite{EGGV22,MV20,V17,VV19,V21,VMV18,V20,V20Rec}, these lemmas were applied to study eigenfunctions and equitable $2$-partitions of the Hamming and Johnson graphs.
In this work, we generalize the reduction lemmas to graphs admitting involutive automorphisms of a special type.
In particular, we prove that an analogue of the reduction lemmas holds for the halved $n$-cube.

The paper is organized as follows. In Section \ref{Sec:Definitions}, we introduce basic definitions.
In Section \ref{Sec:Reduction}, we prove a general version of the reduction lemmas.
Then, in Section \ref{Sec:Examples}, we apply this result to the Hamming graph, the Johnson graph, and the halved $n$-cube.
\section{Basic definitions}\label{Sec:Definitions}
Let $G$ be a graph. The vertex set of $G$ is denoted by $V(G)$.
Given a vertex $x$ of $G$, denote by $N_G(x)$ the set of all neighbors of $x$ in $G$.
For a set $W\subseteq V(G)$, denote by $G[W]$ the subgraph of $G$ induced by $W$.
The automorphism group of $G$ is denoted by $\mathrm{Aut}(G)$. An automorphism $\varphi$ of $G$ is called {\em involutive} if $\varphi^2$ is the identity automorphism.

The eigenvalues of a graph are the eigenvalues of its adjacency matrix.
Let $G$ be a graph and let $\lambda$ be an eigenvalue of $G$.
A function $f:V(G)\longrightarrow{\mathbb{R}}$ is called a {\em $\lambda$-eigenfunction} of $G$ if $f\not\equiv 0$ and the equality
\begin{equation}\label{Eq:Eigenfunction}
\lambda\cdot f(x)=\sum_{y\in{N_G(x)}}f(y)
\end{equation}
holds for any vertex $x\in V(G)$. The set of functions $f:V(G)\longrightarrow{\mathbb{R}}$ satisfying (\ref{Eq:Eigenfunction}) for any vertex $x\in V(G)$ is called a {\em $\lambda$-eigenspace} of $G$. Denote by $U_{\lambda}(G)$ the $\lambda$-eigenspace of $G$.

Let $G$ be a graph. Let $\varphi$ be an automorphism of $G$ and let $\{V_1, V_2, V_3\}$ be a partition of $V(G)$.
The pair $(\varphi,\{V_1, V_2, V_3\})$ is called {\em special} if the following conditions hold:
\begin{enumerate}
    \item $\varphi(V_1)=V_2$ and $\varphi(V_2)=V_1$, i.e., $\varphi$ swaps $V_1$ and $V_2$.
    
    %For any vertex $x\in V_i$, where $i\in \{1,2\}$, the condition $\varphi(x)\in V_{3-i}$ holds.
    
    \item For any vertex $x\in V_i$, where $i\in \{1,2\}$, it holds $N_G(x)\cap V_{3-i}=\{\varphi(x)\}$.
    
    \item $\varphi(x)=x$ for any vertex $x\in V_3$, i.e., $\varphi$ stabilises $V_3$ pointwise.
\end{enumerate}

\begin{remark}\label{RemarkBitrade}
If  $(\varphi,\{V_1, V_2, V_3\})$ is a special pair of a graph $G$, then the following properties hold:
\begin{itemize}
  \item The graphs $G[V_1]$ and $G[V_2]$ are isomorphic.
  \item The graph $G[V_1\cup V_2]$ is isomorphic to the Cartesian product of $G[V_1]$ and $K_2$.
  \item The automorphism $\varphi$ is involutive.
\end{itemize}
\end{remark}

%Suppose $P=(\varphi,\{V_1, V_2, V_3\})$ is a special pair of a graph $G$.
Let $G$ be a graph with a special pair $P=(\varphi,\{V_1, V_2, V_3\})$.
Let $G[V_1]$ and $G[V_2]$ be isomorphic to a graph $G_0$, and let $\varphi_1:V_1\longrightarrow V(G_0)$ and $\varphi_2:V_2\longrightarrow V(G_0)$ be the corresponding isomorphisms. Given a function $f:V(G)\longrightarrow{\mathbb{R}}$, we define a function $f_{P,\varphi_1,\varphi_2}$ on the vertices of $G_0$ as follows:
$$f_{P,\varphi_1,\varphi_2}(x)=f(\varphi_{1}^{-1}(x))-f(\varphi_{2}^{-1}(x)).$$

Let $\{i_1,\ldots,i_k\}$ be a subset of $\{1,2,\ldots,n\}$, where $1\leq k<n$.
For a vector $x\in \mathbb{Z}_{q}^n$, denote by $\Delta_{i_1,\ldots,i_k}(x)$ the vector obtained from $x$ by deleting coordinates with indices $i_1,\ldots,i_k$.


Let $i,j\in \{1,2,\ldots,n\}$ and $i<j$. For a vector $x\in \mathbb{Z}_{q}^n$, denote by $\pi_{i,j}(x)$ the vector obtained from $x$ by interchanging the ith and jth coordinates.

The {\em weight} of a vector $x\in \mathbb{Z}_{q}^n$, denoted by $|x|$, is the number of its non-zero coordinates.
\section{Reduction for eigenfunctions of graphs}\label{Sec:Reduction}
In this section, we prove the main theorem of this paper.
\begin{theorem}\label{Th:Reduction}
%Suppose $P=(\varphi,\{V_1, V_2, V_3\})$ is a special pair of a graph $G$.
Suppose $G$ is a graph with a special pair $P=(\varphi,\{V_1, V_2, V_3\})$
Let $G[V_1]$ and $G[V_2]$ be isomorphic to a graph $G_0$, and let $\varphi_1:V_1\longrightarrow V(G_0)$ and $\varphi_2:V_2\longrightarrow V(G_0)$ be the corresponding isomorphisms. If $f$ is a $\lambda$-eigenfunction of $G$, then $f_{P,\varphi_1,\varphi_2}\in U_{\lambda+1}(G_0)$.
\end{theorem}
\begin{proof}
For every $i\in \{1,2,3\}$, denote $G_i=G[V_i]$. Define a function $h$ on the vertices of $G$  as follows:
$$h(x)=f(x)-f(\varphi(x)).$$
Since $f$ is a $\lambda$-eigenfunction of $G$ and $\varphi\in \mathrm{Aut}(G)$, we have $h\in U_{\lambda}(G)$.
The restriction of $h$ to $V_1$ is denoted by $h_1$.

Let us prove that $h_1\in U_{\lambda+1}(G_1)$. Consider a vertex $x\in V_1$.
Since $h\in U_{\lambda}(G)$, we have $$\lambda\cdot h(x)=\sum_{y\in{N_G(x)}}h(y).$$
Then 
\[
\begin{gathered}
\lambda\cdot h(x)=\sum_{y\in{N_G(x)\cap V_1}}h(y)+\sum_{y\in{N_G(x)\cap V_2}}h(y)+\sum_{y\in{N_G(x)\cap V_3}}h(y)= \\
=\sum_{y\in{N_{G_1}(x)}}h(y)+h(\varphi(x))+\sum_{y\in{N_G(x)\cap V_3}}h(y).
\end{gathered}
\]
Note that $h(\varphi(x))=f(\varphi(x))-f(x)=-h(x)$. Since $\varphi$ stabilises $V_3$ pointwise, we have $h(y)=0$ for any vertex $y\in V_3$.
Hence we obtain that $$(\lambda+1)\cdot h(x)=\sum_{y\in{N_{G_1}(x)}}h(y).$$
Therefore, $h_1\in U_{\lambda+1}(G_1)$.
Finally, note that $f_{P,\varphi_1,\varphi_2}=h_1(\varphi_1^{-1})$. Since $h_1\in U_{\lambda+1}(G_1)$ and $\varphi_1$ is an isomorphism between $G_1$ and $G_0$, we obtain that
$f_{P,\varphi_1,\varphi_2}\in U_{\lambda+1}(G_0)$.
\end{proof}

\section{Examples}\label{Sec:Examples}
In this section, we discuss how to apply Theorem \ref{Th:Reduction} to the Hamming graph, the Johnson graph, and the halved $n$-cube. In particular, we show that these graphs admit special pairs.
\subsection{Hamming graph}\label{SubSec:Hamming }
The {\em  Hamming graph} $H(n,q)$ is defined as follows. The vertex set of $H(n,q)$ is $\mathbb{Z}_{q}^n$, 
and two vertices are adjacent if they differ in exactly one coordinate.

Let $k,m\in \mathbb{Z}_q$, $k\neq m$, and $r\in \{1,2,\ldots,n\}$.
Denote $$V_1=\{x\in\mathbb{Z}_{q}^n:x_r=k\},$$ 
$$V_2=\{x\in\mathbb{Z}_{q}^n:x_r=m\},$$ and
$V_3=\mathbb{Z}_{q}^n\setminus (V_1\cup V_2)$. Denote $X=\{V_1,V_2,V_3\}$. 

Define a map $\varphi:\mathbb{Z}_{q}^n\longrightarrow \mathbb{Z}_{q}^n$ as follows:
$$\varphi(x_1,\ldots,x_n)=(x_1,\ldots,x_{r-1},(km)(x_r),x_{r+1},\ldots,x_n)$$
(here $(km)$ is the transposition of $k$ and $m$).
Note that $(\varphi,X)$ is a special pair of $H(n,q)$.

Let $G_0=H(n-1,q)$. Define maps $\varphi_1:V_1\longrightarrow V(G_0)$ and $\varphi_2:V_2\longrightarrow V(G_0)$ as follows:
$$\varphi_1(x)=\Delta_{r}(x)$$ and $$\varphi_2(y)=\Delta_{r}(y).$$
One can check that $G[V_1]$ and $G[V_2]$ are isomorphic to $G_0$, and $\varphi_1$ and $\varphi_2$ are the corresponding isomorphisms.
Thus, $(\varphi,X)$, $G_0$, $\varphi_1$ and $\varphi_2$ satisfy the conditions of Theorem \ref{Th:Reduction}.

\subsection{Johnson graph}\label{SubSec:Johnson }
The {\em Johnson graph} $J(n,k)$ is defined as follows. The vertex set of $J(n,k)$ is $\{x\in\mathbb{Z}_{2}^n:|x|=k\}$, 
and two vertices are adjacent if they differ in exactly two coordinates.

Let $i,j\in \{1,2,\ldots,n\}$ and $i<j$.
Denote $$V_1=\{x\in\mathbb{Z}_{2}^n:|x|=k,x_i=1,x_j=0\},$$ 
$$V_2=\{x\in\mathbb{Z}_{2}^n:|x|=k,x_i=0,x_j=1\},$$ and
$V_3=V(J(n,k))\setminus (V_1\cup V_2)$. Denote $X=\{V_1,V_2,V_3\}$. 


Define a map $\varphi:V(J(n,k))\longrightarrow V(J(n,k))$ as follows:
$$\varphi(x)=\pi_{i,j}(x).$$
Note that $(\varphi,X)$ is a special pair of $J(n,k)$.

Let $G_0=J(n-2,k-1)$. Define maps $\varphi_1:V_1\longrightarrow V(G_0)$ and $\varphi_2:V_2\longrightarrow V(G_0)$ as follows:
$$\varphi_1(x)=\Delta_{i,j}(x)$$ and $$\varphi_2(y)=\Delta_{i,j}(y).$$
One can check that $G[V_1]$ and $G[V_2]$ are isomorphic to $G_0$, and $\varphi_1$ and $\varphi_2$ are the corresponding isomorphisms.
Thus, $(\varphi,X)$, $G_0$, $\varphi_1$ and $\varphi_2$ satisfy the conditions of Theorem \ref{Th:Reduction}.

\subsection{Halved $n$-cube}\label{SubSec:Halved cube}
The {\em halved $n$-cube} $\frac{1}{2}H(n)$ is defined as follows. The vertex set of $\frac{1}{2}H(n)$ is $\{x\in\mathbb{Z}_{2}^n:|x|~\text{is even}\}$, 
and two vertices are adjacent if they differ in exactly two coordinates.

Let $i,j\in \{1,2,\ldots,n\}$ and $i<j$.
Denote $$V_1=\{x\in\mathbb{Z}_{2}^n:|x|~\text{is even},x_i=1,x_j=0\},$$ 
$$V_2=\{x\in\mathbb{Z}_{2}^n:|x|~\text{is even},x_i=0,x_j=1\},$$ and
$V_3=V(\frac{1}{2}H(n))\setminus (V_1\cup V_2)$. Denote $X=\{V_1,V_2,V_3\}$. 


Define a map $\varphi:V(\frac{1}{2}H(n))\longrightarrow V(\frac{1}{2}H(n))$ as follows:
$$\varphi(x)=\pi_{i,j}(x).$$
Note that $(\varphi,X)$ is a special pair of $\frac{1}{2}H(n)$.

We define a graph $G_0$  as follows. The vertex set of $G_0$ is $\{x\in\mathbb{Z}_{2}^{n-2}:|x|~\text{is odd}\}$, 
and two vertices are adjacent if they differ in exactly two coordinates. 
Note that $G_0$ is isomorphic to $\frac{1}{2}H(n-2)$.
Define maps $\varphi_1:V_1\longrightarrow V(G_0)$ and $\varphi_2:V_2\longrightarrow V(G_0)$ as follows:
$$\varphi_1(x)=\Delta_{i,j}(x)$$ and $$\varphi_2(y)=\Delta_{i,j}(y).$$
One can check that $G[V_1]$ and $G[V_2]$ are isomorphic to $G_0$, and $\varphi_1$ and $\varphi_2$ are the corresponding isomorphisms.
Thus, $(\varphi,X)$, $G_0$, $\varphi_1$ and $\varphi_2$ satisfy the conditions of Theorem \ref{Th:Reduction}.


\section{Acknowledgements}
The author is grateful to Sergey Goryainov and Ivan Mogilnykh for helpful discussions.


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



\bibitem{EGGV22}
R. J. Evans, A. L. Gavrilyuk, S. Goryainov, K. Vorob'ev, 
\href{https://doi.org/10.48550/arXiv.2206.15341} {\it Equitable $2$-partitions of the Johnson graphs $J(n,3)$}, arXiv:2206.15341, August 2022.

\bibitem{MV20}
I. Mogilnykh, A. Valyuzhenich, 
\href{https://doi.org/10.1016/j.disc.2020.112039} {\it Equitable $2$-partitions of the Hamming graphs with the second eigenvalue}, Discrete Mathematics, \textbf{343}:11 (2020), 112039.

\bibitem{V17}
A. Valyuzhenich, 
\href{https://doi.org/10.1016/j.disc.2016.09.018} {\it Minimum supports of eigenfunctions of Hamming graphs}, Discrete Mathematics, \textbf{340}:5 (2017), 1064--1068.

\bibitem{VV19}
A. Valyuzhenich, K. Vorob'ev, 
\href{https://doi.org/10.1016/j.disc.2019.01.015} {\it Minimum supports of functions on the Hamming graphs with spectral constraints}, Discrete Mathematics, \textbf{342}:5 (2019), 1351--1360.


\bibitem{V21}
A. Valyuzhenich, 
\href{https://doi.org/10.1016/j.disc.2020.112228} {\it Eigenfunctions and minimum $1$-perfect bitrades in the Hamming graph}, Discrete Mathematics, \textbf{344}:3 (2021), 112228.


\bibitem{VMV18}
K. Vorob'ev, I. Mogilnykh, A. Valyuzhenich, 
\href{https://doi.org/10.1016/j.disc.2018.04.018} {\it Minimum supports of eigenfunctions of Johnson graphs}, Discrete Mathematics, \textbf{341}:8 (2018), 2151--2158.

\bibitem{V20}
K. Vorob'ev, 
\href{https://doi.org/10.48550/arXiv.2003.10956} {\it Equitable $2$-partitions of Johnson graphs with the second eigenvalue}, arXiv:2003.10956, March 2020.

\bibitem{V20Rec}
K. Vorob'ev, 
\href{https://doi.org/10.1016/j.dam.2019.02.034} {\it On reconstruction of eigenfunctions of Johnson graphs}, Discrete Applied Mathematics, \textbf{276} (2020), 166--171.


\end{thebibliography}
\end{document}
