Counting Independent Sets in Regular Hypergraphs

Combinatorics Seminar
Friday, September 9, 2016 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech

Joint work with Will Perkins and Prasad Tetali.

We consider the extremal counting problem which asks what d-regular, r-uniform hypergraph on n vertices has the largest number of (strong) independent sets. Our goal is to generalize known results for number of matchings and independent sets in regular graphs to give a general bound in the hypergraph case. In particular, we propose an adaptation to the hypergraph setting of the occupancy fraction method pioneered by Davies et al. (2016) for use in the case of graph matchings. Analysis of the resulting LP leads to a new bound for the case r=3 and suggests a method for tackling the general case.