Fan Rong K Chung Graham

Quick Info

9 October 1949
Kaohsiung, Taiwan

Fan Chung is a Taiwanese-born American mathematician who works mainly in graph theory.


Fan Chung's father was an engineer. She attended high school in Kaohsiung, Taiwan and was encouraged to take up mathematics by her father who told her [2]:-
... in math all you need is pencil and paper.
She entered the National Taiwan University to read for a B.S. in mathematics. In [1] she described how she was encouraged to think in terms of a career in mathematics by interaction with her fellow students:-
As an undergraduate in Taiwan, I was surrounded by good friends and many women mathematicians. We enjoyed talking about mathematics and helping each other. A large part of education is learning from your peers, not just the professors. Seeing other women perform well is a great confidence builder, too!
It was during her years as an undergraduate in Taiwan that she was first attracted to combinatorics, the area in which she was soon to begin research [2]:-
... many problems from combinatorics were easily explained, you could get into them quickly, but getting out was often very hard ... Later on I discovered that there were all sorts of connections to other branches of mathematics as well as to many applications.
Chung graduated with a B.S. in mathematics in 1970 and then went to the United States for her graduate studies. She entered the University of Pennsylvania but at first Herbert Wilf, Professor of Mathematics at the University of Pennsylvania, hardly noticed her. Wilf writes (see [1]):-
I never paid any attention to the graduate students until they got past their qualifying exams. My policy then was to go after the best student and try to get him to go into combinatorics. The year she took the exam, 1971, she had the highest score by far-there was a huge gap between her and the next best student. So I immediately sought her out - I had never spoken to her before - and asked her if she knew anything about combinatorics. She said she knew a little from her days at Taiwan National University but not too much. I pulled out one of my magnetic subjects, Ramsey theory, that is guaranteed to get graduate students hooked on combinatorics because it is very pretty stuff. I gave her a book and told her to read the chapter on Ramsey theory. We set up an appointment in a week to talk about it. When she came to the appointment, I asked her how she liked the chapter. She smiled and said it was fine. Then she flipped the book open to a key theorem and said, gently, "I think I can do a little better with the proof." My eyes were bulging. I was very excited. I asked her to go to the blackboard and show me. What she wrote was incredible! In just one week, from a cold start, she had a major result in Ramsey theory. I told her she had just done two-thirds of a doctoral dissertation. "Really?" she said softly. In fact, the result did become a major part of her dissertation.
Chung was awarded an M.S. in 1972, then continued her studies for a Ph.D. with Wilf as her supervisor. She had found her first original results in Ramsey theory and it led to the publication of her first paper On the Ramsey numbers N(3, 3, ..., 3; 2) which appeared in Discrete Mathematics in 1973. In this paper she proved that if f(k)f (k) is the Ramsey number N(3,3,...,3;2)N(3, 3, ..., 3; 2) where there are kk 3s, then N(3,3,3,3;2)>50N(3, 3, 3, 3; 2) > 50 and f(k+1)3f(k)+f(k2)f (k+1) ≥ 3f (k) + f (k-2).

Also in 1973 Chung attended the Capital Conference at George Washington University in Washington, D.C. There she presented a paper On triangular and cyclic Ramsey numbers with k colors which was published in the Proceedings of the Conference in the following year.

