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.