On Partitioning Grids into Equal Parts

Abstract

Let an edge cut partition the vertex set of an n-dimensional quadratic grid with the side length a into k subsets A1, … , Ak with ... . We consider the problem of determining the minimal size c (n,k,a) of such a cut and present its asymptotic c (n,k,a) ~ nan-1  as a, k ®   and k/an ® 0. The same asymptotic holds for partitioning of the n-dimensional torus. We present also some heuristics, which provide better partitioning for n = 2 and small k.