Skip to main content
3 of 3
added 18 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

I assume what is meant is whether it is always possible to choose a size $|\mathcal R|$ subcollection $\mathcal U$ of $\mathcal T$ and elements $e_U \notin U$ for each $U \in \mathcal U$ such that $\{(U \setminus \{t\}) \cup \{e_U\} \mid U \in \mathcal U\}$ is equal to $\mathcal R$. I claim that the answer is yes, provided that $k \geq n-k$. Note that $k \geq n-k$ is necessary since $|\mathcal T|=\binom{n-1}{k-1}$ and $|\mathcal R|=\binom{n-1}{k}$, so we require $\binom{n-1}{k-1} \geq \binom{n-1}{k}$.

Here is the proof. Let $G$ be the bipartite graph where the sets in $\mathcal R$ are the vertices on the left and the sets in $\mathcal T$ are the vertices on the right. Make $R \in \mathcal R$ adjacent to $T \in \mathcal T$ if and only if $T \setminus \{t\} \subseteq R$. Note that every vertex on the left has degree $k$ and every vertex on the right has degree $n-k$. Since $k \geq n-k$, by Hall's theorem, there is a matching in $G$ covering all the vertices on the left. This matching gives the required subcollection $\mathcal U$ of $\mathcal T$ and the elements $e_U$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187