Hall's theorem and double counting

Question

I have the following question.

Use double-counting and Hall's theorem to show that for $0\leqslant r < \frac n2$, there exists an injection $f\colon \binom{[n]}r\to\binom{[n]}{r+1}$ such that $A\subseteq f(A)$ for each $A\in\binom{[n]}r$.

Note that $[n]$ denotes $\{1,\dots,n\}$ and $\binom Ar$ is the set of subsets of $A$ having size $r$, i.e., $$\tbinom Ar= \{B\subseteq A : |B|=r\}.$$ Also, I am using the graph-theoretic formulation of Hall's theorem, i.e., that a bipartite graph with partite sets $S$ and $T$ has a matching from $S$ into $T$ if and only if $|N_G(A)|\geqslant |A|$ for all $A\subseteq S$.

This is what I have tried.

Let $\mathscr X=\binom{[n]}r$ and $\mathscr Y=\binom{[n]}{r+1}$. Define $V=\mathscr X\cup \mathscr Y$ and $$E=\{\{X,Y\}:\text{$X\in\mathscr X$, $Y\in\mathscr Y$ and $X\subseteq Y$}\},$$ and $G=(V,E)$; i.e., we have a bipartite graph with partite sets $\mathscr X$, $\mathscr Y$, where each vertex $X\in\mathscr X$ is connected to all of its supersets in $\mathscr Y$.

To apply Hall's therem, I want that for any $\mathscr A\subseteq\mathscr X$, $|\mathscr A|\leqslant |N_G(\mathscr A)|$. I have tried double-counting, but all I have managed to show is the following.

First, notice that for any $X\in\mathscr X$, $N_G(X)=\binom{n-r}1=n-r$ and similarly for any $Y\in\mathscr Y$, $N_G(Y) = \binom{r+1}r = r+1$.

For double counting, define $\chi(X,Y) = 1$ if $X\subseteq Y$ and $0$ otherwise. Then for any $\mathscr A\subseteq\mathscr X$, \begin{align*} (r+1)|\mathscr A| &= \sum_{X\in\mathscr A}(r+1)\\[5pt] &= \sum_{X\in\mathscr A}\sum_{Y\in N_G(\mathscr{A})}\chi(X,Y)\\[5pt] &= \sum_{Y\in N_G(\mathscr{A})}\sum_{X\in\mathscr A}\chi(X,Y) \qquad\text{(double-counting)}\\[5pt] &\leqslant \sum_{Y\in N_G(\mathscr{A})}(n-r)\\[5pt] &= (n-r)|N_G(\mathscr A)|, \end{align*} which does not let me deduce that $|N_G(\mathscr A)|\geqslant|\mathscr A|$.

I appreciate any assistance with this.

Answer 1

Outline:

1) For $X' \subset X$ show that $|X'|(n-r)$ edges leave $X'$.

2) How many edges can be adjacent to $N(X')$ in total? Show that this is at most $r|N(X')|$.

3) Put steps 1 and 2 together to show that $r|N(X')| \ge |X'|(n-r)$ which implies $|N(X')| \ge |X'|$ so by Hall's theorem, there is a matching.