Lifts, derandomization, and diameters of Schreier graphs of Mealy automata (Q681602)

Not too many recursive constructions of families of expanders are known. On the other hand, a randomized \(2\)-lift of an expander graph has been shown to result with a high probability in another expander graph. The focus of this paper is on derandomization of this observation by constructing iterated families of graphs constructed by assigning to each edge of the base graph parameters that not only determine how the edge will be lifted into a pair of parallel or crossed edges but also which parameters will be assigned to the lifted edges. This allows for repeating the \(2\)-lifts over and over again, each time obtaining a graph of twice the order of the previous graph. The first part of the paper is devoted to two specific ways of assigning the lifting parameters to the base graph consisting of a single vertex and three loops, based on the Aleshin and Bellaterra automata. These automata have been carefully selected from a large set of known Mealy automata with the aim of potentially constructing strongly explict families of expanders. Only computational evidence that this might be the case is provided, however, the authors succeed at proving the weaker result that the diameter of the resulting graphs grows slowly with respect to the orders of the graphs. Namely, they show that the diameter of the \(n\)-th iteration obtained either using the Bellaterra or the Aleshin automaton belongs to \(O(n^2)\) (while the graphs are of order \(2^n\)). This also makes the graphs interesting with respect to the degree/diameter problem of finding the largest graphs of given degree and diameter. In the second part of the paper, general properties of Mealy automata giving rise to graphs with similar diameter growth properties are presented and followed by further specific examples. The paper concludes by highlighting a number of connections to group theory as well as with a list of open problems. In fact, the entire paper is built around investigating various connections between graph, group and automata theories; each of these deserving further investigation.