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)$


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?

  • $\begingroup$ Do I get this right? A $d$-dimensional subcube is basically an element of $\{*,0,1\}^d$? And we also have $*< 0< 1$? $\endgroup$ – M. Winter Aug 10 '19 at 21:27
  • 1
    $\begingroup$ Doesn't the restriction map (just forgetting $k$ components of the vector) does the trick? $\endgroup$ – M. Winter Aug 10 '19 at 22:08
  • $\begingroup$ @M.Winter Partially you are right we have basically an elements of $\{*,0,1\}^n$ but we have no $*\leq 0\leq 1$, but only $*\leq 0$ and $*\leq 1$ and $0$ and $1$ are incomparable. I do not see the restriction does the trick. Please clarify. $\endgroup$ – Evgeny Kuznetsov Aug 11 '19 at 1:30
  • $\begingroup$ @M.Winter Oh, I see; the projection is clearly monotone and the additional condition do also hold. Thank you for suggestion. If you form it as an answer I will accept it. $\endgroup$ – Evgeny Kuznetsov Aug 11 '19 at 8:46
  • $\begingroup$ It is also interesting whether other kind of mappings with this properties exist but projections. $\endgroup$ – Evgeny Kuznetsov Aug 11 '19 at 9:03

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.

  • $\begingroup$ Thank you for the answer and sorry, I somehow missed it. I read it now and, I can not see yet why should $f(z)$ have $0$ on first bit, in case $z$ has first bit determined. $\endgroup$ – Evgeny Kuznetsov Apr 25 '20 at 17:35
  • $\begingroup$ If you speak on part 1; I somehow forgot to mention that wlog $p=1$. Is it clearer now? (will change the answer right now) $\endgroup$ – Ilya Bogdanov Apr 29 '20 at 21:51
  • $\begingroup$ Oh, I misread the "corresponding bit". I understood it as "first bit", I don't know why. Now I see what happens there completely. Sorry it was already clear that we can set $p=1$ without lose of generality. $\endgroup$ – Evgeny Kuznetsov May 5 '20 at 23:28

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$.

  • $\begingroup$ Sorry @M.Winter I missed one condition in the question, and added it just now, that is $x\leq y$ in the following: 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$. It implies, in particular, that vertices should be sent to vertices. Is it possible to modify the example you gave in the last part of your answer for dimension 3 and for arbitrary $d$? I myself was constructing one of that kind meanwhile and while comparing to yours noticed the missing of the condition in the question. $\endgroup$ – Evgeny Kuznetsov Aug 24 '19 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.