% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A note on automorphisms of the infinite-dimensional hypercube graph}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Mark Pankov\\
\small Department of Mathematics and Computer Science\\[-0.8ex]
\small University of Warmia and Mazury\\[-0.8ex] 
\small Olsztyn, Poland\\
\small\tt pankov@matman.uwm.edu.pl\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{}{}\\
\small Mathematics Subject Classifications: 05C63, 20B27}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
We define the infinite-dimensional hypercube graph $H_{{\aleph}_{0}}$ as
a graph whose vertex set is formed by the so-called singular subsets of ${\mathbb Z}\setminus\{0\}$.
This graph is not connected, but it has isomorphic connected components.
We  show that the restrictions of its automorphisms
to the connected components  are induced by permutations on ${\mathbb Z}\setminus\{0\}$ preserving
the family of singular subsets. As an application, we describe the automorphism group of connected component.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} infinite-dimensional hypercube graph;
graph automorphism;  weak wre\-ath product of groups.
\end{abstract}

\section{Introduction}

By \cite{ER}, typical graphs have no non-trivial automorphisms.
On the other hand, the classical Frucht  result \cite{Frucht} states that every abstract group can be realized as
the automorphism group of some graph (we refer \cite{Cam} for more information concerning graph automorphisms).
In particular, the Coxeter group of type ${\textsf B}_{n}={\textsf C}_{n}$ (the wreath product $S_{2}\wr S_{n}$) is isomorphic
to the automorphism group of the $n$-dimensional hypercube graph $H_{n}$.

In this note we consider the infinite-dimensional hypercube graph $H_{{\aleph}_{0}}$.
This is  the Cartesian product of infinitely many factors $K_2$, but it also
can be defined  as a graph whose vertex set is formed by the maximal singular subsets of ${\mathbb Z}\setminus\{0\}$
(Section 2).
This graph is not connected, but it has isomorphic connected components.
We  show that the restrictions of its automorphisms
to the connected components  are induced by permutations on ${\mathbb Z}\setminus\{0\}$ preserving
the family of singular subsets (Theorem 2). As a simple consequence, we establish that
the automorphism group of connected component is isomorphic to
the so-called weak wreath product of $S_{2}$ and $S_{\aleph_{0}}$ (Corollary 5).
Since $H_{{\aleph}_{0}}$ is the Cartesian product of infinitely many
factors $K_2$, the latter statement can be drawn from some results concerning the automorphism group of
Cartesian product of graphs \cite{Im,Miller}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Infinite-dimensional hypercube graph}

A subset $X\subset {\mathbb Z}\setminus\{0\}$ is said to be {\it singular} if
$$i\in X\;\Longrightarrow\;-i\not\in X.$$
For every natural $i$ each maximal singular subset contains precisely one of the numbers $i$ or $-i$;
in other words, if $X$ is a maximal singular subset then the same holds for its complement in ${\mathbb Z}\setminus\{0\}$.
Two maximal singular subsets $X,Y$ are called {\it adjacent} if
$$|X\setminus Y|=|Y\setminus X|=1.$$
In this case, we have
$$X=(X\cap Y)\cup\{i\}\;\mbox{ and }\;Y=(X\cap Y)\cup\{-i\}$$
for some number $i\in {\mathbb Z}\setminus\{0\}$.

Following Example 2.6 in \cite{Pankov-book}, we say that a permutation $s$ on the set ${\mathbb Z}\setminus \{0\}$
is {\it symplectic} if
$$s(-i)=-s(i)\;\;\;\;\;\forall\;i\in {\mathbb Z}\setminus \{0\}.$$
A permutation is symplectic if and only if it preserves
the family of singular subsets.
The group of symplectic permutations is isomorphic to the wreath product $S_{2}\wr S_{\aleph_{0}}$
(we write $S_{\alpha}$ for the group of permutations on a set of cardinality $\alpha$,
see Section 5 for the definition of wreath product).
The action of this group on the family of maximal singular subsets is transitive.

