(Dis)assortative Partitions on Random Regular Graphs

DOI10.1088/1751-8121/AC8B46MaRDI QIDQ6391759arXivFDO

Authors Freya Behrens, Gabriel Arpino, Yaroslav Kivva, Lenka Zdeborová

Publication date 21 February 2022

Published in arXiv

Full work available at URL https://doi.org/10.1088/1751-8121/AC8B46

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

arXiv classification

cond-mat.dis-nncond-mat.stat-mechcs.DMmath.PR

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>lceilfracd2ceil$ 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 $Hlelceilfracd2ceil$ 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.

This page was built for publication: (Dis)assortative Partitions on Random Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6391759)