Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.