Signotopes with Few Plus Signs

We represent each $d$-subset as a set of $d$ tokens, one placed on the real line at each element of the subset. Then the act of going from one $d$-subset to an adjacent $d$-subset in $G_{n,d}$ can be seen as moving a token along the real line (in an arbitrary direction) to the next free integer. Suppose that $b_i>i$. Note that $[b_i-1]$ contains at least $i$ elements of $S_i$ and exactly $i-1$ elements of $B$. Hence, in the process of going along a path from $S_i$ to $B$ in $G_{n,d}$, there must be at least one token from the interval $[b_i-1]$ going to the interval $[b_i,n]$. Therefore, every integer in $[i+1,b_i]$ must be visited by a token at some point in the process (these integers may or may not be visited by the same token). Note that this statement is vacuously true when $b_i=i$ or when $i=0$.

Using a symmetric argument, we also deduce that every integer in $[b_{i+1},n-d+i]$ must also be visited by a token at some point in the process above. Further, at any step, we only move one token, and hence, at most one integer in $[i+1,b_i]\cup [b_{i+1},n-d+i]$ is visited at any step. Hence, we conclude that the path from $S_i$ to $B$ must have length at least $(b_i-i)+(n-d+i-b_{i+1}+1)$. The lemma then follows. $◀$

For a $d$-co-signotope $\tau$, let $G_{n,d}[\tau ]$ be the induced subgraph of $G_{n,d}$ on ${\tau }^{-1}(+)$ (i.e., the $+$-subsets of $\tau$). A maximal connected induced subgraph of $G_{n,d}[\tau ]$ is called a $+$-component of $\tau$. Then it is easy to see that each $+$-component of $\tau$ contains at least one source subset. This is actually tight for all components when $\tau \in {\overline{𝒮}}_p(n,d)$ with $p\le n-d$, as stated in the following lemma.

Suppose we have two source subsets $S_i$ and $S_j$ with . Applying Lemma 6 with $B=S_j$, a path between two source subsets $S_i$ and $S_j$ with has length at least $i-(i+1)+n-d+1=n-d$. This shows that every $+$-component containing $S_i$ and $S_j$ has at least $n-d+1>p$ $+$-subsets. Since $\tau$ has $p$ $+$-subsets, it follows that no component of $G_{n,d}[\tau ]$ can contain more than one source subset. Combined with the fact that each component needs to have at least one source subset, the lemma then follows. $◀$

Motivated by the lemma above, for a co-signotope $\tau \in \overline{𝒮}(n,d)$ and for $i\in [0,d]$, we denote by ${𝒞}_i^{\tau }$ the $+$-component that contains $S_i$ (${𝒞}_i^{\tau }$ may be empty.)

For a co-signotope $\tau \in \overline{𝒮}(n,d)$, a $d$-subset $B$, and an index $j\in [d]$, we say the $(\tau ,B,j)$-series is left-aligned if it starts with a $+$-subset and ends with a $-$-subset, right-aligned if it starts with a $-$-subset and ends with a $+$-subset, and flat if there is no sign change. Since every $(\tau ,B,j)$-series has $n-d+1$ subsets, if $\tau$ has at most $(n-d)$ $+$-subsets, then no flat series has only $+$-subsets. Hence, we have the following simple observation.

The following lemma characterizes which $d$-subsets can be in the same $+$-component as some source subset $S_i$.

We first consider the case when $j\in [i]$. By Lemma 6, the shortest path between $B$ and $S_i$ is at least $b_i-b_{i+1}+n-d+1$. Since $B$ and $S_i$ are in the same $+$-component ${𝒞}_i^{\tau }$ of size $c$, this implies $b_i-b_{i+1}+n-d+1\le c-1$. Moreover since , we obtain $b_{i+1}\le n-d+i+1$. Together this implies

Combining this with the fact that $b_j\le b_i-(i-j)$, we have $b_j\le c+j-1$ as required.

