No Petersen graph in the plane

The square net draws eleven groups asked of each of the eleven uniform nets whether it is the Cayley graph of a group, and found that every one is. The test was Sabidussi’s: a connected graph is a Cayley graph exactly when some group of its automorphisms acts on its vertices regularly, carrying any vertex to any other and leaving none of them where it was. The square net passed eleven ways, the kagome net one. The essay ended on the question its eleven cases could not reach. Is every vertex-transitive net in the plane a Cayley graph, or is there a periodic net that looks the same from every vertex and is the picture of no group at all?

For finite graphs the answer has been known for a long time to be no. The Petersen graph, ten vertices and fifteen edges, drawn as a pentagon inside a five-pointed star, looks the same from every vertex: its automorphism group, of order a hundred and twenty, carries any vertex to any other. But no subgroup of that group acts regularly on the ten vertices, so the Petersen graph is not the Cayley graph of any group. It is the smallest graph with that property, and there are infinitely many more.

The plane has none. That is a strong statement, and it can be settled by a finite computation, because the question turns out not to be about nets at all.

Why the edges do not matter #

A net is vertex-transitive when its symmetry group carries every vertex to every other, which for a periodic net in the plane means its vertices form a single orbit of a plane group. A single orbit of a plane group is the set of points of one Wyckoff position, so the vertices of a vertex-transitive plane net sit on the points of one position of one of the seventeen, with the group as the net’s own symmetry.

Sabidussi’s test then asks whether some subgroup of that group acts on those points regularly. Regularity has two halves. The subgroup must carry any point to any other, and it must fix none. Both halves are statements about the subgroup and the points. The edges of the net decide whether the net is connected and what its symmetry group is, but once the group and the vertex positions are fixed, whether a given subgroup acts regularly does not depend on a single edge.

So the question about every vertex-transitive net in the plane splits into one question for each Wyckoff position of each plane group: does the group contain a subgroup that acts on the position’s points regularly? There are seventy-two positions across the seventeen groups. Seventeen of them are general positions, whose points no operation fixes, and on those the whole group already acts regularly. That leaves fifty-five special positions, the ones whose points each lie on a rotation centre or a mirror, and on them the whole group certainly does not act regularly, since a point on a mirror is fixed by that mirror. The question is whether some smaller group does.

The points a group treats differently introduced the positions as the places a pattern can put an atom. Here they are the places a net can put its vertices, and the census below asks the same question of every one.

The search, made finite #

A regular subgroup has a point group, some subgroup of the parent group’s point group, and a lattice of translations, some sublattice of the parent’s lattice. Regularity fixes how the two must balance. If the position has $k$ points in each cell of the parent lattice and the subgroup’s lattice has index $m$, then a cell of the subgroup’s lattice holds $km$ points, and a regular subgroup must carry one chosen point to each of them by exactly one of its cosets. Its point group therefore has exactly $km$ operations. So once the point group is chosen, the index of the sublattice is fixed, and both are small, because the largest plane point group has twelve operations.

For each point group, then, the search runs over every sublattice of the right index that the point group carries onto itself, and over every choice of translation parts for its generating operations modulo that sublattice. Each choice generates a group, which is closed modulo the sublattice and must come out with exactly the right number of cosets. Then every one of its elements is tested against every point of the position in a cell of the sublattice, and a single element fixing a single point rejects the whole subgroup. What survives is every regular subgroup of the position, not merely one.

This is the search the uniform nets were put through. Run on positions it should find, for the five uniform nets whose vertices sit on a single special position, exactly what it found on the nets. The five nets’ groups are the ones eleven tilings, five groups found by handing the tilings to a detector. It does: thirty-six regular subgroups for the square net’s position, twenty-four for the triangular net’s, fourteen for the honeycomb’s, two for the snub square tiling’s, one for the kagome net’s, and the same wallpaper types in each case. The two searches never saw each other’s input. One was handed a net and found its group; the other was handed a group and a position and never saw an edge.

Fifty-five positions, none without a subgroup #

The census figure at the head of this essay is the result. Every one of the fifty-five special positions has at least one regular subgroup. Together with the seventeen general positions, that means every position of every plane group has a subgroup acting on it regularly, and so every connected vertex-transitive net in the plane whose symmetry group acts on it as a plane group is the Cayley graph of a group. There is no Petersen graph in the plane.

