English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study graphs of polynomial growth from the perspective of asymptoticgeometry and descriptive set theory. The starting point of our investigation isa theorem of Krauthgamer and Lee who showed that every connected graph ofpolynomial growth admits an injective contraction mapping to $(\mathbb Z^n,\|\cdot\|_\infty)$ for some $n\in\mathbb N$. We strengthen and generalize thisresult in a number of ways. In particular, answering a question of Papasoglu,we construct coarse embeddings from graphs of polynomial growth to $\mathbbZ^n$. Moreover, we only require $n$ to be linear in the asymptotic polynomialgrowth rate of the graph; this confirms a conjecture of Levin and Linial,London, and Rabinovich "in the asymptotic sense." (The exact form of theconjecture was refuted by Krauthgamer and Lee.) All our results are proved forBorel graphs, which allows us to settle a number of problems in descriptivecombinatorics. Roughly, we prove that graphs generated by free Borel actions of$\mathbb Z^n$ are universal for the class of Borel graphs of polynomial growth.This provides a general method for extending results about $\mathbbZ^n$-actions to all Borel graphs of polynomial growth. For example, animmediate consequence of our main result is that all Borel graphs of polynomialgrowth are hyperfinite, which answers a well-known question in the area. Asanother illustration, we show that Borel graphs of polynomial growth support acertain combinatorial structure called toast. An important technical tool inour arguments is the notion of padded decomposition from computer science,which is closely related to the concept of asymptotic dimension due to Gromov.Along the way we find an alternative, probabilistic proof of a theorem ofPapasoglu that graphs of asymptotic polynomial growth rate $\rho<\infty$ haveasymptotic dimension at most $\rho$ and establish the same bound in the Borelsetting.

Large-scale geometry of Borel graphs of polynomial growth