DIMACS TR: 2001-03
Constructing Set-Systems with Prescribed Intersection Size
Authors: Vince Grolmusz
ABSTRACT
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