Title:ÌýHypergraph Matchings Avoiding Forbidden Submatchings
| Speaker: | Luke Postle |
| Affiliation: | University of À¶Ý®ÊÓƵ |
| Location: | MC 5501 |
Abstract:ÌýWe overview a general theoryÌýfor finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)). In particular, we haveÌýa new common generalization of the classical theorems ofÌýPippenger (for finding an almost perfect matching of G) and Ajtai, Komlos, Pintz, Spencer, and SzemerediÌý(for finding an independent set in a girth five hypergraph H) into this unified framework. More generally, we proved coloring andÌýlist coloring versions, and also generalized this further to when H is a hypergraph with small codegrees. We also discuss applications to various areas of high girth combinatorics. This is joint work with Michelle Delcourt.