The positions with one point to a cell are the easy ones, and there are twenty-six of them. On such a position the lattice of translations alone acts regularly: it carries the point in one cell to the point in any other, and a translation fixes nothing. That is the observation behind every net with one vertex, where every net of that kind is the Cayley graph of its own lattice, and the census confirms it on every such position. What it adds is how many more there are. The square lattice’s special point in p4m has thirty-six regular subgroups, of eleven wallpaper types, which is the square net’s eleven again. A point of p2’s four special positions has four.

The interesting positions are the twenty-nine with several points to a cell. There the lattice alone is never enough, since it reaches only one point in each cell, and a regular subgroup has to carry the other points of the cell by operations that move them. For those operations to fix nothing, they must be translations, glides, mirrors whose lines miss every point, or rotations whose centres miss every point. The census finds that in twelve of the twenty-nine positions translations, glides and mirrors are not enough: every regular subgroup of those twelve contains a rotation, a turn about a centre that happens to be empty.

Four positions with one rescue each #

The tightest positions are four, and they are reached by exactly one subgroup each.

All four have three points to a cell and live on the hexagonal lattice: a position on the mirrors of p3m1, a position on the mirrors of p31m, the two-fold rotation centres of p6, and the position of p6m whose points are the vertices of the kagome net. In every one of them the single regular subgroup is of type p3, with the parent’s lattice and three-fold rotation centres placed where the position has no points.

Why only p3 is visible in the arithmetic. With three points to a cell, the point group of a regular subgroup must have three operations for each cell of its lattice: three operations on the full lattice, six on a sublattice of index two, twelve on a sublattice of index four. A point group with three operations is the three-fold rotations, and with six it would need a sublattice of index two that a three-fold rotation carries onto itself, which the hexagonal lattice does not have. With twelve it is the whole of p6m’s point group, and every such subgroup contains a mirror or a two-fold rotation through one of the points. That leaves the three-fold rotations on the full lattice, and a group of that kind has its three-fold centres at three places in each cell. The p3 that works is the one whose three classes of centre all avoid the position’s points; every other choice of translation parts puts a centre on a point.

The kagome net was the one uniform net with a single regular subgroup, and it is one of these four. The census shows that it is not alone and not special: any net on any of the other three positions, whatever its edges, has the same single rescue. A net built on the two-fold centres of p6, with edges chosen so that its symmetry is exactly p6, is a Cayley graph of p3 and of nothing else.

What else reaches a position #

The other positions are reached in more ways, and the ways are worth seeing because each uses a different trick to fix nothing.

The two-fold position of pgg has two points to a cell, and its only regular subgroups are of type pg, made of translations and glides. A glide fixes no point anywhere in the plane, so a group of glides acts freely on everything, and the only question is whether it is transitive on the position, which the count of cosets settles. This is the one trick that does not depend on the points at all. Two positions are reached only by it.

The two-fold position of p4 has two points to a cell, and it is reached only by four-fold groups, two of them, both on the lattice of index two turned through forty-five degrees. On the parent lattice every four-fold group contains the half-turns about the position’s points, as the squares of its quarter-turns composed with translations. On the coarser lattice the translations that produced those half-turns are gone, and the half-turns that remain sit at the four-fold centres and at points the position does not use.

The mirror positions of p4m are reached in four ways each, including by a group whose mirrors are the parent’s mirrors that happen to miss the position. A point on a horizontal mirror line is fixed by that mirror, but not by a vertical one that passes elsewhere, and a subgroup that keeps only the mirrors missing the points acts freely.

The three-fold position of p31m, two points to a cell, is reached by a group of mirrors on a centred lattice, of type cm. Its mirror lines pass through the corners of the cell and between the two points, never through them, because the position’s three-fold centres are not on any mirror of p31m at all. This is the position whose points are the vertices of the honeycomb in a group lower than the honeycomb’s own.

The counts, and the minimum #

The distribution has the shape the arithmetic predicts. A position with one point to a cell has as many regular subgroups as there are subgroups whose lattice is the parent’s and whose point group’s every element misses the point, and that is many: twenty-four for the six-fold point of p6m, thirty-six for the four-fold point of p4m. As the points to a cell rise, the point group of a regular subgroup has to grow with them, while its operations must still fix nothing, and the counts fall. The six-point positions of p6m are reached two ways each, the four-point positions of p4m and p4g four or two. The minimum is one, at three points to a cell, and it is never zero.

