3
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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