Conjecture on the limiting probability that a random lift is Ramanujan

Let GG be a Ramanujan graph, and let HH be its random uniform nn-lift. A graph is Ramanujan when all its nontrivial eigenvalues have absolute value at most the Ramanujan bound 2d12\sqrt{d-1} for a dd-regular graph.

Ramanujan-lift probability conjecture. There exists a constant cc with 0<c<10<c<1 such that

P(H is Ramanujan)=c+o(1),\mathbb{P}(H\text{ is Ramanujan})=c+o(1),

where the o(1)o(1) term tends to 00 as nn\to\infty. This predicts that the probability of the Ramanujan property for random lifts converges to a nontrivial limit, rather than to either zero or one. The source presents this as a natural conjecture motivated by the unresolved probability that a random regular graph is Ramanujan; no resolution status is given.

Sources & referencesView supporting material

Primary source

Eyal Lubetzky, Benny Sudakov and Van Vu, “Spectra of lifted Ramanujan graphs”, arXiv:0911.4148 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.