Coarse distinguishability of graphs with symmetric growth

DOI10.26493/1855-3974.2354.616MaRDI QIDQ5013344zbMATH OpenOpenAlexFDO

Authors Jesús A. Álvarez López, Ramón Barral Lijó, Hiraku Nozawa

Publication date 30 November 2021

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.09716

zbMATH Keywords

symmetrygrowthgraph coloringcoarsedistinguishing

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Lipschitz and coarse geometry of metric spaces (51F30)

Abstract: Let $X$ be a connected, locally finite graph with symmetric growth. We prove that there is a vertex coloring $phicolonXo0,1$ and some $RinmathbbN$ such that every automorphism $f$ preserving $phi$ is $R$-close to the identity map; this can be seen as a coarse geometric version of symmetry breaking. We also prove that the infinite motion conjecture is true for graphs where at least one vertex stabilizer $S_x$ satisfies the following condition: for every non-identity automorphism $fin{S}_x$, there is a sequence $x_n$ such that $limd(x_n,f(x_n))=infty$.

Recommendations

• A note on the asymptotic and computational complexity of graph distinguishability
• Distinguishing graphs with intermediate growth
• scientific article; zbMATH DE number 2128201
• The cost of distinguishing graphs
• scientific article; zbMATH DE number 5972334
• Symmetric graphs with respect to graph entropy
• Distinguishing threshold of graphs
• Cohen-Macaulay growing graphs
• The complexity of symmetry breaking in massive graphs
• Detecting almost symmetries of graphs

Cites work

• scientific article; zbMATH DE number 2012373 (Why is no real title available?)
• A conjecture concerning a limit of non-Cayley graphs
• A note on the asymptotic and computational complexity of graph distinguishability
• Amenability, unimodularity, and the spectral radius of random walks on infinite graphs
• Asymmetric trees with two prescribed degrees
• Coarse differentiation of quasi-isometries. I: Spaces not quasi-isometric to Cayley graphs
• Coarse differentiation of quasi-isometries. II: Rigidity for Sol and lamplighter groups
• Distinguishing density and the distinct spheres condition
• Distinguishing graphs with infinite motion and nonlinear growth
• Distinguishing graphs with intermediate growth
• Distinguishing maps
• Generic coarse geometry of leaves
• Horocyclic products of trees
• Local finiteness, distinguishing numbers, and Tucker's conjecture
• On free products of graphs
• Quasi-isometric rigidity of solvable groups
• Random walks on Diestel-Leader graphs
• Symmetry breaking in graphs
• The distinguishing chromatic number
• Topological groups and infinite graphs

This page was built for publication: Coarse distinguishability of graphs with symmetric growth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013344)