Skip to content

Opening book details…

Can I read Counting Independent Sets in Amenable Groups on EtoBox?

Counting Independent Sets in Amenable Groups by Briceño, Raimundo is a scholarly article available to read on EtoBox.

What is Counting Independent Sets in Amenable Groups about?

Given a locally finite graph $\Gamma$, an amenable subgroup $G$ of graph automorphisms acting freely and almost transitively on its vertices, and a $G$-invariant activity function $\lambda$, consider the free energy $f_G(\Gamma,\lambda)$ of the hardcore model defined on the set of independent sets in $\Gamma$ weighted by $\lambda$. Under the assumption that $G$ is finitely generated and its word problem can be solved in exponential time, we define suitable ensembles of hardcore models and prove the following: if $\|\lambda\|_\infty < \lambda_c(\Delta)$, there exists a randomized $\epsilon$-additive approximation scheme for $f_G(\Gamma,\lambda)$ that runs in time $\mathrm{poly}((1+\epsilon^{-1})\lvert \Gamma/G \rvert)$, where $\lambda_c(\Delta)$ denotes the critical activity on the $\Delta$-regular tree. In addition, if $G$ has a finite index linearly ordered subgroup such that its algebraic past can be decided in exponential time, we show that the algorithm can be chosen to be deterministic. On the other hand, we observe that if $\|\lambda\|_\infty > \lambda_c(\Delta)$, there is no efficient approximation scheme, unless $\mathrm{NP} = \mathrm{RP}$. This recovers the computational p

Author
Briceño, Raimundo
Published
2021
Language
EN

More by Briceño, Raimundo

Browse all works by Briceño, Raimundo