Elementary Number Theory, Group Theory and Ramanujan Graphs
Cambridge University Press, Jan 20, 2003 - Mathematics - 144 pages
This text is a self contained treatment of expander graphs and in particular their explicit construction. Expander graphs are both highly connected but sparse, and besides their interest within combinatorics and graph theory, they also find various applications in computer science and engineering.The reader needs only a background in elementary algebra, analysis and combinatorics; the authors supply the necessary background from graph theory, number theory, group theory and representation theory. Thus the text can be used as a brief introduction to these subjects and their synthesis in modern mathematics.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
adjacency matrix algebra assume bipartite Cayley graph change of variables chromatic number compute congruent conjugate connected construction Corollary cycle graph deﬁned Deﬁnition denote dimC divides edges eigenvalue elements equivalent Exercises on Section exists f_LL factorization family of expanders ﬁnd ﬁnite group finite groups ﬁrst ﬁxed four squares function f G-space Gaussian integer group G group homomorphism hence homomorphism inequality integral quaternions invariant subspace irreducible representations isomorphic k-regular graph large girth Lemma Let G linear maximal abelian subgroup metabelian modulo multiplication nontrivial eigenvalue odd prime order q permutation polynomials Proof properties prove PSL2 q Q ll-ll(Z quadratic reciprocity Ramanujan graphs reduced word representation of G resp result right-hand divisor scalar product Show spectral gap square modulo subset sum of four Theorem unique vector space vertex vertex-transitive word of length Xp,q