Random Schreier graphs of the general linear group over finite fields and expanders - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Random Schreier graphs of the general linear group over finite fields and expanders

Résumé

In this paper we discuss potentially practical ways to produce expander graphs with good spectral properties and a compact description. We focus on several classes of uniform and bipartite expander graphs defined as random Schreier graphs of the general linear group over the finite field of size two. We perform numerical experiments and show that such constructions produce spectral expanders that can be useful for practical applications. To find a theoretical explanation of the observed experimental results, we used the method of moments to prove upper bounds for the expected second largest eigenvalue of the random Schreier graphs used in our constructions. We focus on bounds for which it is difficult to study the asymptotic behaviour but it is possible to compute non-trivial conclusions for relatively small graphs with parameters from our numerical experiments (e.g., with less than 2^200 vertices and degree at least logarithmic in the number of vertices).
Fichier principal
Vignette du fichier
2305.02154.pdf (506.36 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-04090380 , version 1 (17-10-2023)

Licence

Identifiants

Citer

Geoffroy Caillat-Grenier. Random Schreier graphs of the general linear group over finite fields and expanders. 2023. ⟨lirmm-04090380⟩
60 Consultations
29 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More