K-core attack, equilibrium K-core, and kinetically constrained spin system
Hai-Jun Zhou






^1Institute of Theoretical Physics, Chinese Academy of Sciences, Zhong-Guan-Cun East Road 55, Beijing 100190, China

^2MinJiang Collaborative Center for Theoretical Physics, MinJiang University, Fuzhou 350108, China

^3School of Physical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China





  Kinetically constrained spin systems are toy models of supercooled liquids and amorphous solids. In this Perspective, we revisit the prototypical Fredrickson-Andersen (FA) kinetically constrained model from the viewpoint of K-core combinatorial optimization. Each kinetic cluster of the FA system, containing all the mutually visitable microscopic occupation configurations, is exactly the solution space of a specific instance of the K-core attack problem. The whole set of different jammed occupation patterns of the FA system is the configuration space of an equilibrium K-core problem. Based on recent theoretical results achieved on the K-core attack and equilibrium K-core problems, we discuss the thermodynamic spin glass phase transitions and the maximum occupation density of the fully unfrozen FA kinetic cluster, and the minimum occupation density and extreme vulnerability of the partially frozen (jammed) kinetic clusters. The equivalence between K-core attack and the fully unfrozen FA kinetic cluster also implies a new way of sampling K-core attack solutions.
  

  

  Key words: Fredrickson-Andersen model; K-core attack; spin glass; jamming
  

  PACS: 64.70.Q-; 05.70.Fh; 75.10.Nr; 89.75.Fb


K-core attack, equilibrium K-core,  and kinetically constrained spin system
    Hai-Jun Zhou^1,2,3
    April 29, 2024
===========================================================================





§ INTRODUCTION



A graph G is formed by N vertices and the edges linking between these vertices. Two vertices i and j are said to be nearest neighbors if they are connected by an edge, which is often denoted as (i, j). The degree d_i of vertex i is defined as the number of attached edges. The mean vertex degree is the averaged value of d_i over all the vertices, and it is denoted as D in the present paper. Lattice structures are typical graphs encountered in the field of condensed-matter physics, finite-connectivity random graphs are widely adopted in theoretical computer science and applied mathematics, and small-world and scale-free complex networks are common in real-life social and technological systems <cit.>.

An important collective and global structural property of a graph is its K-core <cit.>. According to the strict definition, the K-core of a graph G is the unique subgraph induced by a maximal set of vertices under the following simple bootstrap criterion: a vertex i is a member of the K-core if and only if at least K of its d_i nearest neighbors are also members of the K-core <cit.>. As a simple positive example, we see that if d_i ≥ K for all the vertices, the whole graph G is a K-core. Given a graph, we can get its K-core by recursively deleting the vertices that are connected to fewer than K other vertices. If a non-empty subgraph survives this pruning process, then it is the K-core of the original graph, otherwise the graph has no K-core. For example, if a graph is a collection of tree components and there are no loops within the graph, then it contains no K-core, for any K≥ 2.

We can generalize the concept of K-core to incorporate the more common situations of different vertices having different threshold values. Given a set { k_i: i ∈ G} of N non-negative integers, we can define the {k_i}–core as the unique maximal subgraph with each member vertex i being accompanied by at least k_i nearest neighboring member vertices <cit.>. The K-core is simply the special case of {k_i}–core with k_i = K for all the vertices. To be concise, we will assume k_i = K in the following discussions. The extension to the more general {k_i}–core is straightforward.

There have been many inspiring examples of applying K-core to various structural and dynamical issues of complex networks science, see Ref. <cit.> for a comprehensive review. The present Perspective is much limited in scope. We will only review some recent theoretical work done on two K-core combinatorial optimization problems. The emphasize is on the deep relevance of these K-core spin glass problems to the statistical mechanics of kinetically constrained spin models. Especially we will make explicit and obvious the intrinsic link between the K-core attack problem and the configuration space of kinetically constrained spin models (Sec. <ref>). The methodological implications of this bi-directional link will be discussed. 

Kinetically constrained spin systems are simple and popular graphical toy models for understanding the glassy dynamics of supercooled liquids and the jammed packing of amorphous solids <cit.>. The Fredrickson-Andersen (FA) model is a prototypical and the simplest kinetically constrained spin system <cit.>. It assigns a binary occupation state, empty or being occupied, to every vertex of the graph G. For a vertex i to flip its state, however, it must have less than k_i occupied nearest neighbors at the moment of flipping. The FA model and other kinetically constrained spin models have served as basic theoretical platforms to study the dynamical phase transitions of supercooled liquids <cit.>. For simplicity, we will consider only the FA model here (Sec. <ref>).

The local kinetic rule of the FA system leads to kinetic ergodicity-breaking in the configuration space and the emergence of many kinetic clusters, each of which contains all the mutually visitable microscopic occupation configurations (Sec. <ref>). The one-to-one mapping between kinetic clusters and specific instances of the K-core attack problem (Sec. <ref>) implies a principled way of studying the statistical properties of individual kinetic clusters. We focus on the K-core attack problem in Section <ref>, and discuss the issue of thermodynamic phase transitions and maximum unjammed packing. It will become clear that the spin glass transitions in single FA kinetic clusters are induced not by the formation of K-core, but by the global constraint of K-core absence.

The local kinetic rule of the FA system is, at least apparently, identical to the local K-core static constraint. Because of this similarity, the dynamical properties of the FA kinetic system has been studied from the perspective K-core percolation <cit.>, which manifests as the sudden emergence of an extensive K-core of occupied vertices as the fraction of occupied vertices increases beyond certain threshold value p_c <cit.>. This discontinuous K-core phase transition (also referred to as the bootstrap transition) has been associated with the jamming transition of structural glasses <cit.>. We will briefly review the K-core phase transition in Sec. <ref>. Following this, we will then review some recent theoretical efforts on the equilibrium K-core problem, and discuss its relevance with the jammed kinetic clusters of the FA system (Sec. <ref>). Results on minimum jammed packing and on extreme vulnerability of jamming will be demonstrated.

All the theoretical results discussed in the present paper were obtained on random graph ensembles. To deeply appreciate the thermodynamic properties of finite-dimensional FA kinetic systems, we need to extend the investigations on K-core attack and equilibrium K-core optimization problems to finite-dimensional lattices (outlook in Sec. <ref>). Hopefully, this Perspective might be useful and stimulating at least to some researchers working on kinetic constrained models or on K-core optimization problems.




§ THE FREDRICKSON-ANDERSEN MODEL



The Fredrickson-Andersen model was a prototypical kinetically constrained spin system introduced in the early 1980s for the purpose of understanding the dynamical properties of supercooled liquids and structural glasses <cit.>. It has inspired many other kinetically constrained spin models and has stimulated a lot of theoretical and simulation studies <cit.>. The FA model is defined on a finite-connectivity graph G of N vertices <cit.>. Each vertex with index i ∈{1, 2, …, N} has a binary occupation state, c_i = 0 (vertex being empty) or c_i = 1 (vertex being occupied). A microscopic configuration of the whole system at any time is the collection of all these individual states, c⃗≡ (c_1, c_2, …, c_N), and the total number of possible configurations is 2^N. All these configurations are allowed for the system. This is quite different from the static rule of the lattice glass models that were introduced in the early 2000s <cit.>. In a lattice glass, an occupied vertex prohibits its nearest neighbors from being too densely occupied. Such local and static excluded-volume effects are completely absent in the FA system.

The total energy E of a microscopic configuration c⃗ of the FA system is defined as


    E( c⃗ ) = - ∑_i=1^N c_i   .


The energy contribution (-c_i) of each vertex i depends only on its occupation state.  The occupied state c_i = 1 is favored in the energetic sense, and the fully occupied configuration (1, 1, …, 1) is the unique minimum-energy configuration of the system. Because there is no interaction energy between any pair of neighboring vertices, the equilibrium Boltzmann distribution P_B(c⃗) of model (<ref>) is factorized,


    P_B( c⃗ ) =  ∏_i=1^N q(c_i )   ,
        with   
      q(c_i ) = e^β c_i/1 + e^β  .


Here β is the inverse temperature of the environment, and q(c_i) is the marginal probability of the binary occupation state c_i.

We follow this factorized probability distribution to sample an initial configuration (denoted as c⃗^ 0) at certain inverse temperature β_0. The initial states of the N vertices are independent, and every vertex is occupied with the same probability. The mean fraction p of initially occupied vertices is then


    p  =  1/1 + e^-β_0  .



