A grid that loses two crosses every cell

Twelve cables survive a slack one counted the fewest cables that keep a three-by-three grid of square cells rigid when any one of them goes slack. Each cell’s diagonal is a cable, and a cable can only pull, so it braces its cell in one direction of shear. Rigidity reduces to a directed graph with one node per column of cells and one per row. A rising cable is an arrow from its column to its row, a falling one is an arrow back, and the grid is rigid exactly when every node can reach every other along arrows. Surviving a slack cable needs two arrows into and two out of every node. That gives twelve cables, in thirty-six placements.

A spare is worth what its pretension leaves then treated those placements as structures. The cables are pulled taut to a pretension, and a cable that goes slack hands its pull to the rest elastically. The Latin squares, with one rising, one falling and one crossed cell in every row and column, kept the most after a loss, up to 0.404 of the largest pretension. The essay ended with a builder who rates the cables for one loss and has bought a margin for one loss and not two.

A second margin is the obvious next purchase, and the obvious guess is that it costs a cable or two more. It costs six on three by three, and it takes away every choice. On four by four the choice comes back, and with it the question of whether the Latin squares’ advantage survives the second loss. It does, but only once the grid is pretensioned for the loss it is meant to survive.

The third arrow #

The count extends one level directly. Strong connectivity that survives any two arrows being removed needs at least three arrows into every node and three out of it. If a node had only two out, removing both would cut it off from everything it used to reach. So each of the grid’s columns needs three arrows out to the rows, and each of its rows needs three in. On a grid with $c$ columns and $r$ rows that is at least $3\max(c, r)$ arrows from columns to rows, and the same number back.

A cell can hold at most one arrow each way: a rising cable, a falling cable, or both crossed. On a three-by-three grid three arrows each way at each node is nine each way, eighteen in all, and the grid has nine cells, each of which can hold two. The count therefore asks for every arrow there is. The only placement of eighteen cables is the one with both diagonals of every cell, and nothing about it is a design decision.

The count is necessary, and the model checks that it is also the minimum. The fully crossed grid stays strongly connected with every one of its 153 pairs of arrows removed. Each of the eighteen placements of seventeen cables, which are the full grid less one cable, fails, and each has exactly two pairs whose loss is fatal. Removing one cable leaves a node with only two arrows out or in, and the pair that takes both of them disconnects it. Every placement with fewer than seventeen cables sits inside one of those eighteen, and adding cables never breaks survival, so none of them survives either.

The digraph is one route to that answer. The stress is another, and shares nothing with it but the list of cables. A cable grid is rigid when its rigidity matrix has full rank and a self-stress pulls on every cable, and that test, run on the crossed grid with each of its 153 pairs removed, finds every one rigid.

Every cell crossed, priced as a structure #

The crossed grid is the same kind of structure the earlier essay priced. Every bar and cable has the same axial stiffness per unit length. A load is any set of forces on the sixteen joints that is in equilibrium on its own, and the capacity of a pretension is the smallest load, in any direction, that slackens some cable, measured in units of the largest cable pretension. The pretension that maximises the capacity of the intact grid is a linear program over the grid’s self-stresses, of which the crossed grid has thirteen: 42 members against the 29 a rigid framework on sixteen joints needs, the surplus that a constraint that has been said already counts.

Pretensioned for the intact grid it carries 1.800, more than half as much again as the best twelve-cable Latin square’s 1.124. Six more cables buy that much. After its worst single loss it keeps 0.501. After its worst pair it keeps 0.087. No pair leaves another cable slack outright, so the grid stays a working structure whichever two cables go, but on its worst pairs it is close to the edge.

Choosing the pretension for the pairs instead changes the picture at the bottom of the curve and nowhere else. The worst pair now leaves 0.242, nearly three times as much, and the intact grid carries 1.695, six per cent less than its best. The curve starts flat: 32 of the 153 pairs leave exactly the worst value, which is what a pretension chosen for the worst case does. It lifts the worst to meet the next several until they bind together. The median pair hardly moves, 0.546 against 0.561.

