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

DOI10.1007/S00493-016-3306-0zbMATH Open1413.05159arXiv1407.4600OpenAlexW2963114196MaRDI QIDQ681602FDOQ681602

Authors: Igor Pak, A. V. Malyshev 

Publication date: 12 February 2018

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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 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)

Cites Work

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

Cited In (2)

• Self-similar groups and the zig-zag and replacement products of graphs
• Title not available (Why is that?)

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)