Starting from such an initial configuration c⃗^ 0 with occupation density p, the system then evolves with time and finally reaches equilibrium at another inverse temperature β. The inverse temperature β can be the same as the value β_0 of sampling c⃗^ 0. It can also be different from β_0, to allow for cooling or heating in the system and for changes in the mean occupation density.

The FA system explores the configuration space by single-vertex state flips. At each elementary time step (say Δ t = 1/N), a vertex i is picked up uniformly at random from the N vertices, and its state is flipped to the opposite one with probability w_c_i → 1-c_i  and kept unchanged with the remaining probability 1 - w_c_i→ 1-c_i. The flipping probability strongly depends on the states of the nearest neighbors of this vertex i. Denote ∂ i ≡{j : (i, j) ∈ G} as the vertex subset containing all the nearest neighbors. If there are k_i or more occupied nearest neighbors and


    ∑_j∈∂ i c_j  ≥ k_i   ,


then vertex i is blocked from changing state, and w_c_i → 1-c_i = 0 independent of the particular value of c_i.

The empty state has a facilitation effect. In the opposite (facilitated) situation of fewer than k_i occupied nearest neighbors,


    ∑_j∈∂ i c_j  <   k_i   ,


vertex i is free to change state. The flipping probabilities w_1→ 0 and w_0→ 1 then satisfy the detailed balance condition at inverse temperature β,


    w_0→ 1/w_1→ 0 = e^β  .


A convenient choice is to set


    w_0→ 1 = 1/1 + e^-β  ,
        
      w_1→ 0 = 1/1+e^β  .



Notice that under the condition of fixed neighbor states, the state flip between c_i=0 and c_i=1 for each vertex i is locally reversible. The local equilibrium distribution of c_i under such a facilitated boundary condition is described by the same expression q(c_i) of Eq. (<ref>).

For simplicity, we will assume all the threshold numbers k_i in Eqs. (<ref>) and (<ref>) are identical to the same integer value K, with K ≥ 2. 




§ KINETIC ERGODICITY-BREAKING



Because the state of any vertex i is not allowed to flip under the kinetic blocking condition (<ref>), the configuration space of the FA system is not kinetically ergodic as a whole. The 2^N microscopic configurations are distributed to different kinetic clusters C_α with indices α∈{1, …, 𝒩}, where 𝒩 denotes the total number of kinetic clusters. This is a phenomenon of kinetic ergodicity-breaking.



 §.§ The fully unfrozen kinetic cluster C_1


Let us assign the cluster index α = 1 to the kinetic cluster which contains the fully empty configuration 0⃗ with all vertices being empty. We put to this cluster C_1 all the other configurations that are visitable from this seed configuration. Since each state flip is locally reversible, if a configuration c⃗^ ' can be visited from another configuration c⃗ through a sequence of allowed single-vertex flips, the reverse is also true: configuration c⃗ can be visited from c⃗^ ' through a sequence of allowed single-vertex flips. The cluster C_1 therefore contains configuration 0⃗ and all the other configurations that can reach and be reached from 0⃗ through a set of allowed single-vertex flips.

For each vertex i, there is at least one configuration c⃗∈ C_1 in which its state c_i = 1 (e.g., the one with all the other vertices being empty) and there is at least one configuration in which its state c_i = 0. In other words, every vertex is unfrozen in the kinetic cluster C_1.

Notice that if a vertex i is unfrozen in certain kinetic cluster C_α (not necessarily C_1), and its state is c_i = 1 in one configuration c⃗ of this cluster, then the other configuration c⃗^ ' which differs with c⃗ only at vertex i (c_i = 0) must also belong to the same kinetic cluster C_α. We follow the elegant arguments of Perrupato and Rizzo to prove this statement <cit.>.

Since vertex i is unfrozen, there must be a sequence of allowed single-vertex flips, c⃗→c⃗^ 1→…→c⃗^ n, with the last configuration c⃗^ n having c_i = 0. Then the reverse of this trajectory but with c_i being fixed to c_i = 0 must also be an allowed kinetic trajectory. This modified reverse trajectory leads to the configuration c⃗^ ' which is identical to c⃗ except for c_i. This means that c⃗ and c⃗^ ', which differ only at vertex i, are mutually visitable and are members of the same cluster C_α.





Because of this co-appearance property, we can prove that C_1 is the only kinetic cluster in which all the vertices are unfrozen. Suppose this statement is false and there is another kinetic cluster (say C_α) in which all the vertices are also unfrozen. Then if c⃗∈ C_α is a configuration with c_i = 1, the other configuration c⃗^ ' which is identical to c⃗ except for vertex i must also belong to C_α. If some vertices (say j) are occupied in configuration c⃗^ ', we can again flip c_j to c_j = 0 to get another configuration c⃗^ '' that is reachable from c⃗^ '. Continue this flipping process, we will finally arrive at the all-empty configuration 0⃗, which belongs to kinetic cluster C_1. Therefore the fully unfrozen cluster C_α must be identical to C_1.

To complement these above discussions, we draw in Fig. <ref> a schematic picture for the organization of microscopic configurations in the fully unfrozen cluster C_1. 




 §.§ Fully frozen and partially frozen clusters



At the other limit is the cluster C_𝒩 with the maximum index α = 𝒩. It contains a single configuration 1⃗ with all the vertices being occupied. Every vertex is obviously frozen in this single-configuration cluster.

There are other frozen clusters with indices α < 𝒩. If every empty vertex of a configuration c⃗ has ≥ K occupied nearest neighbors, and every occupied vertex of this configuration also has this property, then c⃗ is a fully frozen configuration and it forms a fully frozen kinetic cluster. It is quite easy to write down many such fully frozen configurations for a given input graph G.

Besides fully unfrozen and fully frozen kinetic clusters, there are other partially frozen kinetic clusters C_α, each of which contains at least two (but often many) microscopic configurations. Some of the vertices are frozen in such a cluster, while the states of the remaining vertices are unfrozen. 

A kinetic cluster C_α can be fully specified by its set (F_1) of frozen occupied vertices and the set (F_0) of frozen empty vertices. If two kinetic clusters have identical set F_1 and identical set F_0, they must be the same cluster. To prove this, one only needs to show that the configuration with all the unfrozen vertices being in the empty state must belong to both clusters, and hence these two clusters must be the same.




§ GLOBAL CONSTRAINT ASSOCIATED WITH A SINGLE KINETIC CLUSTER



Each single kinetic cluster C_α contains a maximal set of microscopic configurations c⃗ that are mutually visitable through a sequence of allowed single-vertex flips. There may be strong correlations among the occupation states of the unfrozen vertices of this cluster C_α. We now prove a simple but highly nontrivial fact, that all these possibly complicated correlations can be encoded in a single global constraint.

Let us first consider the fully unfrozen cluster C_1, which contains all the configurations that are visitable from the fully-empty 0⃗. Every vertex i can take both states c_i = 0 and c_i = 1. Given a microscopic configuration c⃗∈ C_1, let us denote by U_0 the set of empty vertices:


    U_0( c⃗ )  =   { i : c_i = 0 }  .


Since there are no frozen vertices in C_1, all the other vertices not belonging to U_0 are in the occupied state. It is obvious that the subgraph induced by these occupied vertices of c⃗ should not form a K-core, because otherwise some of these vertices will be permanently frozen.

The reverse statement is also true. If the subgraph formed by the occupied vertices of a configuration c⃗ and the edges between them is not sustaining a K-core, this configuration must belong to the fully unfrozen cluster C_1, because there is a sequence of allowed single-vertex flips linking configuration c⃗ to the fully-empty 0⃗.

The above two statements mean that the set U_0( c⃗) of empty vertices of each configuration c⃗∈ C_1 must be a K-core attack set: The residual subgraph of G after deleting all the vertices of set U_0(c⃗) contains no K-core <cit.>. And if U_0( c⃗) is a K-core attack set, then the configuration c⃗ must be a member of the fully unfrozen cluster C_1.

Therefore, the configuration subspace C_1 is equivalent to all the K-core attack sets U_0 of the graph G. The statistical physics property of the fully unfrozen cluster C_1 can then be explored by studying the solution space of the corresponding K-core attack problem. This idea will be followed in the next section <ref>.

