Rapid mixing of hypergraph independent sets

DOI10.1002/RSA.20830MaRDI QIDQ5229340zbMATHOpenAlexFDO

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 countingmixing timehypergraph independent sets

Mathematics Subject Classification ID

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

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

(14)

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

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)