Tutte Colloquium - Luke Postle

Friday, November 17, 2023 3:30 pm - 3:30 pm EST (GMT -05:00)

Title: Hypergraph Matchings Avoiding Forbidden Submatchings

Speaker: Luke Postle
Affiliation: University of Waterloo
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.