We make an interesting remark here. This significant link between the configuration subspace C_1 of the FA system and the K-core attack problem also implies a new simulation algorithm to sample solutions for the K-core attack problem. We may adopt the single-vertex flip dynamics of the FA system to obtain equilibrium K-core attack solutions, without checking the global K-core-absence constraint. We will explore this idea in a separate paper, here we focus on the implications of the K-core attack problem to the FA system. (For this sampling purpose, to accelerate the Markov-chain dynamics, we can also add the elementary process of swapping the states of two flippable vertices i and j, without violating the FA kinetic rule.) 

The above-established equivalence relationship also extends to the partially frozen kinetic clusters C_α. For such a partially frozen cluster, we also denote the set of empty unfrozen vertices of each configuration c⃗∈ C_α as U_0( c⃗), namely


    U_0( c⃗) 
       = {i : c_i = 0  ,  vertex  i  being unfrozen}  .


Obviously, all the occupied unfrozen vertices of the configuration c⃗ should not belong to the K-core. Therefore this set U_0 of empty vertices must be a K-core attack set for all the unfrozen vertices of the kinetic cluster C_α.




§ EXPLORING THE FULLY UNFROZEN KINETIC CLUSTER



The discussion of the preceding section <ref> convinces us that each kinetic cluster C_α of the FA model contains all the solutions of a spin glass model with a global constraint of K-core absence. This perfect superposition of configuration spaces implies that, to explore and appreciate the rich statistical property of individual kinetic clusters, we could turn the kinetic FA system into a static spin glass model and then treat this static model by the advanced methods of equilibrium statistical mechanics.  

We begin by defining the K-core attack problem more precisely. To be concrete, let us focus on C_1, the kinetic cluster free of any frozen vertices. Each partially frozen kinetic cluster C_α can be treated in the same way. The only slight complication is that the spin glass model should be defined only on the set of unfrozen vertices, with some environmental pinning effects induced by the frozen vertices.




 §.§ The K-core attack problem


As mentioned earlier, the K-core of a graph G is the unique maximal subgraph in which every member vertex is connected to at least K other member vertices. This unique K-core can be determined through a simple vertex pruning process. As long as there is a vertex whose degree is less than K, it is deleted from the graph together with its attached edges. If a non-vanishing subgraph survives this iterative pruning, it is the K-core.

Given an input graph G of N vertices, let us assign a binary occupation state c_i to each vertex i, c_i = 1 (occupied) or c_i = 0 (empty). The total number of possible microscopic configurations is simply 2^N. If a vertex i is occupied, its energy is E_i = -1, otherwise its energy is E_i = 0. We impose a global constraint on the occupation configuration as follows: The subgraph induced by the occupied vertices should not contain a K-core. This means that if we delete all the empty vertices from the graph G, the remaining subgraph should completely dissolve under the K-core pruning process.

Under this K-core-absence global constraint, we define an equilibrium partition function Z^atk(β) for our K-core attack problem as


    Z^atk(β) = ∑_c_1, …, c_N  I_0( c_1, …, c_N)
      ∏_i=1^N e^β c_i  .


Here I_0(c_1, …, c_N) ∈{0, 1} is the K-core-absence indicator function: I_0= 1 if the occupied vertices of the configuration {c_1, …, c_N}  does not sustain a K-core, otherwise I_0 = 0. This partition function is a weighted summation over all the configurations of the unfrozen kinetic cluster C_1. If a satisfying configuration has N_1 occupied vertices then its contribution is e^β N_1.

The K-core attack problem is a challenging combinatorial optimization problem <cit.>. A special case is the 2-core attack problem (K=2), which means destroying all the loops in the graph by removing a set of vertices, and it is also known as the feedback vertex set problem <cit.>. In the literature, the practical significance of the feedback vertex set problem has been linked to identifying influential spreaders in a complex network <cit.>, see also review articles <cit.>.

At this point, it is helpful to emphasize again the fundamental difference between the K-core attack model (<ref>) for the kinetically constrained FA system and the lattice glass model <cit.>. The latter is characterized by local excluded-volume constraints, such that each occupied vertex i only allows fewer than k_i of its nearest neighbors to be occupied. Some well-known nondeterministic polynomial-complete (NP-complete) optimization problems, such as the vertex cover problem <cit.> and the dominating set problem <cit.>, can also be viewed as lattice glass models. It is now well accepted that these local geometric constraints can lead to ergodicity-breaking in the thermodynamic sense (see also related work linking to the p-spin interaction models <cit.>). Various spin glass macroscopic states will emerge at high densities of occupied vertices.

In contrast, there are no local constraints in the NP-complete K-core attack model (<ref>). All the 2^1+d_i possible local occupation arrangements concerning a vertex i and its d_i nearest neighbors are allowed. The expected low-temperature (high-β) glass phases of this model are completely caused by a single global constraint, that the occupied vertices should not build a K-core. As the K-core-absence constraint is a direct consequence of kinetic visitability within cluster C_1, the low-temperature glass phases of the FA kinetic system, if exist, are essentially thermodynamic phases induced by local kinetic rules.

Stimulated by the breakthrough made on the random K-satisfiability problem in 2002 <cit.>, many NP-complete combinatorial optimization problems have been studied by the mean field cavity method of statistical physics during the last two decades <cit.>. We can also study the K-core attack model (<ref>) by the spin glass cavity method, but a main technical complication is that the indicator function I_0(c_1, …, c_N) depends on the states of all the N vertices. We need to find an efficient way to implement the K-core-absence global constraint into a set of local constraints.

There are two different strategies in the literature. The direct and simple strategy is to assign to each vertex i an integer time label t_i ≥ 0 <cit.>. The initially deleted vertices all have time label t=0 and all the other vertices have positive time labels. The local constraint associated with a vertex i can be constructed based on the K-core pruning dynamics. This implementation is rigorous, but each vertex has many different states and the configuration space of the resulting model is very huge. The other strategy is to map the K-core attack problem to a polymer packing problem <cit.>. Each polymer is essentially in the shape of a directed tree, with the direction marking the partial time order of the K-core pruning dynamics. Many such polymers are packed together in graph G under some local constraints. This second implementation is not completely equivalent to the K-core-absence global constraint. Its advantage is that each vertex only has a small number of states. The message-passing algorithms inspired by this implementation are very efficient and are able to construct close-to-minimum K-core attack solutions for single random graph instances <cit.>. 

Without delve into more technical details, we now review in the following two subsections some main theoretical results obtained on random graphs. Unlike lattice systems, there are no structure in a random graph G. All the edges in such a graph are randomly connected, without any constraint or with the local constraints of fixed vertex degrees. Such a random graph is locally tree-like, and the typical length of loops diverges logarithmically with graph size N <cit.>.  




 §.§ Entropy and maximum occupation density


The partition function (<ref>) contains rich information about the energy landscape of the configuration subspace C_1. The mean occupation density ρ of the graph is defined as the average of the number N_1 (rescaled by N) of occupied vertices among all the configurations that satisfy I_0 = 1, each with weight e^β N_1. The abundance of microscopic configurations at each occupation density ρ is measured by the entropy density s(ρ), which can be deduced from the thermodynamic relationship Z^atk(β) ≈ e^β N ρ e^N s, namely


    s = -  βρ +  1/Nln[ Z^atk(β) ]   .







The mean occupation density ρ increases with the inverse temperature β. When ρ becomes sufficiently large, the entropy density s(ρ) as a function of ρ shows a decreasing trend, and it decreases to zero as ρ approaches certain value ρ_max from below. This threshold value ρ_max is the maximum occupation (packing) density that is achievable in the kinetic cluster C_1, and the corresponding configurations are the densest packing configurations of this kinetic cluster C_1.

As an example, we show in Fig. <ref> the theoretical entropy density curve s(ρ) for the 2-core attack problem (K=2) on the ensemble of maximally random graph of mean vertex degree ⟨ d_i ⟩ = D = 10.0 <cit.>. Such random graphs are referred to as Erdös-Rényi graphs in the literature <cit.>. The (D/2) N edges in such a graph are randomly and independently drawn from the N(N-1)/2 candidate edges, so the vertex degrees are not exactly the same but are distributed around the mean value D.

We see that s(ρ) is a concave function of occupation density ρ. The entropy density approaches zero when ρ reaches the maximum value ρ_max = 0.517. This means that the densest packing as kinetically achievable from the fully empty configuration can not exceed the density 0.517. Numerical results obtained by two different heuristic optimization algorithms on single graph instances have confirmed this prediction <cit.>. This example demonstrates that the static model (<ref>) makes it possible to compute the maximum packing density of the fully unfrozen kinetic cluster C_1. We also notice that, for K = 2, the maximum packing density ρ_max on regular random graph ensembles of degree D has been rigorously upper-bounded <cit.>.





