9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details

Symmetry breaking in graphs and motion conjectures

Presented by Prof. Wilfried IMRICH
Type: Oral presentation
Track: Graph Theory


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}


Location: Koper, Slovenia

Primary authors