2
$\begingroup$

I am trying to prove or disprove the following Lemma:

Let $S=[n]$ and $\mathcal{T}$ be the set of all $k$-subsets of $S$ that contain $t \in [n]$. Furthermore, let $\mathcal{R}$ be the set of all $k$-subsets of $S$ that do no contain $t$.

Is it possible to choose $|\mathcal{R}|$ elements from $\mathcal{T}$ denoted as $T_1, \dots, T_{|\mathcal{R}|}$ and an ordered tuple $u = (u_1, \dots, u_{|\mathcal{R}|})$ with $u_i \in S \setminus T_i$ for all $i \in [|\mathcal{R}|]$ such that $\bigcup_{i=1}^{|\mathcal{R}|} \{(T_i \setminus \{t\}) \cup \{u_i\} \} = \mathcal{R}$.

I don't know whether or not it is true but after trying some examples it seems to be true, e.g., for $n=5$, $k=3$ and $t=3$. I can recover $\mathcal{R}$ from $\{1, 3, 4\}$, $\{1, 3, 5\}$, $\{2, 3, 4\}$, $\{1, 3, 5\}$ by picking the sequence $(2,4,5,2)$. Would it be hard to formally prove this?

Improve this question
$\endgroup$
3
  • $\begingroup$ This seems ill typed. Each $T_i \setminus \{t\} \cup \{u_i\}$ is a subset of $S$. How can the union of such objects equal $\mathcal R$, which is a subset of $2^S$? (Maybe you mean to start with a specific $R \in \mathcal R$. But then do you really mean to pick randomly? The rest of the problem seems not to be asking anything probabilistic.) $\endgroup$
    – LSpice
    Commented Oct 27, 2020 at 22:32
  • 1
    $\begingroup$ @LSpice I assume what is meant is whether it is possible to choose elements such that the collection of all $T_i \setminus \{t\} \cup \{u_i\}$ (not the union) is equal to $\mathcal R$. Also, it seems as if the sequence should be $(2,4,5,2)$ instead of $(2,4,5,1)$. $\endgroup$
    – Tony Huynh
    Commented Oct 27, 2020 at 23:47
  • $\begingroup$ I edited the question to what I think is intended and corrected some typos. Feel free to edit if I misinterpreted you. $\endgroup$
    – Tony Huynh
    Commented Oct 28, 2020 at 1:35

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you so much for the answer and for fixing the formulation of the problem. I have a follow-up question, however, I am not entirely sure how to formulate it. As you said, the theorem just holds if $k \geq n - k$. What if I had $|\mathcal{R}|$ copies of $\mathcal{T}$ (call $\mathcal{T}_R$) and $|\mathcal{T}|$ copies of $\mathcal{R}$ (call $\mathcal{R}_T$). Is there a result and a proper way to connect each element of $\mathcal{T}_R$ with an element of $\mathcal{R}_T$. $\endgroup$
    – timudk
    Commented Oct 28, 2020 at 2:35
  • 2
    $\begingroup$ You're welcome. The answer is yes to your new question. Just use the same proof. This time the bipartite graph $G$ has $|\mathcal R||\mathcal T|$ vertices on each side, and every vertex has degree $k |\mathcal R|=(n-k) |\mathcal T|$. Thus, $G$ has a perfect matching. $\endgroup$
    – Tony Huynh
    Commented Oct 28, 2020 at 3:54
  • $\begingroup$ One last question: what mathematical "object" should I use for the $|\mathcal{R}|$ copies of $\mathcal{T}$. My issues is that, for example, $\{\{1, 2\}, \{1, 3\}, \{1, 2\}, \{1, 3\}\} = \{\{1, 2\}, \{1, 3\}\}$ so it seems I cannot express those copies as sets? $\endgroup$
    – timudk
    Commented Oct 28, 2020 at 14:00
  • 2
    $\begingroup$ Multiset: en.wikipedia.org/wiki/…. $\endgroup$
    – Tony Huynh
    Commented Oct 28, 2020 at 14:32
  • $\begingroup$ Great, thank you. $\endgroup$
    – timudk
    Commented Oct 28, 2020 at 15:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .