Almost-Ramanujan graphs and prime gaps

DOI10.1016/J.EJC.2014.09.001MaRDI QIDQ458598zbMATHOpenAlexFDO

Authors Adrian W. Dudek

Publication date 8 October 2014

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

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

zbMATH Keywords

regular graphalmost-Ramanujan graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(5)

• scientific article; zbMATH DE number 7268671 (Why is no real title available?)
• 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
• The sequence of prime gaps is graphic

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)