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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .