Mapping of subcubes of a $(d+k)$-hypercube onto subcubes of a $d$-hypercube

Question

Denote by $Q_n$ the $n$-dimensional hypercube. A vertex of $Q_n$ is represented by a vector of $n$ $\{0,1\}$-bits. An edge corresponding to two vertices whose vectors differ in one coordinate is represented by a bit vector with a $*$ in that coordinate. A $d$-dimensional subcube $D$ is represented by a bit vector with $d$ $*$’s, where the vertices of $D$ are those vectors obtained by replacing the $*$’s with any combination of bits.

Now let's introduce the natural order relation on subcubes of hypercube $Q_n$ by setting $x\leq y$ iff $x_i\leq y_i$ (where $*\leq 0$ and $*\leq 1$ and $0$, $1$ are incomparable). This poset of subcubes is identified with $\{*,0,1\}^d$ and is a face-poset of a hypercube $Q_d$.

Let me consider a map $f:S(Q_{d+k})\to S(Q_d)$ from face-poset of $Q_{d+k}$ to face-poset of $Q_d$ which is as follows:

$f$ preserves the order relation, i.e., if $x\leq y$ then $f(x)\leq f(y)$

and

if for $x\in Q_{d+k}$ holds that $f(x)\leq z$ then there exist $y\in Q_{d+k}$ such that $x\leq y$ and $f(y)=z$.

M. Winter noticed below in comments that projections, (forgetting $k$ components), are onto maps as described.

I am wondering what other kind of onto mappings exist for some $d$ and $k\neq 0$.

A later addition:

In particular, I am wondering if it is possible to map a face-poset of $Q_{3+k}$ to the face-poset of $Q_3$ by onto mapping as described above in such a way that inverse images of $3$-face are all of the dimension greater then $3$, and how big the dimension of such inverse images can be.

Is it true that the dimension of such inverse images is not bounded by any number by means of varying $k$, or the bound does exist?

Answer 1

Take any maximal face $a$ in the pre-image of $(*,*,*)$ (i.e., of the 3-dimensional face). W.l.o.g., it has the form $a=(\underbrace{*,\dots,*}_k,0,0,\dots,0)$. Denote by $a(p,q)$ the face obtained from $a$ by replacing the $p$th star with $q$ (so $1\leq p\leq k$ and $q\in\{0,1\}$).

We say that a bit is determined if it is not a star. Notice that each $f(a(p,q))$ has a determined bit.

1. Assume that $f(a(p,0))$ and $f(a(p,1))$ have some determined bits in different positions, say $f(a(p,0))$ has the first bit $0$, and $f(a(p,1))$ has the second bit $0$ (wlog $p=1$). Then there is no $y\geq a$ such that $f(y)=(1,1,*)$. Indeed, if $y$ has a determined first bit, then $f(y)$ has $0$ in the corresponding bit. Otherwise, if $y$ has a star in the first bit, then replace it by $0$ to get $y_0$. We have $f(y_0)=(0,\dots)$, so we cannot have $f(y)=(1,\dots)$.

Thus, each of $f(a(p,0))$ and $f(a(p,1))$ has a unique determined bit, and those bits are at the same position $s(p)\in\{1,2,3\}$.

2. Assume that $f(a(p,0))$ and $f(a(p,1))$ coincide, say $f(a(1,0))=f(a(1,1))=(0,*,*)$. Then there is no $y\geq a$ with $f(y)=(1,*,*)$. The reasoning is similar: if the first bit of $y$ is determined, then that of $f(y)$ is $0$; otherwise, replace the first bit in $y$ by $0$.

Thus, $f(a(p,0))$ and $f(a(p,1))$ differ in exactly $s(p)$th bit, the others being stars.

3. Assume that the function $s$ is not injective, say $s(1)=s(2)=1$. We may assume that $f(a(1,0))=(0,*,*)$ and $f(a(2,1))=(1,*,*)$. Then there is no image for $(0,1,\underbrace{*,\dots,*}_{k-2},0,\dots,0)$.

Thus $s$ is injective, which yields $k\leq 3$.

The same reasoning works when 3 is replaced with any other number.

Answer 2

I think the order structure you describe is identical to the face lattice of the $d$-cube. You then ask about an order preserving and surjective map between two such lattices, but not in a standard way, that is, e.g. not like an order embedding. It looks more like you try to find the face lattice of $Q_d$ as a "sub-lattice" in $Q_{d+k}$, but in kind of a graph minor sense.

The set $S(Q_d)$ can also be identified with $\{*,0,1\}^d$, i.e., the set of sequences of length $d$ with these three symbols. One way to map $S(Q_{d+k})\to S(Q_d)$ surjectively and order-preservingly is by restriction, that is, e.g. by deleting the $k$ first entries of the sequence. This corresponds to the geometric operation of projection, as we project the $(d+k)$-cube onto one of its $d$-dimensional faces (which is a $d$-cube).

There are other such maps, though. Look at the following picture, which is meant to partially visualize a map $S(Q_3)\to S(Q_2)$.

This map can be completed to a projection onto some face of $Q_3$ (the face is not uniquely determined). But there are other ways to complete this map, which does not correspond to such a projection:

• The red vertices of $Q_3$ are mapped to the red vertices of $Q_2$.
• The blue edges of $Q_3$ are mapped to the blue edges of $Q_2$.
• The green faces of $Q_3$, their edges, and their non-red vertices are mapped to the green edges of $Q_2$.
• All other subcubes of $Q_3$ ($Q_3$ itself, the non-green faces and the the non-blue edges) are mapped to $Q_2$ itself.

This is not a projection onto a face, since in such a projection from $Q_3$ to $Q_2$ only two faced would be mapped to all of $Q_2$. But you can view this as a diagonal projection as visualized in the following picture.

Similar diagonal projections are certainly possible when going from $Q_{d+1}$ to $Q_d$. And composing serveral such maps then gives you non-standard projections from $Q_{d+k}$ to $Q_d$.