Set-Systems with Restricted Multiple Intersections

Abstract

We give a generalization for the Deza-Frankl-Singhi Theorem in case of multiple intersections. More exactly, we prove, that if ${\cal H}$ is a set-system, which satisfies that for some $k$, the $k$-wise intersections occupy only $\ell$ residue-classes modulo a $p$ prime, while the sizes of the members of ${\cal H}$ are not in these residue classes, then the size of ${\cal H}$ is at most $$(k-1)\sum_{i=0}^{\ell}{n\choose i}$$ This result considerably strengthens an upper bound of Füredi (1983), and gives partial answer to a question of T. Sós (1976).

As an application, we give a direct, explicit construction for coloring the $k$-subsets of an $n$ element set with $t$ colors, such that no monochromatic complete hypergraph on $$\exp{(c(\log m)^{1/t}(\log \log m)^{1/(t-1)})}$$ vertices exists.