14
$\begingroup$

As part of my answer to another question, I needed the following fact: if $S = \{1, \ldots, n\}$ and $k \leq n/2$, then there is a bijection $f : {S \choose k} \to {S \choose k}$ such that $t \cap f(t) = \emptyset$ for all $t \in {S \choose k}$. Here $n$ and $k$ are positive integers, and ${S \choose k}$ denotes the family of all size-$k$ subsets of $S$.

Here's the proof I found for that fact. Let $p = \left\lvert{S \choose k}\right\rvert = {n \choose k}$, and write ${S \choose k} = \{t_1, \ldots, t_p\}$. Construct a bipartite graph $G$ on partite sets $A = \{a_1, \ldots, a_p\}$ and $B = \{b_1, \ldots, b_p\}$ by drawing an edge $a_ib_j$ whenever $t_i \cap t_j = \emptyset$. Observe that $G$ is an ${n-k \choose k}$-regular bipartite graph, where ${n-k \choose k} > 0$, and therefore has a perfect matching $M$, by Hall's Theorem. Now for each $i \in \{1, \ldots, p\}$ we have $a_ib_j \in M$ for exactly one value of $j$, and we get the desired bijection just by taking $f(t_i) = t_j$ for the corresponding value of $j$.

Unfortunately, the proof above doesn't give an explicit construction of the bijection $f$, which makes it hard to naturally use this bijection in a combinatorial proof. When $n = 2k$, the function $f(t) = S-t$ is an easy example of a bijection with this property. Is there a nice explicit construction of such a bijection for general $k$?


Some partial thoughts: it's tempting to try to build on the $n=2k$ case by modifying the function $f(t) = S-t$, say by taking the function $f$ to be "take the $k$ least elements of $S-t$", but it seems that the natural approaches to modifying that function end up failing to be injective (hence also fail to be surjective). For example, the "$k$ least elements of $S-t$" function fails at $n=5$ and $k=2$ because it yields $f(\{3,4\}) = f(\{3,5\}) = \{1,2\}$.

When $k=1$ this is just asking for a derangement of $\{1, \ldots, n\}$, and a function like $f(\{i\}) = \{i+1 \mod n\}$ works, where $x \mod n$ is the residue of $x$ modulo $n$. When $k=2$ and $n \geq 4$, I believe the following function works, where $\{x,y\} + i \mod n$ is shorthand for $\{x+i \mod n, y+i \mod n\}$:

$f(\{i, j\}) = \begin{cases} \{i, j\} + 2 \mod n, & \text{if $i-j \equiv \pm 1 \pmod{n}$} \\ \{i, j\} + 1 \mod n, & \text{otherwise.}\end{cases}$

This suggests that in a general construction, maybe we can just assign an integer $r_t$ for each $t \in {S \choose k}$ and use a map of the form $t \mapsto t+r_t \bmod{n}$, with the values of $r_t$ chosen cleverly to ensure bijectivity and disjointness. However, this approach is doomed to fail when $t$ is a difference set for $\mathbb{Z}_n$. To use an example of such a set due to Jungnickel, Pott, and Smith, when $n = 11$ and $t = \{1,3,4,5,9\}$, it is easy to check that $t + r_t \mod 11$ intersects $t$ regardless of the choice of $r_t$. So this approach cannot work in general either.


Relevant external literature I've found so far:

  • The $n = 2k+1$ case appears to have been solved by Kierstead and Trotter (1988), in a superficially-different but equivalent formulation.
  • Kai Jin (2019) refers to the problem of finding an explicit $1$-factorization of the related "bipartite Kneser graphs" (equivalent to the graph $G$ described in the proof above) as a "challenging open problem", but we are only looking for an explicit description of one matching in a bipartite Kneser graph, not an entire $1$-factorization.
$\endgroup$
  • $\begingroup$ ... such that $t \cap f(t) = \emptyset$ for all $t \in S$. Do you mean to write "for all $t \in \binom{S}{k}$"? (Since that is the domain of $f$.) $\endgroup$ – Kevin Jul 18 at 2:59
  • $\begingroup$ @Kevin yes, that's what I meant, thank you. I've fixed it now. $\endgroup$ – Gregory J. Puleo Jul 18 at 3:12
  • 1
    $\begingroup$ Nice question! If $n$ were prime, I'd be tempted to send $t$ to the $k$ roots of $\prod_{a \in t} (x-a)+1$, but unfortunately $\mathbb{F}_p$ is not algebraically closed. $\endgroup$ – mathworker21 Jul 20 at 7:58
