Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

DOI10.1145/1806689.1806706zbMath1293.05350arXiv0912.2444OpenAlexW2130042807WikidataQ106094403 ScholiaQ106094403MaRDI QIDQ5891427

David Gamarnik, Mohsen Bayati, Prasad Tetali

Publication date: 13 August 2014

Published in: The Annals of Probability, Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.2444

zbMATH Keywords

partition functionscaling limitrandom graphsconstraint satisfaction problems

Mathematics Subject Classification ID

Related Items (55)

On the maximal cut in a random hypergraph ⋮ Universality of the mean-field for the Potts model ⋮ Percolation with small clusters on random graphs ⋮ A positive temperature phase transition in random hypergraph 2-coloring ⋮ The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models ⋮ Factor of IID Percolation on Trees ⋮ Stack domination density ⋮ Information-theoretic thresholds from the cavity method ⋮ On the concentration of the number of solutions of random satisfiability formulas ⋮ Limits of discrete distributions and Gibbs measures on random graphs ⋮ Maximum independent sets on random regular graphs ⋮ Matchings on infinite graphs ⋮ Antiferromagnetic Potts model on the Erdős-Rényi random graph ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Free energy subadditivity for symmetric random Hamiltonians ⋮ Large deviations of the greedy independent set algorithm on sparse random graphs ⋮ MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems ⋮ Lower bounds on the chromatic number of random graphs ⋮ Harnessing the Bethe free energy ⋮ Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree ⋮ Suboptimality of local algorithms for a class of max-cut problems ⋮ General independence sets in random strongly sparse hypergraphs ⋮ Independence numbers of random sparse hypergraphs ⋮ Concentration of multi-overlaps for random dilute ferromagnetic spin models ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Improved replica bounds for the independence ratio of random regular graphs ⋮ On the concentration of the independence numbers of random hypergraphs ⋮ Sharp thresholds in adaptive random graph processes ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ The Interpolation Method for Random Graphs with Prescribed Degrees ⋮ Threshold saturation in spatially coupled constraint satisfaction problems ⋮ Factor models on locally tree-like graphs ⋮ Perfect matchings as IID factors on non-amenable groups ⋮ Nearly subadditive sequences ⋮ The replica symmetric solution for Potts models on \(d\)-regular graphs ⋮ Right-convergence of sparse random graphs ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Charting the replica symmetric phase ⋮ A scaling limit for the length of the longest cycle in a sparse random graph ⋮ Replica bounds by combinatorial interpolation for diluted spin systems ⋮ Spin systems on Bethe lattices ⋮ On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model ⋮ Convergence of maximum bisection ratio of sparse random graphs ⋮ Phase Transitions in Discrete Structures ⋮ Independent Sets in Random Graphs from the Weighted Second Moment Method ⋮ The condensation transition in random hypergraph 2-coloring ⋮ The number of solutions for random regular NAE-SAT ⋮ Limit theory of combinatorial optimization for random geometric graphs ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Typicality and entropy of processes on infinite trees ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ The rank of sparse random matrices ⋮ Minimal contagious sets in random regular graphs ⋮ Sofic homological invariants and the Weak Pinsker Property ⋮ Optimal low-degree hardness of maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ising models on locally tree-like graphs
• Gibbs measures and phase transitions on sparse random graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Bounds for diluted mean-fields spin glass models
• An introduction to covering problems for random walks on graphs
• The thermodynamic limit in mean field spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Linear phase transition in random linear constraint satisfaction problems
• Factor models on locally tree-like graphs
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Percolation
• Dismantling Sparse Random Graphs
• Tight Bounds for LDPC and LDGM Codes Under MAP Decoding
• Sharp thresholds of graph properties, and the $k$-sat problem
• Random MAX SAT, random MAX CUT, and their phase transitions
• Sparse graphs: Metrics and random models
• Replica bounds for diluted non-Poissonian spin systems

This page was built for publication: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs