4
$\begingroup$

I am new here and I hope I don't make any mistakes in asking this question here.

Let $n > k$ be integers, and $\epsilon < 1/2$ be an arbitrarily small constant. What is an upper bound on the maximum size of a family $\{A_1,\ldots,A_N\}$ of subsets of $[n]$ such that:

  • $|A_i| = k$
  • $|A_i \cap A_j| \le (1-\epsilon)k$.

I know there are a bunch of results on this question but I am interested in getting good bounds in the regime where $k \ge n/2$, and I did not manage to get anything.

The most related result I have found is a lemma by Corradi that shows that, in the regime I am interested in, if $\epsilon \ge 1/2$, then the families can have size at most some function of $\epsilon$ (i.e.: constant independent of n). I am trying to find out what we can say when $\epsilon$ is a constant less than 1/2 and, importantly whether a constant bound applies (any loose constant bound will be great). If there is a way of seeing that the bound is not going to be constant, it would also be great.

Any direction would be highly appreciated. Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Small pairwise intersection is eqhuivalent to large symmetric difference. So you are asking about constant weight error correcting codes. You can move to complenents and assume that k is at most n/2. There is large literature about it.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Indeed, that's exactly what I was looking for! Thanks a lot for the answer -- and sorry for taking your time... $\endgroup$
    – user103464
    Jan 11, 2017 at 19:53
  • 1
    $\begingroup$ My pleasure ... $\endgroup$
    – Gil Kalai
    Jan 18, 2017 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.