Abstract
Independent sets on hypergraphs can be encoded as 0-1 configurations on the set of vertices such that each hyperedge is adjacent to at least one 0. This model has been studied for its large gap between efficient MCMC algorithms (previously d <(k-1)/2) and the conjectured onset of computational hardness (d > O(2^{k/2}) ), where d is the largest degree of vertices and k is the minimum size of hyperedges. In this talk we provide a percolation approach to this model and show that the Glauber dynamics is rapid mixing for d < O(2^{k/2}), closing the gap up to a multiplicative constant.
This is joint work with Jonathan Hermon and Allan Sly.