A game that decides what counting only bounds

The count that promises a mechanism subtracts constraints from freedoms and reads the difference as the number of ways a framework can move. The mechanisms a count cannot see shows it failing. This essay is about the repair, which in the plane is complete and is an algorithm rather than a theorem to be applied by hand.

What the count assumes #

Maxwell’s count is 2n − e in the plane: two freedoms for each of n joints, one constraint for each of e bars. Three of the freedoms are always the rigid motions of the plane, so a framework with exactly three is rigid and one with more has a mechanism.

The count assumes the e constraints are independent. When they are not — when a bar is added to a part of the framework that is already rigid — the subtraction removes a freedom that no bar took away.

The failure is not rare and it is not subtle. It happens whenever any part of a framework is braced more than it needs to be, which in a real structure is most of the time — a triangulated panel with an extra tie, a joint with a diagonal in both directions. And because the count nets redundant bars against mechanisms, an over-braced part and a floppy part in the same structure cancel, and the total reports neither.

It is worth being exact about what a freedom is here, because the number three does a lot of work. A framework of n joints in the plane has 2n coordinates; a rigid motion — two translations and a rotation — changes all of them without changing any bar length, so three freedoms are present in every framework however heavily braced. A framework with four has one internal freedom, a way of moving that changes the shape rather than the position, and that is a mechanism. So the pebble game’s output is not a number of mechanisms but a number of freedoms, and the mechanisms are what is left after three are set aside.

The cancellation is worth one more sentence, because it is the practical failure. A structure with three redundant bars in one region and three mechanisms in another has 2n − e exactly equal to three, and reports as minimally rigid. Nothing about the count is wrong arithmetically; the two errors are real and they are equal and opposite, and the number that comes out is the number a rigid structure would give. That is the shape of failure this essay exists to replace: not a bound that is loose, but an answer that is confidently the wrong one.

The condition, and the algorithm that is really the condition #

Laman’s theorem states the repair exactly. A graph on n ≥ 2 joints is minimally rigid in a generic placement precisely when it has e = 2n − 3 bars and every sub-framework on n′ joints has at most 2n′ − 3 bars.

The second clause is what Maxwell’s count leaves out, and checking it as written means examining every subset of the joints — 2ⁿ of them, which is not a check anybody runs.

The pebble game checks it without doing that. Give every joint two pebbles. Take the bars in any order; to admit one, four pebbles must be gathered onto its two ends, moved there along bars already placed. If four can be gathered the bar is independent and consumes one pebble; if they cannot, the bar is redundant and is discarded. When the bars run out, the pebbles that remain are the framework’s freedoms.

Two things about the threshold are worth stating, because the wrong one is the tempting one. Four pebbles are needed to admit a bar, and three is what a minimally rigid framework is left holding at the end. Setting the test at three accepts the sixth bar of a complete four-joint framework — the whole structure’s three remaining pebbles can be gathered onto its two ends — and the redundancy goes unreported. The two threes are different threes, and the algorithm is wrong if they are confused.

The other is that the answer does not depend on the order the bars are taken in. Which particular bar gets refused does, and how many get refused does not. That is a consequence of the underlying structure being a matroid — the independent sets of bars are the independent sets of a matroid on the edge set, and every maximal independent set of a matroid has the same size. So the game is greedy and greedy is correct here, which is the same reason a spanning tree can be built by taking edges in any order.

The cost is worth knowing because it is what makes the repair usable rather than merely correct. Gathering pebbles for one bar is a search backwards through the bars already placed, so it costs at most the number of joints; there are e bars; the whole game is therefore proportional to n · e, which for a framework of a few thousand joints is milliseconds. Checking Laman’s condition as written would visit every subset of the joints. The distance between those two costs is the entire reason the condition is stated one way and computed another, and it is the same distance as between a definition and an algorithm anywhere else.

Checked against something that shares no code #

A combinatorial algorithm answering a question about geometry deserves a second opinion, and there is one available.

The rigidity matrix has a row for each bar and two columns for each joint, holding the components of the bar’s direction with opposite signs at its two ends. Its rank is the number of independent constraints, so 2n minus that rank is the number of freedoms — the same number the game counts in pebbles, arrived at with no shared code and no shared idea.

They agree on all nine frameworks. That agreement is what makes Laman’s theorem visible in this collection rather than quoted: one side of it is a statement about a graph and the other about a matrix, and a mistake would have to be made twice, in two different languages, to survive.

A third computation is available and is not run here, and saying why is part of the argument. The rank could be taken at symbolic coordinates rather than random ones, which would give the generic answer exactly rather than with probability one. It is not done because the two computations here are already independent in the way that matters — one is combinatorial and one is numerical — and because taking the rank at random coordinates has a property symbolic computation does not: it is the same computation an engineer performs on an actual structure, so where it disagrees with the game, the disagreement is about a real placement rather than about a method. What six lengths decide and nine do not makes the same choice for the same reason, checking a determinant against coordinates rather than against another determinant.

The framework the count gets backwards #

One case is worth its own figure, because it shows the error going in the direction that matters.

Take two rigid bodies and join them at a single point. They can turn against each other about that point, so the assembly has one mechanism and four freedoms in total. Build each body as a complete framework on four joints and it carries six bars where five would do, so the pair carries two redundant bars. Maxwell counts fourteen freedoms minus twelve bars and reports two — a number below three, which is the signature of over-constraint.

So the count does not merely fail to see the mechanism. It reports the opposite condition, and it does so because the two redundant bars and the one mechanism are subtracted from each other. A structural engineer reading 2n − e = 2 would conclude the frame is stiffer than it needs to be and consider removing a member. The frame is a hinge.

