Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-044 | 31st July 1998 00:00

#### Bounds on Pairs of Families with Restricted Intersections

TR98-044
Authors: Jiri Sgall
Publication: 5th August 1998 17:00
Keywords:

Abstract:

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\}$.

ISSN 1433-8092 | Imprint