Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
On Construction of Almost-Ramanujan Graphs
verfasst von : He Sun, Hong Zhu
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Reingold et al. introduced the notion zig-zag product on two different graphs, and presented a fully explicit construction of
d
-regular expanders with the second largest eigenvalue
O
(
d
− 1/3
). In the same paper, they ask whether or not the similar technique can be used to construct expanders with the second largest eigenvalue
O
(
d
− 1/2
). Such graphs are called Ramanujan graphs. Recently, zig-zag product has been generalized by Ben-Aroya and Ta-Shma. Using this technique, they present a family of expanders with the second largest eigenvalue
d
− 1/2 +
o
(1)
, what they call almost-Ramanujan graphs. However, their construction relies on local invertible functions and the dependence between the big graph and several small graphs, which makes the construction more complicated.
In this paper, we shall give a generalized theorem of zig-zag product. Specifically, the zig-zag product of one “big” graph and several “small” graphs with the same size will be formalized. By choosing the big graph and several small graphs individually, we shall present a family of fully explicitly almost-Ramanujan graphs with locally invertible function waived.