Notes of John MacKay’s Cambridge lecture 06-04-2017

Poincare profiles of graphs and groups

Joint with David Hume and Romain Tessera.

We study Benjamini-Schramm-Timar’s separation profiles, which are monotone under coarse embeddings. It is the {p=1} case of something that can be defined for every {p\geq 1} and which is close to Poincare inequalities.

1. Separation

All graphs are bounded degree.

Definition 1 (Benjamini-Schramm-Timar) For a finite graph {\Gamma}, let

\displaystyle  \begin{array}{rcl}  cut(\Gamma)=\min\{|S|\,;\, S\textrm{ set of vertices such that all components of }\Gamma\setminus S\textrm{ have size }\leq \frac{1}{2}|\Gamma|\}. \end{array}

For an infinite graph {X}, the separation profile of {X} is a function {sep_X:{\mathbb N}\rightarrow{\mathbb N}} defined by

\displaystyle  \begin{array}{rcl}  sep_X(r)=\sup\{cut(\Gamma)\,;\,\Gamma\subset X,\,|\Gamma|\leq r\}. \end{array}

Examples. For a tree, {sep_X(r)=1}.

For {X={\mathbb Z}^2}, {sep_X(r)\simeq \sqrt{r}}.

1.1. Properties

If a map {F:X\rightarrow Y} is regular, meaning that it is Lipschitz and has fibers of bounded size, then {sep_X \leq sep_Y}.

In particular, {sep} is monotone under coarse embeddings, it is a quasisometry invariant. It makes sense for finitely generating groups, it is monotone under monomorphisms of groups.

Example (Lipton-Tarjan 1979). For a planar graph, {sep_X(r)\leq\sqrt{r}}.

Example. For {X={\mathbb Z}^d}, {sep_X(r)\simeq r^{(d-1)/d}}.

Example. For hyperbolic space {H^d},

\displaystyle  \begin{array}{rcl}  sep_X(r)&\simeq& r^{(d-2)/(d-1)}\quad \textrm{if }d\geq 3.\\ &\simeq&\log r\quad \textrm{if }d=2. \end{array}

Example. For a product of two trees, {sep_X(r)\simeq r/\log r}.

1.2. Link to Poincare inequality

The {\ell^1} Poincare constant of a finite graph.

\displaystyle  \begin{array}{rcl}  h^1(\Gamma)=\inf\{\frac{\|\nabla f\|_1}{\|f-f_\Gamma\|_1}\,;\,f:\Gamma\rightarrow{\mathbb R}\}. \end{array}

Then {h^1} defines an equivalent profile.

2. Poincare profile

For {p\geq 1}, define for finite graphs

\displaystyle  \begin{array}{rcl}  h^p(\Gamma)=\inf\{\frac{\|\nabla f\|_p}{\|f-f_\Gamma\|_p}\,;\,f:\Gamma\rightarrow{\mathbb R}\}. \end{array}

Then define the {p}-Poincare profile for infinite graphs by

\displaystyle  \begin{array}{rcl}  \Lambda^p_X(r)=\sup\{|\Gamma|h^p(\Gamma)\,;\,\Gamma\subset X,\,|\Gamma|\leq r\}. \end{array}

Again, it is monotone under regular maps, hence under coarse embeddings. It is a monotone function of {p}.

For {p=\infty}, it measures nothing but growth of balls.

Theorem 2 (Hume-MacKay-Tessera) If {G} is virtually nilpotent with polynomial growth of degree {d}, then

\displaystyle  \begin{array}{rcl}  \Lambda_X^p(n)\simeq n^{(d-1)/d} \end{array}

for all {p}.

3. Hyperbolic groups

3.1. Trees

Theorem 3 For trees, {\Lambda_X^p(r)\simeq r^{(p-1)/p}}, {\Lambda_X^\infty\simeq r/\log r}.

This amounts to a Poincare inequality. One uses a family of curves that spreads out uniformly.

Since any non-elementary hyperbolic group has embedded trees, {\Lambda_X^p(r)\geq r^{(p-1)/p}}. This sharp only for large {p}. The threshold where profile changes behaviour is an interesting feature of a hyperbolic group.

3.2. Hyperbolic spaces

Theorem 4 For {d}-dimensional real hyperbolic space,

\displaystyle  \begin{array}{rcl}  \Lambda_X^p(r)&\simeq& r^{(d-2)/(d-1)}\quad \textrm{ if }p<d-1,\\ &\simeq& r^{(p-1)/p}\log(r)^{1/p}\quad \textrm{ if }p=d-1,\\ &\simeq& r^{(p-1)/p}\quad \textrm{ if }p>d-1. \end{array}

For other rank one symmetric spaces, we get similar lower bounds (but no sharp upper bounds yet).

Lower bounds for {p\geq d-1} come from Poincare inequalities on balls, which in turn follow from Poincare inequalities on the ideal boundary. This rules out coarse embeddings between rank one symmetric spaces.

Upper bounds rely on Thurston et al.’s centerpoint method. One needs cut an arbitrary subset. Thurston provides a point such that every half-space passing through it cuts the subset in equal halves. Pick a random hyperplane through this point, it provides an appropriate cut.

3.3. Bourdon buildings

We have upper bounds for such buildings. It relies on Helly’s theorem, and wall structure. Indeed, consider halfspaces that contain at least 99% of the subset. Any subcollection of 100 of them intersect. A Helly type theorem implies that there is a common intersection. This provides us with a center point. Then pick a random wall containing it. For lower bounds, the Poincare inequality at infinity is due to Bourdon-Pajot.

Theorem 5 For Bourdon buildings {G_{s,t}} of conformal dimension {Q},

\displaystyle  \begin{array}{rcl}  \Lambda_X^p(r)&\simeq& r^{(Q-1)/Q}\quad \textrm{ if }p<Q,\\ &\simeq& r^{(p-1)/p}\log(r)^{1/p}\quad \textrm{ if }p=Q,\\ &\simeq& r^{(p-1)/p}\quad \textrm{ if }p>Q. \end{array}

This family of examples gives a dense set of exponents for polynomial separations.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in seminar and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s