ON PARTITIONING GRIDS INTO EQUAL PARTS

Let an edge cut partition the vertex set of an n-dimensional quadratic grid with the side length a into k subsets A(1),..., A(k) with \\A(i) \ - \A(j)\\ less than or equal to 1. We consider the problem of determ ining the minimal size c(n, k, a) of such a cut and present its asympt otic c(n, k, a) similar to na(n-1) (n) root k as a, k --> infinity and k/a(n) --> 0. The same asymptotic holds for partitioning of the n-dim ensional torus. We present also some heuristics, which provide better partitioning for n = 2 and small k.