English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the mixing time of the single-site update Markov chain, known as theGlauber dynamics, for generating a random independent set of a tree. Our focusis obtaining optimal convergence results for arbitrary trees. We consider themore general problem of sampling from the Gibbs distribution in the hard-coremodel where independent sets are weighted by a parameter $\lambda>0$. Previouswork of Martinelli, Sinclair and Weitz (2004) obtained optimal mixing timebounds for the complete $\Delta$-regular tree for all $\lambda$. However,Restrepo et al. (2014) showed that for sufficiently large $\lambda$ there arebounded-degree trees where optimal mixing does not hold. Recent work ofEppstein and Frishberg (2022) proved a polynomial mixing time bound for theGlauber dynamics for arbitrary trees, and more generally for graphs of boundedtree-width.  We establish an optimal bound on the relaxation time (i.e., inverse spectralgap) of $O(n)$ for the Glauber dynamics for unweighted independent sets onarbitrary trees. Moreover, for $\lambda\leq .44$ we prove an optimal mixingtime bound of $O(n\log{n})$. We stress that our results hold for arbitrarytrees and there is no dependence on the maximum degree $\Delta$. Interestingly,our results extend (far) beyond the uniqueness threshold which is on the order$\lambda=O(1/\Delta)$. Our proof approach is inspired by recent work onspectral independence. In fact, we prove that spectral independence holds witha constant independent of the maximum degree for any tree, but this does notimply mixing for general trees as the optimal mixing results of Chen, Liu, andVigoda (2021) only apply for bounded degree graphs. We instead utilize thecombinatorial nature of independent sets to directly prove approximatetensorization of variance/entropy via a non-trivial inductive proof.

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees