PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimal contagious sets in random regular graphs

Alberto Guggiola, Guilhem Semerjian

arXiv:1407.7361v2cond-mat.dis-nncond-mat.stat-mechmath.PR

TL;DR

The paper studies the minimum number of initially active vertices needed for complete threshold activation, optionally within a prescribed time horizon. The authors reformulate the optimization as a statistical-mechanics model and analyze it with the cavity method, including replica symmetry breaking. The analysis proposed quantitative conjectures for minimal de-coring sets, with particularly simple rational forms for removing the 3-core in 5- and 6-regular random graphs.

  • Problem

    The paper studies the minimum number of initially active vertices needed for complete threshold activation, optionally within a prescribed time horizon.

    Source: §I · p. 2, C. Definition of the optimization… · p. 4

  • Method

    The authors reformulate the optimization as a statistical-mechanics model and analyze it with the cavity method, including replica symmetry breaking.

    Source: §I · p. 2, E. Main analytical results · p. 7

  • Results

    The analysis proposed quantitative conjectures for minimal de-coring sets, with particularly simple rational forms for removing the 3-core in 5- and 6-regular random graphs.

    Source: §VI · p. 31

  • Takeaways & Limitations

    Minimal contagious sets connect threshold activation to extremal graph problems including independent sets, domination, decycling, and q-core destruction.

    Source: §I · p. 2, §VI · p. 31

Abstract

from arXiv · show

The bootstrap percolation (or threshold model) is a dynamic process modelling the propagation of an epidemic on a graph, where inactive vertices become active if their number of active neighbours reach some threshold. We study an optimization problem related to it, namely the determination of the minimal number of active sites in an initial configuration that leads to the activation of the whole graph under this dynamics, with and without a constraint on the time needed for the complete activation. This problem encompasses in special cases many extremal characteristics of graphs like their independence, decycling or domination number, and can also be seen as a packing problem of repulsive particles. We use the cavity method (including the effects of replica symmetry breaking), an heuristic technique of statistical mechanics many predictions of which have been confirmed rigorously in the recent years. We have obtained in this way several quantitative conjectures on the size of minimal contagious sets in large random regular graphs, the most striking being that 5-regular random graph with a threshold of activation of 3 (resp. 6-regular with threshold 4) have contagious sets containing a fraction 1/6 (resp. 1/4) of the total number of vertices. Equivalently these numbers are the minimal fraction of vertices that have to be removed from a 5-regular (resp. 6-regular) random graph to destroy its 3-core. We also investigated Survey Propagation like algorithmic procedures for solving this optimization problem on single instances of random regular graphs.

I. INTRODUCTION

The paper studies irreversible threshold activation on graphs and asks how few initially active vertices can trigger complete propagation, with or without a time limit. It contrasts this optimization problem with random-initial-condition percolation, where activation occurs above a critical density.

I. INTRODUCTION

  • The threshold model is deterministic, discrete-time, and irreversible: an inactive vertex activates once it reaches its threshold of active neighbours and remains active.The dynamics is a special monotonous contagion process, related to bootstrap percolation.Source: §I · p. 1, A. Definition of the dynamics · p. 3
  • Unlike forward evolution from independent initial states, choosing a minimal activating set is computationally hard and connects to independence, domination, decycling, and related graph problems.The inactive vertices can be interpreted as repulsive particles subject to constraints imposed by eventual complete activation.Source: §I · pp. 1–2
  • The optimization problem seeks either maximal propagation from a fixed seed set or the smallest seed set that activates the entire graph, possibly within a prescribed time.The paper focuses mainly on minimizing the initial active set for complete activation.Source: §I · p. 2

A. Definition of the dynamics

  • The dynamics can equivalently be viewed through sequential removal of inactive vertices, whose terminal inactive set forms a generalized core.The final configuration is independent of whether eligible activations occur in parallel or sequentially.Source: A. Definition of the dynamics · p. 3

B. Reminder of the behaviour for random initial conditions on random regular graphs

  • For a Bernoulli random initial condition with activation probability θ, complete activation occurs above the degree- and threshold-dependent critical density θr(k, l), which increases with l at fixed k.For 2 ≤ l ≤ k−1 the transition is discontinuous, whereas l = k gives a continuous transition.Source: B. Reminder of the behaviour for… · pp. 3–4

