Approximate Counting of Matchings in (3,3)-graphs

Graphs, Hypergraphs, and Computing

11 February 14:00 - 15:00

Edyta Szymanska - Adam Mickiewicz University

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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to