The placement nobody chose

A net has no coordinates. That was the point of throwing the distances away: what is left is a graph with integers on its edges, and a graph does not know where anything is.

So drawing a net means putting something back, and whatever is put back is a choice — the same difficulty as choosing a unit cell, and with the same consequence, that two people drawing the same object may disagree about what it looks like. There is one construction that escapes the difficulty, and it is short enough to state in a sentence.

Put every vertex at the average of its neighbours.

The equation, and why it has an answer #

Written out, the rule is one equation per vertex. If vertex i has degree d, and its neighbours sit in the cells the voltages name, then

$$d\,p_i - \sum p_{\text{neighbours}} = \sum \text{voltages}$$

with the sum on the right over the half-edges leaving i. The left-hand side is the graph Laplacian of the quotient graph applied to the unknown positions; the right-hand side is a vector of integers read off the description.

That system is singular, and it must be: adding the same constant to every position is another solution, because the construction cannot know where the origin is. Pin one vertex and the rest are determined. The solution exists for every connected net, and it is unique up to that translation.

Two things about the arithmetic are worth stating, because both are why this can be done here at all.

It is exact. The Laplacian is an integer matrix and the voltages are integers, so the answer is a vector of rationals with small denominators — thirds for the honeycomb, halves for the kagome net, fifths for the star net. There is no numerical solve and no tolerance.

It is in the lattice basis. Fractional coordinates, against the translations the net was quotiented by, which is exactly the coordinate system this collection decides symmetry in. So the placement can be handed straight to the detector without a conversion, and the conversion is where exactness usually goes.

Why the group of this drawing is the group of the net #

Here is the argument that makes the whole construction worth doing, and it is short.

Let σ be an automorphism of the net that respects the translations. It permutes the vertices and it permutes the equations, because the equation at vertex i is written entirely in terms of i’s neighbours and σ carries neighbours to neighbours. So σ carries solutions to solutions. But the solution is unique up to a translation — therefore σ acts on the plane as an affine map.

An abstract symmetry of a graph has become a motion of the plane, by nothing more than the uniqueness of a linear solve.

The consequence runs the other way too, and it is the sharper half: no other drawing of the same net can have more symmetry than this one, because any symmetry of any drawing is in particular an automorphism of the graph, and every automorphism of the graph is realised here. The barycentric placement is the maximally symmetric drawing of a net, and the group it has is what deserves to be called the net’s group.

Detecting it, and the trap on the way #

Handing the placement to the detector is not quite enough, and the reason is the failure mode this collection has been warning about from its first essay onwards.

The point set of vertices alone can be more symmetric than the net. The triangular net has one vertex per cell; its placement is a single point, and a single point has every symmetry there is. Adding the edge midpoints helps — a motion that permutes the vertices need not respect the edges, and the midpoints usually make the difference — but it introduces a fault of its own: the midpoints of the triangular net’s three edges are the three half-lattice points, and that eight-point set has translations of half a cell which the net does not have. Detected on the points alone the group came back four times too large.

So every operation the detector returns is put through a second test: does it carry every edge of the quotient graph to an edge? The map on vertices is read off the placement, the cell each image lands in is kept rather than reduced away, and the induced map on edges is compared with the edge list. Operations that fail are dropped.

This is the accidental-symmetry problem in a new guise, and it is worse here than for a pattern, because a net has no motif to make asymmetric. A pattern figure can be protected by drawing a comma instead of a dot; a net cannot, because its vertices are points and nothing else. The only protection is to ask the graph.

That last point deserves emphasis, because it is the one that catches people out. Asking what is the symmetry of this net without saying what metric it is drawn at is asking an incomplete question. The honest answer is the maximum over metrics, and taking the maximum is a computation rather than a convention.

Where the construction fails #

A rule with no exceptions is usually a rule nobody has tested. This one has an exception and it has a name.

The placement can put two distinct vertices at the same point. Suppose two quotient vertices have exactly the same neighbours in exactly the same cells: their equations are then the same equation, their averages are the same average, and the solve puts them on top of one another. A net like that is called unstable, its barycentric drawing is not a drawing of it, and everything the argument above claims fails — there is no injective map from vertices to points, so an automorphism has no plane to act on.

Unstable nets are rare and they are not pathological curiosities: Delgado-Friedrichs found them while building the software that does this identification for real structures, and the software has to test for them because a structure database will eventually contain one. A limitation with no example is a limitation nobody believes, which is why one is kept here.

The related failure is an edge that collapses to zero length, which happens for the same reason and is caught by the same test.

What this makes possible #

