2
$\begingroup$

Consider the binary sequence $\{0,1\}^N$ where $N$ is an even integer (for simplicity). Let $M_k := \{\beta\in \{0,1\}^N \rvert \sum_{j=1}^N \beta_j = k\}$ (i.e., $M_k$ is the set that contains all binary sequences with length $N$ and with exactly $k$ 1's). The question is: for general $k \le N/2$, is it always possible to construct a bijective map $\phi: M_k\rightarrow M_{N-k}$ such that $\phi(\beta)_j \ge \beta_j$? (Here, $\phi(\beta)_j$ is the $j^{th}$ coordinate of the binary sequence $\phi(\beta)$.)

Obviously, both sets $M_k$ and $M_{N-k}$ have the same number of elements. When $k = 1$, the construction of $\phi$ is simple. However, for general $k$ and $N$, I am not sure how to systematically construct such a function $\phi$. Any hint or reference would also help a lot. Thank you.

$\endgroup$
2
$\begingroup$

The answer is "yes, this is always possible." The bijection on ranks $k$ and $N-k$ induced from a symmetric chain decomposition of the Boolean lattice gives you what you're asking for. For basics on this topic, see these slides.

$\endgroup$
  • $\begingroup$ Thank you very much, Sam. This looks like exactly what I need. $\endgroup$ – user483904 Jan 31 at 18:45

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.