Random Schreier graphs as expanders

Expander graphs, due to their good mixing properties, are useful in many algorithms and combinatorial constructions. One can produce an expander graph with high probability by taking a random graph. For example, for the case of bipartite graphs of degree $d$ and $n$ vertices in each part we may take independently $d$ permutations of an $n$-element set and use them for edges. This construction is much simpler than all known explicit constructions of expanders and gives graphs with good mixing properties (small second largest eigenvalue) with high probability. However, from the practical viewpoint, it uses too many random bits, so it is difficult to generate and store these bits for reasonably large graphs. The natural idea is to replace the group of all permutations by its small subgroup. Let $n$ be $q^k-1$ for some $k$ and some prime $q$. Then we may interpret vertices as non-zero $k$-dimensional vector over the field $\mathbb{F}_q$, and take random \emph{linear} permutations, i.e., random elements of $GL_k(\mathbb{F}_q)$. In this way the number of random bits used will be polynomial in $k$ (i.e., the logarithm of the graph size, instead of the graph size itself) and the degree. In this paper we provide some experimental data that show that indeed this replacement does not change much the mixing properties (the second eigenvalue) of the random graph that we obtain. These data are provided for several types of graphs (undirected regular and biregular bipartite graphs). We also prove some upper bounds for the second eigenvalue (though it is quite weak compared with the experimental results). Finally, we discuss the possibility to decrease the number of random bits further by using Toeplitz matrices; our experiments show that this change makes the mixing properties of graphs only marginally worse, while the number of random bits decreases significantly.