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

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)