A Graph Decomposition motivated by the Geometry of Randomized Rounding

We introduce a graph decomposition which exists for all simple, connected graphs $G=(V,E)$. The decomposition $V=A\cup B\cup C$ is such that each vertex in $A$ has more neighbors in $B$ than in $A$ and vice versa. $C$ is balanced': each $v \in C$ has the same number of neighbours in $A$ and $B$. These decompositions arise naturally from the behavior of an associated dynamical system (Randomized Rounding’) on $({\mathbb{S}}^1{)}^{\mathrm{\mid }V\mathrm{\mid }}$. Connections to judicious partitions and the $\text{textsc}MaxCut$ problem (in particular the Burer-Monteiro-Zhang heuristic) are being discussed.