9-13 June 2013

Koper, Slovenia

UTC timezone

# Symmetry breaking in graphs and motion conjectures

Presented by Prof. Wilfried IMRICH

Type: Oral presentation

Track: Graph Theory

## Content

This talk is concerned with automorphism breaking of finite and infinite graphs.
Albertson and Collins~\cite{alco-96} introduced the {\it
distinguishing number} $\D(G)$ of a graph $G$ as the least cardinal
$d$ such that $G$ has a labeling with $d$ labels that is only
preserved by the trivial automorphism.
This concept has spawned numerous papers on finite and
infinite graphs. Here we focus on the infinite motion conjecture of Tom Tucker
and generalizations. In particular, we present partial results pertaining to
the conjecture, a generalization to uncountable graphs, and results that
support the conjecture and its generalizations.
The starting point is
\begin{lemma}[ Motion Lemma, Russell and Sundaram \cite{rusu-98}] Let
the motion $\m(G)$ of a graph $G$ be the minimum number
of vertices that is moved by any nonidentity automorphism of $G$. Then
$2^{\frac{\m(G)}{2}} \geq |\Aut(G)|$
implies $\D(G)\leq 2.$
\end{lemma}
The immediate generalization to infinite graphs is the Motion Conjecture, with
Tucker's Infinite Motion Conjecture as a special case:
\begin{conjecture}
[ Motion Conjecture \cite{cuimle-xx}] Let $G$ be a connected, infinite graph with infinite motion $\m(G)$. Then
$2^{\m(G)} \geq |\mbox{Aut}(G)|$ implies $\D(G) \leq 2$.
\end{conjecture}
\begin{conjecture}
[Tucker's Infinite Motion Conjecture \cite{smtuwa-2012}] Let $G$ be a connected, locally finite infinite graph with
infinite motion $\m(G)$. Then
$\D(G) \leq 2$.
\end{conjecture}
Both conjectures are open, but partial results and connections to other structures will be presented in the talk.
We list one is by Florian Lehner \cite{le-xx} and another one by Cuno, Imrich and Lehner \cite{cuimle-xx}.
\begin{theorem}
The Infinite Motion Conjecture is true for graphs of growth $O\left(2^{(1-\epsilon)\frac{\sqrt{n}}{2}}\right)$.
\end{theorem}
\begin{theorem}
\label{thm:moth} Let $G$ be an infinite, connected graph with infinite motion. If $\m(G) \geq|\Aut(G)|$, then $\D(G) \leq 2$.
\end{theorem}
For countable $G$ this is easily shown by induction,
for graphs $G$ with larger cardinality by transfinite induction. We have the following corollary.
\begin{corollary}
\label{cor:moth}
Let $G$ be an uncountably infinite, connected graph with infinite motion, and suppose that $2^{\m(G)} > |\mbox{Aut}(G)|$.
Then, under the assumption of the general continuum hypothesis, $\D(G) \leq 2$.
\end{corollary}
For the analogous result for countably infinite, connected graphs one assumes the CH.
However, if the graphs are locally finite, then the CH is not needed. This was shown in \cite{imsm-xx} and follows from results of either Halin, Trofimov or Evans.
\begin{thebibliography}{99}
\bibitem{alco-96}
M.~O.~Albertson and K.~L.~Collins,
Symmetry breaking in graphs,
{\bf Electron.\ J. Combin.} 3 (1996) R18.
\bibitem{cuimle-xx}
J.~Cuno, W.~Imrich and F.~Lehner, Distinguishing graphs with infinite
motion and nonlinear growth, {\bf Ars Mathematica Contemporanea},
7 (2014), 201--213.
\bibitem{imsm-xx}
W.~Imrich, Simon M.~Smith, T.~Tucker and Mark E.~Watkins,
Infinite Motion and 2-Distiinguishability of Graphs and Groups,
submitted for publication.
\bibitem{le-xx}
F.~Lehner, Distinguishing graphs with intermediate growth, submitted for publication.
\bibitem{rusu-98}
A.~Russell and R.~Sundaram, A note on the asymptotics and
computational complexity of graph distinguishability, {\bf Electron. J. Combin.} 5 (1998) R23.
\bibitem{smtuwa-2012}
Simon M.~Smith, T.~Tucker and Mark E.~Watkins,
Distinguishability Of Infinite Groups And
Graphs, {\bf Electron. J. Combin.} 19 (2012) P27.
\end{thebibliography}
\end{document}

## Place

Location: Koper, Slovenia