Loading jsMath...
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: 2099
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