With a placement and a group in hand, the round trip this collection performs on patterns becomes available for nets, and it is if anything cleaner.

Take a net. Forget everything but the graph. Solve the Laplacian. Hand the point set to a detector that knows nothing about where it came from and enumerates every operation the lattice permits. Filter by the edge test. What comes back is a group, and it was not put in: the input was a list of integers with no geometry in it whatever.

The groups that come back are also a check on the enumeration this whole site rests on. Every one of them is one of the seventeen; none of them is anything else; and the identification is made by an invariant that a change of origin cannot touch — the set of linear parts together with the multiset of kinds, rotation against mirror against glide.

A change of origin is not the only thing that must not touch it, and the other one was missed for five phases. A change of basis does not alter the net and does alter every linear part, so an identification made by comparing linear parts against a fixed list is an identification of the description. What that cost, and the form of the repair, is an essay of its own; the summary is that a net is now given the basis in which the quadratic form its own edges make is reduced, before anything is detected at all.

That identification had to be got right twice. Comparing operations directly fails, because the origin of a barycentric placement is wherever the first vertex was pinned, which is a vertex and never a rotation centre. Searching for the offset on a grid of twelfths fails too, and the star net is why: its placement comes out at fifths, its symmetry elements with them, and a grid of twelfths reports a group of order twelve that is none of the seventeen. The invariants avoid the search entirely, and they are invariants of the group rather than facts about a drawing of it — which is the right kind of thing for a function whose input has no drawing.

One construction, and the one it is named after #

This collection has met a construction of this shape once before, and the resemblance is exact enough to be worth setting out.

The Wigner–Seitz cell is the answer to the same complaint about unit cells: a lattice has infinitely many cells, crystallography picks one by rule, and two people who agree about the lattice can disagree about the cell. The Wigner–Seitz construction escapes by choosing nothing — the set of points nearer to one lattice point than to any other needs no basis, no origin beyond the point itself, and no convention — and it has the lattice’s full point symmetry rather than the part a basis happens to display.

The barycentric placement is the same move made for a graph. A net has infinitely many drawings; this construction chooses none of them; and the drawing it produces has the net’s full symmetry rather than the part a hand-drawn picture happens to display. In both cases the payoff is the same sentence: two people who agree about the object cannot disagree about the answer.

The difference is that a Voronoi cell is a piece of geometry built from geometry, and this is a piece of geometry built from no geometry at all. What goes in is a list of integers.

The physical reading #

The word barycentric is combinatorial and the construction has a physical reading that is worth having, because it is how the placement is usually described in chemistry.

Replace every edge by a spring of zero natural length and let the framework relax, holding the cell fixed. Every vertex ends up where the forces balance, which is at the average of its neighbours; the placement is the equilibrium configuration of a network of identical springs. That is why Delgado-Friedrichs and O’Keeffe call it the equilibrium placement, and why the software that computes it is called Systre — from symmetry, structure and recognition.

It also explains the shape of what comes out. Equilibrium under identical springs is the most even arrangement available, so the placement makes the net look as regular as it can be made to look — which is not a coincidence but the maximum-symmetry theorem, seen from the mechanical side.

The mechanical picture also makes the instability easy to see. Two vertices with identical neighbourhoods are two beads on the same set of springs, and they relax to the same place because nothing distinguishes them. The extreme case in this collection’s registry is a net of five quotient vertices in a ring, each carrying the same pair of loops: the springs pull all five to a single point, and the collision test reports four collided pairs — each vertex against the one it was distinguished from — rather than the single pair the smallest unstable example produces. The net has no drawing at all, and so it is given no group and appears in no figure that needs coordinates. It is not a defect in the construction. The construction is telling the truth about a net that has no most-symmetric drawing, and the honest response is to refuse a group rather than to report the group of whatever picture the collapse produced.

The denominators are worth a sentence, because they are the clearest sign that nothing here is approximate. The solve is a system of linear equations with integer coefficients, so its solution is exact in rationals, and the denominators that come out are properties of the net. The honeycomb’s second vertex lands at (⅓, ⅔); the kagome net’s three land on halves; the star net’s six land on fifths, at (0, ⅘), (⅕, ⅖) and their relatives. Nobody chose a fifth. It is what a six-by-six integer system returns, and it is also the reason a symmetry search on a grid of twelfths cannot find the star net’s elements — the elements are at fifths and twelfths do not reach them.

The cell the placement does not choose #

The construction fixes where the vertices sit inside a cell and says nothing about the cell’s own shape. A net has no metric, so the two translations may be any two independent vectors, and every choice gives a different drawing of the same placement.