The worst pairs share a shape. They lose the same diagonal in the two corner cells at the ends of one edge of the grid, the rising cables of both bottom corners for instance. The pretension chosen for them pulls hardest, at the full pretension of one, on the diagonal of each corner cell that points at the grid’s centre, and least, at 0.875, on the centre cell’s two. The pretension best for the intact grid pulls hardest on the middle cells of the edges instead.

Four by four, where the choice comes back #

A four-by-four grid has sixteen cells and needs twelve arrows each way for two losses, so four cells in each direction go without. Every column then has three rising cables among its four cells, and every row three, so the four cells left without a rising cable are one per row and one per column: the positions of a permutation. The same is true of the falling cables. A placement is two permutations, one for the missing rising cables and one for the missing falling ones, and there are $24 \times 24 = 576$.

They fall into four families by how many positions the two permutations share. A shared position is a cell with neither cable, empty. Two permutations can share no position, one, two or all four (three is impossible, because a permutation that agrees with another in three places agrees in the fourth). The families number 216, 192, 144 and 24, and they have eight, nine, ten and twelve crossed cells. The family with no empty cell is the analogue of the Latin squares: every row and column has one rising cell, one falling cell and two crossed.

At one loss, four by four was where the count stopped being enough. A grid could meet it at every node and still split into two blocks of two columns and two rows, joined by a single arrow each way, a waist that one slack cable cuts. At two losses the count rules that out by itself. A block of two columns and two rows has four cells, so it can hold at most four arrows from its columns to its rows and four back. Its two columns need six arrows out between them, so at least two go to rows outside the block. Its two rows need six arrows out as well, so at least two go to columns outside it. At least four arrows leave the block, by the same argument four enter it, and no pair of losses can cut it off. This is the test the loops are in the graph made on an undirected drawing, asked of every block of a directed one. The model checks all 576 by the digraph and every one survives. For two losses on four by four, the count is the whole rule.

The model also checks that the evaluator it prices them with is right. Pairs of losses are priced by inverting the grid’s stiffness once and treating each pair’s removal as a change of rank two, which turns the 31,000 reduced structures of the 113 classes below into a few seconds of work. A fresh inverse of each reduced structure agrees with it on sampled pairs to $10^{-9}$. The one-cable evaluator of the earlier essay, which shares nothing with it but the frame, agrees on single losses. The square’s eight symmetries take the 576 placements into 113 classes, and placements related by a symmetry are checked to price the same.

The intact grid’s pretension fails the second loss #

Priced first with the pretension best for the intact grid, the four-by-four bracings look like a slightly better version of the twelve-cable ones. They carry 1.14 to 1.37 intact, in every family. Then the pairs are taken away.

On 111 of the 113 classes some pair of losses leaves another cable slack at once, with no load at all, between 5 and 24 pairs of the 276. Slack cables are what the bracing was designed to tolerate. But a cable slackened by the redistribution of two others’ pull is a third loss, beyond the margin the cables were counted for. Only two classes escape, six bracings in all, both in the family with four empty cells, and after their worst pair they keep 0.007 and 0.018, a sliver.

So a bracing counted for two losses and pretensioned the obvious way does not in practice survive two losses. The count guarantees that the remaining cables could hold the grid, if they were pretensioned for the situation they find themselves in. It cannot guarantee that the pull redistributed from the two that went leaves them in that state. The three-by-three crossed grid escaped this because it had no choice of placement and a great deal of redundancy. The four-by-four bracings have exactly the redundancy the count requires and no more.

Pretensioned for the pairs #

The repair is the one the earlier essay found for single losses, applied one level up. Choose the pretension to maximise the capacity left after the worst pair, rather than the capacity of the intact grid. Each pair maps the pretension linearly onto the reduced grid’s forces, so this is again a linear program over the self-stresses. It has one constraint for every remaining cable after every pair, about six thousand on four by four, and it is solved by adding constraints a few at a time, the most violated first, until the answer violates none.

Every bracing keeps something now, between 0.102 and 0.198 after its worst pair. The families overlap at the bottom, where every family’s worst bracing keeps about 0.10. They separate at the top. The family with no empty cell reaches 0.198. The families with one and two empty cells stop at 0.159 and 0.160, and the family with four empty cells at 0.137. The six best classes in the whole census all have no empty cell.

