to obtain a so-called robust partition of our graph. This is a vertex partition in which each part induces a robust expander or a bipartite robust expander and where there are few edges between parts. We give the precise definitions below, but informally we can think of (bipartite) robust expanders as dense (bipartite) graphs with good connectivity properties that are resilient to small alterations. In [@kuhn2014robust], it was shown that such a robust partition exists for dense regular graphs, and crucially, the number of parts is independent of the number of vertices and depends only on the density. The idea of the proof in [@kuhn2014robust] is to iteratively refine the vertex partition as follows. Given a vertex partition $\mathcal{P} = \{U_1, \ldots, U_k\}$, if some $U_i$ is not a (bipartite) robust expander, then they show there exists a partition $U_i = A \cup B$ of $U_i$ where there are few edges between $A$ and $B$; $U_i$ is then replaced with $A,B$ in $\mathcal{P}$ and this is repeated with the new partition. This process must end after a finite number of steps since the density inside parts increases at each step (since there were not many edges between $A$ and $B$). 