A linear programming perspective on the Frankl-Rödl-Pippenger theorem. (English) Zbl 0842.05066
Let \(\mathcal H\) be a \(k\)-bounded hypergraph on vertex-set \(V\) and \(t: {\mathcal H}\to \mathbb{R}^+\) a fractional matching of \(\mathcal H\). Let, furthermore, \(c_1,\dots, c_l: {\mathcal H}\to \mathbb{R}^+\), each satisfying
\[
\sum_{A\in {\mathcal H}} c^2_i(A) t(A)< o\Biggl(\Biggl(\sum_{A\in {\mathcal H}} c_i(A) t(A)\Biggr)^2\Biggr).
\]
The author proves that under these conditions there is a matching \(\mathcal M\) of \(\mathcal H\) satisfying
\[
\sum_{A\in {\mathcal M}} c_i(A)\sim c_i({\mathcal H})
\]
for \(i= 1,\dots, l\), limits taken as \(\alpha(t)\to 0\), where
\[
\alpha(t):= \max\{\sum\{t(A): x, y\in A\in {\mathcal H}\}: x, y\in V,\;x\neq y\}.
\]
In addition, the theorem is interpreted as a statement about the relation between integer and linear programs.
Reviewer: K.Dohmen (Berlin)