Cayley graph
Named by 9 essays across one field — each of them below, with the objects they name alongside it.
The group drawn as a map
A multiplication table says everything about a group and shows nothing; lay the same information out as one dot per element and one arrow per generator, and multiplying becomes walking, distance becomes a word length, and the group acquires a shape.
How fast the ball fills
Count the elements within r steps of doing nothing. The count grows like a polynomial in some groups and like a power of three in others, the distinction survives every change of generating set, and which polynomial degrees are possible is a theorem nobody expected.
The edge that is as big as the ball
In a lattice the boundary of a large ball is a negligible fraction of it. In a tree it is two thirds of it at every size — and that single ratio, not the group's size, is what decides whether a set can be cut into pieces and reassembled into two copies of itself.
What is left when the middle is taken out
Cut a finite piece out of a group's picture and count the parts of what remains that run off forever. The integers leave two, the plane one, a tree more with every cut — and no group anywhere leaves exactly three, because a third end is always the first of infinitely many.
The polygon a lattice becomes from far away
Walk the grid of whole-number points with a fixed set of moves and the places reachable in r moves fill a shape. With axis steps it is a diamond, add a diagonal and it is a hexagon, move like a knight and it is a ragged thing full of holes — which, seen from far enough away, is an octagon exactly. The generators decide the polygon, and the polygon decides the count.
Thirty-one moves from solved
Parity settles which half of a sliding puzzle's arrangements can be reached and is silent about how far away any of them is. Searching every reachable arrangement of the three-by-three tray answers the second question exactly — two arrangements sit thirty-one moves out — and parity turns up again, this time as a law about distance.
The shape a random ball grows into
Give every road of the square grid a random travel time and ask what can be reached from one point in time t. The region is ragged, and rescaled it converges to a fixed convex shape — but which shape is unknown for every natural law. Computing it shows a curve within a few per cent of a circle for continuous travel times, a flat side where fast roads percolate along a diagonal, a time per step that is still drifting at a hundred and twenty-eight steps, and fluctuations that grow like the distance to the power one third rather than one half.
How rarely a walk on a group comes home
Walk at random on the picture of a group, one generator at a time, and ask for the chance of standing at the start after 2n steps. On the line, the plane and three-dimensional space it falls like a power of n. On the tree that pictures the free group it falls by the factor √3/2 every step, exponentially. Kesten proved in 1959 that this is no accident of two examples: the chance falls exponentially exactly when the group's balls are mostly boundary, so a probabilistic rate and a geometric ratio are the same measurement.
Three coordinates and a fourth power
The Heisenberg group is made of triples of whole numbers, and two moves generate all of it. Count the triples within r moves of the start and the count grows like r⁴, not r³: at forty-four moves there are 1,600,703 of them, against 117,569 for the cubic lattice. The fourth power comes from one coordinate that the moves reach by enclosing area, so that height costs only the square root of itself — and seen from far away, the ball of reachable triples is a curved solid with a dimple at each pole.
Named alongside it
The objects these essays reach for when they reach for this one.
Growth rateWord metricFree groupInvariantGroup actionLimit shapeCyclic groupEnds of a groupGenerating setLatticeQuasi isometryAbelian group