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 n^{c} sets each of which is n^{c}-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:
K^{B}(x,y), K^{B}(x), K^{B}(y),
K^{B}(x|y) and K^{B}(y|x). We partition the points
into sets with the same labels. Standard counting arguments from
Kolmogorov complexity show that each partition is n^{c}-good for
some c.