Expander graphs -- both local and global (Q2226628): Difference between revisions

For positive integers \(a>b\), an \((a,b)\)-graph \(G=(V,E)\) is an \(a\)-regular graph in which for every \(v\in V\) the link \(G_{v}\), i.e. the subgraph induced by the set of neighbours of \(v\), is \(b\)-regular. We are interested in the expansion properties of \((a,b)\)-graphs, noting that for a number of the many applications of expander graphs (e.g. in PCP theory on computer science) we want not only the basic graph \(G\) to have good expansion properties but also the link graphs \(G_{v}\). (A random regular graph is, with probability tending to 1 a good expander in a suitable sense: but \(G_{v}\) is typically an anticlique so not an expander.) \par The paper under review constructs two families of \((a,b)\)-graphs where both \(G\) and the links \(G_{v}\) have good expansion properties. The authors consider the second eigenvalue \(\lambda_{2}\) of the graph \(G\), where it is well known that comparatively small values of \(\lambda_{2}\) correspond to good expansion properties. An initial result, based on a result of \textit{N. Alon} and \textit{R. B. Boppana} [Combinatorica 7, 1--22 (1987; Zbl 0631.68041)], is that the second eigenvalue of an \((a,b)\)-graph is at least \(b+2\sqrt{a-b-1} +o(1)\). This bound is tight. However there is a degree of \lq trade-off\rq\, between good expansion of \(G_{v}\) and \(G\). in that as the quality of the expansion in \(G_{v}\) increases the gap between the second eigenvalue of \(G\) and the lower bound just mentioned increases. A key role in constructing the graphs is played by the so-called polygraph construction, which (crudely speaking) transforms high-girth expanders into \((a,b)\)-graphs. \par This work fits into the active research topic of high-dimensional expansion, and there is discussion of links with this area in Section 5 of the paper. Work is still proceeding in this area: see, for example, the recent preprint of \textit{E. Friedgut} and \textit{Y. Iluz} [``Hyper-regular graphs and high dimensional expanders'', Preprint, \url{arxiv:2010.03829}] in which related results are given and relevant literature surveyed. Some other classes of \((a,b)\)-regular graphs, based on regular triangulations of surfaces and tensor products of graphs. A number of open problems are also listed. Including quantifying more precisely the trade-off mentioned above.