On the max‐cut of sparse random graphs

DOI10.1002/rsa.20738zbMath1388.05167arXiv1411.1698OpenAlexW2612126672MaRDI QIDQ4564857

David Gamarnik, Quan Li

Publication date: 7 June 2018

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphslarge deviationsmoment methodslocal optimalitymaximum cuts

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Related Items

On the maximal cut in a random hypergraph ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Friendly bisections of random graphs ⋮ 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 ⋮ 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

This page was built for publication: On the max‐cut of sparse random graphs