2001-11: k-wise Set-Intersections and k-wise Hamming-Distances

DIMACS TR: 2001-11

k-wise Set-Intersections and k-wise Hamming-Distances

Authors: Vince Grolmusz and Benny Sudakov

ABSTRACT
We prove a version of the Ray-Chaudhuri--Wilson and Frankl-Wilson theorems for $k$-wise intersections and also generalize a classical code-theoretic result of Delsarte for $k$-wise Hamming distances. A set of code-words $a^1,a^2,\ldots,a^k$ of length $n$ have $k$-wise Hamming-distance $\ell$, if there are exactly $\ell$ such coordinates, where not all of their coordinates coincide (alternatively, exactly $n-\ell$ of their coordinates are the same). We show a Delsarte-like upper bound: codes with few $k$-wise Hamming-distances must contain few code-words.

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

DIMACS Home Page