Seminar: Hypergraph Matchings Avoiding Forbidden Submatchings

Date: October 24, 2023
Time: 12:00 PM EDT - 1:00 PM EDT
Location: ENG-210 and virtually via zoom
Open To: All faculty, staff, students and guests are welcome to attend
Contact: Pawel Pralat (pralat@torontomu.ca)

This talk overviews 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.