The maximum packing density ρ_max depends strongly on the threshold value K and increases monotonically with K. Table <ref> presents some numerical results obtained on several regular random graph ensembles to confirm this trend. Notice that all the vertices in a regular random graph have the same vertex degree D. The simulation results obtained through two heuristic algorithms are also shown as comparison <cit.>. At fixed value of D, we find that the relative difference between algorithmic results and the theoretical prediction increases as K increases to D-1. This is an indication that reaching the densest packing configurations within the kinetic cluster C_1 is an extremely hard optimization problem. 






 §.§ Spin glass phase transitions


When the inverse temperature β becomes sufficiently high in Eq. (<ref>), the mean density ρ of occupied vertices will be bounded above by the maximum value ρ_max. The limiting value may be impossible to reach in numerical simulations, and instead the low-temperature (high-β) region may be in the spin glass phase. For random graph ensembles, the existence of spin glass phase transitions have been confirmed by theoretical computations.

According to the mean-field theory of spin glasses <cit.>, a graphical model such as (<ref>) could experience a dynamical spin glass phase transition at a critical inverse temperature β_d. As β reaches β_d from below, the configuration space suddenly breaks up into an exponential number of subspaces, each of which is referred to as a macroscopic state, with well-defined thermodynamic quantities such as free energy density and entropy density. There are very high free-energy barriers between these macroscopic states, so that if the system is staying at one macroscopic state with β > β_d, it will take a diverging time to overcome the free energy barrier to reach another different macroscopic state. The critical value β_d for random graph systems can be computed precisely through a method of tree-reconstruction <cit.>.





Another important critical inverse temperature is β_c, the condensation phase transition point. At β = β_c, a non-exponential number of macroscopic states start to dominate the configuration space, while all the other exponential number of macroscopic states have less statistical weights compared with these dominating ones. At different values of β > β_c the dominating macroscopic states may be different. For some systems the condensation transition occurs after the dynamical transition, so β_c > β_d. But for some other systems the two phase transitions coincide and β_c = β_d.  

Figure <ref> shows the critical inverse temperatures β_d and β_c, obtained for the K-core attack problem with K=2 on the regular random graph ensembles of various degrees D <cit.>. Such a phase diagram is quite similar to that of the random vertex cover problem which is a lattie glass model <cit.>. This similarity indicates that the thermodynamic spin glass phase transitions of the kinetic constrained model and the lattice glass model may be closely related. When D ≤ 60 we find that β_c = β_d, but for higher values of D, we have β_c > β_d.

Similar spin glass phase transitions also occurs for K ≥ 3 on random graph ensembles, but the computation of the critical values β_d and β_d become more difficult <cit.>. The existence of these spin glass phase transitions mean that the FA system defined on random graphs really has thermodynamic phase transitions. It is not yet clear whether these spin glass phase transitions will also occur for finite-dimensional systems. Systematic studies on the low-temperature properties of the K-core attack model (<ref>) on finite-dimensional systems are needed to fully resolve this fundamental issue.


For β higher than the condensation transition value β_c the configuration subspace may have the property of full-replica-symmetry-breaking. We expect that the FA system in the kinetic cluster C_1 will also show property similar to the Gardner phase of structural glasses <cit.>. This is an interesting and challenging topic for further exploration, especially for finite-dimensional systems.




§ K-CORE PHASE TRANSITION



Starting from an initial occupation configuration c⃗^ 0 that happens to reside in certain kinetic cluster C_α of the graph G, the evolution trajectory of the FA kinetic system is then confined to this cluster and it will not jump to another different one. To determine which vertices can change occupation states in this cluster C_α and which are completely frozen, we can perform the simple K-core pruning process with c⃗^ 0 as the initial condition: If a vertex i has less than K occupied nearest neighbors, then it is added to the set of unfrozen vertices and is deleted from the graph; and this is repeated on the vertices of the remaining graph until no further modification can be made. The vertices of the final residual graph are then either frozen to the occupied state or frozen to the empty state. It is straightforward to prove that the frozen occupied vertices must form a K-core within themselves. We denote by f the fraction of vertices in this K-core (f is also its relative size). The K-core relative size f can be estimated by a simple mean-field theory for a finite-connectivity random graph G <cit.>. This is also an interesting topic of network science <cit.>.



 §.§ Regular random graph ensemble


As a concrete demonstration, we consider the ensemble of regular random graphs with uniform degree D. The initial fraction of occupied vertices is p, and these vertices are drawn uniformly at random from the graph. A crucial empirical observation underlying this percolation theory is the following: If an extensive frozen K-core emerges in the graph G, the other complementary part of the graph will not be densely connected but will be a collection of (almost) loop-free tree components.

The fraction f of frozen occupied vertices in the regular random graph is equal to the probability of a randomly chosen vertex i being frozen to c_i = 1. Assuming statistical independence among the nearest neighbors of this focal vertex i, we can write down the following expression:


    f = p ∑_d=K^DD!/d! (D-d)!γ^d (1 - γ)^D-d  .


Here γ is the conditional probability of a nearest neighbor j being frozen to the occupied state, given that the state of vertex i is fixed to c_i = 1. The self-consistent equation for γ is similar to Eq.(<ref>),


    γ = p ∑_d=K-1^D-1(D-1)!/d! (D-1-d)!γ^d (1 - γ)^D-1-d  .


This equation always has a trivial fixed point γ = 0, corresponding to the absence of frozen K-core (f=0). 

When K = 2, the stable fixed point γ of Eq. (<ref>) starts to gradually deviate from zero at certain critical value p_c of the initial occupation density p. Consequently, the fraction f of frozen occupied vertices also gradually increases from zero as p increases from p_c. A continuous 2-core percolation transition occurs at p = p_c, similar to the conventional site percolation discussed in percolation theory <cit.>. After this transition, the frozen occupied vertices form an extensive 2-core containing N f vertices.

When K ≥ 3, however, the trivial fixed point γ = 0 is always locally stable, and another stable fixed point with γ considerably larger than zero appears suddenly as p exceeds a critical value p_c. The theory therefore predicts a sudden emergence of an extensive K-core with the relative size f jumping from f=0 to a large value, see Fig. <ref> for an example <cit.>. This explosive emergence of a giant frozen K-core has been verified by computer simulations <cit.>. 




The existence of a discontinuous K-core percolation phase transition for K ≥ 3 means that, the maximally random occupation configurations c⃗^ 0 with occupation density p > p_c are highly likely to be kinetically jammed configurations. Extensively many vertices are unable to change their states under the kinetic rule of the FA system. A dynamical phase transition occurs at p = p_c in the evolution trajectories of the FA system. Information about the initial configuration c⃗^ 0 will be largely reserved even as time goes to infinity, if the fraction of occupied vertices in c⃗^ 0 is larger than p_c, while this memory will be completely lost with time if p is less then p_c. 




 §.§ Periodic cubic lattice


The K-core percolation in finite-dimensional regular lattices has also been extensively investigated in the literature <cit.>. Here we show some representative results obtained on the cubic lattice containing N=L^3 vertices, were L is the side length of the lattice. Periodic conditions along each of the three dimensions are imposed, so every vertex has D=6 nearest neighbors. Such lattices are better models than random graphs for understanding real-world physical systems. 

First, consider the case of K=3 (which is also representative of K=1, 2). The simulation results on the mean relative size f of 3-core are plotted in Fig. <ref>. We see that the curve f(p) is a continuous and smooth function of the initial occupation density p and it is almost independent of N for side lengths L ≥ 32. This means that the emergence of 3-core itself is not a phase transition phenomenon. This smooth behavior of f(p) is a consequence of the lattice geometric structure and is relatively easy to understand. As long as p > 0, many minimum cubes formed by four occupied vertices are dispersed in the cubic system and are contributing to the extensive size of the 3-core. This is also the situation for K=1 and K=2. 

Although there is no phase transition of 3-core emergence in the periodic cubic lattice system, there is a continuous phase transition concerning the emergence of an extensive connected component within the 3-core [Fig. <ref>]. This continuous phase transition is resembling the emergence of an extensive giant component in conventional site percolation and it is amenable to finite-size scaling analysis <cit.>. The phase transition point has been located at the critical value of p_c ≈ 0.5726 <cit.>. We also see from Fig. <ref> that, when the initial occupation density p exceeds 0.75, the 3-core relative size can again be well described by the mean field formula (<ref>).