We now prove by contradiction that the $(\tau ,B,j)$-series is left-aligned. Suppose this is not the case. Combined with Observation 8, $(\tau ,B,j)$-series must then be right-aligned, i.e., all of the subsets after $B$ in the $(B,j)$-series then have to be $+$-subsets. That means each element in $[b_j,n]$ appears in some $+$-subset. If $b_j=j$, then also all elements in $[b_j]$ appear in $S_i$, a $+$-subset. Otherwise, using the same token argument as in the proof of Lemma 6, each element in $[i+1,b_i]$ is contained in some $+$-subset along the path from $S_i$ to $B$ in ${𝒞}_i^{\tau }$. Combining with the fact that $[i]\subseteq S_i$, we obtain that each element in $[b_i]$ appears in some $+$-subset. Overall, each element in $[n]$ appears in some $+$-subset.

Next, observe that going from a subset to an adjacent subset in $G_{n,d}$, we remove one element and add one element. Hence, since ${𝒞}_i^{\tau }$ has at most $p$ elements, the number of elements appearing in at least one $+$-subset is at most $d+p-1\le n-1$. This contradicts with the conclusion above that each element in $[n]$ appears in some $+$-subset.

Hence, (a) holds. With a symmetric argument, we also obtain (b), completing the proof of the lemma. $◀$

A direct consequence of the lemma above is that for a given $\tau \in {\overline{𝒮}}_p(n,d)$, we can identify to which $+$-component a $+$-subset belongs.

Suppose we have a co-signotope $\tau \in {\overline{𝒮}}_{p,i}(n,d)$, we show that for ${ℱ}_{\tau }:=\{g_{n,d,i}(B)\mid B\in {\tau }^{-1}(+)\}$, the set ${ℱ}_{\tau }$ is a $(d,i)$-Ferrers diagram with respect to $p$. By Observation 12, the elements of ${ℱ}_{\tau }$ have positive integral indices, and $g_{n,d,i}$ is injective. Combined with the fact that $\tau$ has $p$ $+$-subsets, this implies that ${ℱ}_{\tau }$ has $p$ elements.

We start by showing that ${ℱ}_{\tau }\subset Z(d,i)$, for $Z(d,i)$ as defined in Definition 13. Consider a $+$-subset $B=(b_1,\mathrm{\dots },b_d)$. For $j\in [2,i]$, we have $b_j>b_{j-1}$ by our convention of a subset. Hence, $f_{n,d,i,j}(b_j)+j-1>f_{n,d,i,j-1}(b_{j-1})+(j-1)-1$, which is equivalent to $f_{n,d,i,j}(b_j)\ge f_{n,d,i,j-1}(b_{j-1})$. Similarly, for $j\in [i+1,n-1]$, we obtain $f_{n,d,i,j}(b_j)\ge f_{n,d,i,j+1}(b_{j+1})$. It follows that ${ℱ}_{\tau }\subset Z(d,i)$. Then Lemma 9 implies that ${ℱ}_{\tau }$ satisfies the condition of a $(d,i)$-Ferrers diagram with respect to $p$ in Definition 13.

For the other direction, suppose we have a $(d,i)$-Ferrers diagram $ℱ$ with respect to $p$. We show that the sign function $\tau$ such that ${\tau }^{-1}(+)=\{g_{n,d,i}^{-1}(X)\mid X\in ℱ\}$ is a co-signotope in ${\overline{𝒮}}_{p,i}(n,d)$. We first show that for every $X=(a_1,\mathrm{\dots },a_d)\in ℱ$, $g_{n,d,i}^{-1}(X)$ is a $d$-subset. Indeed, since $ℱ\subset Z(d,i)$, it is easy to see that for $j\in [2,i]\cup [i+2,n]$, $f_{n,d,i,j}^{-1}(a_j)>f_{n,d,i,j-1}^{-1}(a_{j-1})$. For $j=i+1$, note that if the sum of the indices of $X$ is $s$, then by Definition 13, it is easy to see that for $k\in [d,s]$, there exists an element $Y$ in $ℱ$ whose sum of indices is exactly $k$. Combining this with the fact that there are $p$ elements in $ℱ$, we obtain that $s\le p+d-1$, and consequently, $a_i+a_{i+1}\le p+1$. This implies