C. Definition of the optimization problem over initial conditions

The paper formalizes minimal contagious sets as the smallest initial active fraction that reaches full activation by a time horizon T, then studies the large random-regular-graph limit. Special thresholds recover independent-set, domination, and decycling problems, while edge counting supplies lower bounds.

C. Definition of the optimization problem over initial conditions

  • The central quantity θmin(G, {li}, T) is the minimum initial active fraction that activates every vertex within T steps.The unconstrained-time value is obtained as T tends to infinity.Source: C. Definition of the optimization… · p. 4
  • A statistical-mechanics measure uses µ to control the initial active density and ǫ to penalize vertices remaining inactive at time T; setting ǫ = +∞ restricts support to activating configurations.The entropy of activating configurations is recovered from the partition function through an inverse Legendre transform.Source: C. Definition of the optimization… · pp. 4–5
  • For large random regular graphs, θmin is conjectured to be strictly below the random-initial-condition threshold θr because rare correlated configurations can activate the whole graph.The limit is expected to be self-averaging, while the existence of the unconstrained-time limit is left as a conjecture.Source: C. Definition of the optimization… · p. 5

D. Equivalence with other problems and bounds

  • When li = di, inactive vertices must form an independent set, so θmin equals one minus the maximum independent-set density.For T = 1, the same framework includes the Biroli–Mézard model and, when li = 1, the domination number.Source: D. Equivalence with other problems and… · pp. 5–6
  • When li = di−1 and T = ∞, the inactive induced subgraph must be acyclic, making active vertices a decycling set; more generally, lower bounds follow from edge counting.The decycling bound is tight for large 3-regular random graphs, giving θmin(2, 2) = 1/4.Source: D. Equivalence with other problems and… · p. 6

E. Main analytical results

The paper predicts minimal contagious-set densities by applying RS and 1RSB cavity methods to a statistical-mechanics reformulation of threshold dynamics. Its factor-graph construction makes the activation-time constraints local, enabling analysis on sparse random graphs.

E. Main analytical results

  • Replica-symmetry levels predict bounds θmin,0(k, l, T) ≤ θmin,1(k, l, T) ≤ θmin(k, l, T).The predictions come from solving roughly 2T algebraic equations on 2T unknowns.Source: E. Main analytical results · p. 7
  • Four cases where RS and 1RSB predictions coincide as T →∞ are conjectured to be exact and saturate established lower bounds.The first equality was proven and the second conjectured in.Source: E. Main analytical results · p. 7

A. Factor graph representation

  • Activation dynamics are encoded by local constraints on activation times: each site activates initially or one step after its l-th earliest active neighbor.The activation-time representation is equivalent to the original initial-state dynamics.Source: A. Factor graph representation · p. 7
  • Duplicating activation times on incident edges converts the model into a locally tree-like factor graph suitable for cavity analysis.The construction avoids short interaction loops that would remain without variable duplication.Source: A. Factor graph representation · pp. 7–8

B. Replica Symmetric (RS) formalism

The RS formalism represents activation-time configurations with edge messages and derives recursive Belief Propagation equations. A compact cavity-field parametrization then yields Bethe free entropy, marginals, and entropy densities.

1. Single sample equations

  • On locally tree-like graphs, normalized edge messages over pairs of activation times obey recursive Belief Propagation equations.The equations are exact on finite trees and approximate on locally tree-like graphs under long-range correlation decay.Source: §1 · pp. 8–9
  • The messages determine the Bethe free-entropy density through site and edge partition contributions.They also determine activation-time marginals and initial activation probabilities.Source: §1 · p. 9
  • The entropy density s(θ, θ′) follows from the free entropy by setting uniform chemical-potential and non-activation-cost parameters.The construction relates initial active density θ to the density θ′ active after T steps.Source: §1 · p. 9

2. A more compact parametrization of the messages

  • Although each message initially has (T + 2)^2 − 1 parameters, its entries reduce to 3T + 2 distinct values.The reduction uses time-order classes and recurring linear combinations of matrix entries.Source: §2 · pp. 9–10

1. Single sample equations

  • Threshold conditions in the recursion can be rewritten as counts of time arguments below successive time levels.This reformulation supplies the combinatorial interpretation used in the explicit equations.Source: §2 · p. 10

