Leírás
Let G be an amenable and virtually orderable finitely
generated group (e.g., any group of polynomial growth) and Gamma a
countable graph such that G acts almost transitively and freely on its
vertices. In this talk I will present general conditions sufficient
for approximating with arbitrary accuracy the exponential growth rate
of the number of weighted independent sets in such a graph Gamma. The
techniques involve a special representation of free energy and the
study of self-avoiding walks in graphs. As a by-product of these
results, I will also present a way to approximate the entropy of
G-subshifts of finite type with a universal symbol in polynomial time,
in contrast to the general case, where it is known it could be
uncomputable. These results unify and generalize works of Weitz
(2006), Gamarnik-Katz (2009), Wang-Yin-Zhong (2014), and Marcus-Pavlov
(2015).