This completes the proof that $g_{n,d,i}^{-1}(X)$ is a $d$-subset.

Next, we show that $\tau$ is a co-signotope, i.e., for every $d$-subset $B$ and index $j$, the $(\tau ,B,j)$-series has at most one sign change. This is implied by the condition of a $(d,i)$-Ferrers diagram in Definition 13.

Lastly, observe that for any element $X=(a_1,\mathrm{\dots },a_d)$ in $ℱ$, if it is not $(1,\mathrm{\dots },1)$, then we can find an index $j$ such that the element $X^{\prime }$ obtained from $X$ by replacing $a_j$ with $a_j-1$ is in $Z(d,i)$. Hence, $X^{\prime }$ is in $ℱ$. Repeating this process, we obtain a sequence of elements in $ℱ$ starting from $X$ and ending at $(1,\mathrm{\dots },1)$. This corresponds to a walk in the graph $G_{n,d}$ from a $+$-subset of $\tau$ to $S_i$. (Recall from Observation 12 that $g_{n,d,i}^{-1}((1,\mathrm{\dots },1))=S_i$.) This implies that all $+$-subsets of $\tau$ are connected to $S_i$ in $G_n[\tau ]$. Hence, there is only one $+$-component, and this $+$-component contains $S_i$. Since $g_{n,d,i}^{-1}$ is injective, the $+$-component has $p$ subsets. This completes the proof of the lemma. $◀$

Observe that the set ${ℱ}_{\tau }$ in Lemma 14 depends only on $d$, $i$, and $p$, but not on $n$. Hence, this lemma straighforwardly implies a bijection between ${\overline{𝒮}}_{p,i}(n,d)$ and ${\overline{𝒮}}_{p,i}(\tilde{n},d)$ such that $\min \{n,\tilde{n}\}\ge p+d$, as follows.

For every $d$-subset $B$ of $[n]$ and every index $j$, the $+$-subsets in the $(\tau ,B,j)$-series form a path in $G_{n,d}$. Hence ${\tau }_i$ is a co-signotope in ${\overline{𝒮}}_{|{𝒞}_i^{\tau }|,i}(n,d)$ for $i\in [0,d]$. $◀$

Note that not every tuple $(p_0,\mathrm{\dots },p_d)$ such that ${\sum }_{i=0}^d{p}_i=p$ is the p-sequence of a co-signotope. There are some necessary conditions which turn out to be sufficient as well. For this we define a sparse composition of an integer $p$ as a $(d+1)$-tuple $(c_0,\mathrm{\dots },c_d)$ of non-negative integers such that ${\sum }_{i=0}^n{c}_i=p$ and either $c_i=0$ or $c_{i-1}=0$ for all $i\in [d]$.

To show the first part, note that by Lemma 7, we obtain ${\sum }_{i=0}^d{p}_i=p$. We argue that for all $i\in [p]$, either $p_i=0$ or $p_{i-1}=0$. Indeed, if this is not the case, $S_i$ and $S_{i-1}$ are both $+$-subsets by definition. Then the $(\tau ,S_i,i)$-series starts with a $+$-subset $S_i$ and ends with a $+$-subset $S_{i-1}$. This implies that all subsets in $(\tau ,B,i)$-series are $+$-subsets, and hence this series is flat, a contradiction to Observation 8. Therefore, $(p_0,\mathrm{\dots },p_d)$ is a sparse composition of $p$.

Now let $\tau$ be the sign function over $\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)$ such that ${\tau }^{-1}(+)={\bigcup }_{i=0}^d{\tau }_i^{-1}(+)$. By construction, $\tau$ has at most $p$ $+$-subsets.

