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