Maximum size of k-uniform set family that satisfies a condition

165 Views Asked by At

Let $n \leq 2k$ and $A_1,A_2,...,A_m \subseteq [n]$ be distinct $k$-uniform set where $A_i\cup A_j \neq [n]$ for all $1 \leq i < j \leq m $.

Prove that

$$m \leq (1- \frac{k}{n}) \binom n k$$

and that equality can hold.

I don't know if it is related to Erdős-Ko-Rado theorem. If you have any clue how to come up with this bound please let me know.

1

There are 1 best solutions below

0
On BEST ANSWER

It is related to the Erdős-Rado-Ko theorem indeed.

Consider the sets $$B_i=[n] \setminus A_i \text{ $(1 \leq i \leq m)$}$$ Then we have $B_i \cap B_j \not= \emptyset$ for any $i\leq j$.

By the Erdős-Rado-Ko theorem, we deduce

$$ m \leq \binom{n-1}{n-k-1}=\frac{(n-1)!}{(n-k-1)!k!}= \frac{n-k}{n} \frac{n!}{(n-k)!k!}=(1-\frac{k}{n})\binom{n}{k} $$

Equality is reached when equality is reached in the Erdős-Rado-Ko theorem, i.e. when the $B_i$ are all the subsets containing a fixed element $x$.