Set-systems with restricted multiple intersections

Vince Grolmusz

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

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.

Détail

DOI : 10.37236/1625

Classification : 05D05, 05C65, 05D10
Mots-clés : algorithmic constructions, explicit Ramsey-graphs, explicit Ramsey-hypergraphs, set-system