{
  "id": "2202.10379",
  "version": "v2",
  "published": "2022-02-21T17:16:56.000Z",
  "updated": "2022-03-17T15:13:36.000Z",
  "title": "(Dis)assortative Partitions on Random Regular Graphs",
  "authors": [
    "Freya Behrens",
    "Gabriel Arpino",
    "Yaroslav Kivva",
    "Lenka Zdeborová"
  ],
  "comment": "21 pages",
  "categories": [
    "cond-mat.dis-nn",
    "cond-mat.stat-mech",
    "cs.DM",
    "math.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>\\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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-03-17T15:13:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random regular graphs",
      "assortative partition problem",
      "spin glasses",
      "glassy systems display convergence",
      "single spin flip stable states"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}