Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing

Recent work has generalized the LR theorem different directions in [3]. These results find vertex disjoint paths that “cover” any collection of points specifying certain properties. Consider a subset $X$ of the hypercube that is partitioned into subsets of paths (or chains). Meaning, we partition $X={\bigcup }_i{X}_i$ such that, the vertices of $X_i$ can be ordered according to $\prec$. (Moreover, this is the partition that minimizes the number of sets.) In the vanilla LR setting, each $X_i$ is just $(s,\varphi (s))$ for each $s\in S$. The main theorem of [3] shows that $X$ can be covered by a collection of vertex disjoint paths. A nice implication of their result is that Theorem 1 holds even if $S$ and $T$ were not contained in levels, but were antichains.

We also note that the routing perspective in §4 answers a question of Sachdeva from a collection of open problems on Boolean functions [27] (Pg 19, “Routing on the hypercube”). We discuss more in §4.

If $C$ contains a vertex $S\cup T$, then one obtains a smaller counterexample. If $v\in C\cap S$, then $S^{\prime }:=S\setminus \{v\}$, $T^{\prime }:=T\setminus \{\varphi (v)\}$ and ${\varphi }^{\prime }:={\varphi }_{{|}_{S^{\prime }}}$ forms a matched pair $(S^{\prime },T^{\prime };{\varphi }^{\prime })$ which is also a counterexample: the cut $(C-\{v\})$ is a valid cut of value . So, $C\cap S=\mathrm{\varnothing }$. The proof of $C\cap T=\mathrm{\varnothing }$ is analogous. $◀$ Our setup so far is a restructuring of the original Lehman-Ron proof. The following lemma is where we start to differ. This lemma is a consequence of complementary slackness from the theory of linear optimization, and is the central tool for our new proof.

Note that all these paths are in the cover graph $G_{S,T}$. Using the above collection of paths, we make a key definition.

The Lehman-Ron theorem, Theorem 1, follows directly from the following lemma.

Consider the gateway vertex $v\in L_{j-1}\cap 𝒮$ with edge $(v,w)$ in the cover-graph. Note $w\in T$ and therefore in $𝒯$. There is an edge from $𝒮$ to $𝒯$. Contradiction. Hence, there is no (minimal) counterexample to Theorem 1. $◀$ Before giving the formal proof of Lemma 8 directly, let us describe the main idea which uses the symmetry of the hypercube. First, let us observe the layer $L_i$, that is $S$, contains a gateway vertex $s$. Indeed, there are $\le |S|-1$ paths in $𝒫$ and so there is some $s\in S$ not in any of these paths. Furthermore, all edges that lead $s$ to $\varphi (s)$ lie in the cover-graph.

Now, let’s see how to get a gateway in the next layer $L_{i+1}$. Consider any edge $(s,x^{(1)})$ in $G_{S,T}$, and suppose this edge corresponds to projecting according to some dimension $r$. That is $s_r=0$ and $x_r^{(1)}=1$. If $x^{(1)}$ is not in any path in $𝒫$, we have discovered the desired gateway in $L_{i+1}$. Otherwise, $x^{(1)}$ lies on some path, say, $P\in 𝒫$. Follow $P$ forwards for a single edge from $x^{(1)}$, to get to $x^{(2)}$. Note that $x^{(2)}\in L_{i+2}$ and has $r$th-coordinate $1$. Now, one can project “down” on the $r$-coordinate to get $x^{(3)}\in L_{i+1}$. Observe that $(s,x^{(3)})$ is a projection of the edge $(x^{(1)},x^{(2)})$ along the $r$th-dimension and hence is an edge of the cover-graph. Next, observe that $x^{(3)}$ cannot be in $𝒯$, so either $x^{(3)}\in 𝒮$ or $x^{(3)}\in C$. If $x_3\in 𝒮$ and not on any path in $𝒫$, we are done. Otherwise $x^{(3)}$ lies on some other path $Q\in 𝒫$. We now walk backwards along $Q$, to get $x^{(4)}\in S$. Noting that $x^{(4)}$ has $r$-coordinate $0$, we can redo the entire process above. Observe that each “step” proceeds along a matching. Either we project, walk from $L_{i+1}$ to $L_{i+2}$ using a path in $𝒫$, or walk backward from $L_{i+1}$ to $L_i$ using a path in $𝒫$. Each of these is using a matching edge, and no vertex is ever visited twice in the entire process. Hence, this process must terminate, at which point a gateway is discovered. And then one uses the same idea to obtain a gateway vertex in $L_{i+2}$, and so on. One can convert this idea into a formal proof, but it becomes notationally cumbersome. A cleaner proof method is to consider a potential “fixed point” of this process, and prove a contradiction.