Similar continuous phase transitions also occur for K=1 and K=2. However, when K≥ 4, the K-core percolation on the periodic cubic lattice is a discontinuous process. Some example results obtained for K=4 are shown in Fig. <ref>. For a given system size L (and number of vertices N=L^3), when the initial fraction p of occupied vertices is smaller than certain critical value p_c(L), there is high chance that the random initial configuration c⃗^ 0 contains no 4-core. When p > p_c(L), with high probability there is an extensive 4-core, and its relative size f is close to the value predicted by the mean-field theory (<ref>). The value of p_c(L) for each L is determined as the point of p at which fifty percent of the independent samples c^ 0 contain an extensive 4-core.

Another significant feature of Fig. <ref> is that the threshold value p_c(L) is not fixed but slowly increasing with the side length L. When the periodic cubic lattice becomes infinite, the threshold value will approach unity, p_c(L=∞)= 1 <cit.>. The key to understand this asymptotic behavior is the shape irregularity of a local connected domain of empty vertices. Some of the occupied vertices at the boundary of such an irregular empty domain are unstable and will join this domain. If the enlarged empty domain during this erosion process always deviates significantly from being a cubical shape, it will keep growing. Such rare self-growing empty domains are deemed to be present in an infinite cubic lattice <cit.>.

This type of extreme cascading behavior may be absent in the case of heterogeneous {k_i}–core dynamics, with a finite fraction of the threshold values k_i being k_i ≤ 2 and with these low-threshold vertices i being randomly distributed in the cubic lattice. More thorough simulation studies are needed to clarify this point <cit.>.  Polydispersity of the threshold values {k_i} may be corresponding to polydispersity of particle size or shape in structural glass systems.

We close this section by emphasizing that the kinetic K-core patterns studied here are corresponding to completely random and uncorrelated initial occupation configurations c⃗^ 0. For a given relative size f, these kinetic K-core patterns may far from being the equilibrium (typical) K-core patterns to be discussed in the next section.




§ EXPLORING PARTIALLY FROZEN KINETIC CLUSTERS



As we mentioned earlier (Sec. <ref>), a partially frozen kinetic cluster C_α of the FA system is completely determined by its set of frozen occupied vertices, and these frozen vertices form a jammed K-core pattern in the graph G. The total number 𝒩 of kinetic clusters is huge, and the jammed K-cores obtained through randomized initial conditions (Sec. <ref>) are unlikely to be typical K-core patterns for the given relative size f. In this section we describe an equilibrium K-core statistical physics problem that is quite helpful for exploring the statistical properties of typical jammed K-core patterns.



 §.§ Statistical mechanics of K-core jamming



The total number 𝒩 of possible kinetic clusters for a given graph G is obtained by counting the total number of jammed (frozen) K-cores that can be constructed for this graph. Let us denote by f the fraction of vertices in such a frozen occupied K-core, and denote by s(f) the entropy density of K-cores containing  N f frozen occupied vertices. Then we have


    𝒩 =  1 + 
      ∫ _f_min^1 d f   e^N s(f)   ,


where f_min is the minimum fraction of occupied vertices needed to sustain a non-vanishing K-core.

Computing the entropy density s(f) and determining the minimum occupation fraction f_min are nontrivial tasks. Recently we introduced an equilibrium K-core model to study the network defensive alliance problem and the network engagement problem <cit.>. Since partially frozen kinetic FA clusters are essentially jammed K-core patterns, this same model is naturally also applicable here. In this setting, each vertex i has an aggregated state a_i ∈{0, 1}: a_i = 0 means that it is either initially empty or is unfrozen, and a_i = 1 means that it is always frozen to be occupied. We assign energy values 0 and 1 to these two aggregated states a_i=0 and a_i=1, respectively.

The equilibrium partition function for this system, Z^jam(β), is then written as <cit.>


    Z^jam( β )  =  ∑_{a_i }≠0⃗∏_i=1^N[ δ_a_i^0 + δ_a_i^1
        e^-β I( ∑_j∈∂ i a_j ≥ K ) ]    ,


where the subscript {a_i}≠0⃗ means that the all-empty pattern 0⃗ is excluded from the summation. Here the inverse temperature β controls the size of the K-core. The indicator function I(∑_j∈∂ i a_j ≥  K ) ∈{0, 1} means that if a vertex i belongs to the K-core (a_i = 1), then at least K nearest neighbors of this vertex must also belong to the K-core. For any valid K-core pattern a⃗=(a_1, …, a_N), the equilibrium Boltzmann distribution associated with the partition function Z^jam(β) is simply


    P_B^jam( a⃗ )   =  1/Z^jam(β) ∏_i=1^N
      e^- β a_i   .


We denote by f the fraction (density) of occupied vertices in a K-core pattern, namely f = (1/N) ∑_i a_i. The mean relative size of the equilibrium K-cores at a given inverse temperature is then the average of f among all the valid K-core patterns sampled following Eq. (<ref>).

When β becomes sufficiently high, only the K-core patterns with minimum relative size f_min will be relevant, and the partition function is Z^jam≈ e^- β N f_min. A minimum K-core pattern is extremely sensitive to external perturbations, since deleting any of its member vertices will make the whole K-core completely collapse. This also indicates that a minimum K-core pattern must be very difficult to access in the FA kinetic system (the initial configuration c⃗^ 0 must be chosen extremely carefully).



 §.§ Entropy density, and minimum K-core size



We applied the mean field replica-symmetric cavity method to the model (<ref>), assuming the underlying graph being regular random with uniform degree D <cit.>. Figure <ref> demonstrates some representative theoretical results concerning the entropy density.

For each fixed value of K, the entropy density s(f) has a single maximum at certain intermediate value f^*. This implies that the most abundant K-core patterns have certain intermediate relative size f^*, and the total (exponential) number of kinetic clusters is, to leading order, 𝒩≈ e^N s(f^*). For K=3 and D=6, we have f^* ≈ 0.663 and s(f^*) ≈ 0.561. Notice that the entropy density of kinetic clusters, (1/N) ln𝒩, is much lower than the entropy density ln 2 (≈ 0.693) of microscopic configurations, as it should be.
The entropy of a conventional statistical physics system is a concave function of energy. However, for the K-core jamming system (<ref>), we find that its entropy density s(f) is concave only if f is higher than certain critical value f_x (the inflection point <cit.>). When the K-core relative size is less than f_x, the entropy density becomes a convex function, and the minimum value f = f_min is located at the end of this convex part.  For K=3 and D=6 the predicted minimum is f_min≈ 0.047 and the inflection point is f_x≈ 0.282. Notice that the critical relative size of K-cores obtained through random deletion of occupied vertices, f = 0.294 (Fig. <ref>), is considerably higher than f_x.





This convex property of s(f) means that partially frozen kinetic clusters whose  jammed K-core relative sizes f ∈ (f_min, f_x) are invisible in the conventional thermodynamic sense. If we perform a simulated annealing dynamical process to sample jammed K-core patterns with β increasing at certain rate, it is relatively easy to get K-core patterns with relative sizes ≥ f_x, but the minimum-sized patterns with f ≈ f_min can not be achieved. The sampled jammed K-cores instead often exhibit a sudden drop in their relative size f, from f_x to an intermediate value between f_x and f_min, and then keep fluctuating slightly around this value <cit.>.

Similar to the kinetic procedure of Sec. <ref>, we can also get frozen K-core of occupied vertices by starting from an initial occupation configuration c⃗^ 0. Depending on the particular protocol of sampling c⃗^ 0, K-core jammed patterns with different relative sizes f may be reached. In other words, we may get a “jamming line” which ends at f=1 and possibly begins at f = f_x. We are not yet certain whether or not this jamming line might have some qualitative similarity with the jamming line and the jamming plane of sphere packings <cit.>. Future more systematic investigations may resolve this issue.




 §.§ Extreme vulnerability of K-core