Denote by $H_{{\aleph}_{0}}$ the graph whose vertex set is formed by all maximal singular subsets and whose edges are
adjacent pairs of such subsets.
This graph is not connected. The connected component containing $X\in H_{{\aleph}_{0}}$ will be denoted by $H(X)$;
it consists of all $Y\in H_{{\aleph}_{0}}$ such that
$$|X\setminus Y|=|Y\setminus X|<\infty.$$
Any two connected components $H(X)$ and $H(Y)$ are isomorphic.
Indeed, every symplectic permutation $s$ on the set ${\mathbb Z}\setminus \{0\}$
induces an automorphism of $H_{{\aleph}_{0}}$; this automorphism transfers $H(X)$ to $H(Y)$
if $s(X)=Y$.

It is clear that $H_{{\aleph}_{0}}$ can be identified with the graph whose vertices are sequences
$$\{a_{n}\}_{n\in {\mathbb N}}\;\mbox{ with }\;a_{n}\in \{0,1\}$$
and $\{a_{n}\}_{n\in {\mathbb N}}$ is adjacent with $\{b_{n}\}_{n\in {\mathbb N}}$ (connected by an edge) if
$$\sum_{n\in {\mathbb N}}|a_{n}-b_{n}|=1.$$
Then one of the connected components is formed by all sequences having a finite number of non-zero elements.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Automorphisms}

Every automorphism of $H_{{\aleph}_{0}}$ induced by a  symplectic permutation will be called {\it regular}.
An easy verification  shows that distinct symplectic permutations induce distinct regular automorphisms.
Therefore, the group of regular automorphisms is isomorphic to $S_{2}\wr S_{\aleph_{0}}$.

Non-regular automorphisms exist.
The following example is a modification of examples given in \cite{BH,Pankov1}, see also Example 3.14 in \cite{Pankov-book}.

\begin{example}{\rm
Let $A\in H_{{\aleph}_{0}}$ and $B$ be a vertex of the connected component $H(A)$ distinct from $A$.
We take any symplectic permutation $s$ transferring  $A$ to $B$.
This permutation preserves $H(A)$ and
the mapping
$$f(X):=
\begin{cases}
s(X)&X\in H(A)\\
\;X&X\in H_{{\aleph}_{0}}\setminus H(A)
\end{cases}$$
is well-defined.
Clearly, $f$ is a non-trivial automorphism of $H_{{\aleph}_{0}}$.
Suppose that this automorphism is regular and $t$ is the associated symplectic permutation.
For every $i\in {\mathbb Z}\setminus \{0\}$ there exists a singular subset $N$ such that
$$X=N\cup\{i\}\;\mbox{ and }\;Y=N\cup\{-i\}$$
are elements of $H_{{\aleph}_{0}}\setminus H(A)$.
Then
$$t(N)=t(X\cap Y)=t(X)\cap t(Y)=f(X)\cap f(Y)=X\cap Y=N$$
and
$$N\cup\{i\}=X=f(X)=t(X)=t(N)\cup\{t(i)\}=N\cup\{t(i)\}$$
which implies that $t(i)=i$.
Thus $t$ is identity which is impossible.
So, the automorphism $f$ is non-regular.
}\end{example}

\begin{theorem}
The restriction of every automorphism of $H_{{\aleph}_{0}}$ to any connected component
coincides with the restriction of some regular automorphism to this connected component.
\end{theorem}


A similar result was obtained in \cite{Pankov1} for  infinite Johnson graphs. The proof
of that result  is based on the same idea.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proof of Theorem 2}
Let $A\in H_{{\aleph}_{0}}$ and $f$ be the restriction of an automorphism of $H_{{\aleph}_{0}}$ to
the connected component $H(A)$.
For every $X\in H_{{\aleph}_{0}}$ we denote by $X^{\sim}$ the set which contains $X$ and all vertices of $H_{{\aleph}_{0}}$
adjacent with $X$.
It is clear that $X^{\sim}$ is contained in $H(A)$ if $X\in H(A)$.

\begin{lemma}
For every $X\in H(A)$ there is a symplectic permutation $s_{X}$
such that
\begin{equation}\label{eq1}
f(Y)=s_{X}(Y)\;\;\;\;\;\;\forall\;Y\in X^{\sim}.
\end{equation}
\end{lemma}

\begin{proof}
We can assume that $f(X)$ coincides with $X$
(if $f(X)\ne X$ then we take any symplectic permutation $t$ sending $f(X)$ to $X$ and consider $tf$).
In this case, the restriction of $f$ to $X^{\sim}$ is a bijective transformation of $X^{\sim}$.

