Phase Transitions in the Coloring of Random Graphs

Abstract

We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Renyi and regular random graphs and determine their asymptotic values for large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.

36 pages, 15 figures

References in corpus (7)

• Jamming at Zero Temperature and Zero Applied Stress: the Epitome of Disorder
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Clustering of solutions in the random satisfiability problem
• A Landscape Analysis of Constraint Satisfaction Problems
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Marginal States in Mean Field Glasses

Cited by in corpus (134)

• Critical phenomena in complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Mean field theory of hard sphere glasses and jamming
• Statistical physics of inference: Thresholds and algorithms
• Jamming versus Glass Transitions
• A Landscape Analysis of Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The jamming transition as a paradigm to understand the loss landscape of deep neural networks
• Information-theoretic thresholds from the cavity method
• Entropies of complex networks with hierarchically constrained topologies
• On Convergence of Approximate Message Passing
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Locked constraint satisfaction problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Phase transitions in semisupervised clustering of sparse networks
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Constraint satisfaction problems with isolated solutions are hard
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Reconstruction of Random Colourings
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Networking - A Statistical Physics Perspective
• Quantum algorithm for energy matching in hard optimization problems
• Potts Glass on Random Graphs
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Graph Coloring with Physics-Inspired Graph Neural Networks
• Random subcubes as a toy model for constraint satisfaction problems
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• A Lattice Model for Colloidal Gels and Glasses
• The condensation phase transition in random graph coloring
• Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
• Cusps and shocks in the renormalized potential of glassy random manifolds: How Functional Renormalization Group and Replica Symmetry Breaking fit together
• Constrained quantum annealing of graph coloring
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Approximating the XY model on a random graph with a $q$-state clock model
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Belief Propagation Reconstruction for Discrete Tomography
• Biased landscapes for random Constraint Satisfaction Problems
• Phase transitions in the $q$-coloring of random hypergraphs
• The large deviations of the whitening process in random constraint satisfaction problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• AKLT Models with Quantum Spin Glass Ground States
• Disorder-free spin glass transitions and jamming in exactly solvable mean-field models
• Spin models on random graphs with controlled topologies beyond degree constraints
• A simple model for multiple-choice collective decision making
• On the solution of a `solvable' model of an ideal glass of hard spheres displaying a jamming transition
• Energy landscapes of combinatorial optimization in Ising machines
• Fundamental problems in statistical physics XIV: Lecture on Machine Learning
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Stochastic optimization by message passing
• Role of fluctuations in the phase transitions of coupled plaquette spin models of glasses
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• Numerical Solution-Space Analysis of Satisfiability Problems
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Reconstruction of symmetric Potts Models
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Bond and site color-avoiding percolation in scale free networks
• Solution space structure of random constraint satisfaction problems with growing domains
• Higher order corrections to the effective potential close to the jamming transition in the perceptron model
• Antiferromagnetic Potts model on the Erdos-Renyi random graph
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Planting colourings silently
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Efficient data compression from statistical physics of codes over finite fields
• Backtracking Dynamical Cavity Method
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Ferromagnetism-induced Phase Separation in a Two-dimensional Spin Fluid
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Ferromagnetic and spin-glass like transition in the $q$-neighbor Ising model on random graphs
• Cavity approach to the Sourlas code system
• Dense Hopfield Networks in the Teacher-Student Setting
• Approximating random quantum optimization problems
• Qudit-inspired optimization for graph coloring
• Mean-field phase diagram and spin glass phase of the dipolar Kagome Ising antiferromagnet
• Localization in the constrained quantum annealing of graph coloring
• General theory for extended-range percolation on simple and multiplex networks
• Combined local search strategy for learning in networks of binary synapses
• Optimal Location of Sources in Transportation Networks
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• Coordinating Dynamical Routes with Statistical Physics on Space-time Networks
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Circular Coloring of Random Graphs: Statistical Physics Investigation
• An algorithmic framework for colouring locally sparse graphs
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Adversarial Satisfiability Problem
• Palette-colouring: a belief-propagation approach
• MCMC sampling colourings and independent sets of G(n,d/n) near the uniqueness threshold
• Optimization of the dynamic transition in the continuous coloring problem
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Statistical mechanics of the maximum-average submatrix problem
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Susceptibility Propagation for Constraint Satisfaction Problems
• A residual-based message passing algorithm for constraint satisfaction problems
• Self-sustained Clusters and Ergodicity Breaking in Spin Models
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• The network source location problem: ground state energy, entropy and effects of freezing
• Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
• The effect of quantum fluctuations on the coloring of random graphs
• Critical properties of disordered XY model on sparse random graphs
• The number of solutions for random regular NAE-SAT
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Packing hard spheres with short-range attraction in infinite dimension: Phase structure and algorithmic implications
• Entropic long range order in a 3D spin glass model
• Extremal bipartite independence number and balanced coloring
• Aspects of Statistical Physics in Computational Complexity
• Sparse model from optimal nonuniform embedding of time series
• Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers
• Uniformly Random Colourings of Sparse Graphs
• Improving Parameter Training for VQEs by Sequential Hamiltonian Assembly
• Finite-size scaling in random $K$-satisfiability problems
• Perturbed Message Passing for Constraint Satisfaction Problems
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model
• Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
• Computing a Knot Invariant as a Constraint Satisfaction Problem
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates
• The replica symmetric solution for Orthogonally Constrained Heisenberg Model on Bethe lattice
• A computational method for bounding the probability of reconstruction on trees
• A simple algorithm for sampling colourings of $G(n,d/n)$ up to Gibbs Uniqueness Threshold