Matching in the Boolean Algebra

Question

We consider the Boolean Algebra of the set $[n]=\{1,\dots,n\}$ and the matching $\psi$ from the $m+1$ subsets of $[n]$ into the $m$ subsets of $[n]$ for $(n+1)/2\leq m+1\leq n$, which is used to show that the Boolean Algebra admits the Sperner property.

This matching can be given in several terms (see Aigner: "Lexicographic Matching in Boolean Algebras", Stanton/White "Constructive Combinatorics" and Anderson "Combinatorics of Finite Sets" and many more), here I will repeat the explicit map by Aigner:

If $B=\{i_{1},\dots,i_{m+1}\}$ is our $m+1$ subset of $[n]$ we look at the set $$N(B)=\{j\in\{0,1,\dots,m+1\} \mid i_{j}-2j=\min\},\quad i_{0}:=0$$ (all indices for which $i_j -2j$ is minimized) and then take its minimum: $$n(B)=\min N(B).$$ Then $B$ is mapped to the $m$-set without $i_{n(B)}$: $$\psi(B)=\{i_1,\dots,i_{n(B)-1},i_{n(B)+1},\dots,i_{m+1}\}$$

The recursive algorithm to compute $\psi$ is to write down the upper half of the Boolean Algebra and map an $m+1$ set to the lexicographic smallest $m$ subset that is still available.

The Problem: Let us fix an $m$ set $M$ and restrict $\psi$ to all subsets of $M$ and denote this by $\psi|_{M}$. I am now looking for a description of all subsets of $M$ which are not in the image of $\psi|_{M}$. So either they do not lie in the image of $\psi$ at all or the element that is dropped by $\psi$ is not an element of $M$.

In more detail the $n$ is odd and we fix $k=\lfloor\frac{n}{2}\rfloor$. Now $M$ is a $(k+i)$ set for which $i$ is even and the set I am interested in is $$\mathcal{R}(M)=\{M'\subsetneq M\mid M' \notin\mathrm{Im}(\psi|_{M}),|M'|=k+j, j \text{ even}\}.$$

Example: Let $n=7$, so $k=3$ and $M=\{1,2,3,5,6\}$. Then: $$\mathcal{R}(M)=\{123,136,236,256,356\},$$ since all $4$-subsets of $M$ are $\{1235,1236,1256,1356,2356\}$ and they are mapped to $\{125,126,156,135,235\}$ by $\psi$.

Question: Is there an explicit formula or description to compute all elements in $\mathcal{R}(M)$ for given $M$?

Thanks in advance!

Richard

Answer 1

One can understand the image of $\psi$ or $\psi|_M$ in terms of the inverse map $\phi$.

$\phi$ maps an $m$ set to an $(m+1)$ set (if possible) in the following way. If $$A=\{i_1,\dots,i_m\}$$ is our $m$-set, we again look at the set of indices for which $i_j -2j$ is minimized $$N(A)=\{j\in\{0,1,\dots,m\}\mid i_j -2j=\min\},\quad i_0:=0$$ but this time we take the maximum of all indices and add 1 on the value to get our $(m+1)$-set:$$m(A)=\max N(A)\\ \phi(A)=\{i_1,\dots,i_{m(A)},i_{m(A)}+1,i_{m(A)+1},\dots,i_{m}\}.$$ So $\phi$ is defined iff $i_{m(A)}\neq n$. Moreover: $$\mathrm{Im}(\psi)=\mathrm{Def}(\phi)$$

So now it is easy to generalize this for $\psi|_M$: A subset $M'=\{i_1,\dots,i_l\}$ of $M$ is not in the image of $\psi|_M$ iff $i_{m(M')}+1\notin M$.