Raimundo Briceño: Counting independent sets in amenable almost transitive graphs with an order

Speaker: Raimundo Briceño

Title: Counting independent sets in amenable almost transitive graphs with an order 

Abstract: 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).