## Abstract

In a breakthrough work, Marcus et al. [1] recently showed that every d-regular bipartite Ramanujan graph has a 2-lift that is also d-regular bipartite Ramanujan. As a consequence, a straightforward iterative brute-force search algorithm leads to the construction of a d-regular bipartite Ramanujan graph on N vertices in time 2^{O(dN)}. Shift k-lifts studied in [2] lead to a natural approach for constructing Ramanujan graphs more efficiently. The number of possible shift k-lifts of a d-regular n-vertex graph is k^{nd/2}. Suppose the following holds for k=2^{Ω(n)}: There exists a shift k-lift that maintains the Ramanujanproperty of d-regular bipartite graphson n vertices for all n. Then, by performing a similar brute-force algorithm, one would be able to construct an N-vertex bipartite Ramanujan graph in time 2^{O(dlog2N)}. Also, if (⋆) holds for all k≥2, then one would obtain an algorithm that runs in poly(N^{d}) time. In this work, we take a first step towards proving (⋆) by showing the existence of shift k-lifts that preserve the Ramanujan property in d-regular bipartite graphs for k=3 and for k=4.

Original language | English (US) |
---|---|

Pages (from-to) | 199-214 |

Number of pages | 16 |

Journal | Linear Algebra and Its Applications |

Volume | 529 |

DOIs | |

State | Published - Sep 15 2017 |

## Keywords

- Expanders
- Interlacing
- Lifts

## ASJC Scopus subject areas

- Algebra and Number Theory
- Numerical Analysis
- Geometry and Topology
- Discrete Mathematics and Combinatorics