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.


1 Answer 1


Hint: Let $ B_i = A - A_i$.

Show that we can apply Erdos Ko Rado.
Hence conclude that $ m \leq { n-1 \choose n-k - 1 } $ as desired.


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.