(Random) Trees of Intermediate Volume Growth

EUROCOMB’23

George Kontogeorgiou Martin Winter

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-091

PDF
Abstract
For every sufficiently well-behaved function $g\:\mathbb{R}_{\ge 0}\to\mathbb{R}_{\ge 0}$ that grows at least linearly and at most exponentially we construct a tree $T$ of uniform volume growth $g$, that is, $$C_1\cdot g(r/4)\le |B_G(v,r)| \le C_2\cdot g(4r),\quad\text{for all $r\ge 0$ and $v\in V(T)$},$$ with $C_1,C_2>0$ and where $B_G(v,r)$ denotes the ball of radius $r$ centered at a vertex $v$. In particular, this yields examples of trees of uniform intermediate (\ie\ super-polynomial and sub-exponential) volume growth. We use this construction to provide first examples of unimodular random rooted trees of uniform intermediate growth, answering a question by Itai Benjamini. We find a peculiar change in structural properties for these trees at growth $r^{\log\log r}$. Our results can be applied to obtain triangulations of $\mathbb{R}^2$ with varied growth behaviours and a Riemannian metric on $\mathbb{R}^2$ for the same wide range of growth behaviors.

Pages:
659–668
References

Miklos Abert, Mikolaj Fraczyk and Ben Hayes. Co-spectral radius, equivalence relations and the growth of unimodular random rooted trees. arXiv:2205.06692, 2022.

Jan Ambj, Jan Ambjorn, Bergfinnur Durhuus, Thordur Jonsson, Orur Jonsson, et al.

Quantum geometry: a statistical field theory approach. Cambridge University Press, 1997.

Gideon Amir and Shangjie Yang. The branching number of intermediate growth trees. arXiv:2205.14238, 2022.

Omer Angel. Growth and percolation on the uniform infinite planar triangulation.

Geometric And Functional Analysis, 13(5):935--974, 2003.
https://doi.org/10.1007/s00039-003-0436-5

Laszlo Babai. The growth rate of vertex-transitive planar graphs. SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, pages 564--573, 1997.

Itai Benjamini and Oded Schramm. Recurrence of distributional limits of finite planar graphs. Selected Works of Oded Schramm, pages 533--545. Springer, 2011.
https://doi.org/10.1007/978-1-4419-9675-6_15

Rostislav Ivanovich Grigorchuck. Degrees of growth of finitely generated groups and the theory of invariant means. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 48(5):939--985, 1984.

Clara Loh. Geometric group theory. Springer, 2017.
https://doi.org/10.1007/978-3-319-72254-2

R. Lyons and D. Aldous. Processes on unimodular random networks. Electronic Journal of Probability, 12(54):1454--1508, 2007.
https://doi.org/10.1214/EJP.v12-463

Adam Timar. A stationary random graph of no growth rate. Annales de l'IHP Probabilites et statistiques, volume 50, pages 1161--1164, 2014.
https://doi.org/10.1214/13-AIHP563

Vladimir Ivanovich Trofimov. Graphs with polynomial growth.

Mathematics of the USSR-Sbornik, 51(2):405, 1985.
https://doi.org/10.1070/SM1985v051n02ABEH002866

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 George Kontogeorgiou, Martin Winter

PDF