Lifts, derandomization, and diameters of Schreier graphs of Mealy automata

DOI10.1007/S00493-016-3306-0MaRDI QIDQ681602zbMATHOpenAlexFDO

Authors Igor Pak, A. V. Malyshev

Publication date 12 February 2018

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

diameterMealy automatagroup actions on trees\(2\)-lifts of graphsautomaton groupfamilies of expandersSchreier graph of a Mealy automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: It is known that random 2-lifts of graphs give rise to expander graphs. We present a new conjectured derandomization of this construction based on certain Mealy automata. We verify that these graphs have polylogarithmic diameter, and present a class of automata for which the same is true. However, we also show that some automata in this class do not give rise to expander graphs.

Recommendations

• An Approach to the Herzog-Schönheim Conjecture Using Automata
• scientific article; zbMATH DE number 3984584
• scientific article; zbMATH DE number 1334620
• The Černý conjecture for automata respecting intervals of a directed graph
• The graph structure of a deterministic automaton chosen at random
• scientific article; zbMATH DE number 3959484
• Robinson-Schensted-Knuth algorithm, jeu de taquin, and Kerov-Vershik measures on infinite tableaux
• scientific article; zbMATH DE number 3499653
• scientific article; zbMATH DE number 3900165
• scientific article; zbMATH DE number 4130033

Cites work

• scientific article; zbMATH DE number 5152179 (Why is no real title available?)
• scientific article; zbMATH DE number 2195483 (Why is no real title available?)
• A free group of finite automata
• A geometric approach to (semi)-groups defined by automata via dual transducers.
• Automata and square complexes.
• Automata generating free products of groups of order 2.
• Automata, dynamical systems, and groups
• CONJUGATION IN TREE AUTOMORPHISM GROUPS
• Classification of groups generated by 3-state automata over a 2-letter alphabet
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Expander graphs and their applications
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Lifts, discrepancy and nearly optimal spectral gap
• On a free group of transformations defined by an automaton.
• On a series of finite automata defining free transformation groups.
• On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
• Some topics in the dynamics of group actions on rooted trees.

Cited in

(2)

• scientific article; zbMATH DE number 7710054 (Why is no real title available?)
• Self-similar groups and the zig-zag and replacement products of graphs

This page was built for publication: Lifts, derandomization, and diameters of Schreier graphs of Mealy automata

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