Fix a collection of paths $𝒫$ as given by Lemma 6. As argued above, $L_i$ has a gateway vertex. Let $k\in [i,j-1]$ be the largest value such that $L_k$ contains a gateway vertex. If $k=j-1$, we are done. So suppose that . We now engineer a contradiction. Let $v^{\star }$ be a gateway in $L_k$. So $v^{\star }\in 𝒮$ and has an edge $(v^{\star },w)$ leaving it. Let $r$ be the dimension of this edge implying $v_r^{\star }=0$ and $w_r=1$. Let ${\mathrm{\Pi }}_r$ be the projection operator which flips the $r$th coordinate; so ${\mathrm{\Pi }}_r(v^{\star })=w$ and vice versa. Define the following sets; we give a illustration for convenience where the pink highlighted edges participate in paths of $𝒫$.

• $\mathrm{■}$

  $A=\{a:a\in 𝒮\cap L_k,a_r=0\text{and}{\mathrm{\Pi }}_r(a)\in G_{𝒮,𝒯}\}$.

• $\mathrm{■}$

  $X={\mathrm{\Pi }}_r(A)=\{{\mathrm{\Pi }}_r(a):a\in A\}$.

• $\mathrm{■}$

  $B=\{b:(x,b)\in P,\text{for some}x\in X,P\in 𝒫\}$.

• $\mathrm{■}$

  $Y={\mathrm{\Pi }}_r(B)=\{{\mathrm{\Pi }}_r(b):b\in B\}$.

Observe that $X\cup Y\subseteq L_{k+1}$, and $B\subseteq L_{k+2}$. We next argue these subsets lie in the cover-graph. By definition of $A$, $X\subseteq G_{𝒮,𝒯}$, and since $B$ is obtained via paths from $X$, we get $B\subseteq G_{𝒮,𝒯}$. Finally, for any $y\in Y$, note that $b={\mathrm{\Pi }}_r(y)$ lies in $B$, and there’s a path $(a,x,b)$ for some $a\in A$ and $x={\mathrm{\Pi }}_r(a)$. But note that $(a,y)$ edge is the $r$-projection of $(x,b)$, and so $(a,y,b)$ is a path implying $y\in G_{𝒮,𝒯}$. Thus, $Y$ also lies in the cover-graph.

Since $X$ is a projection of $A$, we get $|X|=|A|$. Consider any $x\in X$. Since $x\in L_{k+1}$, by our choice of $k$, $x$ isn’t a gateway vertex. Since $(a,x)$ is an edge for $a={\mathrm{\Pi }}_r(x)$, we have $x\in 𝒮$ or $x\in C$. In the former case since $x$ isn’t a gateway vertex, and in the latter case by Lemma 6, there exists $P\in 𝒫$ with $x\in P$. And so, $|B|=|X|$. By projection property, $|Y|=|B|$, and so following the above chain of equalities, we get $|Y|=|A|$.

Next consider any $y\in Y$. As argued above, there is a vertex $a\in A$ such that $(a,y)$ is an edge in the cover-graph (the projection of $(x,b)\in P$ where $b={\mathrm{\Pi }}_r(y)$). Since $y\in L_{k+1}$, by our choice of $k$, $y$ isn’t a gateway vertex. Since $(a,y)$ is an edge, we must have $y\in 𝒮$ or $y\in C$. In the former case since $y$ isn’t a gateway vertex, and in the latter case by Lemma 6, there exists $Q\in 𝒫$ with $y\in Q$. Let $(a^{\prime },y)$ be the edge in $Q$ taking $y$ “backward” along $Q$. We claim that $a^{\prime }\in A$. If $y\in 𝒮$, then $a^{\prime }\in 𝒮$ since $(a^{\prime },y)$ is an edge; if $y\in C$ then by Lemma 6, $a^{\prime }\in 𝒮$ (the path $Q$ doesn’t contain two cut-vertices). Since $(a^{\prime },x^{\prime }={\mathrm{\Pi }}_r(a^{\prime }))$ lies in the cover graph since the $r$-projection of the $(a^{\prime },y)$ lies there, we get $x^{\prime }$ lies in the cover-graph, implying $a^{\prime }$ must lie in $A$. The above figure illustrates this. In short, there are $|Y|$ paths of $𝒫$ that contain vertices of $A$. Since $|Y|=|A|$ and since these paths are all vertex-disjoint, we conclude all vertices in $A$ are present in some path of $𝒫$. However, the gateway vertex $v^{\star }\in A$ and doesn’t lie on any path of $𝒫$. Contradiction. $◀$

