Cayley graphs and automatic sequences

DOI10.1007/S10801-016-0706-6zbMATH Open1431.05081arXiv1510.08149OpenAlexW2964152286MaRDI QIDQ510068FDOQ510068

Authors: Pierre Guillot 

Publication date: 16 February 2017

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

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.

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

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

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)

Cites Work

• Automatic congruences for diagonals of rational functions
• Automatic Sequences
• Title not available (Why is that?)
• Noncommutative rational series with applications
• An elementary approach to dessins d'enfants and the Grothendieck-Teichmüller group
• What is \dots an automatic sequence?
• On the Frequency of Letters in Morphic Sequences

Cited In (4)

• Automatic graphs and D0L-sequences of finite graphs
• Cayley automatic groups and numerical characteristics of Turing transducers
• Cayley digraphs and (1,j,n)-sequencings of the alternating groups \(A_ n\)
• 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)