K-core attack, equilibrium K-core, and kinetically constrained spin system

Abstract

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.

14 pages, manuscript under review

References in corpus (14)

• Vital nodes identification in complex networks
• Glassy dynamics of kinetically constrained models
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Distance-d covering problems in scale-free networks with degree correlations
• Statistical Mechanics of the Minimum Dominating Set Problem
• Minimal contagious sets in random regular graphs
• A review on shear jamming
• A loop enhancement strategy for network robustness
• The nature of hypergraph $k$-core percolation problems
• Solving the undirected feedback vertex set problem by local search
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory
• Jamming in confined geometry: Criticality of the jamming transition and implications of structural relaxation in confined supercooled liquids