Local finiteness, distinguishing numbers and Tucker's conjecture
Florian Lehner\thanks{The author acknowledges the support of the Austrian Science Fund (FWF)
project W1230-N13.
A distinguishing colouring of a graph is a colouring of the vertex set such that no non-trivial automorphism preserves the colouring. Tucker conjectured that if every non-trivial automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing $2$-colouring. We show that the requirement of local finiteness is necessary by giving a non-locally finite graph for which no finite number of colours suffices.
dist-nonlocfin.tex
\documentclass[a4paper,abstracton]{scrartcl}

\usepackage{amsfonts,amsthm,amssymb,amsmath}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage[inline]{enumitem}
\usepackage{ifpdf}
   \ifpdf
      \DeclareGraphicsRule{*}{mps}{*}{}
   \fi
   
\usepackage{enumitem}
\usepackage{hyperref}


\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prp}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}

\theoremstyle{remark}
\newtheorem{obs}[thm]{Observation}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{con}[thm]{Conjecture}

\newcommand{\dd}{D}
\newcommand{\Aut}{\mathrm{Aut \,}}
\newcommand{\id}{\mathrm{id}}

%\title{Local finiteness is necessary for Tucker's conjecture}
\title{Local finiteness, distinguishing numbers and Tucker's conjecture}
\author{Florian Lehner\thanks{The author acknowledges the support of the Austrian Science Fund (FWF), project W1230-N13.} \ and R�gnvaldur G.~M�ller}

\begin{document}
\maketitle

\begin{abstract}
A distinguishing colouring of a graph is a colouring of the vertex set such that no non-trivial automorphism preserves the colouring. Tucker conjectured that if every non-trivial automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing $2$-colouring.

We show that the requirement of local finiteness is necessary by giving a non-locally finite graph for which no finite number of colours suffices.
\end{abstract}


\section{Introduction}
\label{sec:intro}

A colouring of the vertices of a graph $G$ is called {\em distinguishing} if no  non-trivial automorphism of $G$ preserves the colouring. This notion was first studied by Albertson and Collins \cite{MR1394549}, motivated by a recreational mathematics problem posed Rubin \cite{rubin}. 

While a distinguishing colouring clearly exists for every graph (simply colour every vertex with a different colour), finding a distinguishing colouring with the minimum number of colours can be challenging.

%In this paper we focus on infinite graphs. 
For infinite graphs one of the most intriguing questions is whether or not the following conjecture of Tucker \cite{MR2776826} is true.  

\begin{con}%[Tucker \cite{MR2776826}]
\label{con:tucker}
Let $G$ be an infinite, connected, locally finite graph with infinite motion. Then there is a distinguishing $2$-colouring of $G$.
\end{con}

This conjecture can be viewed as a generalisation of a result on finite graphs due to Russell and Sundaram \cite{MR1617449}.  It is known to be true for many classes of infinite graphs including trees \cite{MR2302536}, tree-like graphs \cite{MR2302543}, and graphs with countable automorphism group \cite{istw}. In \cite{smtuwa} it is shown that graphs satisfying the so-called distinct spheres condition have infinite motion as well as distinguishing number two. Examples for such graphs include leafless trees, graphs with infinite diameter and primitive automorphism group, vertex-transitive graphs of connectivity $1$, and Cartesian products of graphs where at least two factors have infinite diameter. It is also known that Conjecture~\ref{con:tucker} is true for graphs fulfilling certain growth conditions \cite{growth}. In \cite{lehner-randomcolouring} it is shown that for locally finite graphs random colourings have a good chance of being distinguishing. 

Many of the above results also hold for non-locally finite graphs which raises the question, whether the condition of local finiteness in Tucker's conjecture can be dropped. 

A first indication, that local finiteness may be necessary has been given in the setting of permutation groups acting on countable sets. Here, instead of considering the automorphism group of a graph acting on the vertex set, we consider (faithful) group actions. A generalization of Conjecture \ref{con:tucker} to this setting has been given by Imrich et al.~\cite{istw}.

\begin{con}%[Imrich et al.~\cite{istw}]
\label{con:groups}
Let $\Gamma$ be a closed, subdegree finite permutation group on a set $S$.  Then there is a distinguishing $2$-colouring of $S$.
\end{con}

For this generalization subdegree finiteness (which plays the role of local finiteness) is known to be necessary \cite{MR2587751}. 

In this short note we show that local finiteness is also necessary in the graph case. More precisely we give a non-locally finite, arc transitive graph with infinite motion which does not admit a distinguishing colouring with any finite number of colours.


\section{Preliminaries}

Throughout this paper we will use Greek letters for group related variables while the Latin alphabet will be reserved for sets on which the group acts. 

Let $S$ be a countable set and let $\Gamma$ be a group acting faithfully (i.e. the identity is the only group element which acts trivially) on $S$ from the left. The image of a point $s \in S$ under an element $\gamma \in \Gamma$ is denoted by $\gamma s$.

The \emph{stabilizer} of $s$ in $\Gamma$ is defined as the subgroup $\Gamma_s = \{\gamma \in \Gamma \mid \gamma s = s\}$.
% and it is well known that this is a subgroup of $\Gamma$. 
We say that $\Gamma$ is \emph{subdegree finite} if for every $s \in S$ all orbits of $\Gamma_s$ are finite.

%Since the action of $\Gamma$ is faithful, we can consider it as a \emph{permutation group}, that is, a subgroup of the group $\Pi_S$ of all permutations of $S$. We say that $\Gamma$ is \emph{closed} if it is a closed subgroup of $\Pi_S$ in the topology of pointwise convergence where $S$ is equipped with the discrete topology.

The \emph{motion} of an element $\gamma \in \Gamma$ is the number (possibly infinite) of elements of $S$ which are not fixed by $\gamma$. The \emph{motion of the group $\Gamma$} is the minimal motion of a non-trivial element of $\Gamma$. Notice that the motion is not necessarily finite, in fact all groups considered in this paper have infinite motion.  The \emph{motion of a graph $G$} is the motion of $\Aut G$ acting on the vertex set.

Let $C$ be a (usually finite) set. A \emph{$C$-colouring of $S$} is a map $c \colon S \to C$.  Given a colouring $c$ and $\gamma \in \Gamma$ we say that \emph{$\gamma$ preserves $c$} if $c(\gamma s) = c(s)$ for every $s \in S$.  Call a colouring \emph{distinguishing} if no non-trivial group element preserves the colouring.


\section{The example}

The construction that we use relies on the following result from  \cite{MR2587751} which also shows that there are permutation groups on a countable sets whose distinguishing number is infinite. The proof uses a standard back-and-forth argument, see for example \cite[Sections 9.1 and 9.2]{zbMATH01230795} and \cite[Sections 2.8 and 5.2]{zbMATH00044603}.

\begin{thm}[Laflamme et al.~\cite{MR2587751}]
\label{thm:dist-q}
Let $\Gamma$ be the group of  order automorphisms of $\mathbb Q$ (i.e.\ bijective, order preserving functions $\gamma\colon \mathbb Q \to \mathbb Q$). Then $\Gamma$ has infinite motion but no distinguishing colouring with finitely many colours. \hfill \qedsymbol
\end{thm}


%\begin{proof}
%Suppose we have a colouring of $\mathbb Q$ with finitely many colours.  We show that this colouring is not distinguishing by constructing a non-trivial order and colour preserving function $\gamma\colon \mathbb Q \to \mathbb Q$.  

%It is not assumed that all the colours are dense but by considering an open interval $I$ we may assume that all the colours that occur on that interval are dense in the interval. 

%Now we use induction to construct a non-identity bijective, order and colour preserving, function $\gamma\colon \mathbb Q \to \mathbb Q$.  First, if $x$ is not on the open interval $I$ with end points $a$ and $b$ then we set $\gamma(x)=x$. Find two enumerations $p_1, p_2, \ldots$ and $q_1, q_2, \ldots$ of the interval $I$, and take care that $p_1$ and $q_1$ are different but have the same colour.   Start with setting $\gamma(p_1)=q_1$.  The next step is to find the element $p_i$ with the lowest number $i$ such that $p_i$ has the same colour as $q_2$ and $p_i$ is in the same relationship to $p_1$ as $q_2$ is to $q_1$, i.e.~if $q_2>q_1$ then we want $p_i>p_1$ and if $q_2<q_1$ then we want $p_i<p_1$.  Then set $\gamma(p_i)=q_2$.

%At step $n+1$ in the induction we have already defined $\gamma$ on a set $I_n$ that contains $n$ of the $p_i$'s.   

%If $n+1$ is an odd number, find the lowest number $i$ such that $p_i$ is not in $I_n$, then find the lowest number $j$ such that $q_j$ is not in $\gamma(I_n)$ and $q_j$ has the same colour as $p_i$ and with respect to the order $p_i$ and $q_j$ are in the same relationship to the points in $I_n$ and $\gamma(I_n)$, respectively.  Such a vertex exists because each colour is supposed to be dense in $I$.
%Then set $\gamma(p_i)=q_j$.

%If $n+1$ is even then we let $j$ be the lowest number such that $q_j$ is not in $\gamma(I_n)$.  Then let $i$ be the lowest number such that $p_i$ is not in $I_n$ and $p_i$ has the same colour as $q_j$ and with respect to the order $p_i$ and $q_j$ are in the same relationship to the points in $I_n$ and $\gamma(I_n)$, respectively. Then set $\gamma(p_i)=q_j$.

%Proceeding in this way it is clear that in the end we will have defined $\gamma$ on the whole of $I$ and that $\gamma$ is both injective and surjective.  It is also clear that at each step we have a map $I_n\to \gamma(I_n)$ that preserves the colouring and the ordering.  

%Thus we have defined a function $\gamma\colon \mathbb Q \to \mathbb Q$ that preserves the colouring and the ordering and $\gamma$ is non-trivial because $\gamma(p_1)=q_1\neq p_1$.
%\end{proof}

%\begin{proof}
%Clearly $\Gamma$ has infinite motion because if some element $q \in \mathbb Q$ is moved by $\gamma \in \Gamma$, then all elements that lie between $q$ and $\gamma q$ must be moved as well.

%It remains to show that there is no distinguishing colouring with a finite number of colours. Let $c\colon \mathbb Q \to C$ be a colouring of the rationals with a finite number of colours. It is easy to see that we can find an open interval $I$ such that the preimage of each colour is either dense in $I$ or it does not intersect $I$ at all. We can choose $I$ such that the interval boundaries are rational.

%We now use the interval $I$ to define a colour preserving function $\gamma \in \Gamma$. For $q \in \mathbb Q \setminus I$ let $\gamma q = q$. In order to define $\gamma$ on $I$ let $(q_i)_{i \in \mathbb N}$ be an enumeration of all elements of $\mathbb Q \cap I$.

%\begin{figure}
%\begin{center}
%\includegraphics{images/images.1}
%\end{center}
%\caption[Finding an image and preimage for $q_i$.]{Finding an image and preimage for $q_i$. Arrows indicate, which values of $\gamma$ have already been chosen inside the interval $I = [a,b]$. Note that the arrows cannot cross because the function is order preserving by construction. The grey triangles show the possible choices for $\gamma q_i$ and $\gamma^{-1} q_i$.}
%\label{fig:forwardbackward}
%\end{figure}

%We now inductively define $\gamma$ on $I$. Assume that we have already chosen $\gamma q_j$ and $\gamma^{-1} q_j$ for each $j < i$. The process of finding an image and a preimage of $q_i$ is sketched in Figure~\ref{fig:forwardbackward}. Denote by $P_i$ the set of all $q \in \mathbb Q$ such that $\gamma q$ has already been defined. Note that
%\begin{align*}
%\overline{p_i} &= \min \{q \in P_i \mid q \geq q_i\}& \text{and} && \underline{p_i} &= \max \{q \in P_i \mid q \leq q_i\}
%\end{align*}
%exist. This is because there are only finitely many candidates for the minimum and maximum, namely the boundary points of the interval and the finite set of points inside $I$ whose image has already been chosen. If $\overline{p_i} = \underline{p_i}$, then they must both coincide with $q_i$ and hence we have already chosen the image of $q_i$ in an earlier step. Otherwise we can choose $\gamma q_i \in (\gamma \underline{p_i},\gamma \overline{p_i})$ such that $c(q_i) = c(\gamma q_i)$ because the preimage of $c(q_i)$ is dense in $I$ and hence also in  $(\underline{p_i},\overline{p_i}) \subseteq I$. Furthermore we can choose $\gamma q_i \neq q_i$.

%Next we define $\gamma^{-1}q_i$. For this purpose let $S_i$ be the set of all $q \in \mathbb Q$ whose preimage has already been defined. The elements 
%\begin{align*}
%\overline{s_i} &= \min \{q \in P_i \mid q \geq q_i\}& \text{and} && \underline{s_i} &= \max \{q \in P_i \mid q \leq q_i\}
%\end{align*}
%exist for the analogous reasons as $\overline{p_i}$ and $\underline{p_i}$. If $\overline{s_i} = \underline{s_i}$ then they must both coincide with $q_i$ and hence we have already chosen the preimage of $q_i$ in an earlier step. Otherwise we can choose $\gamma^{-1} q_i \in (\gamma^{-1} \underline{s_i}, \gamma^{-1} \overline{s_i})$ such that $c(q_i) = c(\gamma^{-1} q_i)$.

%If we repeat this construction then we end up with a function $\gamma\colon \mathbb Q \to \mathbb Q$. This function is bijective because every $q \in \mathbb Q$ has a unique image and a unique preimage. It preserves the colouring and the order by construction and it is not the identity because in the first step we can choose $\gamma q_1 \neq q_1$.

%We have showed that for any colouring $c$ of $\mathbb Q$ with a finite number of colours there is a non-trivial permutation $\gamma \in \Gamma$ which preserves $c$. Hence the distinguishing number of this group must be infinite.
%\end{proof}

Clearly the group $\Gamma$ of the above theorem is the full automorphism group of the following directed graph: take $\mathbb Q$ as vertex set and draw an edge from $q$ to $r$ if $q \leq r$. The underlying undirected graph is the complete countable graph which also has infinite distinguishing number but finite motion. 


%One way to turn a directed graph into a graph is replacing every vertex $v$ by an isomorphic copy of an asymmetric graph $H$. In this graph fix two vertices $x^{\text{in}}$ and $x^{\text{out}}$. Denote by $x^{\text{in}}_v$ and $x^{\text{out}}_v$ the vertices corresponding to $x^{\text{in}}$ in the copy of $H$ that replaced the vertex $v$. Finally connect $x^{\text{out}}_v$ to $x^{\text{in}}_w$ whenever there is a directed edge from $v$ to $w$. 

%If we apply this construction to the directed graph obtained from the order of the rationals, then we end up with a undirected graph $G$ with the same automorphism group. Automorphisms of this graph simply permute the copies of $H$ in the same way as the corresponding order automorphism of $\mathbb Q$ permuted the rationals. Clearly we can choose $H$ to be finite. If $H$ has $n$ vertices then there are only $k^n$ different colourings of $H$ with $k$ colours. In particular every colouring of $G$ with $k$ colours corresponds to a colouring of $\mathbb Q$ with $n^k$ colours and hence it cannot be distinguishing. 

%However,with a little more effort we can use Theorem \ref{thm:dist-q} to construct a more symmetric example of a countable graph which does not admit a distinguishing colouring with finitely many colours.

\begin{figure}
\begin{center}
\includegraphics{images.2}
\end{center}
\caption[An induced subgraph of the graph from Theorem \ref{thm:counterexample}.]{An induced subgraph of the graph in Theorem \ref{thm:counterexample}. Note that edges only go from top left to bottom right. By the definition of the graph all such edges are present and every edge is of this type.}
\label{fig:induced}
\end{figure}

\begin{thm}
\label{thm:counterexample}
There is a countable, connected, arc transitive graph with infinite motion which has no distinguishing colouring with a finite number of colours.
\end{thm}


\begin{proof}
Let $\mathbb Q^+$ and $\mathbb Q^-$ be two disjoint copies of $\mathbb Q$. Denote the elements corresponding to $q \in \mathbb Q$ in these copies by $q^+$ and $q^-$, respectively. Consider the (undirected) graph $G = (V,E)$ where $V =\mathbb Q^+ \cup \mathbb Q^-$ and $q^+r^- \in E$  whenever $q < r$. Figure \ref{fig:induced} shows a small subgraph of this graph to give an idea of what it looks like. Clearly $G$ is countable and connected.

Note that $G$ is bipartite with bipartition $\mathbb Q^+ \cup \mathbb Q^-$. Hence every automorphism $\gamma$ of $G$ either fixes $\mathbb Q^+$ and $\mathbb Q^-$ set-wise, or swaps the two sets. Furthermore if $\gamma q^+ = r^+$ then $\gamma q^- = r^-$ because $q^-$ is the unique vertex with the property $N(q^-) = \bigcap_{v \sim q^+} N(v) \setminus \{q^+\}$. A similar argument shows that if $\gamma q^+ = r^-$ then $\gamma q^- = r^+$. So the action on $\mathbb Q^+$ uniquely determines an automorphism of $G$. 


Now, we define a family of automorphisms of $G$ (we will later show that these are in fact all the automorphisms of $G$). For every order automorphism $\gamma$ of $\mathbb Q$, define the functions $\gamma_\uparrow$ and $\gamma_\downarrow$ as follows: 
\begin{itemize}
\item $\gamma_\uparrow$ applies $\gamma$ to both copies of $\mathbb Q$, i.e.\ $\gamma_\uparrow(q^+) = (\gamma(q))^+$, $\gamma_\uparrow(q^-) = (\gamma(q))^-$,
\item $\gamma_\downarrow$ first applies $\gamma$ to both copies, then reverses the order on each of them and swaps them, i.e.\ $\gamma_\downarrow(q^+) = (-\gamma(q))^-$, and $\gamma_\downarrow(q^-) = (-\gamma(q))^+$.
\end{itemize}
It is straightforward to check that these maps are indeed automorphisms of the graph $G$.

To see that $G$ is arc transitive, notice that the arc $0^+1^-$ can be mapped to any arc of the form $q^+r^-$ by the automorphism $\gamma_\uparrow$ where
\[
	\gamma(x) = q+(r-q)x.
\]
The map $\gamma$ is an order automorphism of $\mathbb Q$ since $q^+r^- \in E$ implies that $q < r$. By analogous arguments, the arc $0^+1^-$ can be mapped to any arc of the form $q^-r^+$ by the automorphism $\gamma_\downarrow$ where
\[
	\gamma(x) = -q+(q-r)x.
\]

Every map of the type $\gamma_\uparrow$ and $\gamma_\downarrow$ moves infinitely many vertices. Thus, to show that $G$ has infinite motion, it suffices to prove that the automorphisms of the form $\gamma_\uparrow$ and $\gamma_\downarrow$ as defined above are the only automorphisms of $G$. 


It is not hard to see that $q \geq r$ if and only if $N(q^+) \subseteq N(r^+)$. This implies that $N(\phi(q^+))\subseteq N(\phi(r^+))$ for every automorphism $\varphi$ of $G$. If $\varphi$ fixes $\mathbb Q^+$ set-wise we conclude that $\varphi$ preserves the order on $\mathbb Q^+$, hence it is equal to $\gamma_\uparrow$ for a suitable order automorphism $\gamma$. An analogous argument shows that if  $\varphi$ swaps $\mathbb Q^+$ and $\mathbb Q^-$, then $\varphi = \gamma_\downarrow$ for an order automorphism $\gamma$ of $\mathbb Q$.



Finally, assume that there is a distinguishing colouring $c$ of $G$ with $n < \infty$ colours. In particular this colouring would break every automorphism of the form $\gamma_\uparrow$. Hence the map $q \mapsto (c(q^+), c(q^-))$ would be a distinguishing colouring of $\mathbb Q$ with $n^2 < \infty$ colours, a contradiction to Theorem \ref{thm:dist-q}.
\end{proof}

\bibliographystyle{abbrv}
\bibliography{sources}

\end{document}

dist-nonlocfin.bbl
\begin{thebibliography}{10}

\bibitem{MR1394549}
M.~O. Albertson and K.~L. Collins.
\newblock Symmetry breaking in graphs.
\newblock {\em Electron. J. Combin.}, 3(1):Research Paper 18, approx.\ 17 pp.,
  1996.

\bibitem{zbMATH01230795}
M.~{Bhattacharjee}, D.~{Macpherson}, R.~G. {M\"oller}, and P.~M. {Neumann}.
\newblock {\em {Notes on infinite permutation groups.}}
\newblock Springer Lecture Notes Series 1698.
\newblock Berlin: Springer, 1998.

\bibitem{zbMATH00044603}
P.~J. {Cameron}.
\newblock {\em {Oligomorphic permutation groups.}}
\newblock LMS Lecture Notes Series 152.
\newblock Cambridge: Cambridge University Press, 1990.

\bibitem{MR2302543}
W.~Imrich, S.~Klav{\v{z}}ar, and V.~Trofimov.
\newblock Distinguishing infinite graphs.
\newblock {\em Electron. J. Combin.}, 14(1):Research Paper 36, 12 pp., 2007.

\bibitem{istw}
W.~Imrich, S.~M. Smith, T.~Tucker, and M.~E. Watkins.
\newblock Infinite motion and 2-distinguishability of graphs and groups.
\newblock {\em J.~Algebr.~Comb.}, 41(1):109 -- 122, 2015.

\bibitem{MR2587751}
C.~Laflamme, L.~Nguyen Van~Th{{\'e}}, and N.~Sauer.
\newblock Distinguishing number of countable homogeneous relational structures.
\newblock {\em Electron. J. Combin.}, 17(1):Research Paper 20, 17, 2010.

\bibitem{growth}
F.~Lehner.
\newblock Distinguishing graphs with intermediate growth.
\newblock {\em Combinatorica}, 
\newblock to appear.

\bibitem{lehner-randomcolouring}
F.~Lehner.
\newblock Random colorings and automorphism breaking in locally finite graphs.
\newblock {\em Combin.\ Probab.\ Comput.}, 22(6):885 -- 909, 2013.

\bibitem{rubin}
F.~Rubin.
\newblock Problem 729.
\newblock {\em J. Recreational Math.}, 11:128, 1979.
\newblock (solution in volume 12, 1980).

\bibitem{MR1617449}
A.~Russell and R.~Sundaram.
\newblock A note on the asymptotics and computational complexity of graph
  distinguishability.
\newblock {\em Electron. J. Combin.}, 5:Research Paper 23, 7 pp.\, 1998.

\bibitem{smtuwa}
S.~M. Smith, T.~W. Tucker, and M.~E. Watkins.
\newblock Distinguishability of infinite groups and graphs.
\newblock {\em Electron. J. Combin.}, 19(2):Research Paper 27, 10 pp., 2012.

\bibitem{MR2776826}
T.~W. Tucker.
\newblock Distinguishing maps.
\newblock {\em Electron. J. Combin.}, 18(1):Paper 50, 21, 2011.

\bibitem{MR2302536}
M.~E. Watkins and X.~Zhou.
\newblock Distinguishability of locally finite trees.
\newblock {\em Electron. J. Combin.}, 14(1):Research Paper 29, 10 pp., 2007.

\end{thebibliography}
