## Posts Tagged ‘graph’

### Graph of groups in relation to 3-manifolds

October 24, 2011

(some images might appear soon)

Somehow I decided to wake up at 6:30 a.m. every Thursday to attend Bruce Kleiner‘s 9:30 course in NYU this semester. So far it’s been fun~

I learned about this thing called graph of groups. If you have been reading posts on this blog regarding any geometric group theory stuff (especially those posts related to Kleiner), then warning: this ‘graph’ has nothing to do with the Cayley graph. It’s not much about geometry but a rather ‘category-theoretical’ thing. Well, at this point you may think that you hate those algebra prople and is ready to leave…just don’t do that yet, because I hated them too, and now I finally got a tiny bit of understanding and appreciation on what those abstract non-sense was all about! :-P

So how do we connect cool 3-manifold stuff (incompressible surfaces, loops, embedded discs Heegaard splittings etc.) to groups?

Well, one handy thing is of course the Dehn’s lemma:

Theorem: For 3-manifold $M$ with boundary, if the inclusion map $i: \pi_1(\partial(M)) \rightarrow \pi_1(M)$ is not injective, then there exists a simple non-trivial loop in $\partial M$ bounding an embedded disc in $M$.

Note: Dehn’s theorem was proved by Papakyriakopoulos, I talked about it in this pervious post, although not exactly stated in this form, we can see that Dehn’s lemma follows easily from the loop theorem.

This means we can say things about the 3-manifold by only looking solely at maps between groups!

That’s cool, but sometimes we find groups and just one map between two groups are not enough, and that’s when graph of groups comes in:

Definition: A graph of groups is a graph with vertice set $V$, edge set $E$, to each vertex $v$ we associate a group $G_v$ and to each edge $e$ (say connecting $v_1, v_2$) we also associate a group $G_e$, together with a pair of injective homomorphisms $f_1: G_e \rightarrow G_{v_1}$, $f_2: G_e \rightarrow G_{v_2}$.

In our context, we should think of this as gluing together a bunch of spaces and take the fundamental group of those spaces, along with their pairwise intersections, as our vertice and edge groups. Just note that we need to have injections from the edge group to vertice groups. For simplicity one may first restrict oneself to the case where all edge groups are trivial (say spaces glued along contractible spaces).

There is something called the fundamental group of a graph of groups which is essentially the fundamental group of the resulting space after you glued spaces according to the given graph of groups. Note that the injection associated to edges takes into account how gluing of different pairs interact with each other (that is to say, for example, on a homotopy level it knows about triple intersections, etc.)

Let’s look at an application in this paper of Kleiner and Kapovich which I also talked about in an earlier post. Continue from that pervious post, now we know that

Theorem: Any hyperbolic group (plus obvious conditions, namely torsion free and does not split over a finite cyclic group) with 1-dimensional boundary has $\partial_\infty G$ homeomorphic to $\mathbb{S}^1$, the Sierpinski carpet or the Menger curve.

When $\partial_\infty G = \mathbb{S}^1$, my wonderful advisor Dave Gabai proved that $G$ would act discrete and cocompactly on $\mathbb{H}^2$ by isometries. (i.e. it’s almost the fundamental group of some hyperbolic surface except for possible finite order elements which make the action not properly discontinuous.)

Now the next step is of course figuring out when does groups act on $\mathbb{H}^3$, we have:

Cannon’s conjecture: If hyperbolic group $G$ has boundary $\mathbb{S}^2$, then $G$ acts discretely and cocompactly on $\mathbb{H}^3$ by isometries.

This conjecture was also mentioned another pervious post. Turns our we do not know much about groups with $\mathbb{S}^2$ boundary. However, using graph of groups, they were able to show:

Theorem: If Cannon’s conjecture is true, then those hyperbolic groups with Sierpinski carpet boundary are fundamental groups of hyperbolic 3-manifolds with totally geodesic boundary.

i.e. the idea is to ‘extend’ the group with Sierpinski carpet boundary to a group having sphere boundary. Of course as sets we can embed the carpet into a sphere and start to ‘reflect it along the boundary of the ‘holes’, continue the process and eventually the union of all copies of the carpets is the entire $\mathbb{S}^2$. The problem is how to ‘reflect’ a group?

