Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are "close" to each other. We study the following question: Construct an an infinite sequence of expanders @math , such that for every two consecutive graphs @math and @math , @math can be obtained from @math by adding a single vertex and inserting removing a small number of edges, which we call the expansion cost of transitioning from @math to @math . This question is very natural, e.g., in the context of datacenter networks, where the vertices represent racks of servers, and the expansion cost captures the amount of rewiring needed when adding another rack to the network. We present an explicit construction of @math -regular expanders with expansion cost at most @math , for any @math . Our construction leverages the notion of a "2-lift" of a graph. This operation was first analyzed by Bilu and Linial, who repeatedly applied 2-lifts to construct an infinite family of expanders which double in size from one expander to the next. Our construction can be viewed as a way to "interpolate" between Bilu-Linial expanders with low expansion cost while preserving good edge expansion throughout. While our main motivation is centralized (datacenter networks), we also get the best-known distributed expander construction in the "self-healing" model.
The deterministic explicit construction of expanders is a prominent research area in both mathematics and computer science. See the survey of Hoory, Linial, and Wigderson @cite_2 . Our approach relies on the seminal paper of Bilu and Linial @cite_0 , which proposed and studied the notion of @math -lifting a graph. They proved that when starting with any good'' expander, a random @math -lift results in another good expander and, moreover, that this can be derandomized. Thus @cite_0 provides a means to deterministically construct an infinite sequence of expanders: start with a good expander and repeatedly 2-lift. All expanders in this sequence are proven to be quasi-Ramanujan graphs, and are conjectured to be Ramanujan graphs (i.e., have optimal spectral expansion). Marcus, Spielman, and Srivastava @cite_4 recently showed that this is indeed essentially true for expanders.
@cite_0 @cite_4 @cite_2
2962992640 2950953939
Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map � : H → G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2lift such that all new eigenvalues are in the range [−2 √ d − 1,2 √ d − 1] (If true, this is tight , e.g. by the Alon-Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c,d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by sqrt c-1 +sqrt d-1 , for all c, d 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials'".