Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSelf-avoiding walks and connective constants
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The connective constant $mu(G)$ of a quasi-transitive graph $G$ is the asymptotic growth rate of the number of self-avoiding walks (SAWs) on $G$ from a given starting vertex. We survey several aspects of the relationship between the connective constant and the underlying graph $G$. $bullet$ We present upper and lower bounds for $mu$ in terms of the vertex-degree and girth of a transitive graph. $bullet$ We discuss the question of whether $mugephi$ for transitive cubic graphs (where $phi$ denotes the golden mean), and we introduce the Fisher transformation for SAWs (that is, the replacement of vertices by triangles). $bullet$ We present strict inequalities for the connective constants $mu(G)$ of transitive graphs $G$, as $G$ varies. $bullet$ As a consequence of the last, the connective constant of a Cayley graph of a finitely generated group decreases strictly when a new relator is added, and increases strictly when a non-trivial group element is declared to be a further generator. $bullet$ We describe so-called graph height functions within an account of bridges for quasi-transitive graphs, and indicate that the bridge constant equals the connective constant when the graph has a unimodular graph height function. $bullet$ A partial answer is given to the question of the locality of connective constants, based around the existence of unimodular graph height functions. $bullet$ Examples are presented of Cayley graphs of finitely presented groups that possess graph height functions (that are, in addition, harmonic and unimodular), and that do not. $bullet$ The review closes with a brief account of the speed of SAW.
rate research
Read More
We study the connective constants of weighted self-avoiding walks (SAWs) on infinite graphs and groups. The main focus is upon weighted SAWs on finitely generated, virtually indicable groups. Such groups possess so-called height functions, and this permits the study of SAWs with the special property of being bridges. The group structure is relevant in the interaction between the height function and the weight function. The main difficulties arise when the support of the weight function is unbounded, since the corresponding graph is no longer locally finite. There are two principal results, of which the first is a condition under which the weighted connective constant and the weighted bridge constant are equal. When the weight function has unbounded support, we work with a generalized notion of the length of a walk, which is subject to a certain condition. In the second main result, the above equality is used to prove a continuity theorem for connective constants on the space of weight functions endowed with a suitable distance function.
We define a potential-weighted connective constant that measures the effective strength of a repulsive pair potential of a Gibbs point process modulated by the geometry of the underlying space. We then show that this definition leads to improved bounds for Gibbs uniqueness for all non-trivial repulsive pair potentials on $mathbb R^d$ and other metric measure spaces. We do this by constructing a tree-branching collection of densities associated to the point process that captures the interplay between the potential and the geometry of the space. When the activity is small as a function of the potential-weighted connective constant this object exhibits an infinite volume uniqueness property. On the other hand, we show that our uniqueness bound can be tight for certain spaces: the same infinite volume object exhibits non-uniqueness for activities above our bound in the case when the underlying space has the geometry of a tree.
We prove that for the $d$-regular tessellations of the hyperbolic plane by $k$-gons, there are exponentially more self-avoiding walks of length $n$ than there are self-avoiding polygons of length $n$, and we deduce that the self-avoiding walk is ballistic. The latter implication is proved to hold for arbitrary transitive graphs. Moreover, for every fixed $k$, we show that the connective constant for self-avoiding walks satisfies the asymptotic expansion $d-1-O(1/d)$ as $dto infty$; on the other hand, the connective constant for self-avoiding polygons remains bounded. Finally, we show for all but two tessellations that the number of self-avoiding walks of length $n$ is comparable to the $n$th power of their connective constant. Some of these results were previously obtained by Madras and Wu cite{MaWuSAW} for all but finitely many regular tessellations of the hyperbolic plane.
Let $G$ be a quasi-transitive, locally finite, connected graph rooted at a vertex $o$, and let $c_n(o)$ be the number of self-avoiding walks of length $n$ on $G$ starting at $o$. We show that if $G$ has only thin ends, then the generating function $F_{mathrm{SAW},o}(z)=sum_{n geq 0} c_n(o) z^n$ is an algebraic function. In particular, the connective constant of such a graph is an algebraic number. If $G$ is deterministically edge labelled, that is, every (directed) edge carries a label such that any two edges starting at the same vertex have different labels, then the set of all words which can be read along the edges of self-avoiding walks starting at $o$ forms a language denoted by $L_{mathrm{SAW},o}$. Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that $L_{mathrm{SAW},o}$ is a $k$-multiple context-free language if and only if the size of all ends of $G$ is at most $2k$. Applied to Cayley graphs of finitely generated groups this says that $L_{mathrm{SAW},o}$ is multiple context-free if and only if the group is virtually free.
The connective constant $mu(G)$ of a graph $G$ is the asymptotic growth rate of the number $sigma_{n}$ of self-avoiding walks of length $n$ in $G$ from a given vertex. We prove a formula for the connective constant for free products of quasi-transitive graphs and show that $sigma_{n}sim A_{G} mu(G)^{n}$ for some constant $A_{G}$ that depends on $G$. In the case of finite products $mu(G)$ can be calculated explicitly and is shown to be an algebraic number.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