Proof of (i) is exactly as in Lemma 5. Suppose $v$ participates in at least two edges of $F$. Observe that any $S$-$T$ path through any of these edges must go via $v$. Hence, we can remove these edges from $F$, add $v$ to $C$, and preserve the fact that $C\cup F$ is an $S$-$T$ cut. Moreover, the cut value does not increase. $◀$ We can now give the analog of Lemma 6.

By complementary slackness (Theeorem A.7 of [23]) , every maximum flow must saturate the min cut. Together with integrality of flow, this implies the existence of an integral flow saturating $C\cup F$. We give a (simple) formal explanation. By integrality of flow, there is a maximum flow that can be decomposed into paths. Let $𝒫$ be those paths. Since these paths form a feasible flow, they satisfy the first two bullet points of the lemma. By duality, $|𝒫|=2|C|+|F|$. For each path $p\in P$, let $c_p$ be the number of cut elements in $C\cup F$ that the path contains. For each cut element $e\in C\cup F$, let $k_e$ be the number of paths that $e$ participates in. So ${\sum }_{p\in 𝒫}{c}_p={\sum }_{e\in C\cup F}{k}_e$. Note that $\forall p,c_p\ge 1$, since $C\cup F$ is a valid cut. Thus, ${\sum }_{p\in 𝒫}{c}_p\ge |𝒫|$. Now, observe that $\forall e\in C,k_e\le 2$ and $\forall e\in F$, $k_e\le 1$, since $C\cup F$ must satisfy the flow constraints. Hence, ${\sum }_{e\in C\cup F}{k}_e\le 2|C|+F$. We get $|𝒫|\le {\sum }_{p\in 𝒫}{c}_p={\sum }_{e\in C\cup F}{k}_e=2|C|+|F|=|𝒫|$. Thus, the inequalities above are all equalities. So $\forall p,c_p=1$ (third bullet) and $\forall e\in C,k_e=2$ and $\forall e\in F$, $k_e=1$ (fourth bullet). $◀$ Next we provide the relevant generalization of gateway vertices earlier defined in Definition 7

As before, the proof of Theorem 2 follows from the following lemma, and the remainder of this section will prove it.

As in the proof of Lemma 8, we proceed via minimal counterexamples. First, we establish that there is a vertex in $L_i$ that is a gateway vertex. There are paths in $𝒫$. Since any vertex participates in at most $2$ paths, some vertex in $s$ participates in at most $1$ path. Since $\varphi (s)$ is at least distance $2$ away from $s$, $s$ has degree at least $2$ in $G_{S,T}$. (This is where the distance between $S$ and $T$ is used.) At most one of those edges is in $F$ (Lemma 9), so there is some edge leaving $s$ that is not in $F$. Thus, $s$ is a gateway vertex.

Now, let $k\in [i,j-1]$ be the largest value such that $L_k$ contains a gateway vertex. If $k=j-1$, we are done. So suppose that , and we will engineer a contradiction. Let $v^{\star }$ be a gateway vertex in $L_k$. So $v^{\star }\in 𝒮$, participates in at most one path of $𝒫$, and there is some edge leaving $v^{\star }$ that is not in $F$. First, let us choose the projection dimension $r$ as follows. If $v^{\star }$ lies on exactly one path $P\in 𝒫$, then let $(v^{\star },w)$ be the edge of $P$ incident to $v^{\star }$ and let $r$ be the coordinate that this edge flips. If $v^{\star }$ lies on no path $P\in 𝒫$, then since , there are at least two²²2There is some $s\in S$ such that $s\prec v\prec \varphi (s)$ and there are at least $2$ edge disjoint paths from $v$ to $\varphi (s)$. edges incident to $v^{\star }$ that are in the cover-graph; let $(v^{\star },w)$ be any such edge and let $r$ be the coordinate of this edge. As in the proof of Lemma 8, we let ${\mathrm{\Pi }}_r$ denote the projection operator, and we define the sets exactly as in the previous proof.

• $\mathrm{■}$

  $A=\{a:a\in 𝒮\cap L_k,a_r=0\text{and}{\mathrm{\Pi }}_r(a)\in G_{𝒮,𝒯}\}$. Note that $v^{\star }\in A$.

• $\mathrm{■}$

  $X={\mathrm{\Pi }}_r(A)=\{{\mathrm{\Pi }}_r(a):a\in A\}$.

• $\mathrm{■}$

  $B=\{b:(x,b)\in P,\text{for some}x\in X,P\in 𝒫\}$.

