A finitary structure theorem for vertex-transitive graphs of polynomial growth

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75) Random walks on graphs (05C81) Locally compact groups and their algebras (22D99)

Abstract: We prove a quantitative, finitary version of Trofimov's result that a connected, locally finite vertex-transitive graph G of polynomial growth admits a quotient with finite fibres on which the action of Aut(G) is virtually nilpotent with finite vertex stabilisers. We also present some applications. We show that a finite, connected vertex-transitive graph G of large diameter admits a quotient with fibres of small diameter on which the action of Aut(G) is virtually abelian with vertex stabilisers of bounded size. We also show that G has moderate growth in the sense of Diaconis and Saloff-Coste, which is known to imply that the mixing and relaxation times of the lazy random walk on G are quadratic in the diameter. These results extend results of Breuillard and the second author for finite Cayley graphs of large diameter. Finally, given a connected, locally finite vertex-transitive graph G exhibiting polynomial growth at a single, sufficiently large scale, we describe its growth at subsequent scales, extending a result of Tao and an earlier result of our own for Cayley graphs. In forthcoming work we will give further applications.

Review text

Editorial remark: Accidentally, this article has been issued twice for reviewing. Therefore, we display both reviews, by adding the second one to the originally published review: A graph is vertex-transitive if its automorphism group acts transitively on the vertices of the graph. A special, in some ways more tractable, class of vertex-transitive graphs are Cayley graphs, where a group \(G\) is generated by a set \(S\) of elements which has \(S=S^{-1}\) and \(1\not\in S\) and we then say the Cayley graph has vertex set \(G\) with \(x\) and \(y\) adjacent if and only if \(x=ys\) for some \(s\in S\), where the automorphism group includes \(G\) itself. The paper under review is about approximating vertex-transitive graphs by more general Cayley graphs.\par Given metric spaces \(X\) and \(Y\), a map \(f: X\to Y\) is said to be a \((C,K)\)- quasi-isometry if \(C^{-1}d_{X}(x,y)-K\equiv d_{Y}(f(x),f(y))\leq C d_{X}(x,y)+K\) for all \(x,y\in X\). Whilst examples constructed by \textit{R. Diestel} and \textit{I. Leader} [J. Algebr. Comb. 14, No. 1, 17--25 (2001; Zbl 0985.05020)] and verified by \textit{A. Eskin} et al. [Pure Appl. Math. Q. 3, No. 4, 927--947 (2007; Zbl 1167.22007)] show that not all vertex-transitive graphs are quasi-isometric (with respect to graph distance) to a Cayley graph. However, if the vertex-transitive graph has polynomial growth, meaning that, letting \(\beta_{\Gamma}(n)\) be the number of points in the ball of radius \(n\) around any point, we have \(\beta_{\Gamma}(n)\leq Cn^{d}\) for some constants \(C\), \(d\). \textit{V. I. Trofimov} [Mat. Sb., Nov. Ser. 123(165), No. 3, 407--421 (1984; Zbl 0548.05033)] showed that it can be. More precisely, he showed that a connected locally finite vertex-transitive graph of polynomial growth is quasi-isometric to a locally finite Cayley graph whose underlying group is virtually nilpotent (i.e. has a nilpotent subgroup of finite index). \par A simplified version of the main result of the paper under review, informed by an earlier result of \textit{E. Breuillard} et al. [Publ. Math., Inst. Hautes Étud. Sci. 116, 115--221 (2012; Zbl 1260.20062)], is that if \(K\geq 1\) is a constant then there is \(n_{0}(K)\) such that the following holds. If \(\Gamma\) is a locally finite connected vertex-transitive graph and if there exists \(n\geq n_{0}(K)\) for which \(\beta_{\Gamma}(3n) \leq K \beta_{\Gamma}(n)\), then \(\Gamma\) is \((1,O_K)(n))\)-quasi-isometric to a locally finite Cayley graph whose underlying group has a normal nilpotent subgroup of index at most \(O_{K}(1)\).\par Various applications are presented both in the paper under review and in promised forthcoming work of the authors, see e.g. [``Sharp relations between volume growth, isoperimetry and resistance in vertex-transitive graphs, Preprint, \url{arXiv:2001.01467}] and a further paper in preparation on Lie group approximations of balls with polynomial growth in vertex-transitive graphs. Reviewer: David B. Penman (Colchester) The principal result of the paper is this: For every \(K\le 1\) there exists \(n_0 = n_0 (K)\) such that the following holds. Let \(\Gamma\) be a connected, locally finite vertex-transitive graph, and suppose that there exists \(n\ge n_0\) such that \(\beta_{\Gamma} (3n) \le K\beta_{\Gamma}(n)\). Then \(\Gamma (3n)\) is \((1, O_K (n))\)-quasi-isometric to a locally finite Cayley graph whose underlying group has a nilpotent normal subgroup of rank, step and index at most \(O(1)\). Many Corollaries are given in the paper. \par The paper has a very explicit introductory part, which relates to various results in the nearer surrounding. Reviewer: Ulrich Knauer (Oldenburg)

Recommendations

Cites work

Cited in

(18)

This page was built for publication: A finitary structure theorem for vertex-transitive graphs of polynomial growth

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