\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.40}{21(3)}{2014}
%
\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
%
\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}


% Authors' packages and commands
\usepackage{mathrsfs}
\providecommand{\aut}{\mathop{\rm Aut}\nolimits}
\providecommand{\sym}{\mathop{\rm Sym \,}\nolimits}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\A}{\text{Aut}}
\newcommand{\B}{\mathscr{B}}
\newcommand{\C}{\mathscr{C}}


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

% if needed include a line break (\\) at an appropriate place in the title
\title{{\bf Bounding the distinguishing number of infinite graphs and permutation groups}}

\author{Simon M.~Smith\\
\small Department of Mathematics\\[-0.8ex]
\small NYC College of Technology\\[-0.8ex] 
\small City University of New York\\[-0.8ex] 
\small New York City, U.S.A.\\
\small\tt sismith@citytech.cuny.edu\\
\and
Mark E.~Watkins\\ %\thanks{Partially supported by a grant from the Simons Foundation (\#209803 to Mark E.\,Watkins)}\\
\small Department of Mathematics\\[-0.8ex]
\small Syracuse University\\[-0.8ex]
\small Syracuse, NY, U.S.A.\\
\small\tt mewatkin@syr.edu
}

% \date{\dateline{submission date}{acceptance date}\\
% Use this format: \date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\
\date{\dateline{Jan 10, 2013}{Aug 21, 2014}{Sep 18, 2014}\\
\small Mathematics Subject Classifications: 05C15, 20B27, 05C63, 05C25}

\begin{document}

\maketitle


%\markboth{\textsc{Bounding the distinguishing number}}{\textsc{Bounding the distinguishing number}}

\begin{abstract}
A group of permutations $G$ of a set $V$ is $k$-{\em distinguishable} if there exists a partition of $V$ into $k$ cells such that only the identity permutation in $G$ fixes setwise all of the cells of the partition.  The least cardinal number $k$ such that $(G,V)$ is $k$-distinguishable is its {\em distinguishing number}, $D(G,V)$. In particular, a graph $\Gamma$ is {\em $k$-distinguishable} if its automorphism group $\A(\Gamma)$ satisfies $D(\A(\Gamma),V\Gamma)\leq k$.

Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show first that whenever an infinite connected graph $\Gamma$ is not $k$-distinguishable (for a given cardinal $k$), then it contains a ball of finite radius whose distinguishing number is at least $k$. Moreover, this lower bound cannot be sharpened, since for any integer $k \geq 3$ there exists an infinite, locally finite, connected  graph $\Gamma$ that is not $k$-distinguishable but in which every ball of finite radius is $k$-distinguishable. 

In the second half of this paper we show that a large distinguishing number for an imprimitive permutation group $G$ is traceable to a high distinguishing number either of a block of imprimitivity or of the action induced by $G$ on the corresponding system of imprimitivity.  An immediate application is to automorphism groups of infinite imprimitive graphs.  These results are companion to the study of the distinguishing number of infinite primitive  groups and graphs in a previous paper by the authors together with T.\,W.\, Tucker.

\bigskip\noindent \textbf{Keywords:} Distinguishing number; Distinguishing coloring; Infinite graph; Infinite permutation group; Imprimitive permutation group; Imprimitive graph
\end{abstract}

\maketitle

\section{Introduction}

When studying infinite graphs, one frequently extends properties that originate in finite graph theory. Some theorems in this vein may state that if an infinite graph fails to satisfy such a property, then some finite subgraph is the likely culprit. For example:
\begin{itemize}
\item
	if an infinite graph $\Gamma$ is not $k$-colorable, then there exists a finite subgraph of $\Gamma$ that is not $k$-colorable (part of N.\,G.\,de Bruijn and P.\,Erd\H{o}s' famous theorem, see \cite{bruijn_erdos_51}); and
\item
	if a countably infinite graph is not planar, then some (finite) subgraph is homeomorphic to one of the Kuratowski graphs $K_5$ or $K_{3,3}$ and hence is not planar (attributed to P.\,Erd\H{o}s by G.\,Dirac and S.\,Schuster in \cite{dirac_schuster}).
\end{itemize}

In this note we consider the property of distinguishability.  As automorphism groups of graphs are but special cases of permutation groups on arbitrary sets, we frame this notion in the more general context of permutation groups.  A group $G$ acting faithfully on a set $V$ (often written as a pair $(G,V)$) is $k$-{\em distinguishable} if there exists a partition of $V$ with $k$ cells such that only the identity permutation in $G$ fixes setwise all of the cells of the partition. If $k$ is the minimal cardinal such that the permutation group $(G,V)$ is $k$-distinguishable, then $k$ is the {\em distinguishing number} of $(G,V)$, and we write $D(G,V)=k$. If $G$ acts on $V$, we write $D(G, V)$ to denote the distinguishing number of the subgroup of $\sym(V)$ induced by $G$. Applying this notion to graphs, we say that a graph $\Gamma$ is {\em $k$-distinguishable} if its automorphism group $\A(\Gamma)$ satisfies $D(\A(\Gamma),V\Gamma)\leq k$.  (This notion, applied to finite graphs, is originally due to Albertson and Collins \cite{AC1}.)   For brevity, unless some proper subgroup of $\A(\Gamma)$ is being considered, we write simply $D(\Gamma)$ instead of $D(\A(\Gamma),V\Gamma)$. 

One might hope that if an infinite graph $\Gamma$ fails to be $k$-distinguishable, then some ``interesting'' substructure ought to bear the blame.  Indeed, this is already known for countably infinite trees:
\begin{itemize}
\item if a countably infinite tree has finite distinguishing number $k$, then some finite subtree also has distinguishing number $k$ (see \cite{watkins_zhou}). 
\end{itemize}

In this paper we present two substructures that may be blamed: one is a graph-theoretical substructure and the other is algebraic.  In the first part of this paper we look at a class of subgraphs of $\Gamma$ of  finite diameter that give a meaningful upper bound for $D(\Gamma)$.   In the second part of this paper we look at infinite imprimitive permutation groups, demonstrating a sharp upper bound for their distinguishing numbers in terms of the distinguishing numbers of both a block of imprimitivity and the induced action of the group on the corresponding system of imprimitivity.  Graph-theoretical analogues then follow directly.  These latter results are  companions to results for primitive permutation groups and primitive graphs obtained by the present authors together with T.\,W.\,Tucker (see  \cite{sms_twt_mew}).\\

For infinite graphs in general, the parameter of distinguishing number is not as well-behaved as parameters such as chromatic number and genus; the distinguishing number of a subgraph of a graph $\Gamma$ is not necessarily less than or equal to, but also may be greater than $D(\Gamma)$. For example, any connected graph with infinite diameter contains finite induced subgraphs with distinguishing number $k$ for every $k \in \mathbb{N}$ (to wit, the null graph on $k$ vertices).  The class of subgraphs of finite diameter that we've selected for consideration are the {\em ball-graphs} $B(x,n)$:  for $n \in \mathbb{N}$,  $B(x,n)$ is the subgraph of $\Gamma$ induced by the vertex set $\{y \in V\Gamma : d(x,y) \leq n\}$. Its  {\em radius} is $n$ and it is {\em centered} at $x$.\\

Suppose that $k-1$ is the largest valence of the vertices of a connected graph $\Gamma$.  If $\Gamma$ is finite, then $D(\Gamma)\leq k$ (see \cite[Theorem 4.2]{collins_trenk}).  When $\Gamma$ is infinite, the sharper bound of $D(\Gamma)\leq k-1$ is obtained (see \cite[Theorem 2.1]{imrich_et_al:distinguishing}).  This easily yields the following.

\begin{proposition}Let $\Gamma$ be a connected graph without $3$-cycles and let  $k$ denote some cardinal. If $\Gamma$ is not $k$-distinguishable, then there exists a vertex $x\in V\Gamma$ such that $B(x, 1)$ has distinguishing number at least $k$. \qed
\end{proposition}

We extend this result considerably.

\begin{theorem} \label{thm_finite_balls}  Let $\Gamma$ be a connected graph and let  $k$ denote some cardinal.  If $\Gamma$ is not $k$-distinguishable, then, for any vertex $x\in V\Gamma$, all but finitely many ball-graphs centered at $x$ have distinguishing number at least $k$.  
\end{theorem}

\begin{corollary}\label{SharpBound}  If the graph $\Gamma$ of the above theorem is locally finite, then $k$ is a sharp lower bound for the distinguishing number of its ball-graphs.
\end{corollary}

Notice that we are providing here an upper bound for the distinguishing number of $\Gamma$ in terms of the distinguishing number of its finite ball-subgraphs. It is tempting to think that for an infinite graph $\Gamma$ when $\aut(\Gamma)$ is not trivial, it might be possible to obtain a lower bound more interesting than $D(\Gamma) \geq 2$, but this is not so.  It is easy to construct an example of a connected graph $\Gamma$ in which the distinguishing numbers of the ball-graphs centered at any given vertex of $\Gamma$ are not bounded above, while the whole graph is $2$-distinguishable: consider for example a rooted tree in which, for each $n \in \mathbb{N}$, all the vertices at distance $n$ from the root have valence $n+1$. \\

The purpose of the second part of this article is to describe the distinguishing number of an  imprimitive group action in terms of its blocks of imprimitivity, although we in fact achieve something more general.  Recall that a transitive group $G \leq \sym(V)$ is {\em primitive} if the only $G$-invariant equivalence relations on $V$ are either trivial or universal.  A graph is {\em primitive} if its automorphism group acts primitively on its vertex set. If $G$ is transitive but not primitive, then it is {\em imprimitive}, and there exists a nontrivial and non-universal $G$-invariant equivalence relation $\cong$ on $V$. Any equivalence class $B$ with respect to $\cong$ is called a {\em block of imprimitivity}, or simply a {\em block}. The set $\B=\{B^g : g \in G\}$ is the set of all equivalence classes with respect to $\cong$ and is called a {\em system of imprimitivity}. The group $G$ naturally induces a transitive group of permutations  on $\B$.  If $H$ is the subgroup of $G$ that fixes every block setwise, then $H \lhd G$ and $G/H$ acts transitively and faithfully on $\B$.  

Much is already known about the distinguishing number of primitive permutation groups.  \'{A}.\,Seress \cite[Theorem 1]{akos_seress} showed that all finite primitive permutation groups of degree strictly greater than 32, other than the symmetric and the alternating groups, have distinguishing number 2.  It was shown in \cite{sms_twt_mew} that every infinite primitive permutation group with finite {\em suborbits} (orbits of a point-stabilizer) has distinguishing number 2 and thus that the distinguishing number of any nonnull, infinite,  locally finite, primitive graph is equal to 2.  In light of these results, we here investigate {\em imprimitive} permutation groups and determine that a high distinguishing number for an imprimitive group $G$ is accompanied by the property that, for any system of imprimitivity $\B$ of $G$, either:
\begin{enumerate}
\item
	for any block $A \in \B$, the setwise stabilizer $G_{\{A\}}$ acting on $A$ has a high distinguishing number; or
\item
	the action induced by $G$ on the system of imprimitivity $\B$ has a high distinguishing number.
\end{enumerate}
The following theorem, our second main result, provides sharp bounds for the distinguishing number of $G$ in terms of the distinguishing numbers of these two groups.  

\begin{theorem} \label{thm:wr} Let $V$ be a non-empty set, and $G \leq \sym(V)$. Suppose $V$ admits a $G$-invariant equivalence relation whose set $\B$ of equivalence classes is permuted transitively by $G$. If $A \in \B$ is such an equivalence class, $H$ the subgroup of $\sym(A)$ induced by the setwise stabilizer $G_{\{A\}}$, and $X$ any set such that $|X| =D(G, \B)$, then
\[D(G, V) \leq D(H \wr \sym(X), A \times X).\]
\end{theorem}

Here the symbol $\wr$ denotes the wreath product and is defined in Section~\ref{Imprimitivity}. Note that the hypothesis of the above theorem is satisfied, for example, when $G$ is any transitive subgroup of $\sym(V)$ and $\B$ is any system of imprimitivity of $G$.

In the situation where $G$ is not transitive on $\B$, Theorem~\ref{thm:wr} still gives a meaningful upper bound on $D(G, V)$. If $\{\B_i : i \in I\}$ is the set of orbits of $G$ on $\B$, write $V_i:=\bigcup_{B \in \B_i} B$ and observe that $D(G, V) \leq \sup_{i \in I} D(G_i, V_i)$, where $G_i$ is the subgroup of $\sym(V_i)$ induced by $G$. For each $i \in I$, fix $A_i \in \B_i$, let $H_i$ denote the subgroup of $\sym(A_i)$ induced by the setwise stabilizer of $A_i$ in $G_i$, and let $X_i$ be any set such that $|X_i| = D(G_i, \B_i)$. Applying Theorem~\ref{thm:wr}, we obtain
\[D(G, V) \leq \sup_{i \in I} D(H_i \wr \sym(X_i), A_i \times X_i).\]


An analogous result  for intransitive or imprimitive graphs (Corollary~\ref{thm_imprimitive}) then follows with some care.  For a given cardinal $n$ and any graph $\Lambda$, we denote the disjoint union of $n$ copies of $\Lambda$ by $n \Lambda$.  The complement of $\Lambda$ is denoted  by $\Lambda'$.

\begin{corollary} \label{thm_imprimitive}
Let $\Gamma$ be a graph admitting an $\aut(\Gamma)$-invariant equivalence relation $\cong$ consisting of equivalence classes whose induced subgraphs are isomorphic to some graph $\Delta$. Set $n := D(\Gamma/\cong)$. Then $D(\Gamma) \leq \min \{ D(n\Delta), D(n\Delta') \}$, and this bound is sharp.
\end{corollary}

Clearly, Corollary~\ref{thm_imprimitive} is most useful when $n$ and $D(\Delta)$ are finite. There exists many natural examples of locally finite, infinite, vertex-transitive graphs $\Gamma$ which, under the hypothesis of Corollary~\ref{thm_imprimitive}, satisfy the following: $\Delta$ is finite, $2 < n < \aleph_0$ and $D(\Gamma) > 2$. In Example~\ref{ex:refs_request} we describe an infinite class of such graphs for which the bound given by Corollary~\ref{thm_imprimitive} is sharp.\\


To conclude this article we show that when $D(G/\B)$ is finite, Theorem~\ref{thm:wr} may be deduced (with a little work) from a theorem of Melody Chan \cite[Theorem 2.3]{chan06}.




%%%%%%%Section 2
\section{Distinguishing number and ball-graphs}

The proof of Theorem \ref{thm_finite_balls} consists of bounding the distinguishing number of a connected graph in terms of the distinguishing number of its ball-graphs.  Corollary \ref{SharpBound} will then follow from Example~\ref{main_example} in the final section.

\begin{proof}[Proof of Theorem~\ref{thm_finite_balls}]  It may be assumed that $\Gamma$ has infinite diameter; otherwise there is nothing to prove.  Since $\Gamma$ is connected, this assumption implies that for all $x\in V\Gamma$ and all $m,n\in\N$, if $m<n$, then $B(x,m)$ is a proper subgraph of $B(x,n)$.

We prove the contrapositive.  Suppose that for some $x \in V\Gamma$ there exists an infinite increasing subsequence $\{n_i\}_{i \in \N}$ from $\N$ such that $D(B(x,n_i)) < k$ for each $i \in \mathbb{N}$.  Let us abbreviate $B(x,n_i)$ by $B(i)$.  Let $X$ be a set (of colors) with $|X|= k$, and fix $c_0 \in X$.  It follows that for each $i\in\N$, there exists a distinguishing coloring $\varphi_i:VB(i)\to X$ with the property that $\varphi_i(y)=c_0$ if and only if $y=x$.

We now construct a coloring $\psi:V\Gamma\to X$ with the property that $\psi(y)=c_0$ if and only if $y=x$ and prove by induction on $i$ that $\psi$ is $k$-distinguishing on $B(i)\setminus B(i-1)$ for all $i\in\N$.  From this it will follow that $D(\Gamma)\leq k$.

We begin by setting $\psi_1=\varphi_1$ and remarking that $\psi_1$ is a distinguishing coloring of $B(1)$ with at most $k$ colors that assigns to $y \in VB(1)$ the color $c_0$ if and only if $y=x$.  For $j\geq2$ we define the $k$-coloring $\psi_j: VB(j)\to X$ by

\[\psi_j(y) = \begin{cases} \psi_{j-1}(y) \quad & \text{if $y \in VB(j-1)$,}\\ \varphi_j(y) \quad & \text{if $y\in VB(j)\setminus VB(j-1)$.} \end{cases}\]
Our induction hypothesis is that for all $i<j$, $\psi_i$ is a distinguishing coloring of $B(i)$ that agrees with $\psi_{i-1}$ on $VB(i-1)$.  We claim that $\psi_j$ is a distinguishing coloring of $B(j)$ and is an extension of $\psi_{j-1}$.  For some $g \in \aut(B(j))$, suppose that $\psi_j(y^g) = \psi_j(y)$ for all $y \in VB(j)$. Since $\psi_j(y) = c_0$ if and only if $y = x$, we have that $g$ fixes $x$ and therefore $g$ fixes $VB(j-1)$ setwise. Since $\psi_{j-1}$ is a distinguishing coloring of $B(j-1)$ while $\psi_j$ and $\psi_{j-1}$ agree on $VB(j-1)$, $\psi_j$ restricted to $B(j-1)$ is a distinguishing coloring of $B(j-1)$; hence $g$ fixes $VB(j-1)$ pointwise.  But $g$ also fixes $VB(j) \setminus VB(j-1)$ setwise.  Hence for all $y\in VB(j) \setminus VB(j-1)$, we have $\varphi_j(y)=\psi_j(y)=\psi_j(y^g)=\varphi_j(y^g)$. We have shown that for all $y \in B(j)$ we have $\varphi_j(y) = \varphi_j(y^g)$, which implies $y=y^g$ because $\varphi_j$ is a distinguishing coloring of $B(j)$.  Hence $\psi_j$ is a distinguishing coloring of $B(j)$ that agrees with $\psi_i$ on $B(i)$ whenever $i\leq j$.

Define a function $\psi : V\Gamma \rightarrow X$ as $\psi(y) = \psi_i(y)$ whenever $y \in VB(i) $. The argument of the preceding paragraph implies that $\psi$ is well-defined.  We claim that $\psi$ is a distinguishing coloring of $\Gamma$. For suppose that $\psi(y^g) = \psi(y)$ for some $g \in \aut(\Gamma)$ and all $y \in V\Gamma$.  Then $g$ fixes $x$ and therefore $g$ fixes setwise every set $VB(i)$. Moreover, for all $i \in \mathbb{N}$ and for all $y \in VB(i)$, the function $\psi_i$ is a distinguishing coloring of $B(i)$; since $\psi_i(y^g) = \psi(y^g) = \psi(y) = \psi_i(y)$, it follows that $y^g = y$. Hence $\psi$ is a distinguishing coloring of $\Gamma$, and so $D(\Gamma) \leq|X|=k$.  
\end{proof}


%%%%%%%%%%Section 3
\section{Distinguishing number and imprimitivity}\label{Imprimitivity}


Given an infinite permutation group $(G,V)$, we obtain an upper bound for $D(G,V)$ when $G$ acts imprimitively on $V$.  We then apply this bound to the group of automorphisms of a locally finite graph in order to demonstrate that our bound is sharp.  Since imprimitive groups can be embedded in wreath products in a natural way (see \cite[Theorem 8.5]{bat_mac_mol_neu}, for example), we first present for completeness a definition and notation for the wreath product of two permutation groups.  (See, for example, \cite[pp 67--72]{bat_mac_mol_neu}.)

Let $H \leq \sym(S)$ and $K \leq \sym(T)$.  The {\em wreath product} $H \wr K$ is defined to be the semidirect product $\text{Fun}(T, H) \rtimes K$, where $\text{Fun}(T, H)$ is the group of functions from $T$ to $H$. The wreath product $H \wr K$ has a faithful action (called the imprimitive action) on $S \times T$, defined as follows: for all $(a,b) \in S \times T$, $f \in \text{Fun}(T, H)$, and $k \in K$,
\begin{equation}\label{defn_wreath}
(a,b)^{(f, k)} := (a^{f(b)}, b^k).
\end{equation}

\begin{proof}[Proof of Theorem~\ref{thm:wr}]
Fix some equivalence class $A \in \B$. Let $\chi: \B \rightarrow X$ be a distinguishing coloring of $(G, \B)$, and let $\psi: A \times X \rightarrow Y$ be a distinguishing coloring of $(H \wr \sym(X), A \times X)$, where $Y$ is some sufficiently large set of colors.  Thus $D(H \wr \sym(X), A \times X)\leq|Y|$.

Since $(G, \B)$ is transitive, for each $B\in\B$ there exists $g_B\in G$ such that $B^{g_B}=A$.  This defines an injection $f:\B\to G$ given by $B\mapsto g_B$; that is,
\begin{equation*}
B^{f(B)}=A\ {\text{for each }}B\in\B.
\end{equation*}
We now define a coloring  $\phi: V \rightarrow Y$ as follows: for each $v \in V$, if $B$ is the block in $\B$ containing $v$, then
\begin{equation*}
\phi(v) := \psi \left ( \left ( v^{f(B)}, \chi(B) \right ) \right).
\end{equation*}
It remains only to show that $\phi$ describes a distinguishing coloring of $(G, V)$, for this will imply that, for any set $Y$, if $D(H \wr \sym(X), A \times X)\leq|Y|$, then $D(G,V)\leq|Y|$.

Suppose that some permutation $g\in G$ preserves all the color classes of $\phi$ in $V$. If $x \in A$ and $B \in\B$, then we have
\[\phi(x^{f(B)^{-1} g}) = \phi(x^{f(B)^{-1}}) = \psi \left ( \left ( x^{f(B)^{-1} f(B)}, \chi(B) \right ) \right ) = \psi \left ( \left ( x, \chi(B) \right ) \right ).\]
However, we also have that
\[\phi(x^{ f(B)^{-1} g}) = \psi \left ( \left ( x^{ f(B)^{-1} g \, f(B^g)}, \chi(B^g) \right ) \right ).\]
Hence, for all $x \in A$ and $B \in \B$, and for all $g \in G$ that preserve the coloring function $\phi$, we have
\begin{equation}\label{eq:b}
\psi \left ( \left ( x, \chi(B) \right ) \right ) = \psi \left ( \left ( x^{f(B)^{-1} g \,  f(B^g)}, \chi(B^g) \right ) \right ).
\end{equation}

Fix some $g \in G$ that preserves the coloring $\phi$ of $V$. We now show that $g$ must fix $V$ pointwise, from which it follows that $\phi$ is a distinguishing coloring of $(G,V)$. Fix $B \in \B$ and note that ${f(B)^{-1} g \, f(B^g)} \in G_{\{A\}}$. Let $h \in H$ be the permutation of $A$ induced by ${f(B)^{-1} g \, f(B^g)}$. Let $\sigma \in \sym(X)$ be the permutation of $X$ that interchanges the colors $\chi(B)$ and $\chi(B^g)$ and fixes every other element of $X$; thus either (i) $\sigma$ is is a transposition or (ii) $\sigma=1_X$.

Let us define $\theta : X \rightarrow H$ by
\[\theta(i) = 
\begin{cases}
h & \text{ \ if $i = \chi(B)$;}\\
h^{-1} & \text{ \ if $i = \chi(B^g)$;}\\
1_H & \text{ \ otherwise.}
\end{cases}
\]
Thus $(\theta, \sigma) \in H \wr \sym(X)$, and we must apply Equation (\ref{defn_wreath}) to evaluate $(x, \chi(B))^{(\theta, \sigma)}\in A \times X$ in each of the two cases.

In Case (i), where $\chi(B) \neq \chi(B^g)$, we have by Equation (\ref{defn_wreath}) that $(x, \chi(B))^{(\theta, \sigma)}=(x^{\theta(\chi(B))},\chi(B)^\sigma)=(x^h, \chi(B^g))$ and $(x^h, \chi(B^g))^{(\theta, \sigma)} = (x, \chi(B))$ for all $x\in A$, while all other elements of $A \times X$ remain fixed by $(\theta, \sigma)$. Thus, by Equation (\ref{eq:b}), the permutation $(\theta, \sigma)$ preserves the color classes of $\psi$ on $A\times X$ and is therefore the identity. Since this contradicts the assumption that $\chi(B) \not = \chi(B^g)$, Case (i) is not possible.

So, we must have Case (ii), where $\chi(B) = \chi(B^g)$. We now define
\[\theta(i) = 
\begin{cases}
h & \text{ \ if $i = \chi(B)$;}\\
1_H & \text{ \ otherwise}.
\end{cases}
\]
Applying Equation (\ref{defn_wreath}) again (and noting that $\sigma$ is trivial), we have  $(x, \chi(B))^{(\theta, \sigma)} = (x^h, \chi(B)) = (x^h, \chi(B^g))$ for all $x \in A$; every other element of $A \times X$ is fixed by $(\theta, \sigma)$. Thus by Equation (\ref{eq:b}) the permutation $(\theta, \sigma)$ preserves the coloring $\psi$, and is therefore the identity on $A\times X$. In particular, $h=1_A$.

Since $B \in \B$ was chosen arbitrarily, we have shown that for all $B \in \B$,
$$\chi(B) = \chi(B^g)\qquad{\text{and}}\qquad f(B)^{-1} g f(B) \in G_{(A)},$$
where $G_{(A)}$ here denotes the pointwise stabilizer in $G$ of $A$. Thus the action of $g$ on $\B$ preserves $\chi$, and so $g$ fixes each class in $\B$ setwise. Furthermore, if $y \in V$ then there exists some $B \in \B$ and $x \in A$ such that $y = x^{f(B)^{-1}} = \left ( x^{f(B)^{-1} g f(B)} \right )^{f(B)^{-1}} = x^{f(B)^{-1} g} = y^g$. Hence $g$ fixes $V$ pointwise, and $\phi$ is a distinguishing coloring of $(G, V)$.
\end{proof}

We now use Theorem \ref{thm:wr} to obtain the companion graph-theoretical result.

\begin{proof}[Proof of Corollary~\ref{thm_imprimitive}]
Write $G:=\aut(\Gamma)$ and let $\B$ denote the set of all equivalence classes with respect to $\cong$.  Thus $n=D(G,\B)$.  
Let $X$ be an $n$-set (of colors).  Abusing notation, identify $V\Delta$ with an equivalence class $B\in\B$.  One may thus represent  the vertex set of $n \Delta$ as $B\times N=\{(x, \nu) : x \in B;\  \nu \in N\}$, where we understand that for any given $\nu_0\in N$, the set $\{(x, \nu_0) : x \in B\}$ induces a copy of $\Delta$.  Since $\aut(\Delta) \wr \sym(N)$ acts as a group of permutations on $B\times N$, we have $\aut(\Delta) \wr \sym(N) \leq \sym(B \times N)$.  Since $\aut(\Delta) \wr \sym(N)$ preserves the edge structure of $n \Delta$, we have $\aut(\Delta) \wr \sym(N) \leq \aut(n\Delta)$. 

 Let $H$ be the subgroup of $\sym(B)$ induced by $G_{\{B\}}$. If $\C$ is the orbit of $G$ on $\B$ that includes $B$, then $D(G, \C) \leq D(G, \B)$.  If $W$ is the set of those vertices of $\Gamma$ that lie in some equivalence class in $\C$, we have by Theorem~\ref{thm:wr} applied to $(G,\C)$ that the distinguishing number of the subgroup of $\sym(W)$ induced by $G$ is at most 
$D(H \wr \sym(X), B \times X) \leq D(\aut(\Delta) \wr \sym(X), B \times X) \leq D(n \Delta)$.
Since this is true for all orbits $\C$ of $G$ on $\B$, the inequality $D(G, V) \leq D(n \Delta)$ holds. In the above argument, one may replace $\Gamma$  and $\Delta$ with their respective complements to obtain $D(G, V) \leq D(n\Delta')$.  Hence $D(G, V) \leq \min \{D(n\Delta), D(n \Delta')\}$.
This bound is sharp, since given a cardinal $n$ and a connected graph $\Delta$, one could choose $\Gamma$ to be the graph $n\Delta$.
\end{proof}

\begin{remark} The bound in Corollary~\ref{thm_imprimitive} is sharp even for connected graphs, since $n \Delta$ and its complement have the same distinguishing number.
\end{remark}

The following example constitutes a proof of Corollary~\ref{SharpBound}, by giving a sharp bound for the inequality of Theorem~\ref{thm_finite_balls} in the case of locally finite graphs.

%%%%%%%%Example7
\begin{example} \label{main_example}  For any given integer $k \geq 3$, we construct an infinite, locally finite graph $\Gamma$ with the following two properties:
\begin{enumerate}
\item
	$D(\Gamma)=k+1$; and
\item For all $x \in V\Gamma$, all but finitely many ball-graphs centered at $x$ have distinguishing number $k$.
\end{enumerate}

Let $A_0$ be the complete graph $K_k$ on $k$ vertices; let $A_1$ be the complete graph $K_{k(k-1)}$ minus a $1$-factor, and let $A_2$ be the null graph of order $k$.  (We will use that these three graphs are vertex-transitive,  have distinct valences, and have distinguishing number~$k$.)  Write $[n] := n\pmod{3}$. Let $\Gamma$ be the infinite, locally finite graph with vertex set $V\Gamma = \bigcup_{n \in \Z} \left ( VA_{[n]}\times \{n\} \right )$, in which two vertices $( x,m), (y,n) \in V\Gamma$ are adjacent if and only if 
\begin{enumerate}
\item
	$n=m$ and $x$ and $y$ are adjacent in $A_{[n]}$; or
\item
	$|n-m|=1$.
\end{enumerate}
Intuitively, $\Gamma$ has the  form
\[\cdots-A_2 - A_0-A_1-A_2-A_0-A_1-\cdots\]
in which each vertex of any copy of $A_{[n]}$ is adjacent to every vertex of its adjacent copies of $A_{[n-1]}$ and $A_{[n+1]}$.  For $n \in\Z$, let $H_n$ be the subgraph of $\Gamma$ induced by $VA_{[n]}\times\{n\}$ (so $H_n \cong A_{[n]}$), and let $\mathcal{H}:=\{H_n : n \in \mathbb{Z}\}$.


Let us first examine $\aut(\Gamma)$. One straightforwardly verifies that for all $m\in\N$ the valences (in $\Gamma$) of vertices in $H_{3m},\ H_{3m+1}$, and $H_{3m+2}$ are, respectively, $k^2+k-1$, $k^2+k-2$, and  $k^2$.  Since $k\geq3$, these three integers are distinct, and so the orbit of any vertex in $VH_n$ is the set $\bigcup\{VH_m:m\equiv n\pmod3\}$.
Fix $g \in \aut(\Gamma)$.  Since $H_0 \cong A_0$ is connected, it must therefore hold  that $H_0^g=H_{3m}$ for some $m\in\Z$,
and an elementary adjacency argument shows 
that $g$ satisfies $H_n^g=H_{3m+n}$ for all $n\in\Z$.  If $m\neq0$, then $g$ is a translation.  Thus 
\[\B=\{VH_{3m}\cup VH_{3m+1}\cup VH_{3m+2}: m\in\Z\}\]
is a system of imprimitivity for $\A(\Gamma)$.  It is obvious that $D(\langle P \rangle)=k$ for any $P\in\B$ (where $\langle P \rangle$ denotes the subgraph of $\Gamma$ induced by $P$) and that $D(2\langle P \rangle)=k+1$.  Since $\Gamma/\B$ is a double ray, we have $D(\Gamma/\B)=2$.  Hence by Corollary~\ref{thm_imprimitive}, we have $D(\Gamma)\leq D(2\langle P \rangle)=k+1$. Of course $D(\Gamma) > k$, because there exists a distinguishing $k$-coloring of each subgraph $H_n$, and it is unique up to a permutation of the colors; any $k$-coloring which distinguishes each subgraph $H_n$ is therefore preserved by some non-trivial translation of $\Gamma$.

It remains only to show that for any given $(x, n) \in V\Gamma$ and integer $m\geq3$, the ball-graph $B_m:=B\left ((x,n), m \right )$ has distinguishing number at most $k$.  Clearly
$$VB_m = \bigcup_{i=n-m}^{n+m} VH_{i}.$$
If $|n-i|<m$, then the valence of a vertex in $H_i$ is the same in both $B_m$ and $\Gamma$.  If $|n-i|=m$, then the valence of a vertex in $H_i$ is one of the five smaller values:  $k^2-1$, $k^2-2,\ k^2-k,\ 2k-1,\  k$.  By a simple inductive argument, it follows that every automorphism of $B_m$ fixes $H_i$ setwise whenever $|n-i|\leq m$.  Since $D(H_i)=k$ it must hold that $D(B_m) \leq k$.

We remark that one can find a $k$-subset of the vertices of $H_{3m-1}$ whose union with $H_{3m}$ is isomorphic to $K_{2k}$, but the resulting graph is not a ball-graph.   
\end{example}


Our next example is a graph for which Corollary~\ref{thm_imprimitive} gives a meaningful, sharp upper bound on its distinguishing number. This graph is connected, infinite, locally finite and vertex-transitive; it has a finite distinguishing number strictly greater than $2$ and admits a system of imprimitivity whose blocks are finite.


\begin{example} \label{ex:refs_request} If $\Gamma, \Delta$ are graphs, the {\em lexicographic product} $\Gamma[\Delta]$ is the graph in which each vertex of $\Gamma$ is replaced with a copy of $\Delta$, with all edges joining copies of $\Delta$ corresponding to adjacent vertices in $\Gamma$.

Let $Z$ be the double ray. Fix integers $m, r > 2$, let $\Gamma$ be the graph $Z[mK_r]$, and let $G:=\aut(\Gamma)$. Clearly $G$ is transitive on $V\Gamma$, and there is a $G$-invariant equivalence relation $\cong$ on $V\Gamma$ in which two vertices are equivalent if and only if they lie in the same copy of $K_r$. The quotient graph $\Gamma / \cong$ is isomorphic to $Z[K_m']$ and
$D(\Gamma) = \min\{\ell \in \N : \binom{\ell}{r} \geq m+1\}$. Now $n:= D(\Gamma / \cong) = m+1$, and $D(n K_r) = \min \{\ell \in \N : \binom{\ell}{r} \geq n\}$, so $D(\Gamma) = D(n K_r)$. Thus, the bound given by Corollary~\ref{thm_imprimitive} for $D(\Gamma)$ is sharp, and $2 < D(\Gamma) < \aleph_0$.
\end{example}




Here is another way to bound the distinguishing number of an imprimitive graph.

\begin{corollary} \label{thm_bounds} Under the hypothesis of Corollary~\ref{thm_imprimitive}, if $n:=D(\Gamma / \cong)$ and  $k := D(\Delta)$ are finite, then
\[D(\Gamma) < kn^{1/k}+1.\]
\end{corollary}

\begin{proof} Either $\Delta$ or its complement $\Delta'$ is connected, and $D(\Delta') = D(\Delta)=k$, so without loss of generality, suppose that $\Delta$ is connected.
Let $m$ be the integer satisfying $kn^{1/k} \leq m < kn^{1/k} +1$.  Since $m\geq k$, we have $\binom{m}{k}\geq(m/k)^k\geq n$.
But if $m$ satisfies $\binom{m}{k}\geq n$, then $D(n\Delta)\leq m$, because $\Delta$ is connected and a different $k$-set of colors may be used for each copy of $\Delta$.  Hence by Corollary \ref{thm_imprimitive}, $D(\Gamma)\leq D(n\Delta)\leq m < kn^{1/k}+1$.
\end{proof}

In the Introduction of this article, we referred to a result of Melody Chan, which requires the following notation.  For a permutation group $(H, A)$ let $n_r(H, A)$ be the number of distinct distinguishing $r$-colorings of $(H, A)$.  For $S \subseteq \N$ let
\[{\min}^* S := \begin{cases} \min S \quad \text{if $S \not = \emptyset$; and} \\ \aleph_0 \quad \text{if $S = \emptyset$.} \end{cases}\]
 
\begin{proposition}[M.\,Chan {\cite[Theorem 2.3]{chan06}}] \label{chan} If $(H, A)$ and $(K, B)$ are permutation groups and $D(K, B)$ is finite, then
\[D(H \wr K, A \times B) = {\min}^* \left \{ r \in \N : n_r(H, A) \geq |H|\cdot D(K, B) \right \}.\]
\end{proposition}

We conclude by showing how Chan's result implies Theorem~\ref{thm:wr} (when $G$ is transitive) and Corollary~ \ref{thm_imprimitive} (when $\Gamma$ is vertex-transitive) in the special case of finite distinguishing numbers.\medskip

\begin{proof}  
Suppose that $(G, V)$ is a transitive permutation group that induces a system of imprimitivity $\B$. Let $G^{\B}$ be the subgroup of $\sym(\B)$ induced by the action of $G$ on $\B$.  Suppose that 
$D(G^{\B}, \B)=n$, where $n$ is a positive integer.  Let $X$ denote an $n$-set of colors.  Let $A \in \B$, and let $H$ be the subgroup of $\sym(A)$ induced by the setwise stabilizer $G_{\{A\}}$.
Observe (by \cite[Theorem 8.5]{bat_mac_mol_neu} for example) that $(G, V)$ is permutation-isomorphic to a subgroup of $(H \wr G^{\B}, A \times \B)$. Hence,
$D(G, V) \leq D(H \wr G^{\B}, A \times \B)$
and
$D(G^{\B}, \B) = D(\sym(X), X)$.
Since $n$ is finite,  Proposition~\ref{chan} yields:
\begin{align*} D(H \wr G^{\B}, A \times \B)
&= {\min}^* \left \{ r \in \N : n_r(H, A) \geq |H|\cdot D(G^{\B}, \B) \right \} \\
&= {\min}^* \left \{ r \in \N : n_r(H, A)\geq |H|\cdot D(\sym(X), X) \right \} \\
&= D(H \wr \sym(X), A \times X).
\end{align*}\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
Much of this work was completed while the first author was a Philip T.~Church Postdoctoral Fellow at Syracuse University. The second author was partially supported by a grant from the Simons Foundation (\#209803 to Mark E.\,Watkins).  The authors thank the referee for several clever suggestions, one of which led us to a more general statement for Corollary~\ref{thm_imprimitive}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \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}
\markright{}
%
\bibitem{AC1} M.~O.~Albertson and K.~L.~Collins. \newblock
    Symmetry breaking in graphs. \newblock
    {\em Electron. J. Combin.}, 3, 1996, \#R18.
%
\bibitem {bat_mac_mol_neu}  M.~Bhattacharjee, D.~Macpherson, R.~G.~M{\"o}ller, and P.~M.~Neumann. \newblock
	{\em Notes on infinite permutation groups,} \newblock
    	volume 1698 of {\em Lecture Notes in Mathematics}
    	Springer-Verlag, 1998.
%
\bibitem {bruijn_erdos_51} N.~G.~de Bruijn and P.~Erd\H{o}s. \newblock
	A color problem for infinite graphs and a problem in the theory of relations. \newblock
    	{\em Indagationes Math.},
	13:369--373, 1951.
%
\bibitem {chan06} M.~Chan. \newblock
	The distinguishing number of the direct product and wreath product action. \newblock
	{\em J Algebr. Comb.},
	24:331--345, 2006.
%
\bibitem {collins_trenk} K.~L.~Collins and A.~N.~Trenk. \newblock
	The Distinguishing Chromatic Number. \newblock
	{\em Electron. J. Combin.}, 13, 2006, \#R16.
%
\bibitem {dirac_schuster} G.~A.~Dirac and S.~Schuster. \newblock
   	A theorem of Kuratowski. \newblock
	{\em Indagationes Math.},
	16:343--348, 1954.	
%
 \bibitem{imrich_et_al:distinguishing} W.~Imrich, S.~Klav\u{z}ar,  and V.~Trofimov. \newblock
    Distinguishing infinite graphs. \newblock
    {\em Electron. J. Combin.}, 14, 2007, \#R36.    

%
\bibitem{akos_seress} \'{A}.~Seress. \newblock
    Primitive groups with no regular orbits on the set of subsets. \newblock
    {\em Bull. London Math. Soc.},
    29(6):697--704, 1997.

%
\bibitem {sms_twt_mew} S.~M.~Smith, T.~W.~Tucker, and M.~E.~Watkins. \newblock
	Distinguishability of infinite groups and graphs. \newblock
    	{\em Electron. J. Combin.}, 19, 2012, \#P27.

	%
\bibitem {watkins_zhou}
	M.~E.~Watkins and X.~Zhou. \newblock
	Distinguishability of locally finite trees. \newblock
	{\em Electron. J. Combin.},
	14, 2007, \#R29.
%
\end{thebibliography}

\end{document}