We start by arguing that $\tau$ is a co-signotope. Suppose that this is not the case. Then for some $d$-subset $B=(b_1,\mathrm{\dots },b_d)$ and an index $j$, the $(\tau ,B,j)$-series has more than one sign change. By definition of $\tau$ and by the fact that ${\tau }_i$ is a co-signotope in ${\overline{𝒮}}_{c_i,i}(n,d)$ for $i\in [0,d]$, we must have that for some $i,i^{\prime }\in [0,d]$, the $({\tau }_i,B,j)$-series is left-aligned and $({\tau }_{i^{\prime }},B,j)$-series is right-aligned. Because $(c_0,\mathrm{\dots },c_d)$ is a sparse composition, we have $|i-i^{\prime }|\ge 2$. Let $B^{\alpha }=(b_1^{\alpha },\mathrm{\dots },b_d^{\alpha })$ and $B^{\omega }=(b_1^{\omega },\mathrm{\dots },b_d^{\omega })$ be the first and the last subsets of the $(B,j)$-series, respectively. We use the convention that $b_k=0$ for and $b_k=d+1$ for $k>d$. It is easy to see the following:

1. (a)

   If $j\ge i$, then $[b_i^{\alpha },b_{i+1}^{\alpha }]\subseteq [b_{i-1},b_{i+1}]$;

2. (b)

   If , then $[b_i^{\alpha },b_{i+1}^{\alpha }]\subseteq [b_i,b_{i+1}]$;

3. (c)

   If $j\le i^{\prime }+1$, then $[b_{i^{\prime }}^{\omega },b_{i^{\prime }+1}^{\omega }]\subseteq [b_{i^{\prime }},b_{i^{\prime }+2}]$;

4. (d)

   If $j>i^{\prime }+1$, then $[b_{i^{\prime }}^{\omega },b_{i^{\prime }+1}^{\omega }]\subseteq [b_{i^{\prime }},b_{i^{\prime }+1}]$.

From the above case distinction, we observe that when $j>i^{\prime }+1$, the interiors of $[b_i^{\alpha },b_{i+1}^{\alpha }]$ and $[b_{i^{\prime }}^{\omega },b_{i^{\prime }+1}^{\omega }]$ are disjoint, since $|i^{\prime }-i|\ge 2$. When $j\le i^{\prime }+1$ and $i^{\prime }\ge i+2$, these interiors are also disjoint. When $j\le i^{\prime }+1$ and $i^{\prime }\le i-2$, then (b) and (c) are applicable, and the two interiors are also disjoint.

Hence, we always have that the two interiors above are disjoint. Further, from (a)–(d) above, these interiors contain only integers from $[n]\setminus B\cup \{b_i,b_{i^{\prime }+1}\}$. These two statements imply that $b_{i+1}^{\alpha }-b_i^{\alpha }+b_{i^{\prime }+1}^{\omega }-b_{i^{\prime }}^{\omega }\le n-d+4$.

By Lemma 6, the shortest path between $S_i$ and $B^{\alpha }$ is $b_i^{\alpha }-b_{i+1}^{\alpha }+n-d+1$, whereas the shortest path between $S_{i^{\prime }}$ and $B^{\omega }$ is $b_{i^{\prime }}^{\omega }-b_{i^{\prime }+1}^{\omega }+n-d+1$. Then the sum of the distances is

This implies that $c_i+c_{i^{\prime }}\ge p+1$, a contradiction to the fact that $(c_0,\mathrm{\dots },c_d)$ is a sparse composition of $p$.

