Algorithms for three-dimensional rigidity analysis and a first-order percolation transition

A fast computer algorithm, the pebble game, has been used successfully to analyze the rigidity of two-dimensional (2D) elastic networks, as well as of a special class of 3D networks, the bond-bending networks, and enabled significant progress in studies of rigidity percolation on such networks. Application of the pebble game approach to general 3D networks has been hindered by the fact that the underlying mathematical theory is, strictly speaking, invalid in this case. We construct an approximate pebble game algorithm for general 3D networks, as well as a slower but exact algorithm, the relaxation algorithm, that we use for testing the new pebble game. Based on the results of these tests and additional considerations, we argue that in the particular case of randomly diluted central-force networks on bcc and fcc lattices, the pebble game is essentially exact. Using the pebble game, we observe an extremely sharp jump in the largest rigid cluster size in bond-diluted central-force networks in 3D, with the percolating cluster appearing and taking up most of the network after a single bond addition. This strongly suggests a first-order rigidity percolation transition, which is in contrast to the second-order transitions found previously for the 2D central-force and 3D bond-bending networks. While a first order rigidity transition has been observed previously for Bethe lattices and networks with “chemical order,” here it is in a regular randomly diluted network. In the case of site dilution, the transition is also first order for bcc lattices, but results for fcc lattices suggest a second-order transition. Even in bond-diluted lattices, while the transition appears massively first order in the order parameter (the percolating cluster size), it is continuous in the elastic moduli. This, and the apparent nonuniversality, make this phase transition highly unusual.

Figure 1

Bond-bending networks in 3D. (Top) The fractions of sites belonging to the percolating rigid cluster (open circles) and the percolating stressed region (filled circles) as functions of mean coordination $⟨r⟩$ for the case of random bond dilution of the diamond lattice. The results are averages over 11 networks of 125 000 sites each. Rounding near the transition is due to finite-size effects. (Bottom) The number of floppy modes per degree of freedom $f=F∕3N$ for randomly bond-diluted amorphous silicon networks (circles) and diamond lattices (diamonds). The dashed line is the Maxwell counting result. The inset shows the second derivative of $f$ with respect to $⟨r⟩$. The upper panel is from Ref. 36; the lower panel is adapted from Ref. 3.

Figure 2

(Top) Sketch of a random bond network: sites are connected at random, regardless of the distances. This network consists of two- and three-coordinated sites (gray and black, respectively). (Middle) The fraction of sites in the percolating rigid cluster as a function of $⟨r⟩$ for a bond-bending random bond network consisting of two- and three-coordinated sites in 3D. The solid line is theoretical, the circles are the result of pebble game simulations. The transition occurs at ${⟨r⟩}_c$. (Bottom) The theoretical number of floppy modes per degree of freedom, $f=F∕3N$, for a bond-bending random bond network consisting of two- and three-coordinated sites in 3D. Note the break in the slope at the transition. These panels are adapted from Refs. 3, 37.

Figure 3

Example of a network (the double-banana graph) for which the generalization of the Laman theorem fails. The dashed line is a hinge around which the two bananas can rotate.

Figure 4

Example of a network with a rigid cluster (shown with thinner lines) that is no longer rigid when taken in isolation from the rest of the network. The dashed line is a hinge.

Figure 5

Example of a network with a noncontiguous rigid cluster consisting of sites marked 1, 2, and 3.

Figure 6

Example of a network in which the stressed region is not an induced subgraph, since the thin constraint is the only one that is not stressed.

Figure 7

Example of a network for which different failed pebble search regions do not coincide and the intersection of the regions needs to be taken to identify the stressed region correctly. The constraint marked “TEST” is being inserted. Six pebbles are freed at its ends (shown). No other free pebbles are present, so search for the seventh free pebble cannot succeed. An attempt is made to free the seventh pebble at each neighbor of site 1. When this is done at the site marked 2, sites 3, 4, and 5 are all passed when searching for a pebble. But when this is done at one of the sites marked 3, 4, and 5, site 2 is not passed, since the constraints leading to this site are not covered by pebbles belonging to either of the sites 3, 4, and 5. Clearly, only thick constraints are stressed, and thus the stressed subgraph should not include site 2, so the intersection of failed search regions needs to be taken to identify the stressed region correctly.

Figure 8

