Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCounting self-avoiding walks on free products of graphs
180
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
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.
Formulas are derived for counting walks in the Kronecker product of graphs, and the associated spectral distributions are obtained by the Mellin convolution of probability distributions. Two-dimensional restricted lattices admitting the Kronecker product structure are listed, and their spectral distributions are calculated in terms of elliptic integrals.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