That is not a loose end; it is the same freedom one level up, and it has the same kind of answer. Choose the metric that the net’s own group preserves. The automorphisms act on the translations as integer matrices, and asking for a quadratic form those matrices leave invariant is asking for a fixed point of an averaging — take any form and average it over the group, and what comes out is invariant by construction.

That is exactly the projector this collection uses everywhere else. The invariant metric is the degree-two generator of the net’s invariant ring, and where the group has a rotation of order three or more it is unique up to scale, so the cell’s shape is determined. Where the group is smaller the form is not unique and a choice remains — which is why the honeycomb comes out hexagonal with nothing chosen and a low-symmetry net comes out at whatever metric was supplied.

So the drawing is canonical in two stages and the stages are different in kind. The vertices’ positions are determined by the net alone, exactly, in rationals. The cell’s shape is determined by the net’s group, and only as far as that group forces — which is why the essay’s claim is about the symmetry rather than about the picture.

The equation is a harmonic condition #

The rule put every vertex at the average of its neighbours has a name outside this subject, and knowing it explains why the solution is unique and why the matrix is the one it is.

A function on a graph whose value at every vertex is the average of its neighbours’ values is harmonic, and the Laplacian is the operator saying so. The placement is therefore a harmonic embedding: each coordinate is a harmonic function on the net, with the voltages supplying the periodicity that stops the only solutions being constants.

That framing supplies the uniqueness argument for nothing. A harmonic function on a connected graph is determined by its boundary values, and on an infinite periodic graph with the coordinates required to be periodic modulo the translations, the boundary is the periodicity itself — so the solution is unique up to the additive constant the essay already identifies as the choice of origin.

It also gives the physical reading a second form. A harmonic function is the equilibrium of a diffusion, so the placement is where a random walk’s expected position sits — each vertex at the average of where its neighbours are, which is the same equation as the springs and the same equation as the average. Three descriptions, one linear solve, and the reason the construction is canonical is that all three of them mention nothing but the graph.

What it costs #

The whole computation is a linear solve on a matrix whose size is the number of quotient vertices — two for the honeycomb, six for the star net — followed by a detection over a point set of vertices and edge midpoints.

That is worth noticing, because it is the reason this can be done to every entry in a structure database rather than to a few illustrative examples. The infinite object never appears. Nothing is unfolded, no window is chosen, no cutoff radius is picked; the answer for an infinite graph with an infinite symmetry group comes out of a system with as many equations as the quotient has vertices.

The detection is the expensive half and it grows as the cube of the point set, which is why the tables in these essays state the size of everything they were run on. Where a computation was bounded — a ladder of cutoffs that stops before the point set gets large, a search over basis matrices with entries up to four — the bound is printed beside the answer rather than left in the code, on the principle that a number produced by a bounded search is a different kind of number from a theorem.

What it does not settle #

Three limits, each of which the essays around this one take up.

It does not settle the metric. The placement gives fractional coordinates, and the cell they sit in is still free — a honeycomb drawn on a stretched hexagonal cell is the same placement in the same coordinates and a different picture. What the maximum over metrics settles is which type of cell gives the most symmetry, and that is all.

It does not settle whether the net is realisable. A framework of atoms has bond lengths and angles that real chemistry constrains, and the equilibrium placement respects none of them. It is a statement about the graph.

It does not settle where the net came from. A net is not in a list of atomic coordinates; a net comes from deciding which atoms are bonded, and that is a decision — which is the next rung, and the one place in this ladder where an arbitrary number has to be chosen and admitted to.

One more case is worth quoting because it is the one a reader can check against a picture they already know. The net whose faces are a square and an octagon has four vertices in its quotient, and the solve puts them at (0, 0), (¼, ¼), (0, ½) and (¾, ¼) — quarters, arrived at by solving a four-by-four system and not by anybody deciding that the squares should be regular. The group detected from those four points is p4m, which is the group of the tiling everybody draws by hand. The construction agrees with the drawing, and the point is that it did not consult it.

Where this ladder goes next #

The fourth rung goes back to the beginning of the chain: a net has to come from somewhere, and where it comes from is a cutoff. Two rungs further on, the same nets are read as frameworks of rigid bars and the equilibrium placement becomes the configuration whose freedoms are counted.

The construction also has a use outside this ladder. The restriction — the theorem that a periodic pattern can only have rotations of order one, two, three, four and six — turns out to be provable about nets with no length anywhere in the argument, and the linear parts detected here are the integer matrices the proof is about.