2. A more compact parametrization of the messages

  • Cavity fields h encode the relevant message combinations in 2T real numbers and obey a reduced recursion h = g(h1, . . . , hk).The field representation excludes bT, which disappears from the final expressions.Source: §2 · pp. 10–11
  • The reduced fields provide equivalent expressions for site and edge partition functions and therefore for the Bethe free entropy.Marginals can likewise be computed from incident cavity fields.Source: §2 · p. 11

3. Random (regular) graphs

For random regular graphs, the RS cavity method uses a factorized fixed-point field, while 1RSB replaces single messages with distributions over pure-state messages. The latter captures clustering and condensation when RS correlation decay fails.

3. Random (regular) graphs

  • RS assumes locally tree-like convergence and long-range correlation decay, with a probability distribution over cavity fields as its order parameter.For regular graphs without coupling disorder, a factorized solution with identical cavity fields is used.Source: §3 · pp. 11–12
  • The RS free-entropy density for a (k + 1)-regular graph is computed from fixed-point site and edge contributions.The activation-time marginal and entropy density follow from the same fixed-point field.Source: §3 · p. 12
  • RS becomes unphysical in frustrated regimes because long-range correlations conflict with its correlation-decay assumption.This occurs in the minimal-contagious-set limit µ →−∞, motivating replica-symmetry breaking.Source: §3 · p. 12

C. One step of Replica Symmetry Breaking (1RSB) formalism

  • 1RSB models the configuration space as pure states and characterizes their exponential count through a complexity function Σ(φ).The Parisi parameter m and a Legendre-transform structure reconstruct the complexity.Source: C. One step of Replica Symmetry… · p. 12

1. Single sample equations

  • At 1RSB, each directed edge carries a distribution over RS messages, reweighted by pure-state weights proportional to Zγ^m.The resulting distributions satisfy distributional recurrence equations.Source: §1 · p. 13
  • The 1RSB potential and activation-time marginals are weighted averages of site, edge, and state-level contributions.The field parametrization expresses these quantities through distributions P(h).Source: §1 · p. 13

2. Random regular graphs

The energetic 1RSB limit targets minimally dense fully activating configurations by taking ǫ = +∞ and µ →−∞. In this limit, cavity fields become discrete Warning Propagation messages with an operational activation-time interpretation.

D. “Energetic” 1RSB formalism

  • The energetic 1RSB limit takes m → 0 and µ →−∞ while holding y = −µm fixed, simplifying the computation of minimal contagious-set density.This limit discards cluster-entropy information but preserves the smallest density with nonnegative energetic complexity.Source: D. “Energetic” 1RSB formalism · p. 14
  • The estimate θmin,1 is the smallest θ for which the energetic complexity Σe(θ) is nonnegative.Least-dense activating configurations must belong to some pure states regardless of their internal entropy.Source: D. “Energetic” 1RSB formalism · p. 14

1. Simplification of the cavity field recursion (Warning Propagation equations)

  • In the µ →−∞ limit, cavity fields are assumed integer-valued and reduce to 2T + 1 hard-field types A_t and B_t.The fields encode binary a and b components constrained by the ordering inequalities.Source: §1 · p. 15
  • B_t messages state that a subtree activates within horizon T without the recipient, while A_t messages require the recipient to activate at time t.B_0 denotes an initially active sending vertex.Source: §1 · p. 16
  • Warning Propagation combines incoming messages by checking whether enough B-type neighbors activate early enough to satisfy the threshold.If fewer than l − 1 such messages arrive, the central vertex must be initially active; if at least l arrive, its activation time follows the l-th earliest one.Source: §1 · p. 16
  • When A-type constraints demand earlier activation than B-type messages provide, the receiving site must contribute activation and the outgoing message records the least stringent compatible time.This produces an A-type warning tied to the required activation time.Source: §1 · p. 16

2. Energetic 1RSB single sample equations

The energetic 1RSB formalism reduces the cavity fields to finite-support probability vectors in the µ → −∞, m → 0 limit and uses them to compute the variational potential and energetic complexity.

