MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.