科研之友
微信
新浪微博
Facebook
分享链接
摘要
The method of Murty and Cioaba shows how one can use results about gaps between primes to construct families of almost-Ramanujan graphs. In this paper we give a simpler construction which avoids the search for perfect matchings and thus eliminates the need for any computational effort. A couple of known bounds on the gap between consecutive primes are then used to give the construction of k-regular families with lower bounds on the spectral gaps. We then show that a result of Ben-Aroya and Ta-Shma can be improved using our simpler construction though on the assumption of the Riemann Hypothesis; this sheds some more light on a question raised by Reingold, Vadhan and Widgerson.
- 出版日期2015-1