Given a K-core jamming pattern a⃗ = (a_1, …, a_N) of occupied vertices, we say a vertex i is a “break point” if it belongs to this K-core (a_i = 1) and its flipping (a_i → 0) will cause the K-core to break down completely <cit.>. We denote by ϕ the fraction of break-point vertices. If this fraction is positive, then the K-core pattern a⃗ must be extremely vulnerable to single-vertex perturbations. Obviously we have ϕ( a⃗ ) ≤ f( a⃗ ) for any K-core pattern a⃗. In the limiting case of a⃗ being a minimum K-core, then ϕ = f = f_min (all the members are break points).

When the occupation density f of the equilibrium K-core patterns sampled according to Eq. (<ref>) is sufficiently high, the K-core patterns are quite robust to single-vertex perturbations. Deleting any member vertex from the K-core will only cause small shrinkage in its size, and the fraction of break points is ϕ = 0. However, when f is lower than certain threshold value, the equilibrium K-core patterns become extremely vulnerable to single-vertex perturbations, and the fraction ϕ of break points becomes positive. We have quantitatively studied this phase transition to extreme vulnerability by a replica-symmetric mean-field theory and by computer simulations <cit.>.


Some representative results obtained on the regular random graph ensemble of degree D=6 and threshold value K=3 are shown in Fig. <ref>. The order parameter ϕ starts to be positive as the relative size f of K-core is lowered to the critical value f_wt=0.388, which is referred to as the weak tipping point in Ref. <cit.>. The ratio of ϕ versus f then increases continuously as f is further decreased, and this ratio approaches unity as the minimum relative size f_min is approached from above.





It is interesting to notice that the weak tipping point f_wt is distinctively higher than the entropy inflection point f_x [Fig. <ref>]. This may be a common phenomenon for the equilibrium K-core problem on random graph ensembles. 

The fact that a finite fraction f of vertices are break points means that the partially frozen kinetic clusters C_α of the FA system, with relatively low density of frozen occupied vertices (f < f_wt), are staying at the surface of the fully unfrozen kinetic cluster C_1. Just a single “forced” flip of one break-point vertex is enough to melt the whole cluster C_α and make it merge with a sub-region of the cluster C_1.  This fact also implies the existence of long and complicated paths within C_1 between the all-empty 0⃗ and the configurations at the interface to C_α. The surface of cluster C_1 in the high-dimensional configuration space must have very complex structures.

The vulnerability of equilibrium K-core patterns of structured graph instances were also investigated in Ref. <cit.>. It appears that extreme vulnerability is a general property of K-core patterns of relatively low occupation density f. For example, on the three-dimensional cubic lattice with periodic boundary condition, whose vertex degree is D=6 and size is N=32768 (side length L=32), the equilibrium K-core patterns with K=4 starts to have positive ϕ at a high value of f ≈ 0.83 [Fig. <ref>]. The clear cusp close to the maximum value of ϕ in the curve ϕ(f) of Fig. <ref> may indicate some phase separation behavior.

According to the simulation results of Fig. <ref>, ϕ approaches f as the relative size of equilibrium 4-core patterns is reduced to f≈ 0.15, indicating that the minimum value of relative size must be f_min≤ 0.15. We notice that this minimum value is much lower than the typical relative sizes of random kinetic 4-core patterns [Fig. <ref>].




§ CONCLUSION AND OUTLOOK



In this paper, we reviewed some recent statistical physics results on two combinatorial optimization challenges associated with the K-core collective structure of random graphs, the K-core attack problem and the equilibrium K-core problem. The emphasize of this Perspective has been on the link between the K-core optimization problems and the thermodynamical properties of the Fredrickson-Andersen kinetically constrained spin model. In our opinion, the K-core attack problem is a perfect model for studying the thermodynamic phase transitions of the FA kinetic system, and in return, the FA kinetic system can be employed as an efficient local algorithm to sample equilibrium configurations for the globally constrained K-core attack problem (Section <ref>). We hope our work will stimulate more future work on these and other K-core optimization problems.

The statistical physics properties of the K-core attack problem and the equilibrium K-core problem on finite-dimensional lattices are not yet clear. Systematic numerical and theoretical efforts along this direction, especially concerning the spin glass phase transitions, will be highly desirable in the near future. They will be indispensable for us to fully understand the thermodynamic properties of the finite-dimensional FA kinetic systems.

The global constraint of K-core absence makes the K-core attack problem difficult to tackle theoretically. Although some progresses have been made in recent years, the spin glass phase transition issues are largely unexplored, even for random graph ensembles. To explore the rich structure of the low-temperature (high-occupation density) energy landscape, one particularly interesting non-equilibrium issue is to study the quenched dynamics of the K-core attack model at β = ∞ (see Ref. <cit.> for a related recent work).

We have discussed unjammed maximum packing (ρ_max) and jammed minimum packing (f_min) in the FA kinetic system. Similar quantities are also investigated in the field of structural glasses. Structural glasses and amorphous solid are of course more complicated than the FA model and other kinetically constrained spin models. Particles in a structural glass system have translational degrees of freedom, they will diffuse with time and change their interacting partners.  They may also have different sizes and different shapes, and there are friction forces between the contacting particles (see, for example, Refs. <cit.>  for a glimpse of recent simulation and experimental results). But we feel it may be plausible to expect that the kinetic constraints encountered by the particles during the translational and rotational motions will also bring certain global constraint to the microscopic spatial configurations of the structural glass system, similar to the K-core-absence constraint induced by the kinetic rules of the FA model. If this is the case, then the K-core attack problem will also be relevant for structural glass studies. 


  The author thank Luan Cheng, Yang-Yu Liu, Shao-Meng Qin, David Saad, Shang-Nan Wang, Yi-Zhi Xu, Chi Ho Yeung, Ying Zeng, Pan Zhang, Jin-Hua Zhao, and Jianwen Zhou for collaborations on the K-core optimization problems. The valuable comments of Qinyi Liao on an earlier version of this manuscript is warmly acknowledged. The author also benefited from discussions with Xinyi Fan on the K-core preoclation in cubic lattices. The following funding supports are acknowledged: National Natural Science Foundation of China Grants No. 12247104, 12047503.


10

He-Liu-Wang-2009
D.-R. He, Z.-H. Liu, and B.-H. Wang.
Complex Systems and Complex Networks.
Higher Education Press, Beijing, 2009.

Li-etal-2008
Ji Li, Bing-Hong Wang, Wen-Xu Wang, and Tao Zhou.
Network entropy based on topology configuration and its computation
  to random networks.
Chin. Phys. Lett., 25: 4177–4180, 2008.

Kong-etal-2019
Yi-Xiu Kong, Gui-Yuan Shi, Rui-Jie Wu, and Yi-Cheng Zhang.
k-core: Theories and applications.
Phys. Rep., 832: 1–32, 2019.

DeGregorio-etal-2016
P. De Gregorio, A. Lawlor, and K. A. Dawson.
Bootstrap percolation.
In R. A. Meyers, editor, Encyclopedia of Complexity and Systems
  Science, pages 1–26. Springer, New York, 2016.

Chalupa-Leath-Reich-1979
J. Chalupa, P. L. Leath, and G. R. Reich.
Bootstrap percolation on a Bethe lattice.
J. Phys. C: Solid State Phys., 12: L31–L35, 1979.

Seidman-1983
S. B. Seidman.
Network structure and minimum degree.
Social Networks, 5: 269–287, 1983.

Branco-1993
N. S. Branco.
Probabilistic bootstrap percolation.
J. Stat. Phys., 70: 1035–1044, 1993.

Ritort-Sollich-2003
F. Ritort and P. Sollich.
Glassy dynamics of kinetically constrained models.
Adv. Phys., 52: 219–342, 2003.

Garrahan-etal-2011
Juan P. Garrahan, Peter Sollich, and Cristina Toninelli.
Kinetically constrained models.
In L. Berthier, G. Biroli, J.-P. Bouchaud, L. Cipelletti, and W. van
  Saarloos, editors, Dynamical Heterogeneities in Glasses, Colloids and
  Granular Media, chapter 10, pages 341–369. Oxford University Press, New
  York, 2011.

Jack-2020
Robert L. Jack.
Ergodicity and large deviations in physical systems with stochastic
  dynamics.
Eur. Phys. J. B, 93: 74, 2020.

Fredrickson-Andersen-1984
G. H. Fredrickson and H. C. Andersen.
Kinetic ising model of the glass transition.
Phys. Rev. Lett., 53: 1244–1247, 1984.

Tang-etal-2024
Ying Tang, Jing Liu, Jiang Zhang, and Pan Zhang.
Learning nonequilibrium statistical mechanics and dynamical phase
  transitions.
