Upper bound for a number of subsets of $\{1, \dots, n\}$

Question

Consider $n \leq 2k$ and let $A_1, \dots ,A_m$ be a family of $k$-element subsets of $[n]$ such that $A_i \cup A_j \neq [n] \forall i,j \in [m]$. I want to show that $m$ is bounded above by $(1-\frac{k}{n})\binom{n}{k}$. I understand that the Erdős-Ko-Rado theorem says that if $2k \leq n$ then every intersecting family of $k$-element subsets of an $n$-element set has at most $\binom{n-1}{k-1}$ numbers. However, I am still not sure how to apply this result giving the flip of the inequality. I'm wondering if there is any theorem in combinatorics that may help me with figuring out this problem.

Answer 1

brief informal outline.turn this into a proper proof, if required.

Note that $\left( 1 - \frac{k}{n} \right) \binom{n}{k}= \binom{n - 1}{k}$.

A heuristic is to keep one element of $[n]$ away say $\{n\}$, so that any two $k$-sets formed out of $[n-1]$ never unite to $[n]$. Such a $k$-set family will have $\binom{n - 1}{k}$ elements.

In order to prove that $\binom{n - 1}{k}$ is the upper bound: Let $A$ be a $k$-set of $[n]$ that is a part of the collection $C$ of $k$-sets where no two of them unite to $[n]$. The presence of $A$ does not allow the inclusion of $\binom{k}{k-(n-k)}$ $k$-subsets(where rest $n-k$ remaining are picked from $[n]$ and $k-(n-k)$ of them have to come from $A$). Let say a relation $R$ is defined so that $A$ is related to every member of the $\binom{k}{k-(n-k)}$ subset. With some effort, we can see that $R$ is a equivalence relation.

Hence, $[n]$ can be partitioned into $\binom{k}{2k - n} + 1$ sets out of which only one can be a part of collection $C$. This boils down to prove that, $$\frac{n}{\binom{k}{2k - n} + 1} \le \binom{n - 1}{k}$$ Simplification yields the equivalence to,$1\le \binom{k -1}{n - k -1}$