By this time Chung was married and she had her first child in 1974 before submitting her doctoral thesis [2]:-
That is a wonderful time to have a child. You don't have to attend classes; you only have to write your thesis.
In 1974 Chung graduated with a Ph.D. from the University of Pennsylvania and applied for a job as a member of Technical Staff working for the Mathematical Foundations of Computing Department at Bell Laboratories in Murray Hill, New Jersey. She was appointed and she began working under Henry Pollak who would be her superior at Bell Laboratories for many years. There were many other leading mathematicians working for Bell Laboratories at this time such as Ron Graham and Sloane. She quickly began to collaborate with others at Bell Labs and produced a steady stream of mathematical papers [2]:-
Finding the right problem is often the main part of the work in establishing the connection. Frequently a good problem from someone else will give you a push in the right direction and the next thing you know you have another good problem. You make mathematical friends and share the fun!
In 1975 she published Optimal rearrangeable graphs in which she gave a method of finding the minimum number of edges a rearrangeable graph may have for any choice of nonempty subsets of its vertex set. A Kandel, reviewing this paper wrote:-
This contribution is quite relevant to applied problems, since many problems in switching networks can be viewed in graph-theoretic terms. For example, instead of minimizing the number of crosspoints to reduce the cost of the network, one can consider the problem of finding a graph with the minimal number of edges.
Also in 1975 Chung published her first joint paper with Ron Graham On multicolor Ramsey numbers for complete bipartite graphs which appeared in the Journal of Combinatorial Theory.

While working at Bell Laboratories, Chung became pregnant again [2]:-
I told [Henry Pollak, my manager] that I would work until the day I went to the hospital. Since I already had one at home, I thought what's the problem with one more? I didn't even take maternity leave; there was too much paperwork associated with that. So I just took four weeks vacation and wrote one paper in between.
Her second child was born in 1977 but Chung's marriage was not a successful one and it ended in divorce in 1982. She would marry Ron Graham in 1983 but she continued to publish under her original name of Fan Chung. Graham has said (see [1]):-
Many mathematicians would hate to marry someone in the profession. They fear their relationship would be too competitive. In our case, not only are we both mathematicians, we both do work in the same areas. So we can understand and appreciate what the other is working on, and we can work on things together-and sometimes make good progress.
In 1983 the Bell Telephone Company was split up. Bellcore (Bell Communications Research), and other companies, was set up and Henry Pollak became head of a research unit within the newly formed company at Morristown, New Jersey. He asked Chung to become Research Manager and help him develop the unit:-
For the next seven years, in addition to my research, I had to write reports, attend meetings, and read the research papers of mathematicians I supervised.
She was promoted to Division Manager of Mathematics, Informations Sciences and Operations Research at Bellcore in 1986, a post she held for four years. In the autumn of 1989 Chung became a visiting professor at Princeton. It marked the beginning of a new association with the academic world. In 1990 Bellcore created the idea of a Fellow who would spend a sabbatical at a university. Chung was one of the first to receive such a Fellowship and she went to Harvard:-
It is not easy for some people to leave management, but it was not so hard for me. Usually with positions in management you obtain more influence and you certainly have more power to make decisions. But I do not want people to respect me because of that power. I'd rather win their admiration because of the mathematics I'm doing.
This year was to have a huge influence on Chung who decided to return to the academic world but she did not formally leave Bellcore until 1994. In 1991, however, she became a visiting professor at the Mathematics Department at Harvard University. In August of that year she presented a joint AMS-MAA lecture Laplacians of graphs and hypergraphs in Orono, ME. The lecture was produced on a videocassette by the American Mathematical Society and it comes with the following description:-
"Can you hear the shape of a graph?" may sound like a nonsensical twist on the famous drum problem, but in fact it captures an intriguing analogy between manifolds and graphs. In this clear and well-paced lecture, the noted graph theorist Fan Chung exploits this analogy to produce some interesting and useful results. She starts with a historical perspective on graphs, their uses in computer science, and their inherent mathematical interest. She discusses Laplacians of graphs and hypergraphs from both the homological and graph-theoretic viewpoints. The eigenvalues of the Laplacians can be related to various properties of hypergraphs and used to strengthen and imply previous graph-theoretic results. A variety of applications to extremal combinatorics and computational complexity are discussed, in addition to a number of open problems.
She gave an invited address to the International Congress of Mathematicians in Zürich in 1994. The same year she resigned from Bellcore and spent a year at the Institute for Advanced Study at Princeton before accepting a professorship at the University of Pennsylvania which she took up in 1995. After three years as Professor of Mathematics and Professor of Computer Science at Pennsylvania she was appointed Professor of Mathematics and Professor of Computer Science and Engineering at the University of California, San Diego. She also holds the Akamai Professorship in Internet Mathematics.

