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/

Zendy Plus

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

Zendy Tools

Zendy Open

For spin systems, such as the $q$-colorings and independent-set models,approximating the partition function in the so-called non-uniqueness region,where the model exhibits long-range correlations, is typically computationallyhard for bounded-degree graphs. We present new algorithmic results forapproximating the partition function and sampling from the Gibbs distributionfor spin systems in the non-uniqueness region on random regular bipartitegraphs. We give an $\mathsf{FPRAS}$ for counting $q$-colorings for even$q=O\big(\tfrac{\Delta}{\log{\Delta}}\big)$ on almost every $\Delta$-regularbipartite graph. This is within a factor $O(\log{\Delta})$ of the samplingalgorithm for general graphs in the uniqueness region and improvessignificantly upon the previous best bound of$q=O\big(\tfrac{\sqrt{\Delta}}{(\log\Delta)^2}\big)$ by Jenssen, Keevash, andPerkins (SODA'19). Analogously, for the hard-core model on independent setsweighted by $\lambda>0$, we present an $\mathsf{FPRAS}$ for estimating thepartition function when $\lambda=\Omega\big(\tfrac{\log{\Delta}}{\Delta}\big)$,which improves upon previous results by an $\Omega(\log \Delta)$ factor. Ourresults for the colorings and hard-core models follow from a general resultthat applies to arbitrary spin systems. Our main contribution is to show how toelevate probabilistic/analytic bounds on the marginal probabilities for thetypical structure of phases on random bipartite regular graphs into efficientalgorithms, using the polymer method. We further show evidence that our resultfor colorings is within a constant factor of best possible using currentpolymer-method approaches.

Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region