Title: Hypergraph Matchings Avoiding Forbidden Submatchings
|University of Waterloo
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.