Nature Commun., 15: 1117, 2024.

Franz-etal-2016
Silvio Franz, Giacomo Gradenigo, and Stefano Spigler.
Random-diluted trianglar plaquette model: Study of phase transitions
  in a kinetically constrained model.
Phys. Rev. E, 93: 032601, 2016.

Foini-etal-2012
Laura Foini, Florent Krzakala, and Francesco Zamponi.
On the relation between kinetically constrained models of glass
  dynamics and the random first-order transition theory.
J. Stat. Mech. Theor. Exper., 2012: P06013, 2012.

Adler-1991
Joan Adler.
Bootstrap percolation.
Physica A, 171: 453–470, 1991.

Rizzo-2018
T. Rizzo.
Fate of the hybrid transition of bootstrap percolation in physical
  dimension.
Phys. Rev. Lett., 122: 108301, 2019.

Perrupato-Rizzo-2022
Gianmarco Perrupato and Tommaso Rizzo.
Exact dynamical equations for kinetically-constrained-models.
eprint arXiv:2212.05132 [cond-mat.dis-nn], 2022.

Perrupato-Rizzo-2023
Gianmarco Perrupato and Tommaso Rizzo.
Thermodynamics of the fredrickson-andersen model on the Bethe
  lattice.
eprint arXiv:2312.01430 [cond-mat.dis-nn], 2023.

Pittel-etal-1996
B. Pittel, J. Spencer, and N. Wormald.
Sudden emergence of a giant k-core in a random graph.
J. Combin. Theory B, 67: 111–151, 1996.

Dorogovtsev-etal-2006
S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes.
K-core organization of complex networks.
Phys. Rev. Lett., 96: 040601, 2006.

Zhao-Zhou-Liu-2013
J.-H. Zhao, H.-J. Zhou, and Y.-Y. Liu.
Inducing effect on the percolation transition in complex networks.
Nature Commun., 4: 2412, 2013.

Cellai-etal-2011
Davide Cellai, Aonghus Lawlor, Kenneth A. Dawson, and James P. Gleeson.
Tricritical point in heterogeneous k-core percolation.
Phys. Rev. Lett., 107: 175703, 2011.

Baxter-etal-2011
G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes.
Heterogeneous k-core versus bootstrap percolation on complex
  networks.
Phys. Rev. E, 83: 051134, 2011.

Sellitto-etal-2005
M. Sellitto, G. Biroli, and C. Toninelli.
Facilitated spin models on Bethe lattice: Bootstrap percolation,
  mode-coupling transition and glassy dynamics.
Europhys. Lett., 69: 496–502, 2005.

Schwarz-Liu-Chayes-2006
J. M. Schwarz, A. J. Liu, and L. Q. Chayes.
The onset of jamming as the sudden emergence of an infinite k-core
  cluster.
Europhys. Lett., 73: 560–566, 2006.

Morone-etal-2019
Flaviano Monone, Kate Burleson-Lesser, H. A. Vinutha, Srikanth Sastry, and
  H. A. Makse.
The jamming transition is a k-core percolation transition.
Physica A, 516: 172–177, 2019.

Biroli-Mezard-2002
G. Biroli and M. Mézard.
Lattice glass models.
Phys. Rev. Lett., 88: 025501, 2002.

Rivoire-etal-2004
O. Rivoire, G. Biroli, O. C. Martin, and M. Mézard.
Glass models on Bethe lattice.
Eur. Phys. J. B, 37: 55–78, 2004.

Zhou-2022
Hai-Jun Zhou.
Cycle-tree guided attack of random k-core: Spin glass model and
  efficient message-passing algorithm.
Sci. China-Phys. Mech. Astron., 65: 230511, 2022.

Guggiola-Semerjian-2015
A. Guggiola and G. Semerjian.
Minimal contagious sets in random regular graphs.
J. Stat. Phys., 158: 300–358, 2015.

Zhao-etal-2015
J. Zhao, J. Wu, M. Chen, Z. Fang, and K. Xu.
K-core-based attack to the internet: Is it more malicious then
  degree-based attack?
World Wide Web, 18: 749–766, 2015.

Yuan-etal-2016
X. Yuan, Y. Dai, H. E. Stanley, and S. Havlin.
K-core percolation on complex networks: Comparing random,
  localized, and targeted attacks.
Phys. Rev. E, 93: 062302, 2016.

Schmidt-etal-2018
C. Schmidt, H. D. Pfister, and L. Zdeborová.
Minimal sets to destroy the k-core in random networks.
Phys. Rev. E, 99: 022310, 2019.

Zhou-Zhou-2023
Jianwen Zhou and Hai-Jun Zhou.
Hierarchical cycle-tree packing model for optimal k-core attack.
J. Stat. Phys., 190: 200, 2023.

Fomin-etal-2008
F. V. Fomin, S. Gaspers, A. V. Pyatkin, and I. Razgon.
On the minimum feedback vertex set problem: Exact and enumeration
  algorithms.
Algorithmica, 52: 293–307, 2008.

Zhou-2013
H.-J. Zhou.
Spin glass approach to the feedback vertex set problem.
Eur. Phys. J. B, 86: 455, 2013.

Morone-Makse-2015
F. Morone and H. A. Makse.
Influence maximization in complex networks through optimal
  percolation.
Nature, 524: 65–68, 2015.

Mugisha-Zhou-2016
S. Mugisha and H.-J. Zhou.
Identifying optimal targets of network attack by belief propagation.
Phys. Rev. E, 94: 012305, 2016.

Braunstein-etal-2016
A. Braunstein, L. Dall'Asta, G. Semerjian, and L. Zdeborová.
Network dismantling.
Proc. Natl. Acad. Sci. USA, 113: 12368–12373, 2016.

Zdeborova-etal-2016
L. Zdeborová, P. Zhang, and H.-J. Zhou.
Fast and simple decycling and dismantling of networks.
Sci. Rep., 6: 37954, 2016.

Chujyo-Hayashi-2021
M. Chujyo and Y. Hayashi.
A loop enhancement strategy for network robustness.
Appl. Network Sci., 6: 3, 2021.

Lv-etal-2016
L. Lü, D. Chen, X.-L. Ren, Q.-M. Zhang, Y.-C. Zhang, and T. Zhou.
Vital nodes identification in complex networks.
Phys. Rep., 650: 1–63, 2016.

Pei-etal-2019
Sen Pei, Jiannan Wang, Flaviano Morone, and Hernán A. Makse.
Influencer identification in dynamical complex systems.
J. Compl. Netw., 8: cnz029, 2020.

Weigt-Hartmann-2001
M. Weigt and A. K. Hartmann.
Minimal vertex covers on finite-connectivity random graphs: A
  hard-sphere lattice-gas picture.
Phys. Rev. E, 63: 056127, 2001.

Zhou-2003a
H.-J. Zhou.
Vertex cover problem studied by cavity method: Analytics and
  population dynamics.
Eur. Phys. J. B, 32: 265–270, 2003.

Zhao-Zhou-2014
J.-H. Zhao and H.-J. Zhou.
Statistical physics of hard combinatorial optimization: Vertex cover
  problem.
Chin. Phys. B, 23: 078901, 2014.

Haynes-Hedetniemi-Slater-1998
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater.
Fundamentals of Domination in Graphs.
Marcel Dekker, New York, 1998.

Echenique-etal-2005
P. Echenique, J. Gómez-Gardeñes, Y. Moreno, and A. Vázquez.
Distance-d covering problems in scale-free networks with degree
  correlations.
Phys. Rev. E, 71: 035102(R), 2005.

Zhao-Habibulla-Zhou-2015
J.-H. Zhao, Y. Habibulla, and H.-J. Zhou.
Statistical mechanics of the minimum dominating set problem.
J. Stat. Phys., 159: 1154–1174, 2015.

Mezard-etal-2002
M. Mézard, G. Parisi, and R. Zecchina.
Analytic and algorithmic solution of random satisfiability problems.
Science, 297: 812–815, 2002.

Mezard-Parisi-2001
M. Mézard and G. Parisi.
The Bethe lattice spin glass revisited.
Eur. Phys. J. B, 20: 217–233, 2001.

Mezard-Parisi-2003
M. Mézard and G. Parisi.
The cavity method at zero temperature.
J. Stat. Phys., 111: 1–34, 2003.

Krzakala-etal-PNAS-2007
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and
  L. Zdeborová.
