2001-04: Set-Systems with Restricted Multiple Intersections and Explicit Ramsey Hypergraphs

DIMACS TR: 2001-04

Set-Systems with Restricted Multiple Intersections and Explicit Ramsey Hypergraphs

Authors: Vince Grolmusz

ABSTRACT
We give generalizations 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$, that 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 $$(p-1)(k-1)\sum_{i=1}^{|L|}{n\choose i}$$ This result strengthtens a result of F\"uredi (1983), and gives partial answer to a question of T. S\'os (1976).

As an application, we give explicit constructions for (multi-colored) Ramsey hypergraphs. By our best knowledge, this is the first explicit construction of a Ramsey-hypergraph in the literature.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-04.ps.gz

DIMACS Home Page