• $\mathrm{■}$

  $Y={\mathrm{\Pi }}_r(B)=\{{\mathrm{\Pi }}_r(b):b\in B\}$.

As in the proof of Lemma 8, we have $X\cup Y\subseteq L_{k+1}$, and $B\subseteq L_{k+2}$ and that $A,X,B,Y$ all lie in the cover graph $G_{𝒮,𝒯}$. As there, we crucially use the property that the projection of every $(A,Y)$ edge lies is an $(X,B)$ edge. Note that, we have $|A|=|X|$ and $|B|=|Y|$. However, unlike in Lemma 8, there can be two paths of $𝒫$ that may contain $x\in X$, and thus, $|B|$ may be larger in size than $|X|$. And this makes the proof slightly more complicated.

We now restrict our attention to these four sets. As a result, we only consider the cover graph $G_{A,B}$, which, recall, is the union of all paths from vertices in $A$ to vertices in $B$ (irrespective of whether they contain cut-elements). Both $A$ and $B$ lie in this graph by definition. We assert $X\subseteq G_{A,B}$. Take a vertex $x\in X$. If $x\in P$ for some path $P\in 𝒫$ then it lies in $G_{A,B}$ by construction. We now show if $x$ is not any path in $𝒫$, we already have a contradiction. Indeed, the edge $(a,x)$ where $a={\mathrm{\Pi }}_r(x)$ isn’t in $F$ for otherwise, by Lemma 10 there would be a path containing $(a,x)$. Similarly $x\notin C$. So, $x\in 𝒮$. Since $x\in L_{k+1}$ and , there is at least one edge leaving it, and as before, this edge isn’t in $F$. So, $x$ is a gateway vertex which contradicts the choice of $k$. Thus, the subset $X$ lies in $G_{A,B}$. And since every $(A,Y)$ edge is an $r$-projection of an $(X,B)$ edge, we argue that $Y$ also lies in $G_{A,B}$.
We now make another definition which will lead to our contradiction.

Thus, every pink edge incident to $A$ is incident to $Y$, and every pink edge incident to $X$ is incident to $B$. The following claim is a consequence.

Next, observe that the gateway $v^{\star }$ participates in at most one path of $𝒫$. If such a path existed, we chose the dimension $r$ according to the incident edge of this path. Hence, $\text{pink}(v^{\star })=0$. This is central to proving the final contradiction.

There is a perfect matching between $A$ and $X$. We prove that $\forall a\in A$, $\text{pink}({\mathrm{\Pi }}_r(a))\ge \text{pink}(a)$. Furthermore, for the gateway $v^{\star }$, we get a strict inequality $\text{pink}({\mathrm{\Pi }}_r(v^{\star }))>\text{pink}(v^{\star })$. It is convenient to do a case analysis based on whether $x={\mathrm{\Pi }}_r(a)$ is in $𝒮,C$, or $𝒯$. Note that $\text{pink}(a)\le 2$ by Lemma 10 since any vertex participates in at most $2$ paths of $𝒫$. Note that all edges of $𝒫$ that leave $X$ lead to $B$ (by construction), so all these edges are in $G_{A,B}$.

$x\in C$: This is the easiest. By Lemma 10, there are two paths through $x$. So $\text{pink}(x)=2\ge \text{pink}(a)$.

$x\in 𝒯$: Note that $a\in 𝒮$, and so in this case, the $r$-projection edge $(a,x)$ must be $\in F$. By Lemma 10, there is a path of $𝒫$ through $(a,x)$, and the next edge leaving $x$ goes into $B$. Since the $r$-coordinate doesn’t change, this edge is pink, and so $\text{pink}(x)\ge 1$. Since $a$ participates in the path through projection edge $(a,x)$, which is not pink, it can participate in at most one other path of $𝒫$ (by Lemma 10, no vertex is in more than $2$ paths). Thus, in this case $\text{pink}(a)\le 1$ implying $\text{pink}(a)\le \text{pink}(x)$.

