Computer Science/Discrete Mathematics Seminar I

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 \to [0,1]$ such that for each $v \in V$ we have $\sum_{e \ni v}w(e) = 1$. Given $n\geq 3$ and $3\leq k \leq n$, let $m$ be the smallest integer such that whenever the minimum vertex degree in $H$ satisfies $\delta(H) \geq m$ then $H$ contains a perfect matching, and let $m^∗$ be defined analogously with respect to fractional perfect matchings. Clearly, $m^* \leq m$.

We prove that for large $n,m \sim m^∗$, and suggest an approach to determine $m^∗$, and consequently $m$, utilizing the Farkas Lemma. This is a joint work with Vojta Rodl.