Extremal cuts of sparse random graphs

DOI10.1214/15-AOP1084MaRDI QIDQ2412669zbMATH OpenFDO

Authors Amir Dembo, Subhabrata Sen, Andrea Montanari

Publication date 24 October 2017

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.03923, https://projecteuclid.org/euclid.aop/1490947317

zbMATH Keywords

bisectionErdős-Rényi graphIsing modelmax-cutParisi formularegular graphspin glass

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Abstract: For ErdH{o}s-R'enyi random graphs with average degree $gamma$, and uniformly random $gamma$-regular graph on $n$ vertices, we prove that with high probability the size of both the Max-Cut and maximum bisection are $nBig(fracgamma4+{sfP}_{\ast }sqrtfracgamma4+o(sqrtgamma)Big)+o(n)$ while the size of the minimum bisection is $nBig(fracgamma4-{sfP}_{\ast }sqrtfracgamma4+o(sqrtgamma)Big)+o(n)$. Our derivation relates the free energy of the anti-ferromagnetic Ising model on such graphs to that of the Sherrington-Kirkpatrick model, with ${sfP}_{\ast }approx0.7632$ standing for the ground state energy of the latter, expressed analytically via Parisi's formula.

Recommendations

• The MAX-CUT of sparse random graphs
• On the max-cut of sparse random graphs
• Extremal results in sparse pseudorandom graphs
• On the maximal cut in a random hypergraph
• On limits of sparse random graphs
• Sparsest cuts and bottlenecks in graphs
• Extremal results in random graphs
• Cutoff for nonbacktracking random walks on sparse random graphs
• A probabilistic result for the max-cut problem on random graphs

Cited in

(43)

• Balanced cut approximation in random geometric graphs
• Disorder chaos in some diluted spin Glass models
• MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
• Zero-temperature dynamics in the dilute Curie-Weiss model
• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• Free energy in the Potts spin Glass
• Convergence of maximum bisection ratio of sparse random graphs
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• On the maximal cut in a random hypergraph
• Local minima in disordered mean-field ferromagnets
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• Universality of the mean-field for the Potts model
• Phase transitions of extremal cuts for the configuration model
• Suboptimality of local algorithms for a class of max-cut problems
• The peculiar phase structure of random graph bisection
• On the max-cut of sparse random graphs
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Optimal couplings between sparse block models
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• Factors of IID on trees
• The MAX-CUT of sparse random graphs
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• (Dis)assortative partitions on random regular graphs
• Local approximation of the maximum cut in regular graphs
• The cut metric, random graphs, and branching processes
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• On the minimum bisection of random 3-regular graphs
• Optimization algorithms for multi-species spherical spin glasses
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
• A review on quantum approximate optimization algorithm and its variants
• A unified pre-training and adaptation framework for combinatorial optimization on graphs
• New advances for quantum-inspired optimization
• Tight Lipschitz hardness for optimizing mean field spin glasses
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• Partitioning problems via random processes
• Maximum chordal subgraphs of random graphs
• Optimization of the Sherrington-Kirkpatrick Hamiltonian
• Bounds on the ground state energy of quantum p-spin Hamiltonians
• Kawasaki dynamics beyond the uniqueness threshold
• Equilibrium and nonequilibrium Gibbs states on sofic groups
• Combinatorics. Abstracts from the workshop held January 4--9, 2026

This page was built for publication: Extremal cuts of sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2412669)