Random graphs and applications to Coxeter groups
1. Random graphs
In the Erdös-Renyi model each pair of vertices is connected by an edge independently with probability . Typically, one fixes a function and one wonders wether a property holds with prbability tending to 1 in .
In 1959, Erdös and Renyi showed that a graph is asymptotically almost surely
- connected if ,
- disconnected if .
Let be a one-ended geodesic metric space. The divergence of a geodesic is the distance between and in the complement of . The supremum over all geodesics is the divergence function of . It is a quasi-isometry invariant.
It is useful for
- QI classification.
- Stability of quasi-geodesics.
- Quantification of hyperbolicity.
- Random walks.
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 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 (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 ‘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 , the expected number of squares
Charney-Farber: if , 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 , a.a.s. RACG has quadratic divergence.
If , 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.
Analyze the square graph in graphs extracted from neuroimaging, and detect functional properties of parts of the brain.