Many ended graphs

Section 2.3 Many ended graphs

Our motivation: quasi isometric rigidity.

We say that two groups \(G_1,G_2\) are virually isomorphic if they contain finite index subgroups \(G_i' \stackrel{\mathrm{f.i.}}{\leq} G_i\) and such that there are finite normal subgroups \(K_i \triangleleft G_i'\) (\(i=1,2\)) such that:

\begin{equation*} G_1'/K_1 \approx G_2'/K_2. \end{equation*}

In the previous lecture, we saw that quasi isometry could not distinguish between virtually isomorphic groups. The question still remains: Can quasi isometry determine a group up to virtual isomorphism? The short answer is: no, not always.

The longer answer is sometimes, and even negative results in this matter tend to be non-trivial. The phenomenon where quasi isometry (purely geometric/metric) determines a group property up to virtual isomorphism (purely algebraic) is known as quasi isometric rigidity. Our goal for the next few lectures is will be to prove the simplest possible such result.

Theorem 2.3.1.

\(\ZZ\) is quasi isometrically rigid. That is to say if \(H\) is some group that is quasi isometric to \(\ZZ\) then \(H\) contains a finite index subgroup \(H' \stackrel{\mathrm{f.i.}}{\leq} H\) such that \(H' \approx \ZZ.\)

We first note that all non trivial subgroups of \(\ZZ\) are isomorphic, so there is no need to pass to finite index subgroups of \(\ZZ\text{.}\) The example below shows that there are infnite groups (called periodic groups) which do not contain subgroups isomorphic to \(\ZZ\text{.}\)

Example 2.3.2.

The Burnside Problem is related to this issue. Consider the group

\begin{equation*} \pres{a,b,c}{w^n;w\in F(a,b,c)} \end{equation*}

obtained by declaring every \(n^{\mathrm{th}}\) power to be trivial. For \(n=2,3,4,6\) this group is known to be finite. For \(n=10^{10}\) it is known to be infinite, for \(n=5\text{,}\) it is unknown. In particular, infinite Burnside groups (which exist) do not contain subgroups isomorphic to \(\ZZ\text{.}\)

In particular we will need to show that such a group \(H\) actually contains an infinite order element. The way we will achieve this is via group actions, and a quasi isometry invariant known as ends.

Subsection 2.3.1 Essential disconnecting sets and many endedness

In graph theory, a cutset is a minimal (w.r.t inclusion) set of edges whose removal disconnects a graph. Such sets of edges abound, for example the set of edges incident to a vertex contains a cutset. For infinite graphs we have something more interesting: a subset of a graph is an essential disconnecting set if its removal disconnets the graph into two infinite components. Of most interest to us will be finite essential disconnecting sets.

Example 2.3.3.

In an infinite tree, any finite subset is an essential disconnecting set.
The grid \(\cay{\{\BEmatrix{1\\0},\BEmatrix{0\\1}\}}{\ZZ^2}\) doesn't admit any finite essential disconnecting sets.

Before defining what an end is we have the following.

Definition 2.3.4.

We say a graph \(X\) is

zero ended if it is finite,
many ended if it admits a finite essential disconnecting set
one ended if it none of the above are satisfies, i.e. it is infinte but withuot an essential disconnecting set.

We say a finitely generated group \(G\) is zero, one, or many ended if it has a Cayley graph (w.r.t. a finite generating set) which is zero, one, or many ended, respectively.

We should pause to ponder whether this definition is even well-defined: Why couldn't a group have two Cayley graphs, one of which is one ended and the other one isn't?

Subsection 2.3.2 A digression about paths

At this point we want to provide a perspective on compact essential disconnecting sets that is compatible with quasi-isometry.

If \(X\) is a path connected space (e.g. a connected graph) then we already encountered the notion of a geodesic

\begin{equation*} p:[0,L] \to X. \end{equation*}

We can relax this notion to that of a quasi geodesic

\begin{equation*} q:[0,L] \to X \end{equation*}

where \(q\) is a \((K,C)\)-quasi isometric embedding (where we are equipping the interval \([0,L]\) with the standard metric of length on \(\RR\text{.}\)) Now \(q\) is not necessarily continuous and can do all kinds of strange things. However we can do the following:

Lemma 2.3.5.

Let \(q:[0,L] \to X\) be a \((K,C)\)-quasi geodesic, where \(L \in \ZZ_{>0}\text{,}\) and consider a path \(q_p:[0,L]\to X\) satisfying the following:

For \(i \in [0,L] \cap \ZZ\) \(q_p(i)=q(i)\)
On the open intervals \((i,i+1)\text{,}\) \(i=0,\ldots,L-1\) the restriction \(q_p|_{(i,i+1)}\) is a geodesic joining \(q_p(i)\) and \(q_p(i+1),\)

i.e. \(q_p\) is a piecewise geodesic.

Then for every \(z\in [0,L]\) we have

\begin{equation*} d_X(q(x),q_p(x))\leq 2(K+C). \end{equation*}

The concept of a geodesic path is a global notion, and is a bit too restrictive. The right notion we want is rectifiability, but that takes too much work to properly define and justify. If we restrict ourselves to the case where \(X\) is a graph, then we can make the following assumption: every path in \(X\) is a piecewise geodesic path, specifically it travels through every edge at constant unit speed. This way we can ignore analysis and focus on combinatorics.

Subsection 2.3.3 Many endedness as a quasi-isometry invariant

Now let us give a more metric characterization of a finite essential cut set.

Proposition 2.3.6.

A locally finite graph \(X\) admits a finite essential cutset if and only if there is:

some point \(x_0 \in V(X)\) and a fixed number \(D>0\text{,}\)
two sequences of vertices \((x_n),(y_n)\) with
\begin{equation*} \lim_{n\to \infty}d(x_n,y_n)=\lim_{n\to \infty} d(x_0,x_n) = \lim_{n\to \infty} d(x_0,y_n) = \infty, and \end{equation*}
the following property: every path \(p_n\) from \(x_n\) to \(y_n\) intersects the ball \(B(x_0,D).\)

In particular this result says that a finite essential disconnecting set is a "bottleneck in the graph".

Corollary 2.3.7.

If \(X\) and \(Y\) are quasi isometric graphs, then \(X\) is many ended if and only if \(Y\) is many ended.

In particuar, being 0, 1, or many ended is a quasi isometric invariant.

Exercises 2.3.4 Exercises

1.

Work out the two examples in Example 2.3.3. It's best to use pictures and to be informal.

2.

Prove Lemma 2.3.5

Hint: Use the triangle inequality, don't try to be optimal.

3.

Prove Proposition 2.3.6

4.

Use Proposition 2.3.6 to give a rigourous argument that \(\ZZ^2\) is one ended.

Hint: Fix some \(x_0,D\) take sequences \((x_n),(y_n)\) satisfying the requrements of and show how to construct \(B(x_0,D)\)-avoiding paths from \(x_n\) to \(y_n\text{,}\) provided \(n\) is sufficiently large.

5.

Prove Corollary 2.3.7

Hint: Let \(q:X\to Y\) be a \((K,C)\) quasi-isometry. The piecewise geodesic paths \(p:[0,L] \to X\) are sent via \(q \circ p\) to piecewise quasigeodesic paths, which can then be turned by Lemma 2.3.5 into piecewise geodesics which stay close to \(q\circ p\text{.}\) Assume that \(X\) is many-ended and \(Y\) is one ended and use Proposition 2.3.6 to derive a contradiction.