Next, by Lemma 7, each $+$-component of $\tau$ contains exactly one source subset. Hence, no subset is a $+$-subset of more than one co-signotope among ${\tau }_0,\mathrm{\dots },{\tau }_d$. Therefore, $\tau$ has exactly $p$ $+$-subsets, and each $+$-component of $\tau$ that contains $S_i$ corresponds exactly to the $+$-component of ${\tau }_i$. This also implies that $\tau$ is unique and $\mathrm{\Delta }(\tau )=({\tau }_0,{\tau }_1,\mathrm{\dots },{\tau }_d)$. It follows that $(c_0,\mathrm{\dots },c_d)$ is the p-sequence of $\tau$, completing the proof of the lemma. $◀$

Consider the following mapping ${\zeta }_{n,\tilde{n},d,p}$ from a co-signotope $\tau \in {\overline{𝒮}}_{\le p}(n,d)$ to a co-signotope $\tilde{\tau }\in {\overline{𝒮}}_{\le p}(\tilde{n},d)$. Let $(p_0,\mathrm{\dots },p_d)$ be the p-sequence of $\tau$. We first obtain the $+$-component decomposition $({\tau }_0,{\tau }_1,\mathrm{\dots },{\tau }_d)$ of $\tau$. Next, we use the bijection $h_{n,\tilde{n},d,p_i,i}$ in Corollary 15 to map each of ${\tau }_i\in {\overline{𝒮}}_{p_i,i}(n,d)$ to ${\tilde{\tau }}_i\in {\overline{𝒮}}_{p_i,i}(\tilde{n},d)$. Then from the tuple $({\tilde{\tau }}_0,{\tilde{\tau }}_1,\mathrm{\dots },{\tilde{\tau }}_d)$, we can combine their $+$-subsets to construct $\tilde{\tau }$. By Lemma 17, $\tilde{\tau }\in {\overline{𝒮}}_p(\tilde{n},d)$.

By Corollary 15, Lemma 16, and Lemma 17, the mapping ${\zeta }_{n,\tilde{n},d,p}$ is injective. Also by these corollary and lemmas, the mapping ${\zeta }_{\tilde{n},n,d,p}$ maps $\tilde{\tau }$ back to $\tau$ and generally this mapping maps a signotope in ${\overline{S}}_p(\tilde{n},d)$ to ${\overline{S}}_p(n,d)$. This implies that ${\zeta }_{n,\tilde{n},d,p}$ is a bijection between ${\overline{S}}_p(n,d)$ and ${\overline{S}}_p(\tilde{n},d)$.

It remains to prove that ${\zeta }_{n,\tilde{n},d,p}$ preserves the relation ${⪯}_{\overline{S}}$. For this, it is sufficient to prove that ${\zeta }_{n,\tilde{n},d,p}$ preserves the single step relation. Let $\tau$ and $\rho$ be two $d$-co-signotopes in ${\overline{𝒮}}_{\le p}(n,d)$ such that ${\tau }^{-1}(+)\subset {\rho }^{-1}(+)$ and $|{\rho }^{-1}(+)|=|{\tau }^{-1}(+)|+1=k+1$ for some $k$. Let $({\tau }_0,\mathrm{\dots },{\tau }_d)=\mathrm{\Delta }(\tau )$ and $({\rho }_0,\mathrm{\dots },{\rho }_d)=\mathrm{\Delta }(\rho )$. This implies that $\mathrm{\Delta }(\tau )$ and $\mathrm{\Delta }(\rho )$ agree in all coordinates, except for some $i$-th coordinate, where ${\tau }_i$ and ${\rho }_i$ differ by a single step. Let $\tilde{\tau }$ and $\tilde{\rho }$ be the images of $\tau$ and $\rho$, respectively, in the bijection above. By Corollary 15, it follows that $\mathrm{\Delta }(\tilde{\tau })$ and $\mathrm{\Delta }(\tilde{\rho })$ also agree in all coordinates, except for some $i$-th coordinate, where the two corresponding co-signotopes differ by a single step. This in turns implies that $\tilde{\tau }$ and $\tilde{\rho }$ differ by a single step. This completes the proof of the theorem. $◀$