Return to Answer

Stallings' folding algorithm (described by Agol) is probably the best way of doing this, but I thought I'd mention an older algorithm which is also useful, due to Whitehead.

Let $\{w_k\}$ be a collection of words in $F_n$. The Whitehead graph is defined as follows. There are $2n$ vertices, labelled $x_i^{\pm}$. Whenever $x_ix_j$ appears as subword of some $w_k$, an edge is added from $x_i^+$ to $x_j^-$. Similarly, when $x_i^{-1}x_j$ appears as a subword, an edge is added from $x_i^-$ to $x_j^-$, and so on.

A better description of the Whitehead graph for a topologist is as follows. Realize $F_n$ as the fundamental group of a handlebody $U_n$. Realize the generators $x_i$ by finitely many properly embedded discs $D_i$, which cut the interior of $U_n$ into a ball. Realize the words $w_k$ by an embedded 1-dimensional submanifold of $U_n$; after a homotopy, we may assume that the $w_k$ are `pulled tight' with respect to the discs $D_i$.

As mentioned already, cutting along the discs $D_i$ gives a 3-ball $B$, and each disc $D_i$ lifts to a pair of discs $D_i^{\pm}$ in the boundary of $B$. The submanifold $w_k$ becomes a set of intervals joining these discs. This is precisely the Whitehead graph, with the disc $D_i^{\pm}$ corresponding to the vertex $x_i^{\pm}$.

Here's a picture from one of my papers.

Whitehead used this construction to produce an algorithm that computes shortest representatives for sets of words $\{w_k\}$ under the action of the automorphism group of $F_n$: if the set of words is not of shortest length then one can perform a `Whitehead move', which replaces one cutting disc with a better one, and reduce the length. In particular, his algorithm can be used to recognise generating sets. In fact, he proved the following very useful lemma.

Whitehead's Lemma: If $F_n$ admits a free splitting $A*B$ in which every $w_k$ is conjugate into either $A$ or $B$ then the Whitehead graph is either disconnected or has a cut vertex.

In particular, if the Whitehead graph is connected with no cut vertices then the $w_k$ do not generate. If the Whitehead graph is disconnected or does have a cut vertex then you can perform Whitehead moves until you find the answer.

For further details, see §I.4 of Lyndon and Schupp for the combinatorial approach and a paper of Stallings (see Whitehead graphs on handlebodies for a dvi) for the topological approach.

Stallings' folding algorithm (described by Agol) is probably the best way of doing this, but I thought I'd mention an older algorithm which is also useful, due to Whitehead.

Let $\{w_k\}$ be a collection of words in $F_n$. The Whitehead graph is defined as follows. There are $2n$ vertices, labelled $x_i^{\pm}$. Whenever $x_ix_j$ appears as subword of some $w_k$, an edge is added from $x_i^+$ to $x_j^-$. Similarly, when $x_i^{-1}x_j$ appears as a subword, an edge is added from $x_i^-$ to $x_j^-$, and so on.

A better description of the Whitehead graph for a topologist is as follows. Realize $F_n$ as the fundamental group of a handlebody $U_n$. Realize the generators $x_i$ by finitely many properly embedded discs $D_i$, which cut the interior of $U_n$ into a ball. Realize the words $w_k$ by an embedded 1-dimensional submanifold of $U_n$; after a homotopy, we may assume that the $w_k$ are ‘pulled tight’ with respect to the discs $D_i$.

As mentioned already, cutting along the discs $D_i$ gives a 3-ball $B$, and each disc $D_i$ lifts to a pair of discs $D_i^{\pm}$ in the boundary of $B$. The submanifold $w_k$ becomes a set of intervals joining these discs. This is precisely the Whitehead graph, with the disc $D_i^{\pm}$ corresponding to the vertex $x_i^{\pm}$.

Here's a picture from one of my papers.

Whitehead used this construction to produce an algorithm that computes shortest representatives for sets of words $\{w_k\}$ under the action of the automorphism group of $F_n$: if the set of words is not of shortest length then one can perform a ‘Whitehead move’, which replaces one cutting disc with a better one, and reduce the length. In particular, his algorithm can be used to recognise generating sets. In fact, he proved the following very useful lemma.

Whitehead's Lemma: If $F_n$ admits a free splitting $A*B$ in which every $w_k$ is conjugate into either $A$ or $B$ then the Whitehead graph is either disconnected or has a cut vertex.

In particular, if the Whitehead graph is connected with no cut vertices then the $w_k$ do not generate. If the Whitehead graph is disconnected or does have a cut vertex then you can perform Whitehead moves until you find the answer.

For further details, see §I.4 of Lyndon and Schupp for the combinatorial approach and a paper "Whitehead graphs on handlebodies" of Stallings (DVI or PDF) for the topological approach.

