Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Expanding graphs, Ramanujan graphs, and 1-factor perturbations
 
research article

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

de la Harpe, Pierre
•
Musitelli, Antoine
2006
Bulletin of the Belgian Mathematical Society

We construct (k±1)-regular graphs which provide sequences of expanders by adding or substracting appropriate 1- factors from given sequences of k- regular graphs. We compute numerical examples in a few cases for which the given sequences are from the work of Lubotzky, Phillips, and Sarnak (with k − 1 the order of a finite field). If k + 1 = 7, our construction results in a sequence of 7- regular expanders with all spectral gaps at least 6−2√5 ≈ 1.52; the corresponding minoration for a sequence of Ramanujan 7- regular graphs (which is not known to exist) would be 7 − 2√6 ≈ 2.10.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

PRO 060625.pdf

Access type

openaccess

Size

172.99 KB

Format

Adobe PDF

Checksum (MD5)

a0319a557022537c16bfeb92afdcc6c3

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés