Background
While working with set families related with Sperner's theorem I found this lemma which I am to prove:
If $\Delta\mathcal F=\{ B\in \binom{[n]}{k-1}:\ B\subseteq A,\ \text{for a set } A\in \mathcal F\}$ denotes the shadow of a set $A\in\mathcal F\subseteq \binom{[n]}{k}$, then the following inequality holds
$$\frac{|\Delta\mathcal F|}{\binom{n}{k-1}}\geq \frac{|\mathcal F|}{\binom{n}{k}}.$$
Equality holds if and only if $\mathcal F$ is empty or $\mathcal F$ is precisely $\binom{[n]}{k}$.
Here $\binom{[n]}{k}$ denotes the set of $k$-subsets of $[n]$, the set of the first $n$ positive integers. The reference given for the proof was Sperner's 1928 paper.
My Approach
I have been able to prove the inequality as follows:
- For every $B\in\Delta\mathcal F$, there are $n-(k-1)$ ways to add an element to the set in such a way that we obtain a $k$-subset of $[n]$. This means that there can be no more than $n-k+1$ sets inside of $\mathcal F$ in which we can find $B$ as a subset.
- On the other hand, by virtue of the definition of the shadow of $\mathcal F$, every set $A\in\mathcal F$ contains exactly $\binom{k}{k-1}=k$ sets of $\Delta\mathcal F$.
- Now the number of pairs of sets $(A,B)\in \mathcal F\times \Delta\mathcal F$ such that $B\subseteq A$ is exactly $|\mathcal F|·k$. But such quantity cannot exceed the amount of sets inside of $\Delta\mathcal F$ times the number of ways in which we can find it as a subset of a set in $\mathcal F$. This amount is precisely $|\Delta F|·(n-k+1)$.
In conclusion we obtain
$$|\mathcal F|·k\leq|\Delta F|·(n-k+1), $$
which is equivalent to the initial inequality $\frac{|\Delta\mathcal F|}{\binom{n}{k-1}}\geq \frac{|\mathcal F|}{\binom{n}{k}}$.
My Problem
The final part of the lemma asks us to prove when does equality occur. It can be seen that if $\mathcal F$ is empty or it's the set of $k$-sets, then the inequality becomes an equality.
To prove the other direction is the part giving me some troubles. Proving the other direction is equivalent to proving
If $\mathcal F$ is a non-empty set family of $k$-subsets of $[n]$, and $\frac{|\Delta\mathcal F|}{\binom{n}{k-1}}= \frac{|\mathcal F|}{\binom{n}{k}}$, then $\mathcal F$ is precisely the set of $k$-subsets of $[n]$.
My initial observation was that if the equality holds, then two things occur:
- The number of pairs $(A,B)$ such that $B\subseteq A$ is exactly $|\Delta F|·(n-k+1)$.
- For every $B\in\Delta \mathcal F$, the $n-k+1$ $k$-sets that can contain $B$ will appear in $\mathcal F$.
However with this information I am not able to see how can I deduce that $\mathcal F$ is $\binom{[n]}{k}$, I don't know what am I missing but I feel that it's right under my nose. There's also this hunch that tells me that I could also go along the lines of proving $\Delta \mathcal F$ is $\binom{[n]}{k-1}$. In such a case deducing that $ \mathcal F$ is $\binom{[n]}{k}$ follows from the hypothesis.
I also tried reading Sperner's paper but I don't know german and I can't find similarities between my question and the paper itself. (I mean, it's almost a 100 years old, some notation ought to change)
My Question exactly
- How can I prove the last part of the lemma?
- Also, is my approach for the inequality correct? Did I count correctly?
Any type of lead, suggestion or comment will be kindly received.
Best Answer
$\def\F{\mathscr{F}}\def\dF{Δ\F}$Your proof of the inequality by double counting/Fubini's theorem is correct. Now for the scenario when the inequality becomes identity, assume that $\F ≠ \varnothing$. Note that the proof of the inequality, in particular this line:
implies that if the inequality becomes identity, then\begin{gather*} B \cup \{a\} \in \F. \quad \forall B \in \dF,\ a \in [n] \setminus B \tag{1} \end{gather*} Now, since it is assumed that $\F ≠ \varnothing$, take an arbitrary set $X \in \F$. For any $Y \subseteq [n]$ with $|Y| = k$, (1) enables one to transform $X$ to $Y$ element by element: suppose$$ Z = X \cap Y, \quad X \setminus Y = \{x_1, \cdots, x_m\}, \quad Y \setminus X = \{y_1, \cdots, y_m\}, $$ then using (1) to alternate between $\F$ and $\dF$,\begin{array}{cccc} & \F && \dF\\ & \llap{X =\;} \{x_1, x_2, x_3, \cdots, x_m\} \cup Z & → & \{x_2, x_3, \cdots, x_m\} \cup Z\\ → & \{x_2, x_3, \cdots, x_m; y_1\} \cup Z & → & \{x_3, \cdots, x_m; y_1\} \cup Z\\ → & \{x_3, \cdots, x_m; y_1, y_2\} \cup Z & → & \cdots\\ → & \{y_1, y_2, y_3, \cdots, y_m\} \cup Z \rlap{\; = Y} \end{array} Therefore, $Y \in \F$.