We summarize results for two exactly soluble classes of bond-diluted models for rigidity percolation, which can serve as a benchmark for numerical and approximate methods. For bond dilution problems involving rigidity, the number of floppy modes F plays the role of a free energy. Both models involve pathological lattices with two-dimensional vector displacements. The first model involves hierarchical lattices where renormalization group calculations can be used to give exact solutions. Algebraic scaling transformations produce a transition of the second order, with an unstable critical point and associated scaling laws at a mean coordination 〈r〉=4.41, which is above the ‘mean field’ value 〈r〉=4 predicted by Maxwell constraint counting. The order parameter exponent associated with the spanning rigid cluster geometry is β=0.0775 and that associated with the divergence of the correlation length and the anomalous lattice dimension d is dν=3.533. The second model involves Bethe lattices where the rigidity transition is massively first order by a mean coordination 〈r〉=3.94 slightly below that predicted by Maxwell constraint counting. We show how a Maxwell equal area construction can be used to locate the first-order transition and how this result agrees with simulation results on larger random-bond lattices using the pebble game algorithm.
We review rigidity percolation on a lattice and show that exact solutions can be obtained in two cases. These results are important, as with all exact solutions, to provide benchmarks for approximate methods. They are also interesting in that in one model the phase transition is of the first order and in the other second order.
The first solution involves hierarchical lattices, where in a wide range of lattices, Barré  has shown that the phase transition is of the second order. We give examples of such results here and show how renormalization group calculations can be performed on particular bond-diluted hierarchical lattices in two dimensions and that the transition is of second order. This result is significant as it sets the stage for others to find good approximate renormalization schemes on two-dimensional lattices, for example the triangular net, where good numerical results are known [2,3].
The second solution, known for the rigidity transition, on Cayley tree networks, is first order [4,5]. These are tree-like networks with no rings of bonds which can be solved by transfer matrix counting techniques. It is necessary to include a long busbar to nucleate rigidity (without this the network would be flexible everywhere with no redundant bonds) and then to determine whether rigidity percolates out through each subsequent layer, away from the busbar. In the thermodynamic limit where the number of sites , this can be shown to be equivalent to the random-bond model, where each site is connected to z neighbours initially and these neighbours are chosen from among the other N−1 sites with equal probability. That is, all sites are equivalent neighbours of any chosen site. Bond dilution then proceeds by randomly removing bonds in the usual way with probability 1−p. The random-bond model is useful as it is finite, with no boundary, and the pebble game algorithm can be used. The pebble game is a counting algorithm based on Laman's  theorem for two-dimensional vector displacements which offset constraints against degrees of freedom. Note that counts based on Laman's theorem take account of redundant bonds which are ignored in the Maxwell or ‘mean field’ count . The pebble game is an exact integer algorithm that can enumerate the rigid regions and the pivots between them for a given realization of sites very quickly (hundreds of thousands of sites in a few minutes). Being exact, it always gives a unique answer and does not explore metastable states (that are found in superheating and supercooling around a first-order transition, for example). Thus, in a first-order transition, it sees the collapse of rigidity like a house of cards.
Phase transitions associated with rigidity have experimental importance in the elastic behaviour in chalcogenide glasses , in protein unfolding  and in jamming in granular materials . Rigidity percolation is similar conceptually to the more familiar connectivity percolation [11,12], except that instead of demanding a connected pathway across the sample, the more stringent condition that the connected pathway is also rigid is required.
Rigidity on networks has been studied since 1864 . A mean field description of rigidity percolation proved remarkably accurate [13,14], except very close to the phase transition. Subsequent work has been mainly numerical [2,3]. The associated rigidity phase transition has been most extensively investigated on the triangular network in two dimensions where numerical studies (using the pebble game algorithm outlined below) show that the transition is of the second order and described by critical exponents β=0.18±0.02 and dν=2.42±0.12 that are distinct from those of connectivity percolation (β=5/6=0.139 and dν=8/3=2.667).
Results in three dimensions using the pebble game algorithm  strongly suggest that the rigidity transition is of the first order on a bond-diluted, face-centred cubic lattice, whereas if angular forces are included whenever two adjacent edges are present, the transition is of the second order. This is quite different from connectivity percolation where the transition is always second order in three dimensions .
Some characteristics of networks related to rigidity are illustrated in figure 1. Such particular network realizations are elucidated by exact counting procedures [6,7], such as the Maxwell count (used below) and in the pebble game algorithm. The latter finds the rigid clusters and the flexible joints between them and also determines redundant bonds in overconstrained regions, as illustrated in figure 1.
The number of floppy modes F plays the role of a free energy for bond dilution models for the rigidity problem with the fraction of bonds present, p being analogous to a temperature. The system maximizes the number of floppy modes, where there is more than one solution, and the state with the largest number of floppy modes is always the globally stable state. This is important to know when the transition is of the first order and a criterion can be developed akin to the Maxwell equal area construction to locate the first-order transition. If we define an intensive free energy f(p)=F(p)/2N, then it can be shown that the second derivative satisfies f(2)(p)≥0 and that which gives a Maxwell-type construction that is useful to locate the first-order phase transition . This is discussed in more detail with the Cayley tree which is the second soluble model reviewed here.
2. Hierarchical models
First, we review how exact calculations can be performed for rigidity  on hierarchical networks in two dimensions, taking for detailed discussion the Berker lattice [16,17] shown in figure 2. When diluted, this network is the simplest member of classes which capture fundamental generic features for rigidity percolation. Each generation is obtained by decoration of the previous generation, creating an infinite sequence that can lead to singularities and a phase transition. An exact set of equations can be written down, relating quantities associated with generations n+1 and n, which can be solved at all bond concentrations p by iteration. Most importantly, the stable and unstable fixed points can be found and the structure of the rigidity phase transition can be described by the scaling behaviour obtained by expanding about the unstable fixed point. This can be carried out, with the same qualitative conclusions, for any member of the class of fractals generated as in figure 2 from an n=1 graph having any even central-site coordination greater than or equal to 4.
It is instructive to do a Maxwell count  on the first three generations of the Berker lattice shown in figure 2. The number of floppy modes F is given by the difference in the number of degrees of freedom 2V , associated with the number of vertices V and the number of constraints which are associated with the number E of edges. However, in general not all the edges are independent constraints and so E must be corrected by the number R of redundant edges so that 2.1The number of floppy modes F in equation (2.1) contains the three rigid body motions in two dimensions (two translations and one rotation) that become insignificant in the limit of a very large number of edges.
For bond dilution, where a fraction p of bonds are randomly present, equation (2.1) can be re-written as 2.2where r(p) is the fraction of redundant bonds, and g is the number of degrees of freedom per site.
For the top panel in figure 2, and ignoring R for the moment, F−3=2⋅2−1−3=0 while for the second and third panels, F−3=2⋅5−8−3=−1 and F−3=2⋅29−64−3=−9, respectively, where the negative numbers signify that not all the bonds are independent in these rigid diagrams, and we have removed the three macroscopic floppy modes on the left-hand side of the count. Therefore, there is a single redundant edge in the second panel of figure 2 and nine redundant edges in the third panel (one for each of the eight replications of the second panel, plus a new one). By removing edges randomly from the third panel (i.e. bond diluting), first the redundancy is reduced, and eventually there is no rigid path between the two black vertices, and rigidity is lost. Note that the Maxwell count for figure 1 gives F−3=2⋅8−13−3=0 (again removing the three floppy modes), but as there is one floppy mode associated with the solid vertices, there is also one redundant edge associated with the heavier solid red edges in the left side of the diagram.
The number of edges E or more precisely bonds , and the number of vertices V or sites in the nth generation becomes, for the undiluted case (p=1) shown in figure 2, 2.3
An important quantity is the mean coordination defined by 〈r〉=2E/V which tends to an asymptotic value 〈r〉=14/3=4.667 for the undiluted lattice. It is important that this quantity be above 4, which is the mean field value of the mean coordination needed for rigidity in two dimensions [3,14]. The number of redundant edges is (8n−1)/7 so that the fraction of redundant edges for large n approaches 1/7=14.3% in the undiluted lattice. For the triangular lattice, this fraction is even higher at 1/3=33.3%.
For the diluted case, a bond is present with probability p (concentration) and absent with probability 1−p, so the probability of the two solid dots being rigidly connected in the second panel of figure 2 using the weights from figure 3 is p′=p8+8p7(1−p)+6p6(1−p)2+2p5(1−p)3=2p5+2p7−3p8. This leads to the relationship between the probabilities pn+1,pn of rigidity percolating in successive generations n+1,n: 2.4(with p0=p). The fixed points p* satisfying pn+1=pn=p* are the trivial stable fixed points at p*=0 and p*=1 and the non-trivial unstable fixed point p*=0.9446=pc. Close to this latter fixed point, equation (2.4) can be linearized by differentiating to give (pn+1−pc)=λ1(pn−pc), where .
Using the cluster probabilities and also the number of bonds in each rigid spanning cluster from figure 3, we find from the mean number of bonds that the probability Pn+1(p) of a bond belonging to the percolating rigid cluster is given by the recurrence relation 2.5(with P0(p)=p). Near the unstable fixed point, Pn+1(p)=λ2Pn(p), where , showing that the probability of a bond being in the percolating cluster renormalizes to zero at the phase transition as expected for a second-order phase transition. From figure 4, we can see how the singular behaviour at the phase transition develops as n increases: n=12 appears very close to giving the full singularity. Near p=1, P(p)=p[1−69(1−p)2/4+⋯ ] where the first term is just the probability that a bond is present and the second term that at least two bonds must be removed to produce a bond that is present but not part of the rigid backbone, as indicated, for example, in panel (c) of figure 3.
Using the eigenvalues λ1, λ2 and λ3(=8) of the linearized scaling relationships for p, P(p) and , respectively, we obtain exponents ν, β and fractal dimensionality d, from λ1=b1/ν, λ2=b−β/ν and λ3=bd, where b is the dilatation (length scaling) factor between successive generations of the hierarchical lattice. However, as is typical for such lattices, b is ambiguous ; so we quote only the values of exponents independent of b. These are β=0.0775, which describes how the order parameter P(p) goes to zero at the critical point, and the product dν=3.533, which plays a role in hyperscaling, which does apply here.
The question of hyperscaling involves the critical exponent α that describes the fluctuations associated with the specific heat in the system near the phase transition. The exponent α is most easily calculated by differentiating the free energy twice with respect to the the bond concentration p, and hyperscaling also relates (when it applies) to the free energy. But the question arises as to what is an appropriate free energy as rigidity percolation is not a system described by a Hamiltonian. There is strong evidence, outlined below, that the number of floppy modes given in equation (2.1) serves as the appropriate free energy for it. It can be shown that the second derivative with respect to p is positive definite. For connectivity percolation, the free energy can be found as the limit of the s-state Potts model  and in that case is equivalent to an appropriate version of equation (2.1) in which redundancy refers to loops or multiple pathways between two vertices and the factor 2 is omitted. In this case, a single floppy mode is associated with an isolated cluster, so the free energy is just the total number of isolated clusters, and of course is an extensive quantity. Finally for connectivity and rigidity, these forms of F have been used as a free energy for percolation from a busbar onto a Cayley tree network .
Rather than calculate the number F of floppy modes directly, it is easier to calculate R in equation (2.1), and hence determine F . If the number of redundant bonds at generation n is Rn+1(p), then 2.6(with R0(p)=0). The factor 8 in equation (2.6) comes from the eightfold replication of any redundant bond from the previous generation (e.g. going from n=1 to n=2 in figure 2). The factor comes from additional redundancy if all eight pieces of the graph are rigid (but not necessarily redundant). Equation (2.6) together with (2.3) provides an iterative equation for the free energy Fn(p) resulting from (2.1) 2.7From the eigenvalue λF(=8) for the linearized scaling of Fn(p) at pc and large n, we find that the exponent α is negative (signifying a cusp) and also establish that the hyperscaling relationship to dν is satisfied: .
It is convenient to define the number of floppy modes per degree of freedom as so that 0<f<1. Here, f(p) is the thermodynamic limit as of fn(p). In figure 5, we show both f and its second derivative with respect to p. Solving equations (2.7) at the critical point gives and at small p we have f(p)=1−7p/6+7p8/48+… where the term in p8 is the leading correction owing to redundancy or the onset of dependent constraints. The results here show the general principles that can be used to solve hirearchical lattices. Further examples can be found in Barré .
In the above treatment of the rigidity percolation problem, it has only been necessary to consider averages, of such things as numbers of stress-carrying bonds, redundant ones, floppy modes, etc., governed by additive composition rules. Such additivity is absent for processes, such as percolation conductivity  (or elasticity), where probability distributions have to be rescaled.
For the additive variables of rigidity percolation, probability distributions have been found simply (from algebraic recurrence relations for their Laplace transforms). These can provide further useful information, e.g. for distinguishing the situations with/without central limit simplicity away from/near the transition.
3. Bethe lattices
The second model we review here is the solution on the bond-diluted z coordinated random-bond network shown in figure 6 and the Cayley tree or Bethe lattice shown in figure 7. These networks are equivalent in the limit that the number of sites as neither contains any rings of bonds in that limit as can be seen by inspection and imagining the two networks getting larger and larger. Rings that involve the busbar are discounted. Although these networks are equivalent in the thermodynamic limit, each has its own distinct use as a way of approaching this limit. The random-bond network shown in figure 6 is useful as the pebble game algorithm can be run on a series of realizations for larger and larger sizes N. The Cayley tree, with the busbar to nucleate rigidity, shown in figure 7, can be used with a transfer matrix approach, outlined below, to obtain exact solutions [4,5]. Note that in the original work on the Cayley tree with a busbar , emphasis was placed on the location of the spinodal, whereas subsequently  the actual rigidity phase transition was the focus. In this paper we use the words Cayley tree and Bethe lattice interchangeably and to include a busbar as is necessary to nucleate rigidity.
The busbar is not necessary for connectivity, but is of vital importance for problems involving rigidity, as rigidity needs to nucleate from a site or set of sites . We define to be the probability that a bond on a branch, n levels away from the busbar, is part of the infinite rigid cluster. If the sites of the tree have 2 degrees of freedom, rigidity is transmitted to the next level of the tree provided at least two of the bonds to the lower level are occupied and provided that the sites at the ends of these bonds are rigid. This gives the recurrence relation 3.1If we take the thermodynamic limit (very large n), equation (3.1) iterates to a steady-state solution, T0 given by 3.2From this equation, we can find the probability of having a single degree of freedom with respect to the (distant) boundary. Equation (3.2) is the self-consistent equation for the rigidity order parameter on bond-diluted Cayley trees, and is more conveniently written as 3.3Having found the key element T0 (from the transfer matrix) and pc, we can find f(p), f(1)(p), f(2)(p) and the fraction of redundant bonds r(p) as shown in figure 8. Full details can be found in Duxbury et al. . It can be seen that there are no redundant bonds for p≤pc, and hence f(1) and f(2) are flat in this region. In figure 8, we also show the results from the random-bond model (as small circles), using the pebble game algorithm, and find that the results are the same as expected. Note that with the random-bond model, the first-order transition occurs naturally and no Maxwell construction is needed, as the pebble game always finds the exact bulk equilibrium solution, without hysteresis.
Additional quantities of interest can also be found. The probability of a bond being in the infinite rigid cluster is given by 3.4while the probabilty of a bond being in the overconstrained part of the infinite rigid cluster Pov(p) is given by 3.5The rigidity transition on the Bethe lattice is of the first order  and its location is given by 3.6This integral can be done in closed form by transforming the integration variable from p to u=pT0, and using equation (3.3) to give (for the value uc of u at pc) 3.7together with the following relation for the bond concentration pc at the transition: 3.8For z=6, these two equations can be simplified to give 3.9which has a single real root at uc=0.5987 so that transition is located at 3.10which leads to a value of T0=0.9120 at the transition as can be seen in figure 9. It is quite unusual to be able to write down closed form expressions for the location of a first-order transition. For this case, zpc=3.936 which is within 2% of the mean field Maxwell estimate of zpc=4. Thus, the Maxwell estimate is seen to be remarkably good when the rigidity transition is of either second or first order and provides an even better estimate that the zpc=2 for connectivity percolation.
For very large values of z tending to infinity, equations (3.7) and (3.8) can be written using zuc=A, where 3.11leading to the single positive root at A=2.688, and hence to 3.12which is further from the mean field Maxwell estimate than the z=6 case.
Indeed the smallest value of z for which there is a transition, z=4, leads to zpc=4. The value of zpc decreases monotonically as z increases, tending to zpc=3.588 as the coordination number z tends to infinity. Values of this product for other values of z are given elsewhere  and shown augmented in table 1. We see that the transition is most ‘mean field-like’ (as in the Maxwell count) at the lowest value of the coordination z=4 for which a rigidity transition takes place. As the coordination z is increased, the value of 〈r〉=zpc decreases slowly and monotonically from 4 until it reaches the asymptotic value of 3.588 at very large z. The fraction of floppy modes at the rigidity transition f(pc) increases from zero at z=4 up to just over 10% for very large z. Of particular interest is that the fraction of redundant bonds is zero at the rigidity transition for all values of z. This is because r(p) is continuous, because f(p) is continuous as seen from equation (2.2), and as r(p)=0 for p≤pc, then this implies that r(pc)=0 for all z.
For the bond-diluted z=6 triangular lattice , numerical results using the pebble game algorithm, give pc=0.6602 and f(pc)=0.026 so that 〈r〉=zpc=3.96, which is very close to that given by the Bethe lattice with z=6. The fraction of redundant bonds, although not zero, is given by r(pc)=0.0108 and so is very small at just over 1%. Thus, the Bethe lattice can serve as a guide in rigidity percolation.
The dashed line in figure 9 is unstable as can be seen from using the Maxwell-type construction discussed earlier.
It is seen from figure 8 that the random-bond model is numerically equivalent to the Bethe lattice results, as expected from our previous discussion. The pebble game algorithm, used here, gives the exact number of floppy modes and the associated derivatives. There is therefore no hysteresis in the results of the algorithm on the random-bond model, and in these large samples the system flips from the rigid state to the floppy state around pc=0.656 as a single bond is removed in a given sample. This is a very unusual situation as most numerical techniques, for example Monté Carlo, encounter hysteresis near a first-order transition .
Figure 10 shows the precipitous drop at the phase transition in both-order parameters, where the probability of a bond being in the infinite rigid backbone is of course larger than the fraction of overconstrained regions Pov; the difference being the quite small fraction of isostatic regions for z=6. Note that the isotatic part of the rigid percolating backbone increases to about 1/3 as z gets very large.
We have reviewed two exactly soluble models of rigidity percolation. Both these models have two-dimensional vector displacements (with bond dilution) on somewhat unphysical networks that allow the mathematics to be completed in a way that is not possible on lattices, such as the triangular net and face-centered cubic lattice, where numerical solutions or approximations must be used. In the first model, we have shown how exact renormalization group procedures can be used to describe second-order phase transitions involving rigidity percolation when rigidity percolates on the Berker lattice considered here. This should give insights into how to use renormalization procedures on the triangular lattice and the face-centered cubic lattice.
The second model involves an exact solution on a Cayley tree which is a network with no rings of bonds. In order to nucleate rigidity, a busbar must be introduced. This is essential for rigidity, but is optional for the associated connectivity problem with one degree of freedom per site [4,5]. The rigidity transition is found to be of the first order, and the transition is located by using a Maxwell-type construction. Numerical agreement is obtained with results from the pebble game algorithm.
Why is there a second-order transition in one class of models and a first-order transition in another class of models? This is a question to which we have not had any useful insights to date and it seems that each network must be examined individually. An interesting model that shows mixed first-order and second-order characteristics has recently appeared  which involves stabilizing a square lattice with cross bracing. It is hoped that some approach will be forthcoming to help with this general question. Work continues towards finding hierarchical lattices with a first-order rigidity transition, and possibly a parameter to tune the transition through a tricritical point. Another outstanding challenge is to find more rigorous approaches to establish that the number of floppy modes F is the appropriate free energy for this problem. While there is a suggestive proof for the bond dilution case , there is so far no such proof for the site dilution case.
M.F.T. thanks National Science Foundation for support under grant DMR 07-03973.
We thank Julian Barré, Nihat Berker, Phil Duxbury, Roger Elliott, Don Jacobs, Paul Leath, Cristian Moukarzel and Sergio de Queiroz for useful discussions and insights. M.F.T. thanks Theoretical Physics at the University of Oxford for continuing summer hospitality
One contribution of 14 to a Theo Murphy Meeting Issue ‘Rigidity of periodic and symmetric structures in nature and engineering’.
- © 2013 The Author(s) Published by the Royal Society. All rights reserved.