## Bipartite graphs

Let $G_n$ be the bipartite graph with vertices $\{x_1,\ldots,x_n,y_1,\ldots,y_n \}$ and edges $\{x_iy_j:i and suppose $\epsilon > 0$. Find a constant $M \geq 2$ and (for sufficiently large n) an explicit $\epsilon$-regular partition of $G_n$ into $M$ pieces. Also, how can you show that there is not a constant $M$ such that every $G_n$ has a partition into $M$ (almost) equal vertex classes in which every pair is $\epsilon$-regular?