Wolfram Demonstrations Project

This Demonstration draws the Whitehead graph of a reduced word in a free group of given rank. The word is first cyclically reduced. Multiple edges between vertices are indicated with numbered labels. If the Whitehead graph is connected and does not have a cut vertex, then the word is not separable. Otherwise, by pressing the "forward" button, a Whitehead automorphism is applied to reduce the number of edges.

Contributed by: Matt Clay

The Whitehead graph of an element

in a free group relative to the basis

is a graph with

vertices labeled

with an edge between

and

for each two-letter subword

considered as a cyclic word in the given basis. For example, the subword

would correspond to an edge between

and

and the subword

would correspond to an edge between

and

. Algebraic properties of

are reflected in the structure of the graph. One such property is whether or not there exists a basis for the free group

such that

is conjugate to a word omitting one of the generators

. In terms of the Whitehead graph, this means there is a pair of vertices

not adjacent to any edge. If so,

is called separable. Stallings showed that if

is separable, then every Whitehead graph of

is either disconnected or has a cut vertex, that is, a vertex that when removed results in a disconnected graph. A cut vertex of a connected graph is also referred to as an articulation vertex.

The algorithm to detect if

is separable is as follows. If the Whitehead graph of

does not have an isolated vertex and is disconnected, then there is a certain operation

, called a Whitehead automorphism, such that the Whitehead graph of

has a pair vertices

not adjacent to any edges, and hence

is separable. Then using the basis

we can observe that

is separable. Namely, when written in this new basis, the generator

is omitted.

Next, we check for a cut vertex. If the Whitehead graph does not have a cut vertex, then

is not separable. Otherwise, the Whitehead graph has a cut vertex. In this case, there is a Whitehead automorphism

such that the Whitehead graph for

has fewer edges. Go back to the beginning of the algorithm using this new graph. As the number of edges decreases whenever this last possibility occurs, the process will eventually terminate. By keeping track of the Whitehead automorphisms that arise, we can find the basis that witnesses

as separable if indeed it is.

The snapshots depict using the algorithm to show that the element

in the free group of rank two is separable.

Snapshot 1: The Whitehead graph of

does not have an isolated vertex but is connected and contains a cut vertex. Specifically, the vertex labeled

(The vertex labeled

is also a cut vertex.) The Whitehead automorphism that will reduce the number of edges is displayed.

Snapshot 2: After pressing the "forward" button, the Whitehead automorphism is applied and the resulting graph is now disconnected. The effect of

on the basis

is shown on the bottom of the panel. The original word

is written (cyclically) as

in the basis

and

Snapshot 3: After pressing the "forward" button again, a Whitehead automorphism is applied. The resulting graph has an isolated vertex. This shows that

is separable. The original word

is written (cyclically) as

in the basis

and

Inverses of basis elements are denoted by capital letters:

, etc.

Reference

[1] J. R. Stallings, "Whitehead Graphs in Handlebodies," in Geometric Group Theory Down Under (J. Cossey and C. F. Miller, eds.), Berlin, Germany: Walter de Gruyter, 1996 pp. 317–330.