Portal de Periódicos da CAPES

Rapid mixing of hypergraph independent sets

2018; Wiley; Volume: 54; Issue: 4 Linguagem: Inglês

10.1002/rsa.20830

1098-2418

Jonathan Hermon, Allan Sly, Yumeng Zhang,

Limits and Structures in Graph Theory

We prove that the mixing time of the Glauber dynamics for sampling independent sets on n ‐vertex k ‐uniform hypergraphs is when the maximum degree Δ satisfies Δ ≤ c 2 k /2 , improving on the previous bound Bordewich and co‐workers of Δ ≤ k − 2. This result brings the algorithmic bound to within a constant factor of the hardness bound of Bezakova and co‐workers which showed that it is NP‐hard to approximately count independent sets on hypergraphs when Δ ≥ 5·2 k /2 .