For $k<n/2$ construct a bijection $f$ from $k$-subsets of $[n]$ to $(n-k)$-subsets s.t. $x\subseteq f(x)$

For $k$ less than $n/2$, construct a bijection from the $k$-subsets of $n$ to the $(n-k)$-subsets, such that $x$ is a subset of $f(x)$.

This is a problem from a 2004 Google problem set, and answers have been posted, but could not find a good answer for this one.

-

Here is a simple bijection. Make a string of $n$ parentheses by taking at position $i$ an opening parenthesis if $i$ is absent from the original $k$ subset, and a closing parenthesis if $i$ is present. Now certain parentheses in the string will properly match another one, while others don't. Let $S$ be the set of indices of unmatched parentheses. Focussing on the subword extracted at the positions of $S$, any opening parentheses in the subword comes after any closing parenthesis of the subword, since otherwise there would be at least one pair of matching parentheses in the subword, contrary to its construction. Also there are $(n-k)-k=n-2k>0$ more opening parentheses in the subword than closing parentheses, since the matching pairs that were excluded don't affect this balance.

Now the bijection consists of adding to the $k$ subset the first $n-2k$ elements of $S$ which have an opening parenthesis (meaning they are not yet in the $k$ subset). This turns these parentheses into closing parentheses. The key to the fact that this is a bijection is that this change does not change the unmatched status of the modified parentheses. Therefore the exact same construction on the $n-k$ subset produced will produce the same set $S$ of indices of unmatched parentheses, and now changing the last $n-2k$ closing parentheses at indices of $S$ will reconstruct the original situation (and the same reversal also applies if one starts out with a $n-k$ subset, makes a $k$ subset and then a $n-k$ subset again, showing one really has two mutually inverse procedures).

-
+1: Interesting construction. – Aryabhata Mar 30 '12 at 8:41
I should add (as did the referee when he advised to reject my paper on a related matter) that this is "already folklore in combinatorics, based on the so-called Catalan factorization introduced by Chottin and Cori (1982) and extensively used ever since". But the basic idea in fact goes much futher back. My paper on the Littlewood-Richardson rule lists 6 early references in the footnote on its page 1. – Marc van Leeuwen Mar 30 '12 at 9:34
Thank you for the reference! – Aryabhata Mar 30 '12 at 15:20

I believe an explicit construction can be given as follows:

Note that all we need to do is find a bijection $\displaystyle F$ from $\displaystyle k$-sets to $\displaystyle k$-sets such that $\displaystyle F(X) \cap X = \emptyset$.

Given such an $\displaystyle F$, we can construct the required bijection $\displaystyle f$ by taking $\displaystyle f(X) = [n] - F(X)$, where $\displaystyle [n] = \{1,2,\dots, n\}$ and we are constructing subsets of $\displaystyle [n]$.

Now to construct the bijection $\displaystyle F$. Write $\displaystyle 1,2,\dots n$ along a circle.

Now given a set $\displaystyle X = \{x_1, x_2, \dots, x_k\}$ where $\displaystyle x_1 \lt x_2 \lt \dots x_k$.

Start at $\displaystyle x_1$ and go along the circle clockwise, picking the first element not in the set $\displaystyle X$ (kind of like consistent hashing, if you are a programmer). Then go to $\displaystyle x_2$ and go along clockwise to pick the the first element not picked so far (and not in $\displaystyle X$) and so on.

These $\displaystyle k$ elements you picked form $\displaystyle F(X)$. It is easy to see that $\displaystyle X \cap F(x) = \emptyset$.

We can also show that $\displaystyle F(X) \neq F(Y)$ if $X \neq Y$.

If $\displaystyle X = \{x_1, x_2, \dots, x_k\}$ and $x_1 \lt x_2 \dots$ and

if $\displaystyle Y = \{y_1, y_2, \dots, y_k\}$ and $y_1 \lt y_2 \dots$

Then suppose $j \gt 1$ is the smallest such that $\displaystyle x_j \neq y_j$ and assume $\displaystyle y_j \lt x_j$.

Now the above algorithm will either have picked $\displaystyle y_j$ to be in $\displaystyle F(X)$ or it would pick different numbers (for $\displaystyle F(X)$ and $\displaystyle F(Y)$) in the $\displaystyle j^{th}$ round.

If there is no such $\displaystyle j \gt 1$, then the sets only differ in the smallest element, and in which case, the resulting $\displaystyle F$ sets would be different too.

If we weren't worried about the exact construction, we can also give an existence proof.

The existence of a bijection can be shown by the following theorem:

Theorem: Every $\displaystyle k$-regular bipartite graph has a perfect matching.

This can be proven by induction on $\displaystyle k$ and using Hall's theorem.

You construct a bipartite graph with $\displaystyle k$-sets as the left partition and $\displaystyle n-k$-sets as the right partition.

Vertex $\displaystyle L_i$ is connected to $\displaystyle R_j$ iff $\displaystyle L_i \subset R_j$.

This is a $\displaystyle \binom{n-k}{n-2k}$ regular bipartite graph.

-
I was thinking about that technique too but found a counterexample to show the mapping is not 1-1. Suppose $n=20$ and $x=\{0,1,15,16,17\}$ and $y = \{1,15,16,17,18\}$. Both $x$ and $y$ map to $\{2,3,4,5,6\}$. There are ways to make this basic idea work but I haven't found any with simple proofs yet, and I think that's what the OP was after. – Patrick Mar 29 '12 at 23:40
@Patrick: I have been editing my answer which wasn't clear earlier. Once you pick one element, you jump to the next element of the set and go around the circle again. It seems like it works now.. though my proof might be incorrect. – Aryabhata Mar 29 '12 at 23:46
@Patrick: I have tried to complete the proof. – Aryabhata Mar 29 '12 at 23:52
I don’t think that the proof that $F(X)\ne F(Y)$ works. Let $n=7$, $k=3$, $X=\{1,4,6\}$, and $Y=\{1,3,4\}$. Then $j=2$, but at stage two the algorithm picks $5$ for both $X$ and $Y$. For $X$ it picks (in sequence) $2,5$, and $7$; for $Y$, $2,5$, and $6$. – Brian M. Scott Mar 4 '13 at 9:58
@wemblem: If there are $n$ elements, and you need a graph connecting $k-1$ set to its superset $k$ set, then the degree will be $n-k+1$, not $k$. – Aryabhata May 1 '13 at 0:01