  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.

Disordered Systems and Neural Networks;Statistical Mechanics;Discrete Mathematics;Probability