(Dis)assortative partitions on random regular graphs. (30th September 2022)

• Record Type: Journal Article
• Authors: Behrens, Freya; Arpino, Gabriel; Kivva, Yaroslav; Zdeborová, Lenka
• Is Part Of: Journal of physics. Volume 55:Number 39(2022)
• Publication Date: 2022-09-30
• Subjects: random graphs -- phase transitions -- partitions -- cavity method -- disordered systems -- message passing algorithms; Mathematical physics -- Periodicals; Statistical physics -- Periodicals; Quantum theory -- Periodicals; Matter -- Properties -- Periodicals; 530.105
• DOI: 10.1088/1751-8121/ac8b46
• Languages: English
• ISSNs: 1751-8113

Abstract

Abstract: We study the problem of assortative and disassortative partitions on random d -regular graphs. Nodes in the graph are partitioned into two non-empty groups. In the assortative partition every node requires at least H of their neighbors to be in their own group. In the disassortative partition they require less than H neighbors to be in their own group. Using the cavity method based on analysis of the belief propagation algorithm we establish for which combinations of parameters ( d, H ) these partitions exist with high probability and for which they do not. For H > ⌈ d 2 ⌉ we establish that the structure of solutions to the assortative partition problems corresponds to the so-called frozen-one-step replica symmetry breaking. This entails a conjecture of algorithmic hardness of finding these partitions efficiently. For H ⩽ ⌈ d 2 ⌉ we argue that the assortative partition problem is algorithmically easy on average for all d . Further we provide arguments about asymptotic equivalence between the assortative partition problem and the disassortative one, going through a close relation to the problem of single-spin-flip-stable states in spin glasses. In the context of spin glasses, our results on algorithmic hardness imply a conjecture that gapped single spin flip stable states are hard to find which may be a universal reason behind the observation that physical dynamics in glassy systems display convergence to marginal stability.