ECCC-Report TR98-044https://eccc.weizmann.ac.il/report/1998/044Comments and Revisions published for TR98-044en-usWed, 05 Aug 1998 17:00:10 +0300
Paper TR98-044
| Bounds on Pairs of Families with Restricted Intersections |
Jiri Sgall
https://eccc.weizmann.ac.il/report/1998/044
We study pairs of families ${\cal A},{\cal B}\subseteq
2^{\{1,\ldots,r\}}$ such that $|A\cap B|\in L$ for any
$A\in{\cal A}$, $B\in{\cal B}$. We are interested in the maximal
product $|{\cal A}|\cdot|{\cal B}|$, given $r$ and $L$. We give
asymptotically optimal bounds for $L$ containing only elements
of $s<q$ residue classes modulo $q$, where $q$ is arbitrary
(even non-prime) and $s$ is a constant. As a consequence, we
obtain a version of Frankl-R\"{o}dl result about forbidden
intersections for the case of two forbidden intersections. We
also give tight bounds for $L=\{0,\ldots,k\}$.
Wed, 05 Aug 1998 17:00:10 +0300https://eccc.weizmann.ac.il/report/1998/044