Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
classification
🧮 math.CO
keywords
graphsautomataclassderandomizationexpandergiveliftsmealy
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.