Nothing in that shape forced the minimum to stay above zero. The four tight positions are each held up by one group, and the argument above shows how narrow the margin is: a single three-fold group on the parent lattice, with its centres in the one arrangement that misses the points. A plane group with a fourth position of the same kind, three points to a cell around its three-fold centres, would have had the same rescue; a plane group with three points to a cell around its centres and no subgroup of three-fold rotations would have had none. There is no such group among the seventeen, and that is the whole of why the answer is yes.

Counted twice, and refused twice #

The search decides regularity by a count of cosets and a test for fixed points. A second route decides it on actual positions. For the example subgroup of every position, take one point, apply every element of the subgroup with every translation of its lattice in a window, and record where the point lands inside a block of six cells by six. Regular means that every point of the position in the block is landed on exactly once and nothing lands anywhere else. All fifty-five examples pass, on blocks of thirty-six to two hundred and sixteen points, which checks the search’s own arithmetic by a computation that never asks what an index is.

Two claims are refused. The first is that a plane group acts regularly on its own special positions, which would make the whole census trivial: it fails on all fifty-five, because each point is fixed by its own site symmetry. The second is that a regular subgroup cannot contain a rotation, since every rotation fixes a point. It is half right, because every rotation fixes exactly one point, and the claim forgets that the point need not be a vertex. Twelve positions are reached only by subgroups with rotations, and those twelve are where the refused claim would have reported a Petersen graph that does not exist.

Where the census stops #

The step from a position to a net needs the net’s symmetry to be a plane group. A periodic net is a finite graph wound on a torus, as every net folds onto a torus described it, and its symmetries are automorphisms of an infinite graph before they are motions of anything; the restriction, with no lattice assumed found that even their rotation orders can be proved from the graph alone. For a net whose barycentric placement, the drawing in which every vertex sits at the average of its neighbours, puts no two vertices at one point, every automorphism of the graph acts on that drawing as an affine map, and the group of those maps is a plane group once the drawing is given a suitable metric. That is a theorem of Delgado-Friedrichs, and it is what licenses treating the vertex set as a Wyckoff position. A net whose barycentric placement collides can have automorphisms that permute coincident vertices with no isometry behind them, and the census says nothing about such nets. They exist, and whether any of them is vertex-transitive and not a Cayley graph is not settled here.

The census is about vertices, not edges. It says that every vertex-transitive plane net is a Cayley graph; it does not say of which group with which generating set, which depends on the edges. For any particular net the regular subgroups among the census’s list are the ones that are subgroups of that net’s own symmetry group, and the Cayley structure is then read off the edges at one vertex as the square net draws eleven groups did.

And a net must be connected. A periodic graph in two pieces can be vertex-transitive, and Sabidussi’s criterion is for connected graphs. A net in the sense crystallography uses is connected by definition, and the statement is about those.

Petersen, Sabidussi, and a question from the other end #

Julius Petersen drew his graph in 1898 as a counterexample in a different problem, about factorisations, and it has served as a counterexample to so many conjectures since that a book has been written about it. Its failure to be a Cayley graph is one of the cleaner ones: an automorphism group of order a hundred and twenty acting on ten vertices has stabilisers of order twelve, and no subgroup of order ten acts freely. Gert Sabidussi’s criterion of 1958 made the question of which vertex-transitive graphs are Cayley graphs a question about subgroups, and the finite version has been pursued since in the form of which numbers of vertices admit a vertex-transitive graph that is not a Cayley graph. Ten is the first.

Crystallography arrives at the question from the other end. A crystal chemist meets nets first and groups second, and how fast a group grows found that the sphere counts a chemist takes of a net, the ones counting outwards made, are the word counts a group theorist takes of a group. The census here says that, in the plane, the two descriptions always meet: every net that looks the same from every atom is the picture of some group, and the positions say which.

Still open: space, where a rotation fixes a line #

The same census in space runs over the special positions of the two hundred and thirty space groups, and the reason the plane always escaped does not carry over unchanged. In the plane a rotation fixes a single point, so a regular subgroup can contain any rotation whose centre avoids the vertices, and the four tight positions were rescued exactly that way. In space a rotation fixes a whole line, and a screw fixes nothing. A rotation in a regular subgroup must have an axis that misses every vertex along its entire length, which a vertex set lying on many axes of one kind can make impossible, while a screw axis through the same points remains available. Whether some special position of some space group has no regular subgroup at all, so that a net built on it with exactly that symmetry would be a three-dimensional Petersen graph, needs the space groups’ positions, their subgroups of bounded index and the same fixed-point test. The search has the same shape, larger by the factor a third dimension brings. It has not been run here.