Fetching the paper…

Reading the bibliography…

2015

Diameter of Ramanujan Graphs and Random Cayley Graphs

Sardari, Naser T

Original
PDF
Post on X

Understand

We study the diameter of LPS Ramanujan graphs $X_{p,q}$.

We show that the diameter of the bipartite Ramanujan graphs is greater than $ (4/3)\log_{p}(n) +O(1)$ where $n$ is the number of vertices of $X_{p,q}$.
We also construct an infinite family of $(p+1)$-regular LPS Ramanujan graphs $X_{p,m}$ such that the diameter of these graphs is greater than or equal to $ \lfloor (4/3)\log_{p}(n) \rfloor$.
On the other hand, for any $k$-regular Ramanujan graph we show that the distance of only a tiny fraction of all pairs of vertices is greater than $(1+\epsilon)\log_{k-1}(n)$.

Diameter of Ramanujan Graphs and Random Cayley Graphs · Around

Built on

The diameter of random regular graphs
B. Bollobás and W. Fernandez de la Vega · 1982
Earlier work this paper cites.
Ramanujan graphs
A. Lubotzky, R. Phillips, and P. Sarnak · 1988
Earlier work this paper cites.
Note on the girth of Ramanujan graphs
N. L. Biggs and A. G. Boshier · 1990
Earlier work this paper cites.
Some applications of modular forms
Peter Sarnak · 1990
Earlier work this paper cites.

Similar

Discrete groups, expanding graphs and invariant measures
Alexander Lubotzky · 1994
Cited alongside, same era.
Elementary number theory, group theory, and Ramanujan graphs
Giuliana Davidoff, Peter Sarnak, and Alain Valette · 2003
Cited alongside, same era.
Cutoff on all Ramanujan graphs
E. Lubetzky and Y. Peres · 2015
Cited alongside, same era.

Then

Optimal strong approximation for quadratic forms
N. T Sardari · 2015
Closest in time.
Letter to Scott Aaronson and Andy Pollington on the Solovay-Kitaev Theorem
Peter Sarnak · 2015
Closest in time.
Complexity of strong approximation on the sphere
Naser T Sardari · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…