3
$\begingroup$

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.

2 Answers 2

3

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

  • 0
    Thank you fo$r$ the reference!2012-03-30
2

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.

  • 0
    Oh yes, you're absolutely right - trivial error on my part which was really confusing me. Thank you!2013-05-01