On Local Expansion of Vertex-Transitive Graphs

DOI10.1017/S096354839800340XMaRDI QIDQ4212884zbMATH OpenFDO

Authors András Lukács

Publication date 11 February 1999

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S096354839800340X

zbMATH Keywords

almost Cayley graphsautomorphism groupsdiameterexpansion ratevertex transitive

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Review text

A locally finite, vertex transitive graph \(X\) has subexponential growth if \[ \lim_{n \rightarrow \infty} \log\biggl(\frac{| B(n)| }{n}\biggr)= 0, \] where \(B(n)\) denotes a ball of radius \(n\). Let \(V(X)\) denote the vertex set of \(X\), let \(S \subseteq V(X)\), and let \(\delta(S)\) denote the vertex boundary, i.e. the set of vertices adjacent to vertices in \(S\) which are not contained in \(S\). The expansion rate is defined as \(| \delta(S)| /| S| \) for finite non-empty \(S\). The \textit{L. Babai} and \textit{M. Szegedy} bound [see Comb. Probab. Comput. 1, No. 1, 1-11 (1992; Zbl 0792.05064)] on the expansion rate of infinite locally finite vertex transitive graphs with subexponential growth in terms of the diameter \(d(S)\) is improved here to \(| \delta S| /| S| \geq 2/(d(S) + 1)\) (by counting geodesics that are much larger than the diameter). Equality holds if \(X\) is the infinite path, so the new bound is tight. If \(X\) is an almost Cayley graph the assumption that \(X\) has subexponential growth may be dropped.

Recommendations

• A characterization of locally finite vertex-transitive graphs
• Local expansions on graphs and order of a point
• scientific article; zbMATH DE number 3851987
• Locally \(s\)-transitive graphs
• scientific article; zbMATH DE number 4077280
• scientific article; zbMATH DE number 524155
• Local Expansion of Symmetrical Graphs
• Locally finite, planar, edge-transitive graphs
• On the Complexity of Local Graph Transformations
• Some local-global phenomena in locally finite graphs

Cited in

(10)

• A characterization of locally finite vertex-transitive graphs
• Transitivity of local complementation and switching on graphs.
• Lattices in graphs with polynomial growth
• On small separations in Cayley and vertex transitive graphs
• Small separations in vertex-transitive graphs
• Local Expansion of Symmetrical Graphs
• scientific article; zbMATH DE number 2152972 (Why is no real title available?)
• Finite Voronoi decompositions of infinite vertex transitive graphs
• Expanders via local edge flips in quasilinear time
• Note on locality of volume growth rate of graphs

This page was built for publication: On Local Expansion of Vertex-Transitive Graphs

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