Extremal cuts of sparse random graphs
From MaRDI portal
Publication:2412669
DOI10.1214/15-AOP1084zbMath1372.05196arXiv1503.03923MaRDI QIDQ2412669
Subhabrata Sen, Amir Dembo, 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
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) Density (toughness, etc.) (05C42)
Related Items
On the maximal cut in a random hypergraph, Universality of the mean-field for the Potts model, Disorder chaos in some diluted spin Glass models, MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass, 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, Suboptimality of local algorithms for a class of max-cut problems, On the minimum bisection of random 3-regular graphs, Optimization algorithms for multi-species spherical spin glasses, Local minima in disordered mean-field ferromagnets, A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists, Factors of IID on Trees, Zero-temperature dynamics in the dilute Curie-Weiss model, Network models: structure and function. Abstracts from the workshop held December 10--16, 2017, Optimal couplings between sparse block models, Optimization of the Sherrington--Kirkpatrick Hamiltonian, A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian, Free energy in the Potts spin Glass, On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model, Local approximation of the maximum cut in regular graphs, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, (Dis)assortative partitions on random regular graphs
