2021/10/16 by László Babai, Babai, Laszlo · 1 citation
Neuroscience · Computer Science · Mathematics · #Nuclear Receptors and Signaling #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2110.08492
An asymmetric coloring of a graph is a coloring of its vertices that is not\npreserved by any non-identity automorphism of the graph. The motion of a graph\nis the minimal degree of its automorphism group, i.e., the minimum number of\nelements displaced by any non-identity automorphism. In this paper we confirm\nTom Tucker's "Infinite Motion Conjecture" that connected locally finite graphs\nwith infinite motion admit an asymmetric 2-coloring. We infer this from the\nmore general result that the inverse limit of a sequence of finite permutation\ngroups with disjoint domains, viewed as a permutation group on the union of\nthose domains, admits an asymmetric 2-coloring. The proof is based on the study\nof the interaction between epimorphisms of finite permutation groups and the\nstructure of the setwise stabilizers of subsets of their domains.\n