Almost-Ramanujan graphs and prime gaps

DOI10.1016/J.EJC.2014.09.001zbMATH Open1301.05214arXiv1402.0620OpenAlexW2088619036MaRDI QIDQ458598FDOQ458598

Authors: Adrian W. Dudek 

Publication date: 8 October 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The method of Murty and Cioabu{a} 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 computation. A couple of recent explicit bounds on the gap between consecutive primes are then used to give the construction of $k$-regular families with explicit 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 on the assumption of the Riemann Hypothesis, which sheds some more light on a question raised by Reingold, Vadhan and Widgerson.

Full work available at URL: https://arxiv.org/abs/1402.0620

Recommendations

• Expander graphs and gaps between primes
• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• Corrigendum to: ``Almost-Ramanujan graphs and prime gaps
• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• scientific article; zbMATH DE number 1376670

zbMATH Keywords

regular graphalmost-Ramanujan graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Matrix Analysis
• Eigenvalues and expanders
• Spectra of graphs
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Title not available (Why is that?)
• The difference between consecutive primes. II
• Expander graphs and their applications
• Ramanujan graphs
• On the Riemann hypothesis and the difference between primes
• Cubic Ramanujan graphs
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Title not available (Why is that?)
• Title not available (Why is that?)
• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• On Construction of Almost-Ramanujan Graphs

Cited In (5)

• Title not available (Why is that?)
• Expander graphs and gaps between primes
• The sequence of prime gaps is graphic
• A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
• Corrigendum to: ``Almost-Ramanujan graphs and prime gaps

This page was built for publication: Almost-Ramanujan graphs and prime gaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458598)