For every $i\in {\mathbb Z}\setminus \{0\}$ one of the following possibilities is realized:
\begin{enumerate}
\item[$\bullet$] $i\not\in X$,
\item[$\bullet$] $i\in X$.
\end{enumerate}
Consider the first case. Then $-i\in X$ and there is unique element of $X^{\sim}$ containing $i$, this is
\begin{equation}\label{eq2}
Y=\{i\}\cup(X\setminus \{-i\}).
\end{equation}
Since $f|_{X^{\sim}}$ is a transformation of $X^{\sim}$,
$f(Y)$ is adjacent with $X$ and the set $f(Y)\setminus X$ contains only one element. We denote it by $s_{X}(i)$.
It is clear that $s_{X}(i)\not\in X$.

In the second case,  $-i\not\in X$ and we define $s_{X}(i)$ as $-s_{X}(-i)$.
Since $s_{X}(-i)$ does not belong to $X$, we have $s_{X}(i)\in X$.

So, $s_{X}$ is a symplectic permutation on ${\mathbb Z}\setminus \{0\}$ such that
$$s_{X}(X)=X.$$
Now, we check \eqref{eq1}.

Let $Y\in X^{\sim}$. Then we have \eqref{eq2}
for some $i$ and
$$s_{X}(Y)=\{s_{X}(i)\}\cup (s_{X}(X)\setminus \{-s_{X}(i)\})=\{s_{X}(i)\}\cup (X\setminus \{-s_{X}(i)\})$$
is the unique element of $X^{\sim}$ containing $s_{X}(i)$. On the other hand,
$s_{X}(i)$ belongs to $f(Y)$ by the definition of $s_{X}$.
Therefore, $f(Y)$ coincides with $s_{X}(Y)$.
\end{proof}


\begin{lemma}
If $X,Y\in H(A)$ are adjacent then $s_{X}=s_{Y}$.
\end{lemma}

\begin{proof}
Since $X,Y$ are adjacent, we have
$$X=\{i\}\cup(X\cap Y)\;\mbox{ and }\;Y=\{-i\}\cup(X\cap Y)$$
for some $i\in X$.
We can assume that
$$f(X)=X\;\mbox{ and }\;f(Y)=Y.$$
Indeed, in the general case
$$f(X)=\{j\}\cup(f(X)\cap f(Y))\;\mbox{ and }\;f(Y)=\{-j\}\cup(f(X)\cap f(Y))$$
(since $f(X)$ and $f(Y)$ are adjacent);
we take any symplectic permutation $t$ sending $j$ and $f(X)\cap f(Y)$ to $i$ and $X\cap Y$ (respectively)
and consider $tf$.

Then
$$s_{X}(X\cap Y)=s_{X}(X)\cap s_{X}(Y)=f(X)\cap f(Y)=X\cap Y;$$
similarly,
$$s_{Y}(X\cap Y)=X\cap Y.$$
We have
$$(X\cap Y)\cup\{i\}=X=f(X)=s_{X}(X)=s_{X}((X\cap Y)\cup\{i\})=(X\cap Y)\cup\{s_{X}(i)\}$$
and the same arguments show that
$$(X\cap Y)\cup\{i\}=(X\cap Y)\cup\{s_{Y}(i)\}.$$
Therefore,
$$s_{X}(i)=s_{Y}(i)=i\;\mbox{ and }\;s_{X}(-i)=s_{Y}(-i)=-i.$$
Now, we show that the equality
\begin{equation}\label{eq3}
s_{X}(j)=s_{Y}(j)
\end{equation}
holds for every $j\ne \pm i$. Since $s_{X}$ and $s_{Y}$ are symplectic, it is sufficient to establish \eqref{eq3} only in the case when
$j\not\in X\cup Y$. Indeed, if $j\in X\cap Y$ then $-j$ does not belong to $X\cup Y$.

Let $j$ be an element of ${\mathbb Z}\setminus \{0\}$ which does not belong to $X\cup Y$.
Then $-j\in X\cap Y$ and
$$X':=\{j\}\cup (X\setminus \{-j\})\in X^{\sim},\;\;Y':=\{j\}\cup (Y\setminus \{-j\})\in Y^{\sim}$$
are adjacent. Hence
$$f(X')=s_{X}(X')=\{s_{X}(j)\}\cup (X\setminus \{-s_{X}(j)\})$$
and
$$f(Y')=s_{Y}(Y')=\{s_{Y}(j)\}\cup (Y\setminus \{-s_{Y}(j)\})$$
are adjacent. The latter is possible only in the case when $s_{X}(j)=s_{Y}(j)$.
\end{proof}

Using the connectedness of $H(A)$ and Lemma 4, we establish that $s_{X}=s_{Y}$ for all $X,Y\in H(A)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Automorphisms of connected components}
Let $G_{1}$ and $G_2$ be permutation groups on sets $X_1$ and $X_2$, respectively.
Recall that the {\it wreath product} $G_1\wr G_2$ is a permutation group on $X_1\times X_2$ and its elements are
compositions of the following two types of permutations:
\begin{enumerate}
\item[(1)] for each element $g\in G_{2}$, the permutation $(x_1,x_{2})\to (x_1, g(x_{2}))$;
\item[(2)] for each function $i: X_{2}\to G_1$, the permutation $(x_1,x_{2})\to (i(x_{2})x_1,x_{2})$.
\end{enumerate}
Consider the subgroup of $G_1\wr G_2$ whose elements are compositions of permutations of type (1) and permutations
of type (2) such that the set
$$\{\;x_{2}\in X_2\;:\;i(x_{2})\ne {\rm id}_{X_{1}\;}\}$$
is finite. This is a proper subgroup only in the case when $X_2$ is infinite;
it will be called the {\it weak wreath product} and denoted by $G_1\wr_{w} G_2$.

\begin{corollary}
The automorphism group of the connected component of $H_{{\aleph}_{0}}$ is isomorphic
to the weak wreath product $S_{2}\wr_{w} S_{{\aleph}_{0}}$.
\end{corollary}

\begin{proof}
Let $A\in H_{{\aleph}_{0}}$ and $f$ be an automorphism of the connected component $H(A)$.
By the previous section, $f$ is induced by a symplectic permutation $s$.
Since $f(A)=s(A)$ belongs to $H(A)$,
the set $s(A)\setminus A$ is finite.
So, the automorphism group of $H(A)$ is isomorphic to the group of symplectic permutations $s$
such that the set $s(A)\setminus A$ is finite.
The latter group is isomorphic to the weak wreath product $S_{2}\wr_{w} S_{{\aleph}_{0}}$
(indeed, we  can identify the set ${\mathbb Z}\setminus\{0\}$ with the Cartesian product ${\mathbb Z}_{2}\times A$
and the group $S_{{\aleph}_{0}}$ with the group of all permutation on $A$).
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
I express my deep gratitude to Wilfried Imrich for useful information.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{BH} A.~Blunck, H.~Havlicek.
\newblock On bijections that preserve complementarity of subspaces.
\newblock {\em Discrete Math.},  301:46--56, 2005.

\bibitem{Cam}
P. J.~Cameron. \newblock  Automorphisms of graphs. 
\newblock In {\em Topics in Algebraic Graph Theory}, 
volume 102 of {\em Encyclopedia of Mathematics and Its Applications},
pages 137--155. Cambridge University Press 2005.

\bibitem{ER}
P.~Erd\H{o}s, A.~R\'enyi. \newblock Asymmetric graphs.
\newblock {\em  Acta Math. Acad. Sci. Hungar.}, 14:295--315, 1963.


\bibitem{Frucht}
R.~Frucht. \newblock Herstellung von Graphen mit vorgegebener abstrakter Gruppe.
\newblock {\em Compositio Math.}, 6:239--250, 1938.

\bibitem{Im}
W.~Imrich. \newblock \"{U}ber das schwache Kartesische Produkt von Graphen.
\newblock {\em J. Combin. Theory Ser. B}, 11:1--16, 1971.


\bibitem{Miller}
D. J.~Miller. \newblock The automorphism group of a product of graphs.
\newblock {\em Proc. Amer. Math. Soc.}, 25:24--28, 1970.

\bibitem{Pankov-book}
M.~Pankov. \newblock {\em Grassmannians of classical buildings}. 
\newblock Algebra and Discrete Math. Series, no. 2. 
World Scientific, Singapore, 2010.


\bibitem{Pankov1}
M.~Pankov. \newblock  Automorphisms of infinite Johnson graphs.
\newblock  {\em  Discrete Math.}, accepted.
\end{thebibliography}

\end{document}