Gibbs states and the set of solutions of random constraint
  satisfaction problems.
Proc. Natl. Acad. Sci. USA, 104: 10318–10323, 2007.

Mezard-Montanari-2009
M. Mézard and A. Montanari.
Information, Physics, and Computation.
Oxford Univ. Press, New York, 2009.

Zhou-2015
H.-J. Zhou.
Spin Glass and Message Passing.
Science Press, Beijing, China, 2015.

Altarelli-Braunstein-DallAsta-Zecchina-2013
F. Altarelli, A. Braunstein, L. Dall'Asta, and R. Zecchina.
Optimizing spread dynamics on graphs by message passing.
J. Stat. Mech.: Theor. Exp., 2013: P09011, 2013.

Altarelli-Braunstein-DallAsta-Zecchina-2013b
F. Altarelli, A. Braunstein, L. Dall'Asta, and R. Zecchina.
Large deviations of cascade processes on graphs.
Phys. Rev. E, 87: 062115, 2013.

Li-etal-2021
T. Li, P. Zhang, and H.-J. Zhou.
Long-loop feedback vertex set and dismantling on bipartite factor
  graphs.
Phys. Rev. E, 103: L061302, 2021.

Qin-Zhou-2014
S.-M. Qin and H.-J. Zhou.
Solving the undirected feedback vertex set problem by local search.
Eur. Phys. J. B, 87: 273, 2014.

Bau-Wormald-Zhou-2002
S. Bau, N. C. Wormald, and S. Zhou.
Decycling numbers of random regular graphs.
Random Struct. Alg., 21: 397–413, 2002.

Mezard-Montanari-2006
M. Mézard and A. Montanari.
Reconstruction on trees and spin glass transition.
J. Stat. Phys., 124: 1317–1350, 2006.

Qin-etal-2016
Shao-Meng Qin, Ying Zeng, and Hai-Jun Zhou.
Spin-glass phase transitions and minimum energy of the random
  feedback vertex set problem.
Phys. Rev. E, 94: 022146, 2016.

Zhang-Zeng-Zhou-2009
P. Zhang, Y. Zeng, and H. J. Zhou.
Stability analysis on the finite-temperature replica-symmetric and
  first-step replica-symmetry-broken cavity solutions of the random vertex
  cover problem.
Phys. Rev. E, 80: 021122, 2009.

Urbani-etal-2023
Pierfrancesco Urbani, Yuliang Jin, and Hajime Yoshino.
The Gardner glass.
In Patrick Charbonneau, Enzo Marinari, Marc Mézard, Giorgio Parisi,
  Federico Ricci-Tersenghi, Gabriele Sicuro, and Francesco Zamponi, editors,
  Spin Glass Theory and Far Beyond: Replica Symmetry Breaking After 40
  Years, chapter 12, pages 219–238. World Scientific, Singapore, 2023.

Liao-etal-2023
Qinyi Liao, Ludovic Berthier, Hai-Jun Zhou, and Ning Xu.
Dynamic Gardner cross-over in a simple glass.
Proc. Natl. Acad. Sci. USA, 120: e2218218120, 2023.

Berthier-etal-2016
Ludovic Berthier, Patrick Charbonneau, Yuliang Jin, Giorgio Parisi, Beatriz
  Seoane, and Francesco Zamponi.
Growing timescales and lengthscales characterizing vibrations of
  amorphous solids.
Proc. Natl. Acad. Sci. USA, 113: 8397–8401, 2016.

Bianconi-Dorogovtsev-2024b
Ginestra Bianconi and Sergey N. Dorogovtsev.
Nature of hypergraph k-core percolation problems.
Phys. Rev. E, 109: 014307, 2024.

Wang-etal-2020
S.-N. Wang, L. Cheng, and H.-J. Zhou.
Vulnerability and resilience of social engagement: Equilibrium
  theory.
Europhys. Lett., 132: 60006, 2020.

Sur-etal-1976
Amit Sur, Joel L. Lebowitz, J. Marro, M. H. Kalos, and S. Kirkpatrick.
Monte Carlo studies of percolation phenomena for a simple cubic
  lattice.
J. Stat. Phys., 15: 345–353, 1976.

vanEnter-1987
Aernout C. D. van Enter.
Proof of Straley's argument for bootstrap percolation.
J. Stat. Phys., 48: 943–945, 1987.

Schonmann-1990
Roberto H. Schonmann.
Critical points of two-dimensional bootstrap percolation-like
  cellular automata.
J. Stat. Phys., 58: 1239–1244, 1990.

Schonmann-1992
Roberto H. Schonmann.
On the behavior of some cellular automata related to bootstrap
  percolation.
Ann. Prob., 20: 174–193, 1992.

Lin-Hu-1998
Chai-Yu Lin and Chin-Kun Hu.
Universal finite-size scaling functions for percolation on
  three-dimensional lattices.
Phys. Rev. E, 58: 1521–1527, 1998.

Branco-Silva-1999
N. S. Branco and Cristiano J. Silva.
Universality class for bootstrap percolation with m=3 on the cubic
  lattice.
Int. J. Mod. Phys. C, 10: 921–930, 1999.

Kurtsiefer-2003
Dirk Kurtsiefer.
Threshold value of three-dimensional bootstrap percolation.
Int. J. Mod. Phys. C, 14: 529–536, 2003.

Gregorio-etal-2004
Paolo De Gregorio, Aonghus Lawlor, Phil Bradley, and Kenneth A. Dawson.
Clarification of the bootstrap percolation paradox.
Phys. Rev. Lett., 93: 025501, 2004.

Zhu-etal-2015
Yong Zhu, Zi-Qing Yang, Xin Zhang, and Xiao-Song Chen.
Critical behaviors and universality classes of percolation phase
  transitions on two-dimensional square lattice.
Commun. Theor. Phys., 64: 231–236, 2015.

Xu-etal-2018
Y.-Z. Xu, C. H. Yeung, H.-J. Zhou, and D. Saad.
Entropy inflection and invisible low-energy states: Defensive
  alliance example.
Phys. Rev. Lett., 121: 210602, 2018.

Jin-Yoshino-2021
Yuliang Jin and Hajime Yoshino.
A jamming plane of sphere packings.
Proc. Natl. Acad. Sci. USA, 118: e2021794118, 2021.

Wilken-etal-2021
Sam Wilken, Rodrigo E. Guerra, Dov Levine, and Paul M. Chaikin.
Random close packing as a dynamical phase transition.
Phys. Rev. Lett., 127: 038002, 2021.

Ozawa-etal-2017
Misaki Ozawa, Ludovic Berthier, and Daniele Coslovich.
Exploring the jamming transition over a wide range of critical
  densities.
SciPost Phys., 3: 027, 2017.

Woodcock-2013
Leslie V. Woodcock.
Thermodynamic status of random close packing.
Philosphical Magazine, 93: 4159–4173, 2013.

Li-etal-2010b
ShuiXiang Li, Jian Zhao, Peng Lu, and Yu Xie.
Maximum packing densities of basic 3d objects.
Chinese Science Bulletin, 55: 114–119, 2010.

Jin-Makse-2010
Yuliang Jin and H. A. Makse.
A first-order phase transition defines the random close packing of
  hard spheres.
Physica A, 389: 5362–5379, 2010.

Pan-etal-2023
Deng Pan, Yinqiao Wang, Hajime Yoshino, Jie Zhang, and Yuliang Jin.
A review on shear jamming.
Phys. Rep., 1038: 1–18, 2023.

Folena-etal-2020
Giampaolo Folena, Silvio Franz, and Federico Ricci-Tersenghi.
Rethinking mean-field glassy dynamics and its relation with the
  energy landscape: The surprising case of the spherical mixed p-spin model.
Phys. Rev. X, 10: 031045, 2020.

Liu-Tong-etal-2020
Jun Liu, Hua Tong, Yunhuan Nie, and Ning Xu.
Jamming in confined geometry: Criticality of the jamming transition
  and implications of structural relaxation in confined supercooled liquids.
Chin. Phys. B, 29: 126302, 2020.

Chen-etal-2023
Yanshuang Chen, Zefang Ye, Kexin Wang, Jiping Huang, Hua Tong, Yuliang Jin,
  Ke Chen, Hajime Tanaka, and Peng Tan.
Visualizing slow internal relaxations in a two-dimensional glassy
  system.
Nature Phys., 19: 969–977, 2023.



