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 $\ell$ disjoint source-sink pairs
on the directed hypercube can be connected with edge-disjoint
paths, then monotonicity of functions $f:\zo^n \to \RR$ can be tested
with $O(n)$ queries, for {\em any} totally ordered range $\RR$. More
generally, if at least an $\alpha(n)$ fraction of the pairs can
always be connected with edge-disjoint paths then the query-complexity
is $O(n/\alpha(n))$.

We construct a family of instances of $\ell=\Omega(2^n)$ 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
\cite{le_ro}, 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 $\approx n^{3/2}$.
Additionally, our construction can also be used to obtain a strong counterexample to Szymanski's
conjecture on routing in the hypercube. In particular, we show that for any $\delta > 0$, the $n$-dimensional
hypercube is not $n^{\frac 12 -\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 $\Omega(n/\epsilon)$ 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.