7
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ You only thought about showing that the bipartite graph satisfies Hall's condition? You didn't try to do it? $\endgroup$
    – bof
    Nov 28, 2014 at 11:22

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

The question has already been answered by bof, but let me mention that even more is true: one can write $\mathcal P([n])$ as a disjoint union of $\binom n{\lfloor n/2\rfloor}$ inclusion chains $C_i$ that are centrally symmetric in the sense that each $C_i$ consists of sets $c_{i,m}\subset c_{i,m+1}\subset\dots\subset c_{i,n-m}$, where $|c_{i,j}|=j$.

As one application, this gives for each $k$ a bijection between $k$-element and $(n-k)$-element sets with the property required in the question, namely given a set $|S|=k$, we locate the unique chain $C_i$ such that $S\in C_i$, and make $\iota(S)$ the unique element of $C_i$ of size $n-k$.

As another application, one can use this to give good bounds on the number $\psi(n)$ of upwards closed subsets of $\mathcal P([n])$, or in other words, of monotone Boolean functions in $n$ variables (the Dedekind problem). Trivially, $2^{\binom{n}{\lfloor n/2\rfloor}}\le\psi(n)$. The decomposition into chains implies $\psi(n)\le n^{\binom{n}{\lfloor n/2\rfloor}}+2$ immediately, due to [1], and by a refinement of the same idea $\psi(n)\le3^{\binom{n}{\lfloor n/2\rfloor}}$ due to [2], and $\psi(n)\le2^{\binom{n}{\lfloor n/2\rfloor}(1+O(\log n/n))}$ due to [3,4]; still more precise bounds are known.

One way to construct the chains $C_i$ is by induction on $n$. For $n=0$, we just take one chain consisting of the empty set. Assuming we already have $\mathcal P([n])=\bigcup_{i<s}C_i$, we can write $\mathcal P([n+1])$ as the disjoint union of the following chains:

  • For each $C_i=\{c_{i,m},\dots,c_{i,n-m}\}$, we include the chain $\bigl\{c_{i,m},\dots,c_{i,n-m},c_{i,n-m}\cup\{n+1\}\bigr\}$.

  • For each $C_i$ as above of length at least $2$, we include the chain $\bigl\{c_{i,m}\cup\{n+1\},\dots,c_{i,n-m-1}\cup\{n+1\}\bigr\}$.

A non-inductive explicit description of a (slightly different) partition of $\mathcal P([n])$ into chains was presented in [5]. A subset $A\subseteq[n]$ can be represented by a string $a_1\dots a_n$ of brackets, where $a_i$ is $)$ if $i\in A$, and $($ otherwise. A bracket $a_j={)}$ is paired with a bracket $a_i={(}$ if $a_i$ is the right-most left bracket preceding $a_j$ with the property that there are the same number of left and right brackets in between them. For example, $A=\{1,3,4,8,9\}\subseteq[10]$ is represented by

$$)\color{blue}{()})(\color{red}{(}\color{green}{()}\color{red}{)}(,$$

where the paired brackets are indicated by colours, and the unpaired ones are black. Note that all unpaired right brackets precede all unpaired left brackets. Then two sets $A,B\subseteq[n]$ are in the same chain iff they have the same paired brackets. For example, the chain containing the set above consists of the sets \begin{align} \mathbf(()\mathbf{((}(())\mathbf(&=\{3,8,9\},\\ \mathbf)()\mathbf{((}(())\mathbf(&=\{1,3,8,9\},\\ \mathbf)()\mathbf{)(}(())\mathbf(&=\{1,3,4,8,9\},\\ \mathbf)()\mathbf{))}(())\mathbf(&=\{1,3,4,5,8,9\},\\ \mathbf)()\mathbf{))}(())\mathbf)&=\{1,3,4,5,8,9,10\}, \end{align} where the unpaired brackets are highlighted.

References:

[1] E. N. Gilbert, Lattice theoretic properties of frontal switching functions, J. Math. Phys. 33 (1954), 57–67.

[2] G. Hansel, Sur le nombre des fonctions booléennes monotones de $n$ variables, C. R. Acad. Sci. Paris Sér. A–B 262 (1966), A1088–A1090.

[3] D. Kleitman, On Dedekind’s problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc. 21 (1969), 677–682.

[4] D. Kleitman and G. Markowsky, On Dedekind’s problem: The number of isotone Boolean functions. II, Trans. Amer. Math. Soc. 213 (1975), 373–390.

[5] C. Greene and D. Kleitman, Strong versions of Sperner’s theorem, J. Combinatorial Theory Ser. A, 20 (1976), no. 1, 80–88.

$\endgroup$
1
  • 1
    $\begingroup$ See also Curtis Greene and Daniel J. Kleitman. Strong versions of Sperner’s theorem. J. Combinatorial Theory Ser. A, 20(1):80–88, 1976. For similar decompositions of other posets, search for "symmetric chain decomposition". $\endgroup$
    – Ira Gessel
    Nov 28, 2014 at 16:13
1
$\begingroup$

The Boolean lattice has a symmetric chain decomposition, so the answer is yes. There are inductive and direct proofs of this fact. You should find both in Anderson's book, "Combinatorics of Finite Sets."

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