Rapid mixing of hypergraph independent sets

DOI10.1002/RSA.20830zbMATH Open1417.05147arXiv1610.07999OpenAlexW3102182509MaRDI QIDQ5229340FDOQ5229340

Authors: Jonathan Hermon, Allan Sly, Yumeng Zhang 

Publication date: 14 August 2019

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

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}$.

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

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

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)

Cited In (11)

• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• Title not available (Why is that?)
• Fundamentals of Computation Theory
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Counting Solutions to Random CNF Formulas
• On the zeroes of hypergraph independence polynomials
• Fast sampling of satisfying assignments from random \(k\)-SAT with applications to connectivity
• Counting Hypergraph Colorings in the Local Lemma Regime
• A sharp lower bound on the independence number of \(k\)-regular connected hypergraphs with rank \(R\)
• Inapproximability of counting independent sets in linear hypergraphs

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)