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

Autor:	Anton Malyshev, Igor Pak
Rok vydání:	2017
Předmět:	Class (set theory) TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES 010102 general mathematics 0102 computer and information sciences Nonlinear Sciences::Cellular Automata and Lattice Gases 01 natural sciences Automaton Combinatorics Computational Mathematics Mealy automata 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Expander graph Combinatorics (math.CO) 0101 mathematics Computer Science::Formal Languages and Automata Theory MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Combinatorica. 37:733-765
ISSN:	1439-6912 0209-9683
DOI:	10.1007/s00493-016-3306-0
Popis:	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. 21 pages, 9 figures
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dd34fa33ebaf050d982f9068b97b4e0d https://doi.org/10.1007/s00493-016-3306-0 Zobrazit plný text záznamu Full text from SpringerLink