We have already given some details of Chung's first few publications. Her interests are wide and among her nearly 200 publications there are contributions to spectral graph theory, extremal graphs, graph labelling, graph decompositions, random graphs, graph algorithms, parallel structures and various applications of graph theory in Internet computing, communication networks, software reliability, and discrete geometry. In 1997 the American Mathematical Society published a major book Spectral graph theory by Chung. In this book she writes:-
... the underlying mathematics of spectral graph theory through all its connections to the pure and applied, the continuous and discrete, can be viewed as a single unified subject.
Spectral graph theory studies how the spectrum of the Laplacian of a graph is related to its combinatorial properties. Chung studies this topic from the point of view of spectral geometry in this book drawing the analogy to the spectrum on Riemannian manifolds.

Only one year later, in 1998, another important book appeared, this time jointly written by Chung and her husband Graham. This is Erdős on graphs and in it many of the problems and conjectures in graph theory made by Paul Erdős are listed. It was based on an article Chung published on the same topic in the previous year in the Journal of Graph Theory. Undoubtedly R H Schelp is right when he wrote in his review of the book:-
Surely many of the Erdős problems presented here will remain open for years to come, providing a challenge to future graph theorists. Thus this text will be an important reference volume for the graph theory researcher.
Chung and Graham were not only associated with Erdős through his mathematics, but they also were close personal friends with their home providing for him the only place he had as a base.

It is worth noting the tremendous contribution Chung has made, and continues to make, as a member of the editorial board of various journals. Since the mid 1990s she has served on, and in most cases continues to serve on, the boards of 17 journals. She has also served on the Council of the American Mathematical Society (1989-91) and on several of its committees. Similarly she has also served on the Council of the Society of Industrial and Applied Mathematics (1990-92) and on several of its committees.

Finally we should note that Chung was honoured with the Allendoerfer Award by the Mathematical Association of America in 1990 and by membership of the American Academy of Arts and Science in 1998.

She has made other substantial contributions to the mathematical community with her editorial work, serving on the editorial boards of Mathematics Research Letters, Random Structures and Algorithms, SIAM Journal on Discrete Mathematics, the Journal of Combinatorial Designs, SIAM Review, the Journal of Graph Theory, Annals of Applied Mathematics, the Journal of Combinatorial Optimization, Annals of Combinatorics, the Taiwanese Journal of Mathematics, the Journal of Computer and System Sciences, and Mathematical Systems Theory. In addition she has served as Co-Editor-in-Chief of Advances in Applied Mathematics and the Electronic Journal of Combinatorics, and as Editor-in-Chief of Internet Mathematics and the Journal of Graph Theory.

To give an idea of her recent work let us quote from the abstract for the talk Random Graphs and Internet Graphs which she gave at the University of Manchester in June 2005:-
We will discuss some recent developments on random graphs with given expected degree distributions. Such random graphs can be used to model various very large graphs arising in internet and telecommunications. In turn, these "massive graphs" shed insights and lead to new directions for random graph theory. For example, it can be shown that the sizes of connected components depend primarily on the average degree and the second-order average degree under certain mild conditions. Furthermore, the spectra of the adjacency matrices of some random power law graphs obey the power law while the spectra of the Laplacian follow the semi-circle law. We will mention a number of related results and problems that are suggested by various applications of massive graphs.

References (show)

  1. P Hoffman, The man who loved only numbers (London, 1998).
  2. D Albers, Making Connections : A profile of Fan Chung, Math. Horizon (Sept. 1995), 14-18.

Additional Resources (show)

Honours (show)

Honours awarded to Fan Chung

  1. Noether Lecture 2009

Written by J J O'Connor and E F Robertson
Last Update September 2009