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
    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](http://www-math.univ-poitiers.fr/~maavl/) lists 6 early references in the footnote on its page 1.2012-03-30
  • 0
    Thank you for 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
    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.2012-03-29
  • 0
    @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.2012-03-29
  • 0
    @Patrick: I have tried to complete the proof.2012-03-29
  • 0
    I thought about that too but couldn't find an easy proof to show that $F$ is onto the $k$-sets of $n$. Of course I believe it's true :)2012-03-30
  • 0
    @Patrick: Just showing $F(X) \neq F(Y)$ for $X \neq Y$ is enough, isn't it?2012-03-30
  • 0
    @Patrick: Yes, it is enough to prove that $F(X)$ is bijection from $k$-sets to $k$-sets. The fact that the domain and co-domain is the same (finite) size, and it is an injection, proves that it is onto and so a bijection. Or more simply, if $F(X)$ misses some set, there must be some $X,Y$ such that $F(X) = F(Y)$ by the pigeonhole principle.2012-03-30
  • 0
    @Patrick: See this: http://math.stackexchange.com/questions/63072/surjectivity-implies-injectivity2012-03-30
  • 0
    Thanks, Aryabhata, that seems to be the answer. As I understand it, the inverse to the map is to start with x[k] and go around the circle counterclockwise.2012-03-30
  • 0
    @WilliamScott: I haven't really thought about it, you might be right.2012-03-30
  • 1
    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$.2013-03-04
  • 0
    @BrianM.Scott: You are right! Thanks for pointing that out. Back to the board...2013-03-05
  • 0
    In the bipartite graph version, why is the graph a ${n-k \choose n-2k}$ regular one?2013-04-30
  • 0
    @wemblem: For each $k$-set, you need to count the number of $n-k$ sets which are supersets of it, i.e, you need to select $n-2k$ elements from $n-k$ elements to extend the $k$-set.2013-04-30
  • 0
    I am working on a similar problem, where the bijection needs to be shown to exist between $k$ sets and $k-1$ sets. So if I understand correctly, the graph will just be $k$-regular in this case?2013-04-30
  • 1
    @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$.2013-05-01
  • 0
    Oh yes, you're absolutely right - trivial error on my part which was really confusing me. Thank you!2013-05-01