Energetic-limit ansatz

  • The reweighting factor e^{ya0} multiplies warnings except B0, identifying cases where an active site must be inserted initially.This connects the energetic reweighting directly to whether a site requires initial activation.Source: §2 · p. 17

Site and edge terms

  • The site contribution is interpreted as the probability that an initially inactive site activates at time t under specified neighbour-message distributions and threshold constraints.Activation at time t requires at least l neighbours to activate by t − 1, while excluding configurations that would activate earlier.Source: §2 · p. 17
  • The edge contribution similarly represents complete activation when two messages are sent in opposite directions across an edge.The corresponding factor is expressed through the edge partition term involving the two message distributions.Source: §2 · p. 17

Energetic-limit ansatz

  • In the µ → −∞, m → 0 limit with y = −µm finite, each cavity-field distribution has 2T discrete values represented by normalized probabilities {pt, qt}.The distributions satisfy finite-dimensional recurrence equations P_i→j = G({P_k→i}), with G defined by the hard-field update rule.Source: §2 · pp. 16–17

Energetic potential

  • The energetic 1RSB potential is computed variationally from site and edge terms, with derivatives taken only over its explicit dependence on y.The resulting potential is then used in the inverse Legendre transform to obtain the energetic complexity.Source: §2 · p. 17

3. Random regular graphs

This section develops RS and 1RSB cavity analyses for minimal activating densities in random regular graphs, including their behavior across activation thresholds and times. It also examines activation-time distributions and identifies exceptional parameter pairs with coinciding predictions and simple threshold values.

1. Replica symmetric formalism

  • RS entropy becomes negative below µs=0, indicating replica symmetry failure; 1RSB instead finds a discontinuous dynamic transition with a positive-complexity phase for µ ∈ [µc, µd].For the studied parameters, µc < µd and RS thermodynamic predictions remain valid throughout [µc, µd].Source: §1 · p. 18, §2 · p. 19

3. Energetic 1RSB results

  • Energetic 1RSB reduces the computation to roughly 2T equations and predicts θmin,1 where the cluster complexity vanishes, with T = 1 values cross-checked against the Biroli–Mézard model.The relevant solution is obtained in the joint limit µ → −∞ and m → 0 at finite y = −µm, using the physical concave branch of Σe(θ).Source: §3 · pp. 20–21