That is the reason the repair is worth an algorithm. A bound that is sometimes loose can be used with care; a count whose error can reverse its conclusion cannot be used at all without a second computation, and the second computation is this one.

There is a second reason the hinge is the right example, and it is about how such a structure arises. Nobody designs two complete four-joint bodies sharing a point. What people do design is a structure of rigid panels connected at their corners, and that is the same thing: each panel is internally over-braced, because a panel is rigid and a triangulated panel with an extra member is more so, and a corner connection is a shared joint. So the configuration Maxwell’s count reverses is not a curiosity constructed to break it. It is the ordinary case, and the count is at its least reliable exactly where structures are most often built.

Where a graph stops being enough #

Laman’s theorem is about a graph, and a graph does not record where the joints are.

The theorem says a Laman graph is rigid in a generic placement — for almost every choice of coordinates, in the precise sense that the exceptions form a set of measure zero. Particular placements can be more flexible than the graph allows: three collinear joints, a parallelogram, four joints on a circle in the right configuration. No algorithm that reads only the graph can see any of it.

That is not a defect in the pebble game; it is the boundary of what a combinatorial answer can be. The game returns the generic answer, and the generic answer is right almost always and is wrong exactly at the placements a designer is most likely to choose, because those are the symmetric ones. A structure built at a special position is a structure whose combinatorial analysis is not about it.

The right pairing is therefore the game for the graph and the rank for the placement, and both are computed here for exactly that reason. Where they disagree, the placement is special and the disagreement is the discovery.

The set of special placements has a description worth carrying, because it explains why they are the ones a designer meets. A placement is special when the rigidity matrix loses rank, which happens when a determinant of its minors vanishes — so the special placements are the zero set of a polynomial in the coordinates, and a symmetric arrangement is far more likely to sit on such a set than a random one is. Collinearity, parallelism and equal lengths are all polynomial conditions, and all three are things a designer imposes on purpose. A fold that keeps its symmetry is about the same coincidence from the other side, where the symmetry is the reason the mechanism exists rather than the reason the analysis fails.

What this says about a structure #

Two things, and the second is why the algorithm belongs on a crystallography site at all.

The first is about counting rigid units. A framework structure — corner-sharing tetrahedra, a metal–organic framework, any of the objects whose flexibility is discussed as a count of rigid units and shared corners — is a bar-and-joint framework, and the count applied to it is Maxwell’s. Every caveat above applies: an over-linked region and a floppy region cancel, and the total is a bound rather than a number of modes. The mechanisms a count cannot see is that failure measured on periodic nets.

The second is that the plane is where this works. There is no Laman theorem in three dimensions: the obvious analogue — e = 3n − 6 with every subgraph satisfying e′ ≤ 3n′ − 6 — is false, and the standard counterexample is the double banana, two rigid octahedra sharing two joints, which satisfies the counting condition on every subgraph and hinges about the line through the shared pair. So the exact answer available here is available in the plane and nowhere else, and three-dimensional rigidity is decided by rank computations at generic coordinates rather than by any known combinatorial rule.

The third of those is the one that carries the argument. A bound that is always in the same direction is usable — a lower bound on the freedoms would let a designer trust that a structure is at least as stiff as counted. The hinge shows the error is not signed, so nothing about a count can be relied on in either direction, and that is why the game is not an optimisation of the count but a replacement for it.

There is a third reading, and it is the one that connects this to the collection’s other counting arguments. A polyhedron is two properties of a graph decides whether a graph is a polyhedron by two conditions on the graph alone, one of them a connectivity condition tested by removal. The pattern is the same: a geometric question, an answer that turns out to depend only on the combinatorics, and an algorithm that decides it. The difference is what “only” means. Steinitz’s conditions decide their question outright; Laman’s decide it for almost every placement and leave the exceptional ones to a different computation. Knowing which kind of theorem is in hand is knowing whether an answer about a graph is an answer about an object.

Where this stops #

The three-dimensional case is open in exactly the sense described: no combinatorial characterisation of generic rigidity in space is known, and the pebble game generalises to (k, l)-sparsity for other pairs without generalising to the question. What is known in space, and used in practice, is that the same pebble game with three pebbles a joint decides body-bar rigidity — frameworks of rigid bodies joined by bars — which is a different question that happens to be tractable.

One extension the game reaches and this file does not run is worth naming, because it is what makes the algorithm useful on a structure rather than on an example. The same machinery identifies the rigid clusters — the maximal sets of joints that move rigidly together — by asking, for each bar, whether it could be inserted a second time. That decomposition is what a structural analysis actually wants: not one number for the whole assembly but a map of which parts are stiff and where the freedoms live. A mechanism that is a wave is the periodic version of the same question, where the clusters repeat and the mechanisms are labelled by a wavevector rather than counted.

Nor does anything here address stress. A redundant bar is one that carries no new constraint, and it is also a bar that can carry load in a self-stressed state; the two are the same phenomenon read from opposite sides, and the count of self-stresses is the other half of the rank computation. The mechanisms a count cannot see is where that half is done.

One more limitation belongs with that. The game decides generic rigidity, and generic is a statement about the placement, not about the bar lengths — a framework whose bars are all of equal length is still generic if its joints happen to sit in general position, and one with wildly different lengths can be special. That distinction is easy to lose because the two things are usually adjusted together, and it matters here because the special placements above were produced by moving joints and not by changing any length. The lengths determine the placement only up to the finitely many possibilities what six lengths decide and nine do not counts, and the game does not read them at all.

And the frameworks here are small and chosen. Nine graphs establish the statements the essay makes and are not a survey; the algorithm runs in time proportional to the number of joints times the number of bars, so nothing about the size is a limit, and what is being illustrated is the shape of the answer rather than its reach.