Notes of Jason Behrstock’s Cambridge lecture 11-01-2017

Random graphs and applications to Coxeter groups

1. Random graphs

In the Erdös-Renyi model {\mathcal{G}(n,p)} each pair of vertices is connected by an edge independently with probability {p}. Typically, one fixes a function {p:{\mathbb N}\rightarrow(0,1)} and one wonders wether a property holds with prbability tending to 1 in {\mathcal{G}(n,p(n))}.

In 1959, Erdös and Renyi showed that a graph is asymptotically almost surely

  1. connected if {p(n)\geq(1+\epsilon)\frac{\log n}{n}},
  2. disconnected if {p(n)\leq(1-\epsilon)\frac{\log n}{n}}.

2. Divergence

Let {X} be a one-ended geodesic metric space. The divergence of a geodesic {g(t)} is the distance between {g(-r)} and {g(r)} in the complement of {B(g(0),r)}. The supremum over all geodesics is the divergence function of {X}. It is a quasi-isometry invariant.

It is useful for

  1. QI classification.
  2. Stability of quasi-geodesics.
  3. Quantification of hyperbolicity.
  4. Random walks.

2.1. Examples

Linear for Euclidean space.

Linear for any direct product. Among RACG, these are the only groups with linear divergence (Behrstock-Hagen-Sisto).

Linear for groups that satisfy a law (Drutu-Sapir).

Exponential for hyperbolic space.

Gromov asked wether for {CAT(0)} other behaviours may arise. Gersten soon found a counterexample. He determined the divergence of all 3-manifold groups: exponential, linear and quadratic.

Quadratic for MCG have quadratic divergence.

Quadratic for Teichmüller space.

Quadratic for Artin groups.

Probably quadratic for {Out(F_n)} (not quite known).

Every order of polynomial divergence occurs in some one-ended RACG (Dani-Thomas).

Weird infinitely presented examples have neither exp nor poly divergence (Sapir).

3. Right angled Coxeter groups

These are graph products of {{\mathbb Z}_2}‘s.

Group is finite iff graph is a clique.

Splits over a finite group iff there is a separating clique (Mihalik).

Direct product iff graph is a join.

Hyperbolic iff do induced square (Moussong).

3.1. How common are hyperbolic RACG’s ?

In {\mathcal{G}(n,p)}, the expected number of squares

Charney-Farber: if {p=o(\frac{1}{n})}, RACG is a.a.s. hyperbolic.

In other word, this is very rare.

4. Divergence of RACG’s

Theorem 1 (Behrstock-Hagen-Sisto) Any one-ended RCAG has at most polynomial divergence, or is hyperbolic w.r.t. a collection of subgroups with polynomial divergence (hence divergence is exponential). Decidable in poly time.

In fact, this holds more generally for graphs of groups (Genevoix).

Theorem 2 (Behrstock. at al.) If {p\gg \frac{1}{\sqrt{n}}}, a.a.s. RACG has quadratic divergence.

If {p\ll \frac{1}{\sqrt{n}}}, a.a.s. RACG has at least cubic divergence.

4.1. The square graph

One vertex for each square, an edge when two square share a diagonal. Say a graph is constructed from squares CFS, if some component of the square graph covers all vertices.

Theorem 3 (Levcovitz 2016) A RACG has quadratic divergence iff its presentation is CFS and not a join.

The hardest part is to show that divergence is at least quadratic.

Then we do combinatorics to get the probabilistic threshold.

The sharp threshold for relative hyperbolicity is unknown. We have a partial result.

5. Ongoing

Analyze the square graph in graphs extracted from neuroimaging, and detect functional properties of parts of the brain.


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 Workshop lecture 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