Stallings' folding algorithm (described by Agol) is probably the best way of doing this, but I thought I'd mention an older algorithm which is also useful, due to Whitehead.

Let $\{w_k\}$ be a collection of words in $F_n$. The Whitehead graph is defined as follows. There are $2n$ vertices, labelled $x_i^{\pm}$. Whenever $x_ix_j$ appears as subword of some $w_k$, an edge is added from $x_i^+$ to $x_j^-$. Similarly, when $x_i^{-1}x_j$ appears as a subword, an edge is added from $x_i^-$ to $x_j^-$, and so on.

A better description of the Whitehead graph for a topologist is as follows. Realize $F_n$ as the fundamental group of a handlebody $U_n$. Realize the generators $x_i$ by finitely many properly embedded discs $D_i$, which cut the interior of $U_n$ into a ball. Realize the words $w_k$ by an embedded 1-dimensional submanifold of $U_n$; after a homotopy, we may assume that the $w_k$ are `pulled tight' with respect to the discs $D_i$.

As mentioned already, cutting along the discs $D_i$ gives a 3-ball $B$, and each disc $D_i$ lifts to a pair of discs $D_i^{\pm}$ in the boundary of $B$. The submanifold $w_k$ becomes a set of intervals joining these discs. This is precisely the Whitehead graph, with the disc $D_i^{\pm}$ corresponding to the vertex $x_i^{\pm}$.

Here's a picture from one of my papers.

Whitehead used this construction to produce an algorithm that computes shortest representatives for sets of words $\{w_k\}$ under the action of the automorphism group of $F_n$: if the set of words is not of shortest length then one can perform a `Whitehead move', which replaces one cutting disc with a better one, and reduce the length. In particular, his algorithm can be used to recognise generating sets. In fact, he proved the following very useful lemma.

Whitehead's Lemma: If $F_n$ admits a free splitting $A*B$ in which every $w_k$ is conjugate into either $A$ or $B$ then the Whitehead graph is either disconnected or has a cut vertex.

In particular, if the Whitehead graph is connected with no cut vertices then the $w_k$ do not generate. If the Whitehead graph is disconnected or does have a cut vertex then you can perform Whitehead moves until you find the answer.

For further details, see §I.4 of Lyndon and Schupp for the combinatorial approach and a paper of Stallings (click here for a dvi) for the topological approach.

Stallings' folding algorithm (described by Agol) is probably the best way of doing this, but I thought I'd mention an older algorithm which is also useful, due to Whitehead.

Let $\{w_k\}$ be a collection of words in $F_n$. The Whitehead graph is defined as follows. There are $2n$ vertices, labelled $x_i^{\pm}$. Whenever $x_ix_j$ appears as subword of some $w_k$, an edge is added from $x_i^+$ to $x_j^-$. Similarly, when $x_i^{-1}x_j$ appears as a subword, an edge is added from $x_i^-$ to $x_j^-$, and so on.

A better description of the Whitehead graph for a topologist is as follows. Realize $F_n$ as the fundamental group of a handlebody $U_n$. Realize the generators $x_i$ by finitely many properly embedded discs $D_i$, which cut the interior of $U_n$ into a ball. Realize the words $w_k$ by an embedded 1-dimensional submanifold of $U_n$; after a homotopy, we may assume that the $w_k$ are `pulled tight' with respect to the discs $D_i$.

As mentioned already, cutting along the discs $D_i$ gives a 3-ball $B$, and each disc $D_i$ lifts to a pair of discs $D_i^{\pm}$ in the boundary of $B$. The submanifold $w_k$ becomes a set of intervals joining these discs. This is precisely the Whitehead graph, with the disc $D_i^{\pm}$ corresponding to the vertex $x_i^{\pm}$.

Here's a picture from one of my papers.

Whitehead used this construction to produce an algorithm that computes shortest representatives for sets of words $\{w_k\}$ under the action of the automorphism group of $F_n$: if the set of words is not of shortest length then one can perform a `Whitehead move', which replaces one cutting disc with a better one, and reduce the length. In particular, his algorithm can be used to recognise generating sets. In fact, he proved the following very useful lemma.

Whitehead's Lemma: If $F_n$ admits a free splitting $A*B$ in which every $w_k$ is conjugate into either $A$ or $B$ then the Whitehead graph is either disconnected or has a cut vertex.

In particular, if the Whitehead graph is connected with no cut vertices then the $w_k$ do not generate. If the Whitehead graph is disconnected or does have a cut vertex then you can perform Whitehead moves until you find the answer.

For further details, see §I.4 of Lyndon and Schupp for the combinatorial approach and a paper of Stallings (see Whitehead graphs on handlebodies for a dvi) for the topological approach.

