Preprint series: 03-37 , Preprints

MSC:

05C35 Extremal problems, See also {90C35}

05C65 Hypergraphs

Abstract: Among all collections of a given number of $k$-element subsets of an $n$-element groundset find
a collection which maximizes the number of pairs of subsets which intersect in $k-1$ elements.

This problem was solved for $k=2$ by Ahlswede and Katona, and is open for $k>2$.

We survey some linear algebra approaches which yield to estimations for the maximum number of pairs,
and we present a new and short proof of the Ahlswede-Katona result.

Keywords: Isoperimetric Problem, Kleitman West Problem, Hypergraph

Upload: 2003-11-13-11-13