Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-044 | 31st July 1998 00:00

Bounds on Pairs of Families with Restricted Intersections

RSS-Feed




TR98-044
Authors: Jiri Sgall
Publication: 5th August 1998 17:00
Downloads: 936
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