Self-avoiding walks and multiple context-free languages

Florian Lehner*, Christian Lindorfer

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 SAW,o (z) = n⩾1 cn(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 no two edges starting at the same vertex have the same label, 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 SAW,o . Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that L 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 SAW,o is multiple context-free if and only if the group is virtually free.

Original languageEnglish
Article number#18
Number of pages52
JournalCombinatorial Theory
Volume3
Issue number1
DOIs
Publication statusPublished - 2023

Keywords

  • Cayley graph
  • formal language
  • multiple context free language
  • Self avoiding walk
  • virtually free group

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Cite this