$x\in 𝒮$: By our assumption, $x$ cannot be a gateway vertex. So either all edges leaving $x$ are in $F$ or $x$ is in $2$ paths of $𝒫$. If the latter happens, then $\text{pink}(x)=2$, completing this case. So let us assume the former. There must be some edge leaving $x$ in $G_{A,B}$ because $x$ is in the cover graph $G_{A,B}$; since $x$ is not a gateway vertex, this edge which must be in $F$. By Lemma 10, there is a path $P\in 𝒫$ containing this and the edge incident to $x$ doesn’t change the $r$-coordinate, and thus is pink. So, $\text{pink}(x)\ge 1$. So, if $\text{pink}(a)\le 1$ we are done. So, suppose $\text{pink}(a)=2$. That is, there are two distinct edges $(a,y)$ and $(a,y^{\prime })$ which are pink. Consider the $r$-projection of these edges, $(x,{\mathrm{\Pi }}_r(y))$ and $(x,{\mathrm{\Pi }}_r(y^{\prime }))$; these are present in $G_{A,B}$ and so by our assumption above, these two must be in $F$. But again by Lemma 10, there are two paths in $𝒫$ containing these, and so these edges are pink, implying $\text{pink}(x)=2$ as well. This settles this case.

All in all, we have proven that $\text{pink}(x)\ge \text{pink}(a)$, and note that in all cases, $\text{pink}(x)\ge 1$. Since $\text{pink}(v^{\star })=0$, we get the strict inequality $\text{pink}({\mathrm{\Pi }}_r(v^{\star }))>\text{pink}(v^{\star })$, completing the proof of the claim. $\mathrm{⊲}$ The next claim which, along with Claim 14, contradicts Claim 15, completing our proof of Lemma 12.

There is a perfect matching between $B$ and $Y$ by the ${\mathrm{\Pi }}_r$ projection. We will show that for every $b\in B$, $\text{pink}(b)\le \text{pink}(y)$, where $y={\mathrm{\Pi }}_r(b)$. The proof is analogous to that of Claim 15, with a subtle difference. All edges of $𝒫$ leaving $X$ are in $G_{A,B}$ by construction. But all edges of $𝒫$ entering $Y$ might not be in $G_{A,B}$. In particular, there could be a path $Q\in 𝒫$ which contains $y$ and the predecessor, call it $z$, of $y$ on this path may not be in $A$. For instance, this could occur if $y\in 𝒯$ and $z\in C$ (and thus not in $A$).

With hindsight, we assert that if $y\in 𝒮\cup C$, then the vertex $z$ indeed lies in $A$. To see this note that $z\in 𝒮$; this follows from Lemma 10 since the path $Q$ contains exactly one cut-vertex or cut-edge. Furthermore, ${\mathrm{\Pi }}_r(z)$ must lie in $G_{𝒮,𝒯}$ since $(z,{\mathrm{\Pi }}_r(z),b)$ is present in the hypercube. In all, $z\in A$. The reader may wonder why this subtlety didn’t arise in the original Lehman-Ron proof that we showed in the previous section. Well, there is a vertex $a\in A$ such that $(a,y)$ is an edge, and since in the previous section we only had vertex cuts, we could (and did) assert $y\in S\cup C$. But now the edge $(a,y)$ could be in $F$. As we will see, the case when $y\in T$ is actually easy to take care of.

Now for the case analysis. Recall that $b\in B$ and $y={\mathrm{\Pi }}_r(w)\in Y$.

$y\in C$: By Lemma 10 there are two paths entering $y$, and since $y\in C$ due to the discussion about the subtlety above, $\text{pink}(y)=2$. Note that $\text{pink}(b)\le 2$ since there can be at most two paths of $𝒫$ incident on $b$.

$y\in 𝒮$: Since $y$ is not a gateway vertex (overall assumption), either $y$ participates in two paths of $𝒫$ or all edges leaving $y$ are in $F$. In the former case, since $y\in S$ due to the discussion about the subtlety above, $\text{pink}(y)=2$. In the latter case, the edge $(y,b)$ must be in $F$. So there is at least one path through $y$ and, again since $y\in S$, $\text{pink}(y)\ge 1$. Now note that the $(y,b)$ edge is not pink although it is on a path in $𝒫$ because the $r$-coordinate changes. So, $\text{pink}(b)\le 1$.

$y\in 𝒯$: Observe that all edges $(z,y)$ with $z\in A\subseteq 𝒮$ must be cut, that is $(z,y)\in F$. By Lemma 9, all such edges are on paths in $𝒫$ and are thus pink (they are clearly in $G_{A,B}$ and don’t change $r$-coordinate). Suppose $\text{pink}(b)=t$ where $t\in \{1,2\}$. Then there are $t$ distinct pink edges of the form $(x,b)$ with these $x$’s in $X$. Consider their $r$-projections, that is, the $t$ edges of the form $({\mathrm{\Pi }}_r(x),y)$. Since ${\mathrm{\Pi }}_r(x)\in A$, all these edges must be pink. This shows that if $y\in 𝒯$, $\text{pink}(y)\ge \text{pink}(b)$. $\mathrm{⊲}$