This problem appeared on a qualifying exam
Let $n\leq 2k$ and $A_1,\dots,A_m$ be subsets of size $k$ of $A=\{1,\dots,n\}$ with the following property: $A_i \cup A_j \not = A$ for all $i,j$. Show that $m \leq (1-\frac{k}{n}) \binom{n}{k}$.
Attempt: Firstly, we can observe that with some algebra $(1-\frac{k}{n}) \binom{n}{k}=\binom{n-1}{k}$. Now, I am thinking that we can use a similar double counting argument as in Katona's proof of EKR. We see that if a given cyclic ordering of $\{1,\dots,n\}$ contains some $A_i = (a_1,\dots,a_k)$ in the cyclic ordering, then for every $a_i, a_{i+1}$ the family $\{A_1,\dots,A_m\}$ may admit at most one of the $k$ length sets separating $a_i$ from $a_{i+1}$ because $2k \geq n$ and no two sets may union to $\{1,\dots,n \}$. So now consider the set of all pairs $P=(A_i,\sigma)$, where $A_i \in \{A_1,\dots,A_m\}$ and $\sigma$ is some interval order. We have by our above observation that if $\mathcal{P}$ is the set of all pairs, then $|\mathcal{P}| \leq k(n-1)!$. Also, $|\mathcal{P}| = k! (n-k)!$ because for every set $A_i$ we can arrange it into a cyclic order by permuting its elements then permuting the remaining $(n-k)$ elements.
My problem is that this does not give the desired upperbound as this is exactly Katona's proof. Is there an error in this work? Thank you.