Sketch of the simplest (“trivial”) implied hinge. Constraints 1-2 and 1-3 are present, but there is no constraint between sites 2 and 3. A body on the left denotes a rigid cluster that is rigid by itself. The triple 1-2-3 is also a rigid cluster, but is not rigid by itself. Line 2-3 is an implied hinge. In many cases, this is the most frequent situation involving an implied hinge. It will not cause errors in the floppy mode count or stress determination, but the cluster 1-2-3 may be missed by the rigid cluster decomposition procedure.

Figure 9

For the relaxation procedure described in the text, the base-10 logarithm of the sum over two realizations of the absolute value of the quantity ${\delta }_{kl}$ in Eq. (5) for all pairs of sites of a network with 216 sites. The gap between “zero” and “nonzero” values is clearly seen. Pairs with values below the gap are mutually rigid, those with values above the gap are not.

Figure 10

Smallest graph of the double-banana type that can exist in the diluted fcc network. The dashed line is the hinge. The outlines of two unit cells are shown for clarity with thin lines.

Figure 11

(Color online) (Top) Number of floppy modes per degree of freedom, $f=F∕3N$, for bond-diluted central-force bcc networks, for three different sizes: small (686 sites; symbols, green online); medium (3456 sites; the thin line without symbols, red online); and large (54 000 sites; the thick line). For the smallest size, the results obtained by both the pebble game (circles) and the relaxation algorithm (pluses inside the circles) are shown; the same realizations are used in both cases. For the other two sizes, the pebble game was used. The dashed line is the Maxwell counting result. (Bottom) Fraction of sites in the largest rigid cluster and fraction of bonds in the only stressed region for bond-diluted central-force bcc networks, for three different sizes. The line thicknesses and the color scheme (in the online version) are the same as in the top panel. For each size, the top line represents the largest rigid cluster and the bottom line, the stressed region. For the smallest size, the results obtained by both the pebble game (circles for the largest rigid cluster, squares for the stressed region) and the relaxation algorithm (pluses and ×’s, respectively) are shown. For the other two sizes, the pebble game was used. In both panels, the results for the small and medium sizes are averages over 100 networks, with intervals between data points equal to one bond; the results for the largest size are averages over ten networks, with intervals between data points equal to one bond in the vicinity of the transition and ten bonds elsewhere.

Figure 12

(Color online) Same as in Fig. 11, for bond-diluted fcc networks. The sizes used are 500 (small), 4000 (medium), and 62 500 sites (large).

Figure 13

Fraction of sites in the percolating rigid cluster (open circles) and fraction of bonds in the only stressed region (filled circles) as a function of the number of bonds in the network, for a single bond-diluted bcc network of 54 000 sites built incrementally, bond by bond. Note that the interval between adjacent data points is one bond.

Figure 14

Same as in Fig. 13, for a single bond-diluted fcc network of 62 500 sites.

Figure 15

Elastic moduli for the bond-diluted fcc network (adapted from Ref. 28).

Figure 16

Fraction of sites (among those still present, i.e., undeleted) in the largest rigid cluster for the site-diluted central-force bcc networks. Results for ten realizations on networks initially consisting of 54 000 sites are plotted separately. The step between adjacent data points is one site.

Figure 17

(Color online) Fraction of sites (among those still present, i.e., undeleted) in the largest rigid cluster for the site-diluted central-force fcc networks. For the smallest (500 sites initially) and medium (4000 sites) networks, the average over 100 realizations is plotted; for the largest (62 500 sites) networks, both the average over ten realizations (the thick black line) and the results for the individual realizations (thin lines) are plotted. The step between adjacent data points is one site in all cases.

Figure 18

Top: two connected fourfold coordinated sites and their neighbors in a bond-bending network with both central-force (thick lines) and bond-bending (thin lines) constraints shown. This is equivalent to a double-banana graph with the hinge added explicitly (bottom).

Figure 19

Fragments of networks consisting of atoms of valence 2 and 4. (a) A pair of corner-sharing tetrahedra. (b) A pair of edge-sharing tetrahedra. In both cases, thick lines are first-neighbor constraints and thin lines are second-neighbor (angular) constraints; black atoms have valence 4 and have all associated angular constraints present, while gray atoms have valence 2 and their angular constraints are missing, so that angles marked with dashed arcs are not constrained. It is implied that these pairs of tetrahedra are connected to the rest of the network, as shown by short black lines stemming from atoms of valence 2. In particular, in the edge-sharing case, each of the two tetrahedra shares an edge with yet another tetrahedron, and thus a chain of edge-sharing tetrahedra will be formed.