The basic ℓ2\ell^2-distance conjecture for Ramanujan graphs

About 5 years old · traced to

Let XX be a sequence of Ramanujan graphs, let nn denote the number of vertices, let dd be their common degree, and set p=d−1p=d-1. Let d2(t)d_2(t) be the average squared ℓ2\ell^2 distance from stationarity at time tt, and let N(t)N(t) denote the quantity defined in the paper. The basic ℓ2\ell^2-distance conjecture. If t<2otlog⁡pnt<2 ot\log_p n, then

d2(t)∼1N(t)d_2(t)\sim\frac{1}{N(t)}

as n→∞n\to\infty. This conjecture predicts the asymptotic behavior of the distance before the cutoff window for non-backtracking random walks on Ramanujan graphs; the supplied text does not state whether it has been proved or disproved.

References

Primary source

Evita Nestoridi and Peter Sarnak, “Bounded cutoff window for the non-backtracking random walk on Ramanujan Graphs”, arXiv:2103.15176 (2021).

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.