Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
|---|---|---|---|---|---|
Searching... | 30000010025924 | QA166 D35 2003 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
This text is a self-contained study of expander graphs, specifically, their explicit construction. Expander graphs are highly connected but sparse, and while being of interest within combinatorics and graph theory, they can also be applied to computer science and engineering. Only a knowledge of elementary algebra, analysis and combinatorics is required because the authors provide 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.
Reviews 1
Choice Review
Number theory once epitomized pure mathematics, but nowadays its rivals in purity proliferate even as number theory itself spawns critical daily applications. Applied number theory usually means cryptography, especially the public-key systems that enable presumably secure communication even with one's enemies. Very simple mathematics, cleverly used, occasionally produces spectacular practical results and indeed the first public-key cryptosystems needed only the most rudimentary number theory. But modern elaborations use all the number theoretic tools one can reasonably expect from an undergraduate. Thus cryptography returns the favor as it motivates a new generation of students to study number theory. Already one has many fine monographs at the graduate level, but the subject moves quickly and also Mollin and Wagstaff have pitched their new books to undergraduates. Mollin (Univ. of Calgary) presumes a course in number theory but develops discrete log primality testing (but a breakthrough last summer already makes this chapter out-of-date!), factoring, and elliptic curves. Mollin discusses practical implementation in details and develops diverse applications: e.g., digital cash, secret sharing, and key management. Cryptography connotes mainly the crafting of codes, but cryptanalysis refers to the effort that breaks codes. The preponderance of books discusses mainly the former meaning. Wagstaff presumes less from the reader, covers similar ground to Mollin, and his theme of attack makes for an especially exciting read. Cryptography aside, applied number theory might mean communication networks. Sparse but highly connected graphs (expanders) have many applications. Erdos's probabilistic methods guarantee that such graphs exist but offer no construction. Number theory often yields deterministic structures that provably exhibit properties associated with random structures. In particular, Davidoff (Mount Holyoke College), Sarnak (Princeton Univ.; New York Univ.), and Valette (Universite de Neuchatel) explain why certain Cayley graphs for certain finite groups of matrices over finite fields provide explicit expanders. Because they run together threads from number theory, group theory, and combinatorics to establish an important result, their book makes an ideal basis for an undergraduate capstone course. ^BSumming Up: All three books: Recommended. Upper-division undergraduates through professionals. D. V. Feldman University of New Hampshire
Table of Contents
| An overview |
| 1 Graph theory |
| 2 Number theory |
| 3 PSL2(q) |
| 4 The graphs Xp, q |
| Appendix A 4-regular graphs with large girth |
| Index |
| Bibliography |
