Let $n$ be a positive integer. A subset of $[n] := \{1,2,...,n\}$ having $k$ elements will be called a $k$-subset.


For $n,k \in \mathbb{N}$ with $k \leq \lfloor n/2 \rfloor$, it is clear that one can associate bijectively $(n-k)$-subsets with $k$-subsets through complements: $S \mapsto \bar{S}$. However, the image is never a subset of the element being mapped (far from it). I would like a bijection $\iota$ between (n-k)-subsets and k-subsets such that $\iota(S) \supseteq S$, for every $S$ (n-k)-subset.


I tried imposing a total order on $[n]$ and playing with lexicographic ordering of the characteristic vectors, but it didn't work. I also thought about showing that the obvious bipartite graph satisfies Hall's condition. Does anyone have either an explicit bijection or a proof that Hall's condition is fulfilled? Actually, I would also be interested in a proof that such bijection does not exist, but I don't believe this to be true.



Inclusion-preserving bijection between subsets of cardinality k and n-k
Each $(n-k)$-subset contains $m$ $\,k$-subsets, and each $k$-subset is contained in $m$ $\,(n-k)$-subsets, where $m=\binom{n-k}k$. An $m$-regular bipartite graph can be decomposed into $m$ perfect matchings.


