Coarse distinguishability of graphs with symmetric growth

DOI10.26493/1855-3974.2354.616zbMATH Open1479.05088arXiv2005.09716OpenAlexW3154163285MaRDI QIDQ5013344FDOQ5013344

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)

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$.

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

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

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)

Cites Work

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

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)