9
$\begingroup$

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).

$\endgroup$

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.