Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSelf-avoiding walks and multiple context-free languages
84
0
0.0
(
0
)
Added by
Christian Lindorfer
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
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.
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.
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.
Let $G$ be an infinite, vertex-transitive lattice with degree $lambda$ and fix a vertex on it. Consider all cycles of length exactly $l$ from this vertex to itself on $G$. Erasing loops chronologically from these cycles, what is the fraction $F_p/lambda^{ell(p)}$ of cycles of length $l$ whose last erased loop is some chosen self-avoiding polygon $p$ of length $ell(p)$, when $ltoinfty$ ? We use combinatorial sieves to prove an exact formula for $F_p/lambda^{ell(p)}$ that we evaluate explicitly. We further prove that for all self-avoiding polygons $p$, $F_pinmathbb{Q}[chi]$ with $chi$ an irrational number depending on the lattice, e.g. $chi=1/pi$ on the infinite square lattice. In stark contrast we current methods, we proceed via purely deterministic arguments relying on Viennots theory of heaps of pieces seen as a semi-commutative extension of number theory. Our approach also sheds light on the origin of the difference between exponents stemming from loop-erased walk and self-avoiding polygon models, and suggests a natural route to bridge the gap between both.
We study a restricted class of self-avoiding walks (SAW) which start at the origin (0, 0), end at $(L, L)$, and are entirely contained in the square $[0, L] times [0, L]$ on the square lattice ${mathbb Z}^2$. The number of distinct walks is known to grow as $lambda^{L^2+o(L^2)}$. We estimate $lambda = 1.744550 pm 0.000005$ as well as obtaining strict upper and lower bounds, $1.628 < lambda < 1.782.$ We give exact results for the number of SAW of length $2L + 2K$ for $K = 0, 1, 2$ and asymptotic results for $K = o(L^{1/3})$. We also consider the model in which a weight or {em fugacity} $x$ is associated with each step of the walk. This gives rise to a canonical model of a phase transition. For $x < 1/mu$ the average length of a SAW grows as $L$, while for $x > 1/mu$ it grows as $L^2$. Here $mu$ is the growth constant of unconstrained SAW in ${mathbb Z}^2$. For $x = 1/mu$ we provide numerical evidence, but no proof, that the average walk length grows as $L^{4/3}$. We also consider Hamiltonian walks under the same restriction. They are known to grow as $tau^{L^2+o(L^2)}$ on the same $L times L$ lattice. We give precise estimates for $tau$ as well as upper and lower bounds, and prove that $tau < lambda.$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