First, since the boundary is homeomorphic to the carpet, there are countably many well-defined ‘boundary circles’, the group $G$ acts on the set of boundary circles. They showed this action has only finitely many different orbits. (those orbits of boundary circles will eventually correspond to those totally geodesic boundary components of our resulting 3-manifold). We pick one boundary circle from each orbit and denote their stabilizers $H_1, \cdots, H_k$ each $H_i < G$.

Define a graph of groups $\mathcal{G}$ with two vertices both labeled $G$, with $k$ edges, all going from one vertex to the other. Let the edge groups be $H_1, \cdots, H_k$.

Now we can start to 'unfold' the graph： Let $X_G$ be a 2-complex associated to a set of generators and relations for $G$ and $X_i$ be 2-complexes associated to $H_i$. The inclusion map induces cellular maps $h_i: X_i \rightarrow X_G$. Hence we have

$\displaystyle h: \sqcup_{i=1}^n X_i \rightarrow X_G$

Let $X$ be the mapping cylinder of $h$. i.e. $X$ has boundary components $\sqcup_{i=1}^n X_i$ and $X_G$.

Let $DX$ be the complex obtained by gluing together two copies of $X$ along $\sqcup_{i=1}^n X_i$, take it’s universal cover $\widetilde{DX}$. Now the fundemental group $\hat{G}$ of $DX$ is, in some sense, the group obtained by doubling $G$ along each $H_i$. i.e. $\hat{G}$ is the fundamental group of the graph graph of groups $\mathcal{G}$.

Now by studying the 1-skeleton of the complex $\widetilde{DX}$, one is able to conclude that $\hat{G}$ is Gromov hyperbolic with $\mathbb{S}^2$ boundary, as expected.

Hence from groups with Sierpinski carpet boundary we are able to produce groups with sphere boundary. Now if Cannon’s conjecture is true, $\hat{G}$ is fundamental group of some hyperbolic 3-manifold, together with Gabai’s result that $H_i$ are fundamental groups of hyperbolic surfaces, we would have that $G$ is the fundamental group of a hyperbolic 3-manifold with $n$ totally geodesic boundary components.

Well, since now we don’t have Cannon’s conjecture, there is still something we can conclude:

Definition: A n-dimensional Poincare duality group is a group which has group cohomology satisfying n-dimensional Poincare duality.

Those should be thought of as fundamental groups of manifolds in the level of homology. Well, I know nothing about group cohomologies, luckily we have:

Theorem: (Bestvina-Mess)

$\Gamma$ is a n-dimensional Poincare duality group iff it’s torsion free and $\partial \Gamma$ has integral Cech cohomology of $\mathbb{S}^{n-1}$

Great! In our case $\partial \hat{G}$ IS the sphere! So it’s a 3-dimensional Poincare duality group~ Now we have a splitting of $\hat{G}$ over a bunch of 2-dimensional Poincare duality groups (namely $H_i$) it follows that $(G; H_1, \cdots, H_n)$ is a Poincare duality pair.

It is not known whether all such pairs can be realized as fundamental groups of 3-manifolds with boundary. If so, then by Thurston’s geometrization we can also obtain what we derived assuming Cannon’s conjecture.

### Kissing numbers of sphere packings

September 26, 2011

Enough of the ‘trying to understand recent big theorems’ on this blog, let’s do something light and fun this week!

As I was browsing the ArXiv one day, one thing led to anther and I eventually arrived in a very short and cute paper of Greg Kuperberg and Oded Schramm.

So, we have sphere packings, which is simply a bunch of spheres (say in $\mathbb{R}^3$) with disjoint interiors, some of them might be tangent to others, in which case we say the two sphere ‘kiss‘, like this: (points of tangency are marked with a red cross)

We can associate a graph to a sphere packing with vertices representing spheres and join two vertices with an edge if two sphere kisses:

Question: What kind of graph can appear this way?

Now if we go back to two-dimensions, it’s a classical theorem that any planar graph can appear as the nerve of a circle packing. (In fact, as mentioned at the end of this earlier post, something much stronger is true. i.e. it’s a theorem of Schramm that one can ‘kiss’ pretty much any given set of planar objects with a given nerve.)

In light of this, it’s nature to wonder whether every graph can be realized as a nerve of some sphere packing (since all graph embeds in some oriented surface which then embeds in $\mathbb{R}^3$). Turns out, no.

