DIMACS TR: 2001-03

Constructing Set-Systems with Prescribed Intersection Size

Authors: Vince Grolmusz


Let $f$ be an $n$ variable polynomial with positive integer coefficients, and let ${\cal H}=\{H_1,H_2,\ldots,H_m\}$ be a set-system on the $n$-element universe. We define set-system $f({\cal H})=\{G_1,G_2,\ldots,G_m\}$, and prove that $f(H_{i1}\cap H_{i2}\cap\ldots\cap H_{ik})=|G_{i1}\cap G_{i2}\cap\ldots\cap G_{ik}|$, for any $1\leq k\leq m$, where $f(H_{i1}\cap H_{i2}\cap\ldots\cap H_{ik})$ denotes the value of $f$ on the characteristic vector of $H_{i1}\cap H_{i2}\cap\ldots\cap H_{ik}$.

The construction of $f({\cal H})$ is a straightforward polynomial--time algorithm from ${\cal H}$ and polynomial $f$. In this paper we use this algorithm for constructing set-systems with prescribed intersection sizes modulo an integer.

As a by-product of our method, some Ray-Chaudhuri--Wilson-like theorems are proved.

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

DIMACS Home Page