The expansion rate of Margulis expanders and LPS expanders for vertex set Z Ã\x97 Z

Author

Li, Fulu

Author_Institution

Massachusetts Inst. of Technol., Cambridge, MA

fYear

2008

fDate

19-21 March 2008

Firstpage

1069

Lastpage

1074

Abstract

Expanders are potential mathematic tools to design robust computer networks and to analyze the formation and expansion of today´s Internet. In this paper, we derive lower bounds regarding the expansion rate of Margulis expanders, lower bounds and upper bounds regarding the expansion rate of LPS expanders, for vertex set Z times Z . The two types of expanders we study are variants of the expanders due to Margulis [4] and Lubotzky, Philips, Sarnak (LPS) [3] respectively. We consider the compact planar integer point-sets Z times Z and the corresponding counting measure. Following [1], the proof is based on symmetrization.

Keywords

graph theory; set theory; Internet; LPS expanders; Margulis expanders; computer network design; highly connected sparse graph; mathematic tools; planar integer point set; vertex set; Algorithm design and analysis; Computer networks; Decoding; Eigenvalues and eigenfunctions; Graph theory; IP networks; Information analysis; Mathematics; Robustness; Upper bound; Expanders; expansion rate; network formation;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Sciences and Systems, 2008. CISS 2008. 42nd Annual Conference on

Conference_Location

Princeton, NJ

Print_ISBN

978-1-4244-2246-3

Electronic_ISBN

978-1-4244-2247-0

Type

conf

DOI

10.1109/CISS.2008.4558677

Filename

4558677