Cayley graphs and automatic sequences

DOI10.1007/S10801-016-0706-6MaRDI QIDQ510068zbMATH OpenOpenAlexFDO

Authors Pierre Guillot

Publication date 16 February 2017

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08149

zbMATH Keywords

Cayley graphsautomataautomatic sequencesdessins d'enfants

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Sequences (mod (m)) (11B50) Automata sequences (11B85) Arithmetic aspects of dessins d'enfants, Bely? theory (11G32)

Abstract: We study those automatic sequences which are produced by an automaton whose underlying graph is the Cayley graph of a finite group. For $2$-automatic sequences, we find a characterization in terms of what we call homogeneity, and among homogeneous sequences, we single out those enjoying what we call self-similarity. It turns out that self-similar $2$-automatic sequences (viewed up to a permutation of their alphabet) are in bijection with many interesting objects, for example dessins d'enfants (covers of the Riemann sphere with three points removed). For any $p$ we show that, in the case of an automatic sequence produced "by a Cayley graph", the group and indeed the automaton can be recovered canonically from the sequence. Further, we show that a rational fraction may be associated to any automatic sequence. To compute this fraction explicitly, knowledge of a certain graph is required. We prove that for the sequences studied in the first part, the graph is simply the Cayley graph that we start from, and so calculations are possible. We give applications to the study of the frequencies of letters.

Recommendations

• Automorphisms of Cayley graphs
• scientific article; zbMATH DE number 51232
• Cayley graphs with few automorphisms
• Automorphism groups of some generalized Cayley graphs
• Automatic graphs and D0L-sequences of finite graphs
• On automorphisms and structural properties of generalized Cayley graphs
• Cayley digraphs and graphs
• scientific article; zbMATH DE number 1145214
• scientific article; zbMATH DE number 5605487
• Cayley graphs

Cites work

• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• An elementary approach to dessins d'enfants and the Grothendieck-Teichmüller group
• Automatic Sequences
• Automatic congruences for diagonals of rational functions
• Noncommutative rational series with applications
• On the Frequency of Letters in Morphic Sequences
• What is \dots an automatic sequence?

Cited in

(4)

• Automatic graphs and D0L-sequences of finite graphs
• Cayley digraphs and (1,j,n)-sequencings of the alternating groups \(A_ n\)
• Cayley automatic groups and numerical characteristics of Turing transducers
• Artwork based on automatic sequences

This page was built for publication: Cayley graphs and automatic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510068)