On a small cancellation theorem of Gromov
Yann Ollivier
We give a combinatorial proof of a theorem of Gromov, which extends the scope of small cancellation theory to group presentations arising from labelled graphs.
scgraph.tex
\documentclass[12pt,a4paper]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amssymb,amsmath}


%\addtolength{\headsep}{}
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}

\newcommand{\thmheadercommand}[1]{\textbf{\scshape{}#1}}


\def\d{{\mathrm{d}}}
\def\N{{\mathbb{N}}}
\def\Z{{\mathbb{Z}}}
\def\Nstar{{\mathbb{N}^\star}}
\def\Q{{\mathbb{Q}}}
\def\R{{\mathbb{R}}}
\def\C{{\mathbb{C}}}

\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}

\renewcommand{\emptyset}{\varnothing}

\def\eps{\varepsilon}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\phi}{\varphi}

\def\ds{\displaystyle}

\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\diam}{diam}

\DeclareMathOperator{\lap}{\Delta\!}
\DeclareMathOperator{\nab}{\nabla\!\!}

\DeclareMathOperator{\mult}{mult}
\DeclareMathOperator{\Card}{Card}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Epi}{Epi}
\DeclareMathOperator{\Spec}{Sp}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\Img}{Im}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\id}{id}

\newcommand{\abs}[1]{\left|\mskip1mu#1\right|}
\newcommand{\norm}[1]{\left\|#1\right\|}

\newcommand{\ilim}[1]{\underset{#1}{\underrightarrow{\lim\vspace{.5ex}}}\,}
\newcommand{\plim}[1]{\underset{#1}{\underleftarrow{\lim\vspace{.5ex}}}\,}

\DeclareMathOperator*{\vlimsup}{\varlimsup}
\DeclareMathOperator*{\vliminf}{\varliminf}

\newcommand{\presgroup}[2]{\left\langle\,#1 \mid  #2\,\right\rangle}


\newcounter{prop}
\newcounter{defi}
\newcounter{thm}
\newcounter{lem}

\newenvironment{dem}[1][]{\noindent{\thmheadercommand{Proof#1}}\,\,--\,\,}{$\square$\medskip}

\newenvironment{enonce}[1]{\medskip\noindent{\thmheadercommand{#1}}\,\,--\,\,\begin{slshape}}{\end{slshape}\medskip}

\newenvironment{enonce2}[1]{\medskip\noindent{\thmheadercommand{#1}}\,\,--\,\,}{\medskip}

\newenvironment{defi}[1][]{\refstepcounter{prop}
\begin{enonce}{Definition \theprop{}#1}}{\end{enonce}}
\newenvironment{prop}[1][]{\refstepcounter{prop}
\begin{enonce}{Proposition \theprop{}#1}}{\end{enonce}}
\newenvironment{thm}[1][]{\refstepcounter{prop}
\begin{enonce}{Theorem \theprop{}#1}}{\end{enonce}}
\newenvironment{lem}[1][]{\refstepcounter{prop}
\begin{enonce}{Lemma \theprop{}#1}}{\end{enonce}}
\newenvironment{cor}[1][]{\refstepcounter{prop}
\begin{enonce}{Corollary \theprop{}#1}}{\end{enonce}}

\newenvironment{defi*}[1][]{
\begin{enonce}{Definition#1}}{\end{enonce}}
\newenvironment{prop*}[1][]{
\begin{enonce}{Proposition#1}}{\end{enonce}}
\newenvironment{thm*}[1][]{
\begin{enonce}{Theorem#1}}{\end{enonce}}
\newenvironment{lem*}[1][]{
\begin{enonce}{Lemma#1}}{\end{enonce}}
\newenvironment{cor*}[1][]{
\begin{enonce}{Corollary#1}}{\end{enonce}}

\newenvironment{ex}[1][]{\begin{enonce}{Example#1}}{\end{enonce}}
\newenvironment{exs}[1][]{\begin{enonce}{Examples#1}}{\end{enonce}}

\newenvironment{exo}[1][]{\begin{enonce}{Exercise#1}}{\end{enonce}}
\newenvironment{exos}[1][]{\begin{enonce}{Exercises#1}}{\end{enonce}}

\newenvironment{rem}[1][]{\refstepcounter{prop}
\medskip\noindent{\thmheadercommand{Remark \theprop{}#1}}\,\,--\,\,}{\medskip}

\newenvironment{rem*}[1][]{\medskip\noindent{\thmheadercommand{Remark#1}}\,\,--\,\,}{\medskip}

\newcommand{\bin}[2]{\tbinom{#1}{#2}}

\usepackage{graphicx}

\def\d{\partial}

\title {On a small cancellation theorem of Gromov}

\author{Yann Ollivier}

\date{}

\begin{document}

\maketitle

\begin{abstract}
We give a combinatorial proof of a theorem of Gromov, which extends the
scope of small cancellation theory to group presentations arising from
labelled graphs.
\end{abstract}

In this paper we present a combinatorial proof of a small cancellation
theorem stated by M.~Gromov in~\cite{Gro2}, which strongly generalizes the
usual tool of small cancellation. Our aim is to complete the
six-line-long proof given in~\cite{Gro2} (which invokes geometric
arguments).

Small cancellation theory  is an easy-to-apply tool of combinatorial
group theory (see~\cite{Sch} for an old but nicely written introduction,
or~\cite{GH} and~\cite{LS}). In one of its forms, it basically asserts
that if we face a group presentation in which no two relators share a
common subword of length greater than $1/6$ of their length, then the
group so defined is hyperbolic (in the sense of~\cite{Gro1},
see also~\cite{GH} or~\cite{Sh} for basic properties), and infinite
except for some trivial cases.

The theorem extends these conclusions to much more general situations.
Suppose that we are given a finite graph whose edges are labelled by
generators of the free group $F_m$ and their inverses (in a reduced way,
see technical definition below). If no word of length greater than $1/6$
times the length of the smallest loop of the graph appears on the graph,
then the presentation obtained by taking as relations all the words read
on all loops of the graph defines an hyperbolic group which (if the rank
of the graph is at least $m+1$, to avoid trivial cases) is infinite.
Moreover, the given graph naturally embeds isometrically into the Cayley
graph.

The new theorem reduces to the classical one when the graph is a bouquet
of circles.  Noticeably, this criterion is as easy to use as the standard
one.

For example, ordinary small cancellation theory cannot deal with such
simple group presentations as $\presgroup{S}{w_1=w_2=w_3}$ because the
two relators involved here, $w_1w_2^{-1}$ and $w_1w_3^{-1}$, share a long
common subword. The new theorem can handle such situations: for
``arbitrary enough'' words $w_1,w_2,w_3$, such presentations will define
infinite, hyperbolic groups, although from the classical point of view
these presentations satisfy a priori only the $C'(1/2)$ condition from
which nothing could be deduced.

\bigskip

Most importantly, this technique allows to (quasi-)embed prescribed
gra\-phs into the Cayley graphs of hyperbolic groups. It is the basic
construction involved in the announcement of a counter-example to the
Baum-Connes conjecture with coefficients (see~\cite{HLS} which elaborates
on~\cite{Gro2}, or~\cite{Gh} for a survey).  Indeed, this counter-example is
obtained by constructing a finitely generated group (which is a limit of
hyperbolic groups) whose Cayley graph quasi-isometrically contains a
family of expanders.

\section{Statement and discussion}

Let $S$ be a finite set which is the disjoint union of two sets $S'$ and
$S''$, with a bijection from $S'$ to $S''$ called \emph{being inverse}.
The elements of $S$ are called \emph{letters}.

A \emph{word} is a finite sequence of letters. The inverse of a
word is the word made of the inverse letters put in reverse order.

A word is called \emph{reduced} if it does not contain a letter
immediately followed by its inverse.

A \emph{labelled complex} is a finite unoriented $2$-complex in which
each oriented edge bears a letter, such that opposite edges bear inverse
letters. (Each unoriented edge is considered as a couple of two oriented
edges.) Thus each face defines a word (up to inversion and cyclic
permutation) read on its boundary.  We require a map of labelled
complexes to preserve labels (but it may change orientation of faces,
sending a face to a face with inverse boundary label --- this amounts to
considering maps between the corresponding oriented complexes).


A \emph{labelled graph} is a $1$-dimensional labelled complex.

A labelled complex is said to be \emph{reduced} if there is no pair of
oriented edges arising from the same vertex and bearing the same letter.

Note that a word can be seen as a (linear) labelled graph, which we will
implicitly do from now on. The word is reduced if and only if the labelled
graph is.

A \emph{doublet} of a labelled complex is a word which has two different
immersions in the labelled complex. (An immersion is a locally injective
map of labelled complexes. Two immersions are considered different if
they are different as maps of $2$-complexes.) This is analogue to the
traditionnal ``piece'' of small cancellation theory.

A \emph{standard family of cycles} for a graph is a set of paths
in the graph, generating the fundamental group, such that there exists a
maximal subtree of the graph such that, when the subtree is contracted to
a point (so that the graph becomes a bouquet of circles), the set of
generating cycles is exactly the set of these circles. There always
exists some.

We are now in a position to state the theorem.

\begin{thm}[ (M.~Gromov)]
Let $\Gamma$ be a reduced labelled graph. Let $R$ be the set of words read on
all cycles of $\Gamma$ (or on a generating family of cycles). Let $g$ be the girth of $\Gamma$ and $\Lambda$ be the
length of the longest doublet of $\Gamma$.

If $\Lambda<g/6$ then the presentation $\presgroup{S}{R}$ defines a
group $G$ enjoying the following properties.
\begin{enumerate}
\item It is hyperbolic, torsion-free.
\item If the rank of the fundamental group of $\Gamma$ is greater than
the number of generators, $G$ is infinite and not quasi-isometric to
$\mathbb{Z}$.
\item Any presentation of $G$ by the words read on a standard family of
cycles of $\Gamma$ is aspherical (hence the cohomological dimension
of $G$ is at most $2$).
\item The shortest relation in $G$ is of length $g$.
\item For any reduced word $w$ equal to $e$ in $G$, some cyclic
permutation of $w$ contains a subword of a word read on a cycle of $\Gamma$, of length
at least $(1-3\Lambda/g)>\frac12$ times the length of this cycle.
\item The natural map from the labelled graph $\Gamma$ into the
Cayley graph of $G$ is an isometric embedding.
\end{enumerate}
\end{thm}

If $\Gamma$ is a disjoint union of circles, this theorem almost reduces
to ordinary $1/6$ small cancellation theory. The ``almost'' accounts for
the fact that the length of a shared doublet between two relators is
supposed to be less than $1/6$ the length of the smallest of the two
relators in ordinary small cancellation theory, and less than $1/6$ the
length of the smallest of all relators in our case. But it is clear from
the proof below that the assumption in the theorem can be replaced by the
following slightly weaker one: for each doublet, its length is less than
$1/6$ the minimal length of the cycles of the graph on which the doublet
appears. With this assumption, the theorem reduces to
ordinary small cancellation when the graph is a disjoint union of
circles.

The group obtained is not always non-elementary: for example, if there
are three generators $a,b,c$ and the graph consists in two points joined
by three edges bearing $a$, $b$ and $c$ respectively, one obtains the
presentation $\presgroup{a,b,c}{a=b=c}$ which defines $\Z$.
However, since the cohomological dimension is at most $2$, it is easy to
check (computing the Euler characteristic) that if the rank of the
fundamental group of $\Gamma$ is greater than the number of generators, then
$G$ is non-elementary.

\medskip

This theorem is not stated explicitly in~\cite{Gro2} in the form we give but
using a much more abstract formalism of ``rotation families of groups''.
In the vocabulary thereof, the case presented here is when this rotation
family contains only one subgroup of the free group (and its conjugates),
namely the one generated by the words read on cycles of the graph with
some base point; the
corresponding ``invariant line'' $U$ is the universal cover of the
labelled graph $\Gamma$ (viewed embedded in the Cayley graph of the free
group). Reducedness of the labelling ensures quasi-convexity.

In~\cite{Gro2}, this theorem is applied to a random labelling (or rather a
variant of this theorem given below, in which reducedness is replaced
with quasi-geodesi\-city). It is not difficult, using for example the
techniques described in~\cite{Oll}, to check that a random labelling
satifies the small cancellation and quasi-geodesi\-city assumptions.

\section{Proof}

We now give some more definitions which are useful for the proof.

A \emph{tile} is a planar labelled complex with only one face and no other edge
than the boundary edges of this face (but not necessarily simply
connected).  By our definition of maps between labelled complexes, a tile
is considered equal to the tile bearing the inverse word.

{
\footnotesize
Convention: A tile may bear a word which is not simple
(i.e.\ is a power of a smaller word). In this case the tile has a
non-trivial automorphism. Say that on each boundary component of a tile
we mark a starting point and that a map between tiles has to preserve marked
points. This is useful for the study of torsion because with this
convention asphericity of a presentation implies torsion-freeness and
asphericity of the Cayley complex. Note that our definition
of asphericity is thus slightly stronger than the one in~\cite{LS}.

}

The \emph{length} of a tile is the length of its boundary.

A \emph{tile of a labelled complex} is any of its faces.

A \emph{doublet} with respect to a set of tiles is a word which has
immersions in the boundary two different tiles, or two distinct
immersions in the boundary of one tile.

A \emph{puzzle} with respect to a set of tiles is a planar
labelled complex all tiles of which belong to this set of
tiles (the same tile may appear several times in a puzzle).

A puzzle is said to be \emph{minimal} if it has the minimal number of
tiles for a given boundary word.

A puzzle is said to be \emph{van Kampen-reduced} if there is no pair of
adjacent faces such that the words read on the boundary of these two
faces are inverse and the position (with respect to the marked point) of
the letter read at a common edge of these faces is the same in the two
copies of the boundary word of these faces  (in other words, there is no
trivial gluing). This corresponds to reduced van Kampen diagrams
(see~\cite{LS}).
(Incidentally, a reduced puzzle is van Kampen-reduced, though the converse is
not necessarily true.)


\begin{dem}[  of the theorem]
Let $\Gamma$ be a reduced labelled graph. $\Gamma$ defines a presentation
$R$ by taking all the words read along its cycles. The group presented by
$\presgroup{S}{R}$ will be the same if we take not all cycles but only
a generating set of cycles.

Note that the assumption on doublets implies that no two distinct cycles
of $\Gamma$ bear the same word. We will implicitly use this fact below
for unicity of lifts to $\Gamma$.

The fundamental group of the graph $\Gamma$ is a free group. Let
$\mathcal{C}$ be a finite generating set of $\pi_1(\Gamma)$ (maybe not
standard). Let $R$ be the set of words read on the cycles in
$\mathcal{C}$.

Add $2$-faces to $\Gamma$ in the following way: for each cycle in
$\mathcal{C}$, glue a disk bordering this cycle.

Note $\Gamma$ again this $2$-complex.  As the cycles in $\mathcal{C}$
generate all cycles, $\Gamma$ is simply connected.
If $\mathcal{C}$ is taken standard, $\Gamma$ has no homotopy in degree
$2$.
%As the fundamental
%group of a graph is free, if $\mathcal{C}$ is taken of minimal size
%(hence free), $\Gamma$ has no homotopy in degree $2$.

\bigskip

Let $D$ be a simply connected puzzle with respect to the tiles of
$\Gamma$. We are going to show that there exists a constant $C>0$ such
that for any $D$, if $D$ is van Kampen-reduced, then $D$ satisfies a linear
isoperimetric inequality $\abs{\d D}\geq C\abs{D}$ where $\abs{\d D}$ is
the boundary length of $D$ and $\abs{D}$ is the number of faces of $D$.
This implies hyperbolicity (see for example~\cite{Sh}).

We can safely assume that all edges of $D$ lie on some face (there are no
``filaments'').  Indeed, filaments only improve isoperimetry.
Generally speaking, in what follows we will never mention the possible
occurrence of filaments, their treatment being immediate. In particular,
we suppose that all vertices of $\Gamma$ are adjacent to at least two
edges (or, equivalently, that any edge is adjacent to some face).

Let $e$ be an internal edge of $D$, between faces $f_1$ and $f_2$. As $D$ is a
puzzle over the tiles of $\Gamma$, there are faces $f'_1$ and $f'_2$ of
$\Gamma$ bearing the same boundary word as $f_1$ and $f_2$ respectively
(maybe up to inversion).  (Note that these faces are unique, since
no two faces of $\Gamma$ can bear the same word as it would contradict
the $1/6$ condition on doublets.)

The edge $e$ belongs to $f_1$ and $f_2$ and thus can be lifted in
$\Gamma$ either in $f'_1$ or in $f'_2$. Say $e$ is an \emph{edge
originating from $\Gamma$} if these two lifts coincide, so that in
$\Gamma$, the two faces at play are adjacent along the same edge as they
are in $D$.

Any labelled complex with respect to the tiles of $\Gamma$, all edges of
which originate from $\Gamma$, can thus be lifted to $\Gamma$ by lifting
each of its edges.

Note that $D$ is van Kampen-reduced if and only if there is no edge $e$
originating from $\Gamma$ and adjacent to faces $f_1$, $f_2$ such that
$f'_1=f'_2$.

\bigskip

We work by first proving the isoperimetric inequality for puzzles having all
edges originating from $\Gamma$. Second, we will decompose the graph $D$
into parts having all their edges originating from $\Gamma$ and show that
these parts are in $1/6$ small cancellation with each other. Then we will
use ordinary small cancellation theory to conclude.

We begin by proving what we want for some particular choice of $R$.

\begin{lem}\label{lemmain}
Let $\Delta=\diam(\Gamma)$. Suppose that $R$ was chosen to be the set of words read on
closed paths embedded in $\Gamma$ of length at most $3\Delta$. Then, for
any closed path in $\Gamma$ labelling a reduced word $w$, there exists a
simply connected puzzle with boundary word $w$, with tiles having their
boundary words in $R$, all edges of which originate from $\Gamma$, and
with at most $3\abs{w}/g$ tiles.
\end{lem}

\begin{dem}[ of Lemma~\ref{lemmain}]
If $w \leq 2\Delta$ then by definition of $R$ there exists a one-tile puzzle
spanning $w$, and as $\abs{w}\geq g$ the conclusion holds.
Show by induction on $n$ that if $\abs{w}\leq n\Delta$ there
exists a puzzle $D$ spanning $w$ with at most $n$ pieces. This is true
for $n=2$. Suppose this is true up to $n\Delta$ and suppose that
$2\Delta\leq \abs{w}\leq (n+1)\Delta$.

Let $w=w'w''$ where $\abs{w'}=2\Delta$. As the diameter of $\Gamma$ is
$\Delta$, there exists a path in $\Gamma$ labelling a word $x$ joining
the endpoints of $w'$, with $\abs{x}\leq \Delta$. So $w'x^{-1}$ is read
on a cycle of $\Gamma$ of length at most $3\Delta$, hence (its reduction)
belongs to $R$. Now $xw''$ is a word read on a cycle of $\Gamma$, of
length at most $\abs{w}-\Delta\leq n\Delta$. So there is a puzzle with at
most $n$ tiles spanning $xw''$. Gluing this puzzle with the tile spanning
$w'x^{-1}$ along the $x$-sides provides the desired puzzle. (Note that this gluing
occurs in $\Gamma$, so that edges of the resulting puzzle originate from
$\Gamma$.)

So for any $w$ we can find a puzzle spanning it with at most
$1+\abs{w}/\Delta$ tiles. As $\Delta\geq g/2$ and as $\abs{w}\geq g$, we
have $1+\abs{w}/\Delta\leq 1+2\abs{w}/g \leq 3\abs{w}/g$.
\end{dem}

\begin{cor}\label{lemmult}
For any choice of $R$, there exists a constant $\alpha$ such that any
minimal simply connected puzzle $D$ with
respect to the tiles of $\Gamma$ all internal edges of which originate
from
$\Gamma$ satisfies the isoperimetric inequality $\abs{\d D}\geq
\alpha\abs{D}$.
%
%Moreover, if $R$ is minimal, this is true for any van Kampen-reduced
%diagram instead of minimal ones.
\end{cor}

\begin{dem}[ of Corollary~\ref{lemmult}]
Indeed, the existence of an isoperimetric constant does not depend on the
presentation.
%
%As the fundamental group of a graph is free, if the generating set of
%cycles $\mathcal{C}$ taken is minimal, it freely generates all cycles of
%$\Gamma$ (w.r.t.\ some base point). Two van Kampen-reduced puzzles with
%edges originating from $\Gamma$, with the same boundary word, will lift
%in $\Gamma$ to the same disk and will have the same number of tiles.
\end{dem}


The second lemma is just ordinary small cancellation theory (see for
example the appendix of~\cite{GH}, or~\cite{LS}), stated in the form
we need. We include a short proof here for completeness.

\begin{lem}\label{lemsc}
Let $R$ be a set of simply connected reduced tiles. Suppose that any doublet with
respect to two tiles $t,t'\in R$ is a word of length at most $\lambda$ times 
the smallest boundary length of $t$ and $t'$, for some constant
$\lambda<1/6$.

Then any simply connected van Kampen-reduced puzzle $D$ with respect to the tiles of $R$
satisfies the following properties.
\begin{enumerate}%[iii]
\item The reduction $w$ of the boundary word of $D$
contains a subword of some tile $t$ with length at least
$(1-3\lambda)>\frac12$ times the boundary length of $t$.
\item
The word $w$ is not a
proper subword of the boundary word of some tile.
\item
The boundary length $\abs{\d D}$ is at
least $1-6\lambda$ times the sum of the lengths of the faces of $D$, and
at least the boundary length of the largest tile it contains.
\end{enumerate}
\end{lem}

The value $1/6$ is optimal, as a hexagonal tiling shows.

\begin{dem}
Let $D$ be a van Kampen-reduced puzzle w.r.t.\ $R$. We can suppose that its
boundary word is reduced (isoperimetry for the reduction implies
isoperimetry for $D$ a fortiori). It is a planar graph. Define a
metric graph $D'$ as follows: start with $D$, but for each pair of
adjacent faces, replace all consecutive edges between these two faces by
a single edge. Define the length of this new edge as the number of edges
it replaces. So $D'$ is a metric planar graph having the same faces as
$D$ but in which every vertex is of degree at least $3$. The
small cancellation assumption states that the length of any edge in $D'$ is
at most $\lambda$ times the smallest boundary length of the two
adjacent faces.

\begin{center}
\includegraphics[scale=0.7]{coarsening.eps}
\end{center}

Let $V$, $E$ and $F$ denote the number of vertices, edges and faces of
$D'$, respectively. Let $E_i$ and $E_e$ denote the number of internal and
external edges, and $F_i$, $F_e$ the number of internal faces and faces
adjacent to the boundary. Let $F_e^1$ and $F_e^2$ denote the number of external
faces with exactly one, or at least two, external edges, respectively.

As every vertex has degree at least $3$, we have $E\geq 3V/2$. By
definition we have $E_e\geq F_e^1+2F_e^2$.  Since $\lambda<1/6$, any
internal face has at least $6$ edges.

We now prove that there are at least two external faces with exactly one
external edge and at most three internal edges (this will prove the
first assertion of the lemma). Let $F'_e$ and $F''_e$ be the number of external faces
with exactly one external edge and, respectively, at most three or at
least four internal edges.
Since any internal face has at least six internal edges,
and since any external face with two external edges has at least two
internal edges, we get $E_i\geq \frac12 \left(F'_e+4F''_e+2F_e^2+6F_i\right)$.

The Euler formula writes
\begin{eqnarray*}
1&=& V-E+F = V-\frac23 E -\frac13 E +F
\\&\leq&
0 -\frac13 E_i -\frac13 E_e +F_e+F_i
\\&\leq& -\frac16 \left(F'_e+4F''_e+2F_e^2+6F_i\right) -\frac13
\left(F'_e+F''_e+2F_e^2\right) +F'_e+F''_e+F_e^2+F_i 
\\&=& \frac12 F'_e
\end{eqnarray*}
Hence there exist at least two faces with exactly one external edge and at most
three internal ones.

By the small cancellation assumption, the internal edges of such a face
have cumulated length at most $3\lambda$ times the length of this face.
This proves the first assertion of the lemma.

The second assertion is easy. Suppose that the boundary word of some
puzzle is a proper subword $w$ of the boundary word $x$ of some tile $t$.
We know that $w$ contains a subword which contains a proportion at least
$(1-3\lambda)>1/2$ of the boundary word of some tile $t'$. If $\abs{w}\leq
\abs{x}/2$ we have $t'\neq t$, so $t$ and $t'$ share a common subword of
length more than one half the boundary length of $t'$, which contradicts
the small cancellation assumption. If $\abs{w} > \abs{x}/2$, then define
a new puzzle by gluing the inverse tile $t^{-1}$ to the original puzzle
(and reducing the resulting puzzle): the new puzzles now contains the
reduction of the word $wx^{-1}$, which is at least one half of the
boundary word of $t^{-1}$; use the same argument.

Isoperimetry follows immediately. Let $F$ be a external face of $D'$ with
at most three internal edges. Let $\ell$ be the length of $F$. Let $D''$
be the (maybe non connected) graph obtained from $D'$ by removing $F$. We
have $\abs{\d D'}= \abs{\d D''}+ \ell -2\abs{F\cap D''}\geq
\abs{\d D''}+(1-6\lambda)\ell$ hence the conclusion by backwards
induction on the number of faces.

The fact that the boundary length of $D$ is at least the boundary length
of the largest face is trivial if $D$ has only one face, and otherwise
follows from the fact that there are two external faces having at least a
proportion $1-3\lambda>\frac12$  of their length on the boundary. Remove
such a face (but not the largest one): this decreases the boundary
length. Iterate this process up to a diagram containing only the largest
face.
\end{dem}

\begin{cor}\label{nohole}
Let $R$ be a set of (not necessarily simply connected) reduced tiles. Suppose
that any doublet with respect to two tiles $t,t'\in R$ is a word of
length at most $\lambda$ times the smallest length of the boundary
component of $t$ and $t'$ it immerses in, for some constant $\lambda<1/6$.

Then, any simply connected puzzle with respect to this set of tiles
contains only simply connected tiles.
\end{cor}

\begin{dem}[ of the corollary]
Let $D$ be a simply connected puzzle with respect to $R$. Let $t$ be a
non-simply connected tile in $D$. Consider the subdiagram $D'$ of $D$
filling one of the holes of $t$. We can suppose that $D'$ contains only
simply connected tiles (otherwise, take again a non-simply connected tile
in $D'$ and a diagram filling one of its holes, and repeat this operation
as many times as necessary).

By the previous lemma, the boundary word $w$ of $D'$ contains a subword
$w'$ of the boundary word $w_{t'}$ of some tile $t'$ of $D'$, with
$\abs{w'}\geq \abs{w_{t'}}/2$. But as all tiles are reduced, the boundary
word of $D'$ is the word read on the boundary component of $t$ spanning
$D'$. So $t'$ and $t$ have in common a word of length at least one half
the boundary length of $t'$, which contradicts the assumption.
\end{dem}




Back to our simply connected puzzle $D$ with tiles in $\Gamma$. A puzzle
is built by taking the disjoint union of all its tiles and gluing them
along the internal edges.

First, define a (maybe not connected) puzzle $D'$ by taking the disjoint
union of all tiles of $D$ and gluing them along the internal edges of
$D$ originating from $\Gamma$. All internal edges of $D'$ originate from
$\Gamma$.

As $D$ is van Kampen-reduced, $D'$ is as well.

Let $D_i$, $i=1,\ldots,n$ be the connected components of $D'$. They form
a partition of $D$. The puzzle $D$ is obtained by gluing these components
along the internal edges of $D$ not originating from $\Gamma$.

It may be the case that the boundary word of some $D_i$ is not reduced.
This means that there is a vertex on the boundary of $D_i$ which is the
origin of two (oriented) edges bearing the same vertex. We will modify
$D$ in order to avoid this. Suppose some $D_i$ has non-reduced boundary
and consider two edges $e_1, e_2$ of $D$ responsible for this: $e_1$ and
$e_2$ are two consecutive edges with inverse labels. These edges
are either boundary edges of $D$ or internal edges. In the latter case
this means that $D_i$ is to be glued to some $D_j$. We treat only this
latter case as the other one is even simpler.

Make the following transformation of $D$: do not glue any more edge $e_1$
of $D_i$ with edge $e_1$ of $D_j$, neither edge $e_2$
of $D_i$ with edge $e_2$ of $D_j$, but rather glue edges $e_1$ and $e_2$
of $D_i$, as well as edges $e_1$ and $e_2$ of $D_j$, as in the
following picture. This is possible since by definition $e_1$ and $e_2$
bear inverse labels.

\begin{center}
\includegraphics[scale=0.7]{reduction.eps}
\end{center}

This kind of operation has been studied and termed \emph{diamond move} in
\cite{CH}.

Since $\Gamma$ is reduced, the lifts to $\Gamma$ of the edges $e_1$ and
$e_2$ of $D_i$ are the same edge of $\Gamma$. This shows that the
transformation above preserves the fact that all edges of $D_i$ and of
$D_j$ originate from $\Gamma$.

The resulting diagram (denoted $D$ again) has the same number of faces as
before, and no more boundary edges. Thus, proving isoperimetry for the
modified diagram will imply isoperimetry for the original one as well.
So we can safely assume that the boundary words of the $D_i$'s are
reduced.

Now consider $D$ as a puzzle with the $D_i$'s as tiles. Note that these
tiles are not necessarily simply connected.

These tiles satisfy the condition of Corollary~\ref{nohole}. Indeed, suppose
that the two tiles $D_i$, $D_j$ are to be glued along a common (reduced!)
word $w$.  By definition of the $D_i$'s, the edges making up $w$ do not
originate from $\Gamma$.

As the edges of $D_i$ originate from $\Gamma$, there is a lift
$\phi_i:D_i\rightarrow \Gamma$ (as noted above).
Consider the two lifts $\phi_i(w)$ and $\phi_j(w)$. As the edges making
up $w$ do not originate from $\Gamma$, these two lifts are different. As
$w$ is reduced these lifts are immersions.  So $w$ is a doublet. By
assumption the length of $w$ is at most $\Lambda<g/6$.

Now as $D_i$ lifts to $\Gamma$, any boundary component of $D_i$ goes to a
closed path in the $1$-skeleton of $\Gamma$. This proves that the length
of any boundary component of $D_i$ is at least $g$.

So the tiles $D_i$ satisfy the small cancellation condition with
$\lambda=\Lambda/g<1/6$. As they are tiles of a simply connected puzzle,
by Corollary~\ref{nohole} they are simply connected.

Then by Lemma~\ref{lemsc}, the boundary of $D$ is at
least $1-6\lambda$ times the sum of the boundary lengths of the $D_i$'s.
Since $D$ is minimal, each $D_i$ is as well, and as $D_i$ is simply
connected, by Corollary~\ref{lemmult} it satisfies the isoperimetric inequality
$\abs{\d D_i}\geq \alpha \abs{D_i}$. So
\[
\abs{\d D}\geq (1-6\lambda) \sum \abs{\d D_i}\geq \alpha (1-6\lambda)
\sum \abs{D_i}=\alpha (1-6\lambda)\abs{D}
\]
which shows the isoperimetric inequality for $D$, hence hyperbolicity.

For asphericity and the cohomological dimension (hence torsion-freeness),
suppose that $R$ is standard (so that $\Gamma$ is aspherical) and that
there exists a van Kampen-reduced spherical diagram $D$. Define the
$D_i$'s as above. As we shown above that the boundary length of $D$
(which is $0$) is at least the boundary length of any $D_i$, this means
that the boundary length of all the $D_i$'s is $0$. Hence each $D_i$ is a
spherical diagram itself.  But by definition $D_i$ lifts to $\Gamma$. We
conclude with the following lemma.

\begin{lem}
Suppose that the set of paths read along faces of $\Gamma$ is standard.
Let $D$ be a non-empty spherical puzzle all edges of which come from $\Gamma$.
Then $D$ is not reduced.
\end{lem}

\begin{dem}[ of the lemma]
Let $T$ be a maximal tree of the $1$-skeleton of $\Gamma$ witnessing for
standardness of the family of cycles. Homotope $T$
to a point. This turns $\Gamma$ into a bouquet of circles with a face in
each circle. Similarly, homotope to a point any edge of $D$ coming from a
suppressed edge of $\Gamma$. This way we turn $D$ into a spherical van
Kampen diagram with respect to the presentation of the fundamental group
of $\Gamma$ (i.e.\ the trivial group) by 
$\presgroup{c_1,\ldots,c_n}{c_1=e,\ldots,c_n=e}$. But there is no reduced
spherical van Kampen diagram with respect to this presentation, as can
immediately be checked.
\end{dem}

The last affirmations of the theorem follow easily from the last
affirmations of Lemma~\ref{lemsc}. The smallest relation in the group
presented by $\presgroup{S}{R}$ is the boundary length of the smallest
puzzle, which by Lemma~\ref{lemsc} is at least the smallest boundary
length of the $D_i$'s, which is at least $g$. Similarly, any reduced
word representing the trivial element in the group is the boundary of a
reduced diagram, thus contains as a subword at least one half of the boundary
word of some $D_i$.

For the isoperimetric embedding of $\Gamma$ in the Cayley graph of the
group, suppose that some geodesic path in the graph labelling a word $x$
is equal to a shorter word $y$ in the quotient. This means that there
exists a puzzle with boundary word $xy^{-1}$, made up of tiles with
cycles of $\Gamma$ as boundary words. Now (if $\Gamma$ contains no
filaments) $x$ is part of some cycle labelled by $w=xz$ of the graph.
Since the path $x$ is of minimal length, we have $\abs{x}\leq \abs{z}$.
So $\abs{xy^{-1}}< \abs{w}$ and in particular, the puzzle bordering
$xy^{-1}$ cannot contain a tile with boundary word $w$. Glue a tile
with boundary word $(xz)^{-1}$ to the puzzle $xy^{-1}$ along the subwords
$x$ and $x^{-1}$. This results in a (reduced) puzzle bordering
$z^{-1}y^{-1}$, containing a tile $z^{-1}x^{-1}$. This is impossible as
by assumption $\abs{y}<\abs{x}$.

Non-elementariness in case the rank of the fundamental group of
$\Gamma$ is large enough follows immediately from a computation of the 
Euler characteristic, using that the cohomological dimension is at most 
$2$.

This proves the theorem.
\end{dem}


\section{Further remarks}

\begin{rem}
The proof above gives an explicit isoperimetric constant when the set of
relators taken is the set of all words read on cycles of the graph of
length at most three times the diameter: in this case, any
%van Kampen-reduced (not only minimal)
minimal simply connected puzzle satisfies the
isoperimetric inequality
\[
\abs{\d D}\geq g(1-6\Lambda/g)\abs{D}/3
\]
This explicit isoperimetric constant growing linearly with $g$ (i.e.~``homogeneous'') can be
very useful if one wants to apply such theorems as the local-global
hyperbolic principle, which requires the isoperimetric constant to grow
linearly with the sizes of the relators.
\end{rem}

\begin{rem}
The assumption that $\Gamma$ is reduced can be relaxed a little bit,
provided that some quasi-geodesicity assumption is granted, and that the
definition of a doublet is emended.

Redefine a \emph{doublet} to be a couple of words $(w_1,w_2)$ such that
both immerse in $\Gamma$ and such that $w_1=w_2$ in the free group. The
\emph{length} of a doublet $(w_1,w_2)$ is the maximal length of $w_1$ and
$w_2$.

There are trivial doublets, for example if $w_1=w_2$ and both have the
same immersion. However, forbidding this is not enough: for example, if a
word of the form $aa^{-1}w$ immerses in the graph, then $(aa^{-1}w, w)$
will be a doublet.


A \emph{trivial doublet} is a doublet $(w_1,w_2)$ such that
there exists a path $p$ in $\Gamma$ joining the beginning of the
immersion of $w_1$ to the beginning of the immersion of $w_2$ such that
$p$ is labelled with a word equal to $e$ in the free group.

The new theorem is as follows.
\end{rem}

\begin{thm}[ (M.~Gromov)]
Let $\Gamma$ be a labelled graph. Let $R$ be the set of words read on
all cycles of $\Gamma$ (or on a generating family of cycles). Let $g$ be the girth of $\Gamma$ and $\Lambda$ be the
length of the longest non-trivial doublet of $\Gamma$.

Suppose that $\lambda=\Lambda/g$ is less than $1/6$.

Suppose that there exist a constant $A>0$ such that any word $w$ immersed
in $\Gamma$ of length at least $L$ satisfies $\norm{w}\geq
A(\abs{w}-L)$ for some $L<(1-6\lambda)g/2$.

Then the presentation $\presgroup{S}{R}$ defines a hyperbolic,
infinite, torsion-free group $G$, and (if $R$ is standard) this presentation is aspherical
(hence the cohomological dimension of $G$ is at most $2$). Moreover, the
natural map of labelled graphs from $\Gamma$ to the Cayley graph of $G$
is a $(1/A,AL)$-quasi-isometry. The shortest relation of
$G$ is of length at least $Ag/2$, and any reduced word equal to $e$ in $G$
contains as a subword the reduction of at least one half of a word read
on a cycle of $\Gamma$.
\end{thm}

(In the notation of~\cite{GH}, by a $(\lambda,c)$-quasi-isometry we wean
a map $f$ such that $d(x,y)/\lambda-c\leq d(f(x),f(y))\leq \lambda
d(x,y)+c$.)

\begin{rem}
The same theorems hold if we use the $C(7)$ condition instead of the
$C'(1/6)$ condition, but in this case there is no control on the radius
of injectivity.
\end{rem}

\begin{rem}
Using the techniques in~\cite{Del} or~\cite{Oll}, the same kind of theorem
holds starting with any torsion-free hyperbolic group instead of the free
group, provided that the
girth of the graph is large enough w.r.t.\ the hyperbolicity constant,
and that the labelling is quasi-geodesic.
\end{rem}


Thanks to Thomas Delzant for having brought the problem to my attention
and to �tienne Ghys and Pierre Pansu for helpful discussions and comments
on the manuscript.


\begin{thebibliography}{MMM}

\bibitem[CH]{CH} J.D.~Collins, J.~Huebschmann, \emph{Spherical diagrams
and identities among relations}, Math.\ Ann.~\textbf{261} (1982), No.~2,
155--183.

\bibitem[Del]{Del}
T.~Delzant,
\emph{Sous-groupes distingu�s et quotients des groupes hyperboliques},
Duke Math.\ J.~\textbf{83} (1996), No.~3, 661--682.

\bibitem[Gh]{Gh} �.~Ghys, \emph{Groupes al�atoires}, s�minaire
Bourbaki~\textbf{916} (2003).

\bibitem[GH]{GH}
�.~Ghys, P.~de la Harpe,
\emph{Sur les groupes hyperboliques d'apr�s Mikhael Gromov},
Progress in Math.~\textbf{83}, Birkh�user (1990).

\bibitem[Gro1]{Gro1} M.~Gromov, \emph{Hyperbolic Groups}, in \emph{Essays
in group theory}, ed.\ S.M.~Gersten, Springer (1987), 75--265.

\bibitem[Gro2]{Gro2}
M.~Gromov,
\emph{Random Walk in Random Groups},
Geom.\ Funct.\ Anal.~\textbf{13} (2003), No.~1, 73--146.

\bibitem[HLS]{HLS} N.~Higson, V.~Lafforgue, G.~Skandalis,
\emph{Counterexamples to the Baum-Connes conjecture}, Geom.\ Funct.\
Anal.~\textbf{12} (2002), No.~2, 330--354.

\bibitem[LS]{LS}
R.C.~Lyndon, P.E.~Schupp,
\emph{Combinatorial Group Theory},
Ergebnisse der Mathematik und ihrer Grenzgebiete~\textbf{89}, Springer (1977).

\bibitem[Oll]{Oll} Y.~Ollivier, \emph{Sharp phase transition theorems for
hyperbolicity of random groups}, to appear in Geom.\ Funct.\ Anal.
Preprint available on ArXiV: math.GR/0301187

\bibitem[Sch]{Sch} P.E.~Schupp, \emph{A survey of small cancellation
theory}, in W.W.~Boone, F.B.~Cannonito, R.C.~Lyndon, eds, \emph{Word
problems}, Studies in logic and the foundations of
mathematics~\textbf{71}, North Holland Publ.\ Comp.\ (1973), 569--589.

\bibitem[Sh]{Sh} A.~Short et al., in \emph{Group Theory from a
Geometrical Viewpoint}, ed.\ �.~Ghys, A.~Haefliger, A.~Verjovsky, World
Scientific (1991).

\end{thebibliography}

\end{document}

math0310022.extracted_bib
\begin{thebibliography}{MMM}

\bibitem[CH]{CH} J.D.~Collins, J.~Huebschmann, \emph{Spherical diagrams
and identities among relations}, Math.\ Ann.~\textbf{261} (1982), No.~2,
155--183.

\bibitem[Del]{Del}
T.~Delzant,
\emph{Sous-groupes distingu�s et quotients des groupes hyperboliques},
Duke Math.\ J.~\textbf{83} (1996), No.~3, 661--682.

\bibitem[Gh]{Gh} �.~Ghys, \emph{Groupes al�atoires}, s�minaire
Bourbaki~\textbf{916} (2003).

\bibitem[GH]{GH}
�.~Ghys, P.~de la Harpe,
\emph{Sur les groupes hyperboliques d'apr�s Mikhael Gromov},
Progress in Math.~\textbf{83}, Birkh�user (1990).

\bibitem[Gro1]{Gro1} M.~Gromov, \emph{Hyperbolic Groups}, in \emph{Essays
in group theory}, ed.\ S.M.~Gersten, Springer (1987), 75--265.

\bibitem[Gro2]{Gro2}
M.~Gromov,
\emph{Random Walk in Random Groups},
Geom.\ Funct.\ Anal.~\textbf{13} (2003), No.~1, 73--146.

\bibitem[HLS]{HLS} N.~Higson, V.~Lafforgue, G.~Skandalis,
\emph{Counterexamples to the Baum-Connes conjecture}, Geom.\ Funct.\
Anal.~\textbf{12} (2002), No.~2, 330--354.

\bibitem[LS]{LS}
R.C.~Lyndon, P.E.~Schupp,
\emph{Combinatorial Group Theory},
Ergebnisse der Mathematik und ihrer Grenzgebiete~\textbf{89}, Springer (1977).

\bibitem[Oll]{Oll} Y.~Ollivier, \emph{Sharp phase transition theorems for
hyperbolicity of random groups}, to appear in Geom.\ Funct.\ Anal.
Preprint available on ArXiV: math.GR/0301187

\bibitem[Sch]{Sch} P.E.~Schupp, \emph{A survey of small cancellation
theory}, in W.W.~Boone, F.B.~Cannonito, R.C.~Lyndon, eds, \emph{Word
problems}, Studies in logic and the foundations of
mathematics~\textbf{71}, North Holland Publ.\ Comp.\ (1973), 569--589.

\bibitem[Sh]{Sh} A.~Short et al., in \emph{Group Theory from a
Geometrical Viewpoint}, ed.\ �.~Ghys, A.~Haefliger, A.~Verjovsky, World
Scientific (1991).

\end{thebibliography}