However I would imagine it’s not easy to show things such as a given graph cannot be realized. In the paper they came up with what’s perhaps the first restriction that shows not all graphs can be realized in such packing, namely:

The average kissing number is, as one might expect, in average how many kisses does each sphere get, i.e.

2 * number of tangency points / number of balls $= 2|E|/|V|$

If one thinks about it, how might one attempt to construct a packing with super large average kissing number? Well, perhaps we start with a single sphere, put a huge amount of small spheres around it (because one cannot fit many large spheres), then this middle one does get a lot of kisses, but what about the smaller ones? If they are equal sized then all the small spheres only gets roughly 7 kisses…now we need to put even smaller spheres around each of those…If we stop at any stage, there would be more smallers spheres that’s not taken care of than the larger ones with lots of kisses, so it’s not clear at all if the average can blow up.

As usual, things are much simpler in two dimensions: Since the Euler characteristic of any planar graph is 2 ($|V|+|F|-|E|=2$), and $|F| \leq 2|E|/3$ (any face needs at least 3 edges around them, precisely two faces share an edge) we have

$|V| \geq |E|/3+2$, hence $2|E|/|V| \leq 6 - 12/|V|$ < $6$

On the other hand, for our all-time favorite hexagonal packing of congruent circles, if we take more and more layers, the number of balls with six kisses grow like $n^2$, the number of balls on the boundary (hence with less than six kisses) is like $n$. Hence by adding enough layers we can make the average as close to 6 as we want~

Hexagonals are the best, as expected~

Now comes what’s in the paper: they showed that for any sphere packing, the average kissing number is less than $8+4\sqrt{3}$. Hence any graph with average degree larger than 15 cannot be realized. They also provided an example of sphere packings with average kissing number larger than 12.

For simplicity I’ll only reproduce the ‘warm-up case’ in the paper which proves the kissing number is no more than 24. (well, since our goal here is only to say that not all graphs can be realized.) I find this observation (due to Schramm) is very simple, cute, and works in any dimensions.

Let’s first define some numbers:

$k_c(n) =$ the maximum number of congruent sphere kissing one sphere (i.e. how many unit spheres we can place around a unit sphere) $k_c$ can be easily computed, for example $k_c(2) = 6$ and $k_c(3)=12$, etc.

Let $k(n) = \sup \{$ average kissing number of sphere packings in dimension $n \}$. As we have seen $k(2) = k_c(2) = 6$ and we are interested in giving upper bounds to $k(3)$.

Theorem: $k(n) \leq 2 k_c(n)$.

Given a sphere packing $P$, let $E$ be the set of kissing pairs and $V$ be the set of spheres.

Define map $f: E \rightarrow V$ where $f$ maps each pair to the sphere in the pair with smaller radius (if the two spheres has the same radius, then just randomly choose one).

Since each sphere can only be surrounded by $k_c(n)$ spheres of its size (of course larger than its size would give us fewer), we conclude that $f$ is at most $k_c$ to $1$. Therefore, we have

$|E| \leq k_c(n) |V|$, i.e. $k = 2|E|/|V| \leq 2k_c(n)$

How simple!

Now going from 24 to $8+4\sqrt{3}$ requires some estimates relying on us being in 3-dimensions. Essentially, given any sphere in the packing, if we enlarge it by a ratio $\lambda$ w.r.t its center, then this ‘shell’ intersect some other spheres in disjoint circles. Those circles of course cuts out a fraction of the area that’s < 1 on the shell. Summing this fraction over all $\lambda$ shells results a number that’s less than $|V|$.

Now if we look at each pair of balls, say take pair (V_1, V_2), it turns out that if they kiss, the fraction of shell around $V_1$ that’s cut out by $V_2$ plus the fraction of shell around $V_2$ cut out by $V_1$ is a constant depending only on $\lambda$.

Hence we get a relation $|V| \geq c(\lambda) \times |E|$. Choose an optimum $\lambda$ gives $8+4 \sqrt{3}$ which is a bit less than 15.

So we know $k(3) \leq 8+4 \sqrt{3}$ but larger than 12, the problem of finding the exact value of $k(3)$ remains open, so is the problem of giving other restrictions on the graph for being the nerve of a sphere packing.