4
$\begingroup$

The Bilu-Linial conjecture claims that every $d-$regular graph has a $2-$lift such that for the signing matrix has its eigenvalues between $[-2\sqrt{d-1},2\sqrt{d-1}]$ (the ``signing matrix" is the adjacency matrix of the graph but with $\pm 1$ entries denoting which edges got lifted by the identity("+") permutation on two elements and which ones got the flip("-")

Now one knows that for such a $2-$lift the adjacency eigenvalues of the new lifted graph is the union of the old eigenvalues and the eigenvalues of the signing matrix.

  • I want to know as to how/if a positive resolution to the Bilu-Linial conjecture necessarily will imply that this special $2-$lift can be used to construct Ramanujan graphs.

Even if this special signing claimed by Bilu-Linial were to actually exist wouldn't it still be possible that may be the original graph had eigenvalues in the interval $(2\sqrt{d-1},d)$ and which would still persist and hence the lifted graph wouldn't become Ramanujan? Or am I missing something?

  • Also what is the significance of the lower bound of $-2\sqrt{d-1}$ in the Bilu-Linial conjecture? (the definition of the Ramanujan graph doesn't seem to need that..)

By a "Ramanujan graph" I would mean a $d-$regular graph whose second largest eigenvalue is $\leq 2\sqrt{d-1}$.

I am aware of the proof of the positive resolution of this conjecture for the bipartite case by Nikhil Srivastava, Adam Marcus and Daniel Spielman. (..though their proof doesn't seem to use bipartition anywhere - its just that they can control for only the upper bound $2\sqrt{d-1}$ and the lower bound gets implied by the bipartition structure and hence the theorem holds..)

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think you have to start with a d-regular Ramanujan graph and take a 2-lift of it with all new eigenvalues at most 2\sqrt{d-1} and repeat. $\endgroup$
    – Sebi Cioaba
    Commented Jan 11, 2015 at 23:02
  • $\begingroup$ @SebiCioaba That is one of their conjectures that if you start with a Ramanujan graph then such a lift exists. But they also conjecture that such a lift exists for any d-regular graph too. But does this second more general conjecture help in constructing a Ramanujan graph? $\endgroup$
    – user6818
    Commented Jan 11, 2015 at 23:29
  • $\begingroup$ I am not aware of an application of the 2nd conjecture in constructing infinite families of Ramanujan graphs. $\endgroup$
    – Sebi Cioaba
    Commented Jan 12, 2015 at 12:17

0

Reset to default

You must log in to answer this question.