Zurück zu den Preprints des Jahres 2003


2003-37

Remarks on an edge isoperimetric problem

by Bey, Ch..


Series: 2003-37, Preprints

MSC:
05C35 Extremal problems
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