The trade with intact capacity runs the other way. The four-empty family keeps 0.81 to 1.05 intact under the pretension chosen for the pairs. The others keep 0.49 to 0.86, about half of what they carry when pretensioned for the intact grid. A pretension for losing two costs the four-by-four bracings far more of their intact capacity than it cost the crossed three-by-three grid, which gave up only six per cent.

The best bracing overall is unusually regular. All four corner cells and all four centre cells are crossed, and each edge’s two middle cells hold one rising cable and one falling cable alone. The placement is symmetric under all eight of the square’s symmetries, so it is its own class of one. It crosses exactly the corners whose loss the crossed three-by-three grid found most dangerous. The earlier essay’s Latin squares were the analogue at one loss, and their advantage was a factor of four over the worst family. Here the advantage of the best Latin-like bracing over the best of the four-empty family is less than half as much again, and a badly chosen Latin-like bracing is no better than a badly chosen bracing of any family.

What a second margin costs #

The numbers line up into a single ledger.

On three by three, the step from one margin to two is from twelve cables to eighteen. The worst-case capacity, each pretensioned for the loss it is designed for, goes from 0.404 after one loss to 0.242 after two. The extra six cables make the intact grid stronger, at 1.695 against 0.998 for the Latin square pretensioned for its loss. They do not buy a second loss at the price of the first.

On four by four, the step is from sixteen cables to twenty-four, and the best bracing keeps 0.198 after its worst pair. The larger grid has more cables but less redundancy per cable, since the count leaves it exactly three arrows each way at every node and nothing over. The three-by-three crossed grid is not efficient, but its eighteen cables are all the cables it can hold, and that saturation is what makes it forgiving.

For a builder, the lesson is in three parts. Count for the number of losses to be survived, three arrows each way for two. Pretension for those losses and not for the intact grid, because the intact grid’s best pretension fails the second loss on all but six of the 576 four-by-four bracings. Then prefer bracings with no empty cell, while knowing that the count does not make them good and that each must still be priced.

Two routes, and where they part #

The count, a cable is half a brace and the census essays all asked yes-or-no questions of a directed graph. The structure asks how much, and the answers diverge in a way the graph cannot see. Every one of the 576 bracings is equally good to the graph, which says each survives any two losses. As structures, all but six of them fail under the obvious pretension, and under the right one their capacities differ by a factor of two.

That divergence is the same one the count says how many and not where found for bars, now in a sharper form, and the same one the price is one self-stress found when a framework’s play was priced rather than counted. A count of constraints says whether a structure can be rigid. It cannot say how well the structure carries load, and with cables it cannot even say whether a given pretension will leave the structure in the state the count assumed. Which diagonal rigidifies a grid began this line of questions with a single brace per cell. With two losses to survive the grid must be braced almost everywhere, and what remains to be chosen is mostly a pretension.

What this does not settle #

Re-tensioning after a loss. Every capacity here is the one left when the lost cables’ pull is shared out elastically and nobody adjusts anything. A grid re-tensioned after a loss can do better, and the earlier essay measured that bound for one loss. For pairs it was not computed.

Larger grids. On four by four, the count is the whole rule for two losses. Whether that holds on five by five, where blocks of two by three can form, is not tested. The argument about blocks suggests that a waist needs a block whose nodes can find three arrows each way inside it, which needs blocks of at least three columns and three rows.

The pretension chosen for the pairs is chosen for the pairs only. It was not asked to do well after single losses, and the trade between capacity after one loss and after two was not traced.

Still open: a grid that loses a cable and a bar #

Every loss here was a cable going slack, and the bars of the frame were treated as permanent. A real grid can also lose a bar, to a failed joint or a buckled member, and a bar is a constraint in both directions, worth an arrow each way in the digraph at once.

The distinct argument would add bar losses to the count. It would ask for the fewest cables that keep a three-by-three grid rigid after any one cable and any one bar are lost together, and whether the answer sits between the twelve of one loss and the eighteen of two. The pricing would follow the same pattern as here, with the frame’s members now among the removable ones. It would also say whether the bars of the frame’s interior, which every cell shares with a neighbour, are more dangerous to lose than any cable.