Given a directed graph G = (V,E) and an integer k \geq 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, E_H) that has (1) the same transitive-closure as G and (2) diameter at most k. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction for applications in access control, property testing and data structures.

In this work we study the number of edges in the sparsest 2-TC-spanners for the directed hypercube \{0,1\}^d and hypergrid \{1,2,\dots,m\}^d with the usual partial order, \preceq, defined by: x_1\dots x_d \preceq y_1\dots y_d if and only if x_i \leq y_i for all i\in\{1,...,d\}. We show that the number of edges in the sparsest 2-TC-spanner of the hypercube is 2^{cd+\Theta(\log d)}, where c\approx 1.1620. We also present upper and lower bounds on the size of the sparsest 2-TC-spanner of the directed hypergrid. Our first pair of upper and lower bounds for the hypergrid is in terms of an expression with binomial coefficients. The bounds differ by a factor of O(d^{2m}) and, in particular, give tight (up to a poly(d) factor) bounds for constant m. We also give a second set of bounds, which show that the number of edges in the sparsest 2-TC-spanner of the hypergrid is at most m^d \log^d m and at least \Omega (\max \{m^d (\log^d m)/((2d\log\log m)^{d-1}) , (m-1)^d 2^{(c+\alpha-1)d} \} ), where c \approx 1.1620, as above, and \alpha > 0 satisfies 1+H_b(\alpha) < c. The two sets of bounds are, in general, incomparable.

Our results rule out a class of approaches to monotonicity testing of functions of the form f:\{0,1\}^d\to R and, more generally, f:\{1,2,\dots, m\}^d\to R, where R is an arbitrary range. \cite{tc-spanners-soda} showed that sparse 2-TC-spanners imply fast monotonicity testers, and used this connection to improve existing monotonicity testers for planar and other H-minor-free graphs. It left open the question, which was again raised at the 2008 Dagstuhl seminar on Sublinear Algorithms, of whether the 2-TC-spanner approach can improve monotonicity testers on the hypercube and hypergrid. We show that a fundamentally new approach is required.