Fractional perfect matchings in hypergraphs

Combinatorics Seminar
Friday, November 5, 2010 - 15:05
1 hour (actually 50 minutes)
Skiles 255
A. Mickiewicz University and Emory University
A  perfect matching in a $k$-uniform hypergraph $H=(V,E)$ on $n$ vertices is a set of$n/k$ disjoint edges of $H$, whilea fractional perfect matching in $H$ is a function $w:E --> [0,1]$ such that for each $v\in V$ we have $\sum_{e\ni v} w(e) = 1.$ Given $n \ge 3$ and $3\le k\le n$, let $m$ be the smallest integer suchthat whenever the minimum vertex degree in $H$ satisfies $\delta(H)\ge m$ then $H$ contains  aperfect matching, and let $m^*$ be defined analogously with respect to  fractional perfectmatchings. Clearly, $m^*\le m$.We prove that for large $n$, $m\sim m^*$, and suggest an approach  to determine $m^*$, andconsequently $m$, utilizing the Farkas Lemma. This is a joint work with Vojta Rodl.