Edyta Szymanska: Approximate Counting of Matchings in (3,3)-graphs

In this talk we give a fully polynomial deterministic approximation scheme (FPTAS) for the number of matchings in 3-uniform hypergraphs whose maximum vertex degree is bounded by three, referred to as (3,3)-graphs. Our proof follows via a correlation decay method applied to counting independent sets in the intersection graphs of (3,3)-graphs, which, naturally, do not contain induced copies of the star K_{1,4}.  

This is joint work with Andrzej Dudek, Marek Karpinski, and Andrzej Rucinski.