Define $m(n,k,l)$ as the maximal size of a family $k$-element subsets of $[n]$ having the property that the intersection of every two sets is less than $l$.

As stated on wikipedia, in 1985 Rödl proved Erdős’s conjecture that for fixed $k$ and $l$ $$ \lim_{n \to \infty} m(n,k,l) = \binom{n}{l}/\binom{k}{l}.$$

(The book "the probabilistic method" contains a proof of this fact.)

Does anybody know what happens when $k = k(n), l = l(n)$? I am especially interested in the case when $l = O(\log n)$ and $k = n^{\epsilon}$ (which is one of the settings that has applications in theoretical computer science for Nisan-Wigderson pseudorandom generators).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.