Notes of Alina Vdovina’s Cambridge lecture 31-05-2017

Expanders, Beauville surfaces and buildings

1. Expanders

For a graph, Cheeger’s constant enters in the isoperimetric inequality

\displaystyle  \begin{array}{rcl}  \min\{|A|,|V\setminus A|\}\leq h\,|A|. \end{array}

Example. For a {n}-regular tree, {h=n-2}.

Definition 1 An expander is a sequence of finite bounded degree graphs whose Cheeger constants are bounded below.

I will stick to {p}-regular graphs.

1.1. Examples

In 1973, Pinsker showed that most {p}-regular graphs with enough vertices have Cheeger cobstant {h\geq 1/2}.

Margulis gave explicit examples of 8-regular expander graphs as Cayley graphs of finite groups.

Note that Cheeger constant is not very robust. Small changes affect it. Therefore direct computation is uneasy.

1.2. Spectral properties

Let {A} be the 0-1 adjacency matrix. If graph is {p}-regular, all its eigenvalues belong to {[-p,p]}, and {p=\lambda_1} is an eigenvalue. The second eigenvalue {\lambda_2<p} iff graph is connected.

The spectral gap is {p-\lambda_2}. Then a sequence of {p}-regular graphs is an expander iff the spectral gaps are bounded below (Dodziuk 1984, Alon-Milman 1985, Alon 1986).

2. New examples

Ramanujan graphs, zig-zag products, finite simple groups, Lubotzky-Samuels-Vishne, Sarveniazi: link to Euclidean buildings.

The following examples arise from group actions on buildings.

Theorem 2 (Peyerimhof-Vdovina) We give an explicit sequence {\Gamma_n=\langle x,y|r_1,r_2,r_3,[y,x,\ldots,x]\rangle} of finite groups whose Cayley graphs on {\{x,y\}} form an expander. The pro-2 completion {\Gamma_0} satisfies Golod-Shafarevitch’s inequality.

We give an explicit sequence {N_k} of finite {2}-groups and generators {\{x_k,y_k\}}, forming a tower, whose Cayley graphs on {\{x_k,y_k\}} form an expander.

2.1. The construction

Start with a group {\Gamma} with 7 generators and 7 relators, whose Cayley graph is the 1-skeleton of a thick {\tilde A_2} building whose links are projective planes over {F_2}. It appears first in Edjvet-Howie 1989 in the context of small cancellation.

2.2. SQ-universality of small cancellation groups

The star graph of a group presentation {\langle X|R\rangle} has vertex set {X\cup X^{-1}} and as many edges between {x} and {y} as words {w} such that {x^{-1}yw} is a cyclic conjugate of an element of {R\cup R^{-1}}.

The previous example has star graph the projective plane over {F_2}.

Say a presentation is {(m,k)}-special if relators have length {k} and its star graph is a generalized {m}-gon.

Question (Jim Howie 1989). Are groups with {(3,3)}-special presentations SQ-universal?

Martin Edjvet and I proved that the answer is negative. Indeed, we show that all of them act on {\tilde A_2} buildings, and apply Margulis’ finiteness theorem: all their quotients are finite (attributed to Shalom-Steger but unpublished for non-Bruhat-Tits buildings).

Nicolas Radu recently found a group with {(3,3)}-special presentation which acts on a building with non-classical links.

2.3. Back to construction

The subgroup {\Gamma_0} generated by the first two generators has index 2. It has a linear representation in {Gl(9,2)}. We turn them into finite band infinite Toeplitz matrices, getting elements in {Gl(9,F_2[1/y])}.

We conjecture that the lower exponent-2 central series of {\Gamma_0} givens rise to finite abelian quotients or orders 8,8,4,… periodically.

3. Beauville surfaces

A colleague in Newcastle once observed that a 256-element group arising in our construction also appeared in a paper by Bauer-Catanese-Grunewald on Beauville surfaces.

A Beauville surface is a complex algebraic surface of the form {(C_1\times C_2)/G} where {C_1} and {C_2} are non-singular projective curves of genera {\geq 2} and {G} a finite group acting freely and holomorphically.

Beauville’s original example consists of two Fermat curves of degree 5 with {G={\mathbb Z}/5{\mathbb Z}\times {\mathbb Z}/5{\mathbb Z}}. It is a fake {P^1\times P^1} (same numerical invariants).

Theorem 3 (Barker-Boston-Peyerimhoff-Vdovina) Consider the lower exponent-2 central series {(H_k)} of {\Gamma} (resp. of {\Gamma_0}). The quotients {\Gamma/H_k} induce Beauville surfaces if {k} is not a power of 2.

The Riemann surfaces form a tower of Belyi branched coverings (coverings of {P^1} branched over 3 points {a,b,c}). The etale covering over the punctured Riemann sphere is induced by the morphism

\displaystyle  \pi_1(P^1\setminus\{a,b,c\})\rightarrow\Gamma/H_k

mapping the three generators (with trivial product) to three generators of {\Gamma} (with trivial product).


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