Stallings' folding algorithm (described by Agol) is probably the best way of doing this, but I thought I'd mention an older algorithm which is also useful, due to Whitehead.

Let $\{w_k\}$ be a collection of words in $F_n$. The Whitehead graph is defined as follows. There are $2n$ vertices, labelled $x_i^{\pm}$. Whenever $x_ix_j$ appears as subword of some $w_k$, an edge is added from $x_i^+$ to $x_j^-$. Similarly, when $x_i^{-1}x_j$ appears as a subword, an edge is added from $x_i^-$ to $x_j^-$, and so on.

A better description of the Whitehead graph for a topologist is as follows. Realize $F_n$ as the fundamental group of a handlebody $U_n$. Realize the generators $x_i$ by finitely many properly embedded discs $D_i$, which cut the interior of $U_n$ into a ball. Realize the words $w_k$ by an embedded 1-dimensional submanifold of $U_n$; after a homotopy, we may assume that the $w_k$ are `pulled tight' with respect to the discs $D_i$.

As mentioned already, cutting along the discs $D_i$ gives a 3-ball $B$, and each disc $D_i$ lifts to a pair of discs $D_i^{\pm}$ in the boundary of $B$. The submanifold $w_k$ becomes a set of intervals joining these discs. This is precisely the Whitehead graph, with the disc $D_i^{\pm}$ corresponding to the vertex $x_i^{\pm}$.

Here's a picture from one of my papers.

The Whitehead graph of b^{-1}aba^{-2}. http://www.freeimagehosting.net/6wb7s

Whitehead used this construction to produce an algorithm that computes shortest representatives for sets of words $\{w_k\}$ under the action of the automorphism group of $F_n$: if the set of words is not of shortest length then one can perform a `Whitehead move', which replaces one cutting disc with a better one, and reduce the length. In particular, his algorithm can be used to recognise generating sets. In fact, he proved the following very useful lemma.

Whitehead's Lemma: If $F_n$ admits a free splitting $A*B$ in which every $w_k$ is conjugate into either $A$ or $B$ then the Whitehead graph is either disconnected or has a cut vertex.

In particular, if the Whitehead graph is connected with no cut vertices then the $w_k$ do not generate. If the Whitehead graph is disconnected or does have a cut vertex then you can perform Whitehead moves until you find the answer.

For further details, see §I.4 of Lyndon and Schupp for the combinatorial approach and a paper of Stallings (click here for a dvi) for the topological approach.

Stallings' folding algorithm (described by Agol) is probably the best way of doing this, but I thought I'd mention an older algorithm which is also useful, due to Whitehead.

Let $\{w_k\}$ be a collection of words in $F_n$. The Whitehead graph is defined as follows. There are $2n$ vertices, labelled $x_i^{\pm}$. Whenever $x_ix_j$ appears as subword of some $w_k$, an edge is added from $x_i^+$ to $x_j^-$. Similarly, when $x_i^{-1}x_j$ appears as a subword, an edge is added from $x_i^-$ to $x_j^-$, and so on.

A better description of the Whitehead graph for a topologist is as follows. Realize $F_n$ as the fundamental group of a handlebody $U_n$. Realize the generators $x_i$ by finitely many properly embedded discs $D_i$, which cut the interior of $U_n$ into a ball. Realize the words $w_k$ by an embedded 1-dimensional submanifold of $U_n$; after a homotopy, we may assume that the $w_k$ are `pulled tight' with respect to the discs $D_i$.

As mentioned already, cutting along the discs $D_i$ gives a 3-ball $B$, and each disc $D_i$ lifts to a pair of discs $D_i^{\pm}$ in the boundary of $B$. The submanifold $w_k$ becomes a set of intervals joining these discs. This is precisely the Whitehead graph, with the disc $D_i^{\pm}$ corresponding to the vertex $x_i^{\pm}$.

Here's a picture from one of my papers.

Whitehead used this construction to produce an algorithm that computes shortest representatives for sets of words $\{w_k\}$ under the action of the automorphism group of $F_n$: if the set of words is not of shortest length then one can perform a `Whitehead move', which replaces one cutting disc with a better one, and reduce the length. In particular, his algorithm can be used to recognise generating sets. In fact, he proved the following very useful lemma.

Whitehead's Lemma: If $F_n$ admits a free splitting $A*B$ in which every $w_k$ is conjugate into either $A$ or $B$ then the Whitehead graph is either disconnected or has a cut vertex.

In particular, if the Whitehead graph is connected with no cut vertices then the $w_k$ do not generate. If the Whitehead graph is disconnected or does have a cut vertex then you can perform Whitehead moves until you find the answer.

For further details, see §I.4 of Lyndon and Schupp for the combinatorial approach and a paper of Stallings (click here for a dvi) for the topological approach.