Monotonicity testing and shortest-path routing on the cube

We study the problem of monotonicity testing over the hypercube. As previously observed in several works, a positive answer to a natural question about routing properties of the hypercube network would imply the existence of efficient monotonicity testers. In particular, if any set of source-sink pairs on the directed hypercube (with all sources and all sinks distinct) can be connected with edge-disjoint paths, then monotonicity of functions $f:{ 0,1} ^n to mathcal{R}$ can be tested with O(n/∈) queries, for any totally ordered range $mathcal{R}$ . More generally, if at least a µ(n) fraction of the pairs can always be connected with edge-disjoint paths then the query complexity is O(n/(∈µ(n))). We construct a family of instances of Ω(2 ⁿ ) pairs in n-dimensional hypercubes such that no more than roughly a $frac{1} {{sqrt n }}$ fraction of the pairs can be simultaneously connected with edge-disjoint paths. This answers an open question of Lehman and Ron [16], and suggests that the aforementioned appealing combinatorial approach for deriving query-complexity upper bounds from routing properties cannot yield, by itself, query-complexity bounds better than ≈ n ^3/2. Additionally, our construction can also be used to obtain a strong counterexample to Szymanski’s conjecture about routing on the hypercube. In particular, we show that for any δ > 0, the n-dimensional hypercube is not $n^{tfrac{1} {2} - delta }$ -realizable with shortest paths, while previously it was only known that hypercubes are not 1-realizable with shortest paths. We also prove a lower bound of Ω(n/∈) queries for one-sided non-adaptive testing of monotonicity over the n-dimensional hypercube, as well as additional bounds for specific classes of functions and testers.