Let $k$ and $n$ be two nonnegative integers with $2k+1 \leq n$. Let $A$ be the set of all $k$-subsets of $\left\{1,2,\ldots,n\right\}$. Let $B$ be the set of all $\left(k+1\right)$-subsets of $\left\{1,2,\ldots,n\right\}$. Consider the bipartite graph whose vertices are the elements of $A \cup B$; two vertices $a \in A$ and $b \in B$ are connected by an edge if $a \subseteq b$. I need to use Hall's Marriage theorem to show that this bipartite graph has a matching with $\dbinom{n}{k}$ edges.

I am very lost here I do not know where to start. I feel like multiplying the size of the sets by d will come into play but I am not sure. Any hints are greatly appreciated

  • $\begingroup$ It follows pretty directly from Hall's Marriage Theorem. What have you tried, where are you stuck? $\endgroup$
    – Calvin Lin
    Nov 22 '19 at 7:21
  • $\begingroup$ Start by categorizing sets in $A$ and $B$ and their relation to one another. If a set in $A$ is $\{1,2,\cdots ,k\}$, then what are the sets in $B$ containing it? If a set in $B$ is $\{1,2,\cdots ,k+1\}$, what sets in $A$ are contained in it? Then devise a plan from here $\endgroup$
    – oshill
    Nov 22 '19 at 9:44

First note that a set of $A$ is a subset of $n-k$ sets of $B$. Conversely, a set of $B$ contains $k+1$ sets of $A$.

Now consider $M$ sets of $A$. There are $M(n-k)$ edges to sets of $B$ and so these edges must connect to at least $$\frac{M(n-k)}{k+1}\ge M $$ distinct sets of $B$.

Therefore, by the Marriage Theorem, there is a matching for all $\begin{pmatrix}n\\k\\\end{pmatrix}$ sets of $A$.


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.