{"id":"arxiv/2605.10911","url":"https://arxiv.org/abs/2605.10911","tags":["math.PR","cs.CC","cs.DS","math.CO","math.ST"],"score":0,"title":"The stochastic block model has the overlap graph property for modularity","domain":"math.PR","source":"arxiv","authors":["Shankar Bhamidi","David Gamarnik","Remco van der Hofstad","Nelly Litvak","Pawel Pralat","Fiona Skerman","Yasmin Tousinejad"],"reviews":0,"subject":"math.PR","summary":"The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with $k$ equal-size blocks which form the `communities', and where, for parameters $p>q$, vertices within the same community connect with probability $p$, while vertices in different communities connect with probability $q$, independently…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-11","reactions":{}}