×

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)

MSC:

05C65 Hypergraphs
90C05 Linear programming
Full Text: DOI