Summer reading seminar 2008
A few words on research for graduate students
Fan Chung Graham
(professional name:
Fan Chung ,
Chinese name 
)
is the Akamai Professor in Internet Mathematics
at UC San Diego.
Previously, she
had taught
at U Penn, worked
at Bell
Labs in its glory days, and directed some great research groups
at Bellcore.
Her research interests are primarily in graph thoery, combinatorics and algorithmic design.
In particular, she is known for her work for initiating and developing three fundamental areas in combinatorics:
- Spectral graph theory.
In her book
Spectral Graph Theory, a normalized and powerful Laplacian for gener
al
graphs was introduced and examined.
The eigenvalues of the Laplacian
capture fundamental properties of a graph/network and
have connections with
the pure (spectral geometry, extremal graph theory, representation theory, etc)
and the applied (Markov chains, approximation algorithms,
segmentation, computer vision, Internet algorithms, etc).
Recently she has been working on spectral aspects of directed graphs.
-
Random
graphs with general degree distribution
with applications to complex networks.
Graph theory has emerged as a primary tool for detecting numerous
hidden structures in various information networks, including
Internet graphs, social networks, biological networks, or
any graph representing relations in massive data sets.
One of the main tools is
random graph theory for general degree distributions.
On this topic, a new book
Complex graphs and networks
coauthored with Lincoln Lu was recently published by AMS, based
on ten lectures
given at
the
CBMS Workshop on
"The Combinatorics of Large Sparse Graphs"
2004.
There is
a new journal
Internet Mathematics
,
for which she serves as the
Editor-in-Chief. Her on-going research
focuses on exploring the structure of large
random-like graphs and the relationship with its subgraphs as well as developing
efficient local algorithms.
-
Quasi-randomness.
A large family of graph properties, all of which
are shared by random graphs, were shown to be equivalent in the sense that if a
graph satisfies one of the properties, it must satisfy all of them.
The list of equivalent graph properties includes some hard-to-compute
properties such as the expansion property,
the discrepancy property, subgraph enumeration properties as well as some easy-
to-compute
properties such as the eigenvalue property and four-cycle properties.
This
provides a validation scheme for
approximating one graph property by using other equivalent properties.
The theory of quasi-randomness
was introduced through
a
series of papers and recently has been further developed in additive combinatorics.
A topic of her on-going work is sparse quasi-random graphs for graphs with general degree distribution.
Recently, she has been working on
a new topic ---
the mathematical analysis of
PageRank, which is a new and important graph invariant
concerning correlations between vertices in a graph.
The analysis of PageRank and its variations uses both probabilistic and spectral methods with
special emphasis on graph partitioning.
Further variations using
the (discrete) heat kernel are examined as well as their implications on
local partitioning algorithms.
Other topics that she has investigated now and then include:
|
Ramsey theory|
universal graphs|
unavoidable graphs|
diameter|
average distance|
graph embeddings|
parallel computing|
communication networks|
discrete geometry|
algorithms|
Steiner trees|
Buckyball|
hypercubes|
codes|.
She has written over 240
papers
and
has
about 120
coauthors.
In addition to Spectral Graph Theory and
Complex Graphs and Networks (coauthored with Lincoln Lu), she has a third book
Erdös on Graphs,
coauthored with Ron Graham.
She serves on the editorial boards of a dozen or so journals.
In 1990, she was awarded the Allendoerfer Award by Mathematical Association of America.
In 1994, she gave an invited talk at the International Congress of
Mathematicians (ICM) in Zürich.
Since 1998, she has been a fellow of American Academy of Arts and Sciences.
In January 2008, she gave a Joint AMS-MAA Invited Address at the annual meeting.
Related links: