A Tight Bound for Testing Partition Properties

A partition property of order k asks if a graph can be partitioned into k vertex sets of prescribed sizes so that the densities between any pair of sets falls within a prescribed range. This family of properties has been extensively studied in various areas of research ranging from theoretical computer science to statistical physics. Our main result is that every partition property of order k is testable with query complexity poly(k/ε). We thus obtain an exponential improvement (in k) over the (1/ε) O(k) bound obtained by Goldreich, Goldwasser and Ron in their seminal FOCS 1996 paper. We further prove that our bound is tight in the sense that it cannot be made sub-polynomial in either k or ε.

Besides the intrinsic interest in obtaining a tight bound for the above well studied family of properties, our improved bound has several algorithmic implications, stemming from the fact that it remains polynomial even when testing partition properties of order k = poly(1/ε).