Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 23, 2017, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Penny Haxell (University of Waterloo)
We consider a hypergraph analogue of the basic fact that every regular bipartite graph has a perfect matching. A theorem of Aharoni implies that every regular tripartite hypergraph $H$ with $n$ vertics in each class has a matching of size at least $n/2$, and moreover this bound is tight. We prove a stability version of this statement, showing that if $H$ has matching number close to $n/2$ then it is correspondingly close in structure to the extremal configuration.
Automatic MiSe System Software Version 1.4803M | admin login