We say A is good is every nonempty row has m/r elements and every nomempty column has m/c elements of A. A rectangle has this property, as does a diagonal. We say A is k-good if every nonempty row has at most km/r elements and every nonempty column has at most km/c elements. A is good if it is 1-good.
Vereshchagin's Theorem: There is a constant c such that for all finite subsets B of N×N with n = log |B| there is a partition of B into at most nc sets each of which is nc-good.
Vereshchagin asks whether there is a purely combinatorial proof of this theorem. If you know of one let me know.
For those who know some Kolmogorov complexity, let me sketch the proof: We label each point (x,y) of B with the following five values: KB(x,y), KB(x), KB(y), KB(x|y) and KB(y|x). We partition the points into sets with the same labels. Standard counting arguments from Kolmogorov complexity show that each partition is nc-good for some c.