Phase transitions in discrete structures
type: Item
instance of: scholarly article
title: Phase transitions in discrete structures
zbMATH Open document ID: 1403.82009
DOI: 10.4171/176-1/28
author: Amin Coja-Oghlan
publication date: 2018-11-14T00:00:00Z
review text: Summary: Many important parameters of random discrete structures such as random graphs, formulas and codes undergo phase transitions. While some phase transitions such as the emergence of a giant component in the Erdős-Rényi random graph are very well understood, other, less understood ones resemble phase transitions in statistical physics models of disordered systems. This paper gives an impression of what we know about this latter class with the particular example of the random graph colouring problem. For the entire collection see [Zbl 1396.00017].
Mathematics Subject Classification ID: 82B26
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 82B44
zbMATH DE Number: 6979405
zbMATH Keywords: random graph
zbMATH Keywords: phase transition
zbMATH Keywords: disordered system
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.4171/176-1/28
OpenAlex ID: W4230535748
cites work: Q4705349
cites work: Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
cites work: The two possible values of the chromatic number of a random graph
cites work: The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
cites work: The concentration of the chromatic number of random graphs
cites work: Q3503433
cites work: Harnessing the Bethe free energy
cites work: The condensation phase transition in the regular $k$-SAT model
cites work: Planting Colourings Silently
cites work: The condensation phase transition in random graph coloring
cites work: Q3999841
cites work: Q4449244
cites work: Random graphs.
cites work: The chromatic number of random graphs
cites work: Percolation
cites work: Q4228436
cites work: Upper-bounding the \(k\)-colorability threshold by counting covers
cites work: Local Convergence of Random Graph Colorings
cites work: Information-theoretic thresholds from the cavity method
cites work: The asymptotic \(k\)-SAT threshold
cites work: Limits of discrete distributions and Gibbs measures on random graphs
cites work: The Chromatic Number of Random Graphs for Most Average Degrees
cites work: Factor models on locally tree-like graphs
cites work: Satisfiability threshold for random regular NAE-SAT
cites work: Maximum independent sets on random regular graphs
cites work: Proof of the Satisfiability Conjecture for Large k
cites work: Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
cites work: Some remarks on the theory of graphs
cites work: Graph Theory and Probability
cites work: Replica bounds for optimization problems and diluted spin systems
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: Random Graphs
cites work: Asymptotic enumeration and limit laws of planar graphs
cites work: A threshold for unsatisfiability
cites work: Q4519896
cites work: Uniqueness of uniform random colorings of regular trees
cites work: Approximating the unsatisfiability threshold of random formulas
cites work: Gibbs states and the set of solutions of random constraint satisfaction problems
cites work: A note on the sharp concentration of the chromatic number of random graphs
cites work: Threshold values of random K‐SAT from the cavity method
cites work: Information, Physics, and Computation
cites work: The freezing threshold for k-colourings of a random graph
cites work: Reconstruction and Clustering in Random Constraint Satisfaction Problems
cites work: Q3090774
cites work: On the hardness of sampling independent sets beyond the tree threshold
cites work: A Combinatorial Classic — Sparse Graphs with High Chromatic Number
cites work: The Sherrington-Kirkpatrick Model
cites work: Bounds for diluted mean-fields spin glass models
cites work: Random Geometric Graphs
cites work: Modern Coding Theory
cites work: Almost all regular graphs are hamiltonian
cites work: Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
description: scientific article; zbMATH DE number 6979405