Counting independent sets in amenable groups

Simple item page
dc.catalogadorjca
dc.contributor.authorBriceño Domínguez, Raimundo José
dc.date.accessioned2023-11-02T19:04:03Z
dc.date.available2023-11-02T19:04:03Z
dc.date.issued2023
dc.description.abstractGiven a locally finite graph Γ, an amenable subgroup G of graph automorphisms acting freely and almost transitively on its vertices, and a G-invariant activity function λ, consider the free energy fG(Γ,λ) of the hardcore model defined on the set of independent sets in Γ weighted by λ. 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 ∥λ∥∞<λc(Δ), there exists a randomized ϵ-additive approximation scheme for fG(Γ,λ) that runs in time poly((1+ϵ−1)|Γ/G|), where λc(Δ) denotes the critical activity on the Δ-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. However, we observe that if ∥λ∥∞>λc(Δ), there is no efficient approximation scheme, unless NP=RP. This recovers the computational phase transition for the partition function of the hardcore model on finite graphs and provides an extension to the infinite setting. As an application in symbolic dynamics, we use these results to develop efficient approximation algorithms for the topological entropy of subshifts of finite type with enough safe symbols, we obtain a representation formula of pressure in terms of random trees of self-avoiding walks, and we provide new conditions for the uniqueness of the measure of maximal entropy based on the connective constant of a particular associated graph.
dc.fechaingreso.objetodigital2023-11-02
dc.fuente.origenCambridge University Press
dc.identifier.doi10.1017/etds.2023.38
dc.identifier.issn1469-4417
dc.identifier.urihttps://doi.org/10.1017/etds.2023.38
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/75214
dc.information.autorucFacultad de Matemáticas ; Briceño Domínguez, Raimundo José ; S/I ; 1101906
dc.language.isoen
dc.nota.accesoContenido completo
dc.pagina.final55
dc.pagina.inicio1
dc.revistaErgodic Theory and Dynamical Systems
dc.rightsacceso abierto
dc.subjectAmenable group
dc.subjectIndependent set
dc.subjectEntropy
dc.subjectGibbs measure
dc.subjectStrong spatial mixing
dc.subjectComputational phase transition
dc.subject.ddc510
dc.subject.deweyMatemática física y químicaes_ES
dc.titleCounting independent sets in amenable groups
dc.typeartículo
sipa.codpersvinculados1101906
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
counting-independent-sets-in-amenable-groups.pdf
Size:
1.19 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas