Rapid mixing of hypergraph independent sets

DOI10.1002/RSA.20830MaRDI QIDQ5229340zbMATH OpenOpenAlexFDO

Authors Jonathan Hermon, Allan Sly, Yumeng Zhang

Publication date 14 August 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.07999

zbMATH Keywords

approximate countinghypergraph independent setsmixing time

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We prove that the the mixing time of the Glauber dynamics for sampling independent sets on $n$-vertex $k$-uniform hypergraphs is $O(nlogn)$ when the maximum degree $Delta$ satisfies $Deltaleqc{2}^{k/2}$, improving on the previous bound [BDK06] of $Deltaleqk-2$. This result brings the algorithmic bound to within a constant factor of the hardness bound of [BGG+16] which showed that it is NP-hard to approximately count independent sets on hypergraphs when $Deltageq5cdot{2}^{k/2}$.

Recommendations

• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Fundamentals of Computation Theory
• A note on the Glauber dynamics for sampling independent sets
• Fast convergence of the Glauber dynamics for sampling independent sets
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

Cited in

(18)

• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• Mixing times for exclusion processes on hypergraphs
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Counting solutions to random CNF formulas
• Counting hypergraph colorings in the local lemma regime
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 6469177 (Why is no real title available?)
• Slow mixing of Glauber dynamics for the hard-core model on the hypercube
• Inapproximability of counting independent sets in linear hypergraphs
• On the zeroes of hypergraph independence polynomials
• Fast sampling of satisfying assignments from random k-SAT with applications to connectivity
• A sharp lower bound on the independence number of k-regular connected hypergraphs with rank R
• Counting solutions to random CNF formulas
• Some combinatorial algorithms on the independent number of k-regular connected hypergraphs
• Toward derandomizing Markov chain Monte Carlo
• Inapproximability of counting hypergraph colourings

This page was built for publication: Rapid mixing of hypergraph independent sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5229340)