Emmy Noether Lectures

Nowadays we are surrounded by numerous large information networks, such as the WWW graph, the telephone graph and various social networks. Many new questions arise. How are these graphs formed? What are basic structures of such large networks? How do they evolve? What are the underlying principles that dictate their behavior? How are subgraphs related to the large host graph? What are the main graph invariants that capture the myriad properties of such large sparse graphs and subgraphs. In this talk, we discuss some recent developments in the study of large sparse graphs and speculate about future directions in graph theory.

Brief Biography

Fan Chung is an exceptionally productive and influential world-class scholar whose impact has been felt in the classroom, the academy, and the corporate world. Her research interests are primarily in graph theory, combinatorics, and algorithmic design, in particular, in spectral graph theory, extremal graphs, graph labeling, graph decompositions, random graphs, graph algorithms, parallel structures and various applications of graph theory in Internet computing, communication networks, software reliability, and various areas of mathematics and the natural sciences. She has recently been conducting a mathematical analysis of PageRank, a new and important graph invariant concerning correlations between vertices in a graph.

Dr. Chung has made significant contributions to several fields. In combinatorics she has conducted important research in counting Baxter permutations, determining sharper bounds for various Ramsey numbers, in creating, with Ronald L. Graham, the theory of quasi-random combinatorial objects, and in many other areas. In graph theory she has notable results concerning Steiner trees, and a whole sequence of papers, partly with S. T. Yau, concerning the Laplacian of a graph and its significance and properties and implications. Recently she has been interested in the graph-theoretic structure of the Internet, and specifically of the World Wide Web. In that area she has found a number of graph-theoretic statistics and some arresting connections with the Riemann zeta function.

Professor Chung currently holds the positions of Professor of Mathematics, Professor of Computer Science and Engineering, and Akamai Professor in Internet Mathematics at the University of California, San Diego. She was formerly the Class of 1965 Professor of Mathematics at the University of Pennsylvania. For the 20 years following her doctoral studies, she held research positions at Bell Labs and Bellcore, where she headed the Mathematics, Information Sciences and Operations Research Division and directed research groups in combinatorics, algorithms, cryptography, and optimization. At Bell, Fan met and collaborated with many research scientists and mathematicians, including Ronald L. Graham who was to become her husband. At Bell, Fan developed and honed her talent for making connections with seemingly disparate areas of mathematics and the sciences and with the practitioners of those disciplines. She visited Harvard University in 1991 as a Bellcore Fellow and a few years later returned to academia.

Dr. Chung has been awarded numerous honors and awards for her groundbreaking work in spectral graph theory, discrete geometry, algorithms, and communications networks. She has written over 240 papers with about 120 coauthors. Dr. Chung has written 3 books: Spectral Graph Theory, Complex Graphs and Networks (with Lincoln Lu) and Erdös on Graphs (with Ronald L. Graham). She has been a fellow in the American Academy of Arts and Sciences since 1998, an invited speaker at the International Congress of Mathematicians in Zürich (1994), and the recipient of the Mathematical Association of America Allendoerfer Award for expository excellence for her article “Steiner Trees on a Checkerboard” co-authored with Martin Gardner and Ronald L. Graham (1990). She is a magnet for very bright students at UCSD, and has frequently published joint research with them.

The daughter of an engineer, Fan grew up in Kaoshiung, Taiwan. She received a B.S. degree in mathematics from National Taiwan University in 1970 and her Ph.D. in mathematics from University of Pennsylvania in 1974 under Herbert Wilf who directed her thesis entitled “Ramsey Numbers in Multi-Colors.”