Towards Constructing Ramanujan Graphs Using Shift Lifts

Understand

In a breakthrough work, Marcus-Spielman-Srivastava 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 by Agarwal-Kolla-Madan 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}$.