1. The case k = l

  • For k = l = 2, the T →∞ analysis gives θmin = θr/2 = 1/4, saturating the decycling lower bound and recovering the rigorous result for 3-regular graphs.The endpoint entropy is positive, while the energetic complexity retains only a vertical segment in the limit.Source: §1 · pp. 22–23
  • For k = l = 3, the analysis likewise predicts θmin = θr/2 = 1/3, whereas the nontrivial complexity above θmin suggests that θd and θc remain strictly larger than 1/3.This value again saturates the lower bound and agrees with the conjecture in.Source: §1 · p. 23
  • For k = l ≥4, the RS entropy vanishes above θr/2 and 1RSB gives a slightly larger θmin,1, whose exact status is uncertain because further replica-symmetry breaking has not been tested.The authors treat the 1RSB value as potentially a conjecture or lower bound, depending on k.Source: §1 · p. 23
  • Finite-T corrections to θmin are exponential for k = l = 2 and 3, scaling as 2^-T and 3^-T respectively, but only polynomially small for k = l ≥4.For θ < θr, activation-time distributions have a t^-2 tail, compared with t^-3 at θr and exponential decay above θr.Source: §1 · p. 24
  • The limiting RS entropy and energetic complexity define θmin,0 and θmin,1; across most tested (k,l), θmin,1 is slightly larger than θmin,0.The exactness of the 1RSB prediction remains dependent on stability against further replica-symmetry breaking.Source: §2 · p. 26
  • For (k,l) = (4,3) and (5,4), θmin,0 = θmin,1 because the entropy and complexity curves contain a positive vertical segment.This exceptional behavior occurs for k < 2l − 1 and is not found for other tested values of k and l.Source: §2 · pp. 26–27
  • The exceptional cases predict θmin = 1/6 for (k,l) = (4,3) and θmin = 1/4 for (k,l) = (5,4), saturating the lower bound in (17).In both cases, the 1RSB entropy and energetic complexity remain strictly positive at the limiting value.Source: §2 · p. 27
  • As T →∞, RS activation times split into three finite-fraction categories: t = O(1), t = O(T), and t = T − O(1).The middle category is described by a reduced-time scaling function P(s) for s ∈ ]0,1[, while the endpoint masses represent the first and third categories; the stated regime is θ(λ) < θr.Source: §2 · p. 27

V. ALGORITHMIC RESULTS

The paper constructs activating initial configurations on finite random regular graphs using iterative algorithms that add one active vertex at a time. It compares a greedy strategy with a cavity-method-inspired approach for contagious-set optimization.

V. ALGORITHMIC RESULTS

  • Numerical experiments construct activating initial configurations on finite random regular graphs by iteratively adding one active vertex at a time.The configurations begin with all vertices inactive and stop when complete activation is achieved.Source: §V · pp. 27–28
  • The greedy and cavity-inspired procedures differ in the rule used to select the next inactive vertex added to the initial configuration.Both procedures build a percolating configuration incrementally, but use different selection criteria.Source: §V · pp. 27–28

A. A greedy algorithm

The greedy algorithm adds the inactive vertex that maximizes the resulting activated set, producing contagious sets below the random-percolation threshold. Its performance reaches the predicted minimum for k = l = 2 but remains above the cavity prediction in most other cases, while activation times scale logarithmically with graph size.

A. A greedy algorithm

  • At each step, the greedy procedure adds the inactive vertex whose activation produces the largest resulting active set, stopping at the first percolating configuration.For T = ∞, monotonicity allows the final activated configuration to be computed sequentially, reducing the total complexity to quadratic scaling with N.Source: A. A greedy algorithm · p. 28
  • For finite time horizons, greedy contagious-set densities exceed the 1RSB cavity prediction and those reached by more involved message-passing algorithms.These finite-time results were averaged over ten graphs with N = 10^4 vertices.Source: A. A greedy algorithm · p. 28, Table V · p. 29
  • The greedy algorithm reaches the predicted minimal density 1/4 for k = l = 2, while generally producing densities above the cavity-method prediction θmin,1.The exception is linked to the disappearance of the replica-symmetry-breaking phase in the large-T limit for k = l = 2.Source: A. A greedy algorithm · p. 29
  • The greedy algorithm finds contagious sets with density strictly below θr in every investigated case, although usually above the predicted minimal density θmin,1.Here θr is the density above which typical uncorrelated initial configurations percolate.Source: A. A greedy algorithm · p. 29
  • Activation completes in a time that scales logarithmically with graph size, but the greedy activation-time distributions do not quantitatively match the RS predictions.The discrepancy may reflect that greedy configurations are out of equilibrium rather than typical under the equilibrium measure.Source: A. A greedy algorithm · p. 30, Figure 12 · p. 30

B. Survey propagation

The paper develops a Survey Propagation-like decimation procedure for constructing minimal contagious sets and compares its performance with simpler algorithms and theoretical predictions. It concludes by identifying unresolved stability, graph-ensemble, optimization, and convergence questions.

B. Survey propagation

  • Survey Propagation-like decimation assigns edge-message probability vectors, iterates energetic 1RSB equations, and activates the vertex with the largest site contribution W_i.Activated vertices enter the equations as boundary conditions, while W_i measures their tendency to be active across the considered clusters.Source: B. Survey propagation · p. 31
  • The procedure fixes y at an analytically determined value, while recomputing y during decimation produced no significant performance improvement in the tested cases.Source: B. Survey propagation · p. 31
  • The constructed densities outperform a simple greedy algorithm and often the maxsum replica-symmetric procedure, but can deviate significantly from the predicted minimal density.For k = 3, l = 2 and T ≥ 4, unconverged message iterations still beat greedy performance but can be worse than maxsum.Source: B. Survey propagation · p. 31

VI. CONCLUSIONS AND PERSPECTIVES

  • Replica symmetry breaking is necessary for determining the minimal active density, and the large-T limit simplifies the equations when the time constraint disappears.The analysis also recovers known decycling results and proposes quantitative de-coring conjectures for regular random graphs.Source: §VI · p. 31
  • The paper leaves open testing 1RSB stability, proving predictions rigorously, and deriving large-degree asymptotic expansions for θ_min,0(k,l) and θ_min,1(k,l).Source: §VI · p. 31
  • The explicit results concern regular random graphs, although the cavity equations extend to arbitrary sparse degree distributions and fluctuating, potentially degree-correlated thresholds.The authors expect local fluctuations, especially power-law degree tails, could substantially modify the results.Source: §VI · pp. 31–32
  • The study optimizes the number of initially active vertices while requiring eventual full activation, leaving partial-activation optimization and improved message-passing convergence for future work.Larger T causes convergence problems, and reinforcement or broader maxsum comparisons are suggested.Source: §VI · p. 32

Appendix A: The limit µ →−∞of the fields recursion

The appendices formulate the factorized RS cavity equations and their hard-field recursion, then express thermodynamic and activation-time quantities through transformed variables. These equations share a common structure across RS and energetic 1RSB treatments.

Appendix A: The limit µ →−∞of the fields recursion

  • The hard-field recursion follows from enumerating the possible A_t and B_t cases and combining the resulting logical rules.The resulting conditions include g(h_1,...,h_k)=A_t iff a_t=1 and a_{t+1}=0, with an analogous condition for B_t.Source: Appendix A · pp. 32–33

Appendix B: Technical details on the resolution of the factorized RS and energetic 1RSB equations

  • The technical appendix treats RS and energetic 1RSB cavity equations together for random (k+1)-regular graphs with uniform activation threshold l.It also discusses the special case l = k and the limit T → ∞.Source: Appendix B · p. 33

a. RS cavity method

  • The factorized RS equations use a fixed-point equation on the field vector together with boundary conditions and separate site and edge contributions.Source: a. RS cavity method · pp. 33–34
  • In the RS formulation, transformed variables u_t=e^-µa_t and v_t=e^-µb_t satisfy polynomial equations parameterized by λ and T, with ordered boundary conditions.The chemical potential is recovered from λ and u_0 after solving these equations.Source: a. RS cavity method · p. 34
  • The RS thermodynamic quantities and cumulative activation-time distribution are obtained from the transformed fixed-point solution.The distribution satisfies P_0=θ and P_T=1, corresponding to the initial active fraction and complete final activation.Source: a. RS cavity method · p. 34

b. Energetic 1RSB cavity method

The energetic 1RSB treatment solves a normalized probability-vector fixed point and derives its potential from site and edge contributions. For l = k, the transformed equations coincide with the RS system and become directly solvable by recurrence.

b. Energetic 1RSB cavity method

  • The energetic 1RSB method determines a normalized vector P=(p_0,...,p_{T−1},q_T,...,q_0) from the factorized fixed-point equation P=G(P,...,P).Source: b. Energetic 1RSB cavity method · p. 35
  • Its thermodynamic description combines the factorized site and edge contributions of the energetic 1RSB potential, with θ obtained from the derivative of Φ_e with respect to y.Source: b. Energetic 1RSB cavity method · p. 35
  • Changing variables from p_t,q_t,y to u_t,v_t,λ yields exactly the same equations, boundary conditions, and inequalities as in the RS case.The parameter y is recovered from the normalization condition.Source: b. Energetic 1RSB cavity method · p. 35

c. Simplifications for l = k

  • When l=k, the equations simplify because S(u,v) becomes independent of u and the solution can be obtained by successive recurrences.The activation-time distribution and thermodynamic observables can then be simplified as well.Source: c. Simplifications for l = k · p. 36

d. Numerical resolution for l < k

For l<k, the transformed cavity equations require numerical solution, whereas the large-T trivial branch admits an analytic interpretation. In that branch, the activation-time distribution matches that of random initial conditions above the percolation threshold.

d. Numerical resolution for l < k

  • For l<k, Newton-Raphson iterations solve the cavity equations because no triangular variable transformation was found.Depending on λ and T, the parametrization can show zero, one, or two relevant solutions, although each chemical potential or 1RSB parameter has a single physical solution.Source: d. Numerical resolution for l < k · p. 36

2. The large T limit

a. The trivial solution

  • The recursion is represented graphically through v_{t+1}=1+λv_t^k, with distinct fixed-point behavior below, at, and above λ_c.Source: Figure 14 · p. 37, a. The trivial solution · p. 37
  • For θ>θ_r, the trivial branch yields s(θ)=−θ ln θ−(1−θ)ln(1−θ), and its activation-time distribution equals that of random initial conditions.The branch is characterized by u_t-independent solutions and the relation e^u=1+λe^{uk}.Source: a. The trivial solution · p. 37

b. Asymptotics for l = k

For l = k, the large-T behavior is governed by a critical parameter λc separating finite and divergent recursion behavior, with scaling windows resolving the non-trivial density regime.

Critical recursion

  • λ > λc makes vt diverge doubly exponentially, while λ ≤ λc keeps vt finite as t →∞.The divergent branch also sends u0 to infinity and produces a vertical tangent in the RS entropy and energetic 1RSB complexity curves.Source: b. Asymptotics for l = k · p. 37
  • The divergent branch converges to an initially active-site density θ = (k −1)/(2k) in both RS and energetic 1RSB formalisms.This branch is therefore represented as a vertical segment, with Fsite tending to k + 1.Source: b. Asymptotics for l = k · pp. 37–38

Scaling regime

  • The limits T →∞ for λ < λc and λ > λc cover only the trivial RS entropy branch and its vertical segment, so the interval [θr/2, θr] requires a T-dependent scaling window around λc.At λ = λc, the recursion approaches a fixed point; just above criticality it spends order δ−1/2 steps near that avoided fixed point.Source: b. Asymptotics for l = k · p. 39
  • A first scaling ansatz with fixed bλ < 1 yields u0 → vc and therefore describes only the endpoint θ ≈ θr of the trivial branch.To obtain non-trivial densities, bλ must approach 1 as 1 − O(T −1/4).Source: b. Asymptotics for l = k · pp. 39–40
  • The refined scaling regime parametrized by eλ spans θ from θr/2 to θr in RS, while the energetic 1RSB result remains parametrized by eλ.Finite-T corrections in this regime are polynomially small in T, whereas the k = l cases have corrections of order k−T in the stated limits.Source: b. Asymptotics for l = k · pp. 39–40

Activation times

  • For finite activation times in the eλ regime, Fsite(eλ,t) approaches its long-time value, so the activation-time distribution has support that does not scale with T.The cumulative distribution follows by expressing the eλ-dependent quantities as functions of θ.Source: b. Asymptotics for l = k · p. 40

c. Asymptotics for l < k

For l < k, the large-T recursion follows a line of marginal fixed points satisfying C(u,v) = 1, with boundary layers determining its endpoints and thermodynamic quantities.

Marginal fixed-point line

  • The four-dimensional recursion has fixed points with u = u+ and v = v−, but only the line C(u,v) = 1 lacks unstable directions and can connect the two boundary manifolds as T →∞.Numerical solutions confirm that most (ut,vt) lie on this marginal line, away from the two boundary regions.Source: c. Asymptotics for l < k · p. 41, Figure 15 · p. 41

Scaling solution

  • The large-T solution is described by scaling functions U(s) and V(s), with s = t/T, satisfying C(U(s),V(s)) = 1 at leading order.For finite t, ut tends to u∗ while vt follows a reduced recursion and converges to v∗ at the beginning of the scaling regime.Source: c. Asymptotics for l < k · pp. 41–42

Boundary matching

  • The endpoint constants satisfy C(u∗,v∗) = 1 and v∗ = 1 + S(u∗,v∗), while the terminal constants satisfy C(bu,bv) = 1 and bv = S(bu,bv) + bu − S(bu,bu).For λ ∈ ]0,λr], the ordering is u∗ ≥ bu ≥ bv ≥ v∗; at λr the four values merge pairwise with the trivial solution.Source: c. Asymptotics for l < k · p. 42

Thermodynamic quantities

  • The thermodynamic limits Fedge and Fsite are obtained by converting sums over the scaling trajectory into integrals along C(u,v) = 1.The resulting parametric representations of s(θ) and Σe(θ) follow from the corresponding definitions after evaluating these integrals.Source: c. Asymptotics for l < k · pp. 42–43

Activation times

  • For activation times t = sT with 0 < s < 1, the limiting Fsite expression yields the fractions activating at the very beginning and very end of the process.These endpoint fractions are obtained by taking s → 0+ and s → 1−.Source: c. Asymptotics for l < k · p. 43
Loading 1407.7361v2…