2
$\begingroup$

Let $n\geq 1$. Let $[n]=\{0<1\}^n$ equipped with the product order. Let $f:[n]\to [n]$ be a strictly increasing map. When $f$ is bijective, there exists a permutation $\sigma$ of $\{1,\dots,n\}$ such that $f(\epsilon_1,\dots,\epsilon_n)=(\epsilon_{\sigma(1)},\dots,\epsilon_{\sigma(n)})$.

Is there such a representation theorem when $f$ is not bijective ?

For $n=2$, the only maps are $(\epsilon_1,\epsilon_2)\to (\epsilon_1,\epsilon_2)$, $(\epsilon_1,\epsilon_2)\to (\epsilon_2,\epsilon_1)$, $(\epsilon_1,\epsilon_2)\to (\min(\epsilon_1,\epsilon_2),\max(\epsilon_1,\epsilon_2))$ and $(\epsilon_1,\epsilon_2)\to (\max(\epsilon_1,\epsilon_2),\min(\epsilon_1,\epsilon_2))$. For $n\geq 3$, things become more complicated and I am not aware of any canonical representation, or at least of a way of listing all strictly increasing maps $f:[n]\to [n]$.

Motivation: When $f$ is bijective or for $n=2$, I can see $f$ as a continuous map $[0,1]^n\to [0,1]^n$ which moreover, for people interested in directed homotopy theory, takes a directed path of $[0,1]^n$ to another directed path of $[0,1]^n$ preserving the initial and final states of the $n$-cube. I would like to do the same thing for the other cases.

$\endgroup$
6
  • $\begingroup$ Even classifying the images of such maps seems highly nontrivial. I don’t see why you couldn’t get e.g. every rank n graded poset this way. $\endgroup$ Commented Jul 28, 2022 at 15:30
  • $\begingroup$ @SamHopkins, some of them are easy to eliminate. In particular, if the second-lowest rank has all $n$ tuples with total weight 1 then the map must be bijective. To take another example, if $n=3$ and the ranks have restrictively 1,2,2,1 elements, one of the elements at rank value 1 has two successors at rank level 2, and the other has only one. $\endgroup$ Commented Jul 29, 2022 at 8:22
  • $\begingroup$ More generally, if two words $w_1, w_2$ of weight $k$ have Hamming distance 2, the Hamming distance of $f(w_1), f(w_2)$ must be at most 2, and if it is equal to 2 then $f(w_1 \vee w_2) = f(w_1) \vee f(w_2)$. $\endgroup$ Commented Jul 29, 2022 at 8:26
  • $\begingroup$ @PeterTaylor I don't know what the Hamming distance is but all such $f$ have the property that $\epsilon_1+\dots+\epsilon_n=f(\epsilon_1)+\dots+f(\epsilon_n)$. $\endgroup$ Commented Jul 29, 2022 at 8:47
  • $\begingroup$ The Hamming distance is the number of positions in which the tuple/word differs. (The (Hamming) weight is the Hamming distance from $0^n$, and I think that your comment is intended to say that the Hamming weight of $f(w)$ is the Hamming weight of $w$, which follows easily from the property that the map is strictly increasing). $\endgroup$ Commented Jul 29, 2022 at 8:54

1 Answer 1

1
$\begingroup$

I have found a way published in a recent preprint (https://doi.org/10.48550/arXiv.2209.02667).

Theorem: Let $n\geq 1$. Let $f=(f_1,\dots,f_n):[n]\to [n]$ be a stricly increasing map. Then there is the equality $ f_i(x_1,\dots,x_n) = \max_{(\epsilon_1,\dots,\epsilon_n)\in f_i^{-1}(1)} \min \{x_k\mid \epsilon_k=1\}$ for all $1\leq i\leq n$.

I explain the result with an example instead. Consider the map $f:[3]\to[3]$ depicted in the following picture (the top diagram is the source, the bottom diagram is the image):

Let $f=(f_1,f_2,f_3)$. For boolean values, $\min$ means "and" and $\max$ means "or". If $x_1=1$ and $x_3=1$, or $x_1=1$ and $x_2=1$ and $x_3=1$, then $f_1(x_1,x_2,x_3)=1$. Thus $f_1(x_1,x_2,x_3)=\max(\min(x_1,x_3),\min(x_1,x_2,x_3))$. If $x_1=1$ and $x_2=1$, or $x_2=1$ and $x_3=1$, or $x_1=1$ and $x_2=1$ and $x_3=1$, then $f_2(x_1,x_2,x_3)=1$. Thus $f_2(x_1,x_2,x_3)=\max(\min(x_1,x_2),\min(x_2,x_3),\min(x_1,x_2,x_3))$. Finally, if $x_1=1$ and $x_2=1$, or $x_1=1$ and $x_3=1$, or $x_2=1$ and $x_3=1$, or $x_1=1$ and $x_2=1$ and $x_3=1$, then $f_3(x_1,x_2,x_3)=1$. Thus $f_3(x_1,x_2,x_3)=\max(\min(x_1,x_2),\min(x_1,x_3),\min(x_2,x_3),\min(x_1,x_2,x_3))$.

$\endgroup$
2
  • 2
    $\begingroup$ This theorem doesn't use that $f$ is strictly increasing. It treats each component $f_i$ independently of the others, and it amounts to saying simply that $f_i$ is a weakly increasing function to $\{0,1\}$. That is, the max and min in the formula for $f_i$ just say that $f_i(\vec x)=1$ iff $\vec x\geq\vec\varepsilon$ for some $\vec\varepsilon$ with $f_i(\vec\varepsilon)=1$. $\endgroup$ Commented Sep 7, 2022 at 14:56
  • $\begingroup$ @AndreasBlass You're perfectly right. I use strictly increasing only to prove specific properties of the "topologification" of $f$. $\endgroup$ Commented Sep 7, 2022 at 15:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .