MATH Seminar

Title: Fractional perfect matchings in hypergraphs
Seminar: Combinatorics
Speaker: Andrzej Rucinski of Adam Mickiewicz University, Poznan, Poland and Emory University, Atlanta
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2010-11-19 at 4:00PM
Venue: W306
Download Flyer
Abstract: 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 assigning to each edge of H a real number from [0,1] in such a way that for each vertex v the sum of the weights of the edges containing v equals 1. Given n>3 and 2< k< n, let m be the smallest integer such that whenever the minimum vertex degree in H is at least m then H contains a perfect matching, and let m* be defined analogously with respect to fractional perfect matchings. Clearly, m* does not exceed m. We prove that for large n, m and m* are asymptotically equal, and suggest an approach to determine m*, and consequently m, utilizing the Farkas Lemma. This is a joint work with Vojta Rodl.