×

A conjecture concerning a limit of non-Cayley graphs. (English) Zbl 0985.05020

Graphs \(G\) and \(H\) are quasi-isometric if there exist a function \(\theta:V(G)\to V(H)\) and constants \(C, D\geq 1\) such that for all \(x,y\in V(G)\) and all \(z\in V(H)\) the usual distance metrics in \(G\) and \(H\) satisfy: (1) \(d(\theta x,\theta y)\leq Cd(x,y)\); (2) \(d(x,y)\geq D\) implies \(d(\theta x,\theta y)\leq d(x,y)/C\); and (3) \(d(\theta[V(G)],z)\leq D\). Intuitively, \(G\) and \(H\) “look the same \(\ldots\) from far away.”
W. Woess [Discrete Math. 95, No. 1-3, 373-384 (1991; Zbl 0757.05060)] posed the question as to whether every vertex-transitive graph is quasi-isomorphic to some Cayley graph. The present authors construct a sequence of graphs “that seem to look less and less like Cayley graphs.” The sequence converges, in a certain sense, to a 5-valent, 1-ended graph which is conjectured to be a counterexample to Woess’ query.
Reviewer’s remark: The volume and paper number of the cited reference by W. Woess are incorrect in the article. The correct numbers appear in this review.

MSC:

05C12 Distance in graphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0757.05060
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Babai, “Vertex-transitive graphs and vertex-transitive maps,” J. Graph Theory15 (1991), 587-627. · Zbl 0743.05020
[2] Gromov, M.; Niblo, G. A. (ed.); Roller, M. A. (ed.), Asymptotic invariants of infinite groups (1993), Cambridge
[3] W. Magnus, A. Karrass, and D. Solitar, Combinatorial Group Theory, Dover, New York, 1976.
[4] P.M. Soardi and W. Woess, “Amenability, unimodularity, and the spectral radius of random walks on infinite graphs,” Math. Z.205 (1990), 471-486. · Zbl 0693.43001
[5] C. Thomassen and M.E. Watkins, “Infinite vertex-transitive, edge-transitive, non-1-transitive graphs,” Proc. Amer. Math. Soc.105 (1989), 258-261. · Zbl 0677.05042
[6] V.I. Trofimov, “Graphs with polynomial growth,” Math. USSR-Sb. 51 (1985), 405-417. · Zbl 0565.05035
[7] W. Woess, “Topological groups and infinite graphs,” Discrete Math.94 (1991), 1-12.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.