Extremal set theory problem

392 Views Asked by At

What are good bounds(asymptotic bounds preferred) on the cardinality of the largest family $S$, of $m$-element subsets of an $n$-element set, if any pair of elements intersect in a set that has cardinality no larger than $k$?

Thanks in advance.

Update: By Pigeon Hole Principle, we can have an upper bound $$ \frac{n \choose k}{m \choose k} $$; and then by Stirling's Approximation, we can obtain an asymptotic upper bound.

1

There are 1 best solutions below

4
On BEST ANSWER

I'm not familiar with Sperner's Lemma, but Frankl-Wilson (pg 178 of jukna's extremal comb) gives an upper bound of ${n}\choose{k}$ for this problem, which seems a little steep.