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
Preprints, Working Papers, ... Year : 2023

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

Abstract

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
Origin Files produced by the author(s)

Dates and versions

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

Licence

Identifiers

Cite

Geoffroy Caillat-Grenier. Random Schreier graphs of the general linear group over finite fields and expanders. 2023. ⟨lirmm-04090380⟩
61 View
33 Download

Altmetric

Share

More