Fractional Perfect Matchings in Hypergraphs

Fractional Perfect Matchings in Hypergraphs - Andrzej Rucinski

Andrzej Rucinski
Adam Mickiewicz University in Polznan, Poland; Emory University
November 15, 2010

A perfect matching in a k-uniform hypergraph H = (V, E) on n vertices
is a set of n/k disjoint edges of H, while a fractional perfect matching
in H is a function w : E → [0, 1] such that for each v ∈ V we have
e∋v w(e) = 1. Given n ≥ 3 and 3 ≤ k ≤ n, let m be the smallest
integer such that whenever the minimum vertex degree in H satisfies
δ(H) ≥ m then H contains a perfect matching, and let m∗ be defined
analogously with respect to fractional perfect matchings. Clearly, m∗ ≤
m.

We prove that for large n, m ∼ m∗ , and suggest an approach to deter-
mine m∗ , and consequently m, utilizing the Farkas Lemma.
This is a joint work with Vojta Rodl.