4
+50
$\begingroup$

Yes, there is! In fact, here's $(n-1)!$ of them!

I wish to thank user Phylliida for both the algorithm and the python psudocode below. The proof is my own (though I've found it hard to write in some standard notation...).

The idea is based on the $k=1$ case. For a set $A = \{a_1, \cdots, a_k \}$ we increase $a_1$ (modulo n) until it's no longer in $A,$ and put that element in $f(A).$ Now we take $a_2$ and increment it until it is no longer in $A$ or an element we've already put in $f(A),$ and declare that to be in $f(A).$ We carry on like this for all the $a_i,$ so that our output has the correct size.

For example, with the set $\{1,3,4,5,9\}$ mod $11,$ we would first increment $1$ up to $2$ and put this into our output, then we move $3$ to $6,$ passing over $4$ and $5$ because they are in the input set. We similarly move $4,5$ and $9$ to $7,8$ and $10$ respectively. Our output is thus $\{2,6,7,8, 10\}.$

It is clear that this will always give us a disjoint set from the input of the right size. However, it is not at all clear that this is well defined (does the order of the $a_i$ matter?) or that it is invertible. It turns out this algorithm is essentially its own inverse, so that if we phrase it with a bit of generality it will suffice to show it's well defined.


So, with more generality now. Fix an $n$-cycle $\pi,$ and a set $A$ as above. Define the multiset $A_1 = A \cup \pi A$ of size $2k.$ We then construct $A_2$ by applying $\pi$ to all but one of each duplicate element in $A_1.$ In general we have $$A_{i+1} = set(A_i) \cup \pi (A_i - set(A_i)) $$

where $set(U)$ denotes the set of elements in a multiset $U,$ multiset difference removes instances (ie, $(1,2,2) - (1,2) = (2)$), and the union is treated as a union of multisets. Note that $A_{i+1} = A_i$ when $A_i$ is a set, that we always have exactly $2k$ elements in $A_{i+1},$ and finally that after $k$ steps we must have an actual set instead of a multiset. So we define $$f_\pi(A) = A_k - A.$$

This is equivalent to the algorithm outlined above when $\pi = (1, \cdots, n).$ We're just incrementing each element (mod n) until they find an unused place. If two elements find the same place, then we leave one of them in the gap and continue incrementing the other.

Now, I claim the inverse to $f_{\pi}$ is $f_{\pi^{-1}}.$ This follows almost immediately if we return to our original presentation of the algorithm: Suppose $a_k$ is incremented to $\pi^j a_k.$ Then we must have $\pi^1 a_k, \pi^2 a_k, \cdots, \pi^{j-1} a_k \in f_\pi(A),$ which implies that $f_{\pi^{-1}}$ will return $\pi^j a_k$ to the first open spot, namely $a_k.$ After performing this move, we're in exactly the same state as $f_\pi$ would be before moving $a_k.$ $f_{\pi^{-1}}$ continues exactly undoing $f_\pi$ if we next consider wherever $a_{i}$ ended up in descending order.

As an example of the inverse direction, if we start with ${2, 6, 7, 8, 10}$ then we would first decrement $10$ to the first open place ($9$), then $8$ would be decreased past $7$ and $6$ down to $5.$ Similarly $6,7$ are moved to $3,4.$ Finally $2$ gets decreased down to $1.$ Note we've moved each number back to where it came from in the original setup.


I conclude with some python code for the bijection.

def rot(bits,inv):
 res = [x for x in bits]
 original = [x for x in bits]
 n = len(bits)
 for i in range(n)[::inv]:
  if original[i] == 1:
   for j in range(1,n+1)[::inv]:
    new = (i + j) % n
    if res[new] == 0 and original[new] == 0:
     res[new] = 1
     res[i] = 0
     break
 return res

res should be an array with a $1$ in the ith place if $i \in A.$ inv should be set to 1 to do the forward direction, -1 to invert. For example

rot([1,0,1,1,1,0,0,0,1,0,0], 1) = [0,1,0,0,0,1,1,1,0,1,0]
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note we're using that $k \leq n/2$ when we assert that this terminates. $\endgroup$ – Artimis Fowl Jul 20 at 18:16
  • $\begingroup$ I'm going to wait a few days longer before awarding the checkmark or the bounty in order to give any other answerers a fair chance, but thank you for this -- it is an elegant solution. $\endgroup$ – Gregory J. Puleo Jul 20 at 18:20
  • 2
    $\begingroup$ wow, nice. really surprised this works $\endgroup$ – mathworker21 Jul 20 at 20:35
  • $\begingroup$ @ArtimisFowl "its well defined" --> "it's well defined" $\endgroup$ – mathworker21 Jul 20 at 21:33
  • $\begingroup$ Grammar slowly improving $\endgroup$ – Artimis Fowl Jul 20 at 22:45
1
$\begingroup$

On thinking about this some more, I think at least one construction can be obtained by adapting a construction of Greene and Kleitman giving a symmetric chain decomposition of the poset $2^S$, where $S = \{1, \ldots, n\}$. I'll give a description of the construction here, but I'd still be interested in whether there's a simpler construction I'm missing.

Given a set $t \in 2^S$, or, in particular, $t \in {S \choose k}$, we associate $t$ with an $n$-character string, where the $i$th character is a left-parenthesis if $i \notin t$ or a right-parenthesis if $i \in t$. For example, if $n=5$, we would associate the set $\{3,5\}$ with the string $\texttt{(()()}$. When $t \in {S \choose k}$, the resulting string clearly has exactly $k$ right-parentheses.

Now, some of these parentheses can be "paired up" following the usual rules, and some cannot. For example, in the string for $\{3,5\}$, the leftmost parenthesis cannot be paired with anything, but the remaining $4$ characters form two sets of matched parentheses: $\texttt{(} \color{red}{\texttt{()}} \color{blue}{\texttt{()}}$. Similarly, the string for $\{3,4\}$ can be matched as $\color{red}{\texttt{(}}\color{blue}{\texttt{()}}\color{red}{\texttt{)}}\texttt{(}$.

Now, the Greene--Kleitman construction gives a way to produce a chain of sets in $2^S$ -- that is, a nested family $t_1 \subset t_2 \subset \cdots \subset t_k$ -- that contains the given set, such that $|t_1| + |t_k| = n$. We produce $t_1$ just by taking all unmatched right-parentheses and flipping them to left-parentheses and, given $t_i$, we produce $t_{i+1}$ by flipping the leftmost unmatched left-parenthesis to a right-parenthesis. To use the example given by Greene--Kleitman, if $A = \{1,3,4,8,9\}$ in the set $S = \{1, \ldots, 10\}$, then the corresponding string is $\texttt{)}\color{red}{\texttt{()}}\texttt{)(}\color{blue}{\texttt{(}}\color{orange}{\texttt{()}}\color{blue}{\texttt{)}}\texttt{(}$, so the chain starts at the set corresponding to $\texttt{(}\color{red}{\texttt{()}}\texttt{((}\color{blue}{\texttt{(}}\color{orange}{\texttt{()}}\color{blue}{\texttt{)}}\texttt{(}$, namely $\{3,8,9\}$, and then, flipping one unmatched parenthesis after another, proceeds along to $\{1,3,8,9\}$, $\{1,3,4,8,9\}$, $\{1,3,4,5,8,9\}$, ending at $\{1,3,4,5,8,9,10\}$ corresponding to the string$\texttt{)}\color{red}{\texttt{()}}\texttt{))}\color{blue}{\texttt{(}}\color{orange}{\texttt{()}}\color{blue}{\texttt{)}}\texttt{)}$.

What does this have to do with the stated problem? Given that $t$ is in the chain and $t$ has size $k$, there is also a size-$(n-k)$ set $t'$ in the same chain, with $t \subset t'$. This means that $S - t'$ is a size-$k$ set disjoint from $t$. Furthermore, $t$ is the only size-$k$ set in the chain and $t'$ the only size-$(n-k)$ set, so there's no danger that two distinct sets $t_1, t_2$ can have the same $t'$.

So we can build the desired bijection by starting from the parenthesis-representation of $t$, flipping parentheses until there are exactly $n-k$ right-parentheses, and then taking $f(t)$ to be the set of indices of the left-parentheses in the resulting string (taking left-parentheses instead of right-parentheses models taking the complement of the set $t'$). This is a pretty explicit construction, but a part of me wonders if it is overkill for the somewhat smaller task we've set for ourselves.


I believe it can be shown that, as Artimis Fowl and I speculated in the comments, this construction is equivalent to Artimis Fowl and Phylliida's (henceforth AFP) elegant construction applied to the permutation $\sigma^{-1}$, where $\sigma = (1, \cdots, n)$. That is, it's equivalent to defining $f(t)$ by processing each $a_i \in t$ one at a time, decrementing $a_i$ modulo $n$ until it reaches a value that is not equal to any other $a_j$ or any value previously declared to be in $f(t)$, and declaring that value to be in $f(t)$.

Here's a rough sketch of a proof of that. Let's take it as given that the result of AFP's operation does not depend on the order in which the $a_i$ are processed. Now, given a set $t$, we form its parenthesis-representation. We will apply AFP's function $f$ to $t$ and show that it produces the same result as the Greene--Kleitman construction.

To compute $f(t)$, we start by processing the values $a_i \in t$ that correspond to paired right-parentheses, always choosing an innermost paired parenthesis among the unprocessed ones to process next. By always choosing an innermost parenthesis, we can see that on applying $f$, each paired right-parenthesis will be left-shifted until it reaches the matching left-parenthesis. (Skipping over already-occupied slots means we would skip over the already-matched left-parentheses for any pairs contained within the parentheses being processed.)

Next, consider the unpaired right-parentheses in $t$. All such parentheses must occur to the left of all unpaired right-parentheses in the representation. Thus, on applying $f$, each unpaired right-parenthesis will be shifted left until it "wraps around" to the end of the string, and sent to the position of a rightmost not-yet-occupied unmatched left-parenthesis.

So, in summary, applying $f$ sends each matched right-parenthesis to its matching left-parenthesis, and sends each unmatched right-parenthesis to an unmatched left-parenthesis as close to the end of the string as possible. So $f(t)$ consists of the indices of the matched left parentheses for $t$, as well as a a "rightward-closed" set of unmatched left-parentheses. (That is, if the set has an unmatched left-parenthesis at position $i$, then all unmatched left-parentheses at positions $j > i$ must also be in the set.) This means that the complement of $f(t)$ is a set consisting of all the matched right-parentheses for $t$ as well as a "leftward-closed" set of unmatched right-parentheses.

This means that the complement of $f(t)$ is in the same Greene--Kleitman chain as $t$, so that $f(t) = t'$ where $t \subset t'$ and $|t'| = n-k$. That is, $f(t)$ as defined by AFP, using the permutation $\sigma^{-1}$, is the same function as $f(t)$ as defined in this answer using Greene--Kleitman.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ With this construction, does $\{3,8,9\}$ map to $\{2,6,7 \}$? Also, the middle example confuses me, what with a disappearing $8$ and the addition of a $10$ to an example with $S = [9].$ $\endgroup$ – Artimis Fowl Jul 20 at 18:20
  • $\begingroup$ @ArtimisFowl sorry, those were typos, now fixed. I'll work out in a moment how exactly $\{3,8,9\}$ gets handled. $\endgroup$ – Gregory J. Puleo Jul 20 at 18:22
  • $\begingroup$ $t = \{3,8,9\}$ gives $t' = \{1,3,4,5,8,9,10\}$, so $f(t) = S - t' = \{2,6,7\}$, yes. $\endgroup$ – Gregory J. Puleo Jul 20 at 18:23
  • $\begingroup$ Thanks for fixing. I'm curious then if this is always $f_{\sigma^{-1}}$ with $\sigma = (1,\cdots n),$ (definition in other answer) or if we've got a happy coincidence. $\endgroup$ – Artimis Fowl Jul 20 at 18:25
  • 1
    $\begingroup$ Excellent! I think I follow the proof. $\endgroup$ – Artimis Fowl Jul 22 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.