We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Explicit near-Ramanujan graphs of every degree

Formal Metadata

Title
Explicit near-Ramanujan graphs of every degree
Title of Series
Number of Parts
12
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
For every constant d >= 3 and epsilon > 0, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n) vertices that is epsilon-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2sqrt(d-1)+epsilon (excluding the single trivial eigenvalue of d).