Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
arXiv:1407.4600
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.
21 pages, 9 figures