(Dis)assortative Partitions on Random Regular Graphs

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>\lceil \frac{d}{2}\rceil$ we establish that the structure of solutions to the assortative partition problems corresponds to the so-called frozen-1RSB. This entails a conjecture of algorithmic hardness of finding these partitions efficiently. For $H\le \lceil \frac{d}{2}\rceil$ 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 trough 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.

arXiv comment21 pages; Corrected usage of the world "planted" in Section 4

References in corpus (14)

• Assortative mixing in networks
• Marginal Stability in Structural, Spin and Electron Glasses
• Extremal Cuts of Sparse Random Graphs
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Suboptimality of local algorithms for a class of max-cut problems
• Storage capacity in symmetric binary perceptrons
• Random multi-index matching problems
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Conjecture on the maximum cut and bisection width in random regular graphs
• Statistical Physics of Hard Optimization Problems
• A frozen glass phase in the multi-index matching problem
• The marginally stable Bethe lattice spin glass revisited