This week, I am presenting the second of my ongoing series of interviews with influential mathematicians.

Fan Chung Graham (born in Taiwan in 1949) is one of the world’s leading graph theorists and combinatorialists, with major contributions to spectral graph theory, random and quasi-random graphs, Ramsey theory, extremal graph theory, and complex networks.

Fan is a professor at University of California, San Diego, where she holds the Paul Erdős Chair in Combinatorics. She spent a sizeable portion of her career working in industry at Bell Laboratories and Bellcore.

She published hundreds of papers and three books in mathematics, and remains very active in research. Fan won numerous awards for her mathematical work, and was inducted as a fellow of the American Mathematical Society in 2012.

I first met Fan in Vancouver in 2003 at the Workshop On Algorithms And Models For The Web Graph. My first memories of her were approachable, witty, and brilliant. Years later, I visited her home in La Jolla during a research visit at UCSD. I have great memories of walking through the cliff-top trails along the shore musing about the current and future directions of mathematics.

Fan is married to mathematician Ron Graham, and the two form a mathematical power couple. Ron is not only a stellar mathematician, but also an accomplished juggler and trampolinist.  The Simons Foundation completed some recent, terrific interviews with Ron, who recently turned 80.

In January 2016, a retirement conference was held for Fan and Ron at UCSD. Although they deserve the rest, it is difficult to imagine mathematics without them.

Below is the transcript from my interview with Fan. Her wit and wisdom shines through as brightly as ever.

Enjoy!

AB: How did you first realize you wanted to study mathematics?

FCG: I loved geometry in middle school in Taiwan (which is equivalent to the 9th grade here). I was pretty good at puzzles. There were always these curiosity and problem solving components to my work.

My father was the one who said when you are choosing your major, if you choose mathematics then you can easily change to other areas, and not vice versa. He was completely right. Although I didn’t change to other areas, the kind of mathematics I’ve been doing easily branches into subjects like computer science. Even now I hold a joint appointment in the departments of Mathematics and Computer Science at UCSD. In fact, so many areas of computer science nowadays really involve beautiful mathematics, leading to good research directions. The situation is just like physics in the old days. A lot of inspiration now is coming from information theory and computer science.

AB: Seguing off that, can you describe how real world applications such as complex networks have influenced your work?

FCG: I think combinatorics and graph theory in particular, is a beautiful area but it also has connections with so many other disciplines. With the rise of network science, graph theory plays a vital role in laying the foundation for the rigorous analysis of modelling real world networks. In the other direction, we feel the influence also: problems in information networks really enrich the research in graph theory. They often point to many central directions.

For example, random graphs can be used to study real world networks. Classical random graph models use equal probability distribution on nodes and edges; each has equal importance. This doesn’t happen in real networks. This idea opens up a whole range of problems and directions in studying extremal and random graph problems in a much richer context.

AB: What led you to work with Herbert Wilf as your doctoral supervisor?

FCG: Herb had a huge influence in my research and career. I was lucky to run into him. I have never really taken classes in graph theory before I met Herb. Before I met him, I didn’t even know the existence of such an area.

I remember the day vividly when he walked into the office of graduate students where I was working. Later on, he told me he usually approached doctoral students who passed their qualifying examinations with the highest scores.  At University of Pennsylvania, I was a very good student, so he came to talk to me.

He introduced me to combinatorics by telling me research problems.  I had a good background in mathematics when I was an undergraduate at National Taiwan University, where I took many advanced courses. With Herb, I really started to learn how to do research. I used what I learned to attack research problems.

He gave me many good problems. In our first meeting it was a Ramsey number problem, and that topic is always delightful. It was a multi-color Ramsey number problem, which was an old one. At that time, I didn’t know its history. I just picked up the problem and found a better bound.

AB: How did you do that? Did the ideas for the proof just come to you?

FCG: You know how it works with mathematics: you just work with pen and paper. I was just playing around. Ramsey problems is like a puzzle; in combinatorics it is about finding or avoiding patterns. These are classical problems.

My result is still the best one to date for triangle with multi-colors. At that time, I didn’t realize that. I just solved a problem! Herb was really very enthusiastic hearing my solution, and encouraged me onwards. After that, I started working with Herb.

Herb had a gift of choosing terrific problems. He was an excellent teacher but also a great mathematician. Recently, I co-authored an article in the American Mathematical Society Notices about him. As a student, I solved one problem of his after another; altogether, I solved four problems. It was tremendously enjoyable working with him.

AB: You’ve had an impact on many areas such as spectral graph theory, Ramsey theory, and complex networks. Did you move between these areas by accident or design (or both)?

FCG: Both. After I received my PhD, I start working at Bell Labs. At that time, we had a lot of interesting people coming through, like Paul Erdős and Joel Spencer. I was doing extremal graph theory at the beginning, and it was much like the Hungarian school; they are so strong in that area.

In looking back, I moved from one area gradually to another. One area that I think is quite central is quasi-randomness. In extremal graph theory, you usually study one graph property and relate it to another. For example, if a graph has too many edges, then some pattern appears, like cliques or complete bipartite graphs.  At some point, it was quite natural to take all these properties and put them in their rightful places.

The study of quasi-random graphs is used to identify these graph properties that look different but are in fact equivalent. These properties happen to be satisfied by random graphs. If you want to validate one property, then you choose the easiest one and you get them all. Quasi-random graph properties unified random and extremal ideas. To me, randomness in graphs is defined by properties of graphs.

We worked on quasi-random graphs, hypergraphs, and other structures like sequences. But although we wrote all these papers (on quasi-randomness), not many people were following up (at the time), although I know it was a really good topic. Maybe we wrote too many papers on this area. We decided to stop for a while. Ten years later, there is huge following in the area, with results cited in at least four textbooks, and a great deal of new developments.

Then I moved to spectral graph theory, which I think is a major graph invariant. Think of a complicated structure far away, like a distant galaxy. We want to use relatively few parameters or quantities to nail down its properties. Spectral graph theory uses eigenvalue or the spectral gap to tell the shape of the network.

From the very beginning, I realized spectral graph theory was central. But the classical work in the area was algebraic, using tools from group theory and linear algebra. If the graph is very symmetric (for example, vertex- or edge-transitive, or even distance transitive), then the spectrum is short with high multiplicity.

Nowadays, in real-world networks, you can’t see the whole structure, and these networks are far from regular. For example, think of internet networks or social networks. I realized that spectral graph theory could be viewed geometrically rather than algebraically. The algebraic approach has clear rules and you nail down things precisely. Geometrically, you want to simplify the structure… just get the first order of things. In particular, I realized the connection with spectral geometry, its continuous counterpart.

The spectral graph theory I am doing is great for working with general graphs; that is, non-regular ones. The spectral gap will capture its shape, rather than in the usual adjacency matrix which might capture a few large degrees. To use eigenvalues to study the shape of the network, we had to use the normalized Laplacian. The formulation is a bit complicated; it isn’t just a 0-1 matrix. But the normalized Laplacian relates to random walks, diffusion, and the shape of the network. I knew it was harder to get this formulation accepted by other graph theorists, but I realized it was the right way to see it.

In spite of the early resistance, it was clear to me that the normalized Laplacian was the right way to proceed. In the beginning, most people used it in computer vision and optimization, as they had to deal with subgraphs. Subgraphs of regular graphs aren’t usually regular.

Now, my approach to spectral graph theory has been accepted, especially in the algorithmic community and in complex networks. If the eigenvalues are known, then you can make a great deal of predictions about a network’s structure.

Looking back, I moved from one area to another, but the underlying mathematics is connected, and not so different.

AB: You worked in academia and in industry at Bell Laboratories and Bellcore. How would you compare working in industry versus academia? Do you prefer one to the other?

FCG: I had a great experience at Bell Labs. In the old days, we had so many good people. Those good days, however, are in the past. It was a very different environment compared to a university. Imagine having 3,000 PhDs working under one principal investigator all under one roof. In those days, we could recruit the top people, beating even top universities like M.I.T. or other places.

Because of my research, I made the transition to academia quite easily. Ingrid Daubechies and myself were some of the first women to get tenure at Ivy League schools; I moved to University of Pennsylvania and Ingrid Daubechies went to Princeton. The academic world is thoroughly enjoyable with great students. But it is different.

In Bell Labs, we tackled big projects sometimes. That function is now taken over to some extent by start-up companies. In the mathematics center at Bell Labs, we usually had smaller projects like our own research papers on topics of our own interest.

Another great thing about Bell Labs was that you could easily go across the boundary of one discipline to another: problem solving has no boundaries. You need to use tools from all directions. My office was next to Michael Garey and David Johnson who worked in computer science, and I moved in that direction quite easily.

AB: Cross-disciplinary work happens quite a bit in academia, but it does feel that departments are too cloistered.

FCG: Not only because of the department division lines, but also because of the peer review process. You need to define which area you are. That is not helping you break into other areas. But still, peer review is the best way. For example, democracy is not always efficient. But what is the alternative? At the big labs those division lines were not there.

At UCSD, most of my co-authors are in computer science, which is a great source of great problems, especially in combinatorics.

AB: You and Ron Graham were some of the best-known collaborators and supporters of Paul Erdős. What was Erdős’s impact on your work and life?

FCG: That is actually a very good question. I look back and reflect on the papers from when I worked with Paul. In extremal graph theory, about half of my work was directly or indirectly with Paul. I have joint papers with him, but mainly I got problems from him. He was like a bird picking up seeds from different places. Whenever he came through, he would mention problems he heard from other places. If Paul was interested in a problem, then there was extra motivation to work on them.

One example is my work on graph pebbling, which is a popular problem now. I first heard that problem from Paul; it wasn’t his problem, but he told me about it. I liked hypercubes so I worked on it and wrote a paper. I included a conjecture at the end, which is now called the Graham conjecture. In fact, I had a casual conversation about it with Ron, and I put his name on it! Usually at the end of the paper, I like to put conjectures.

That summer Joe Galian ran his Research Experience for Undergraduates (REU) and he asked for some of my papers. I sent him the pebbling paper and that did the job. The students all started work on it, and other REUs at other places did too. Now, there is a huge following for this area.

AB: It was the seed that Erdős brought that you germinated, and it grew into a garden.

FCG: Exactly. I heard this problem from Erdős, gave the problem to Galian, and now every time I go to conferences there are papers in this area. This is one example of how Erdős’s problems propagated.

AB: What advice would you give students studying mathematics, especially young women studying in mathematics?

FCG: My answer is simple: don’t be intimidated. In mathematics, you can build up one step at a time. Once you do it, it’s yours. It is a big area, and no one knows everything.

AB: I am familiar with your painting and musicianship (I’ve seen you play piano and Chinese harp or guzheng). What draws you to the creative arts?

FCG: It works in a different part of your brain than mathematics. It is nice to transition between the two. I really enjoy watercolors and guzheng. I think it helps me; it complements rigorous mathematics thinking.

Mathematics and art are related in different ways. In watercolors, the work is done in layers. You have to wait until it dries. The color and texture can be different from what you expect. The challenge is to partition your picture into different layers, adding a conceptual viewpoint of how they all fit together. Painting is an interesting, unpredictable art-form.

I started by doing landscape and seascapes. I didn’t get too much progress, so I spoke to my painting teacher Maria Klawe, and also started to do portraits. I did portraits of mathematicians who influenced my work. Portraits are much harder as our eyes are so critical of human faces. I added one layer after another and a stranger stared at me back. A person emerged that was different than I intended, so I had to start again. It’s very interesting to reveal some aspect of your painting subject. You can’t include every aspect, but if you grab some aspect of the person, then it is a success.

It’s like mathematics: when you are proving theorems: you solve a small piece of the puzzle. Sometimes after you have done enough, there is a chance of developing a theory.

AB: What are some of the major directions now in mathematics?

FCG: In the old days, physics was a major driving force in mathematics. Nowadays, the new directions are often coming from data and network science. Combinatorics is serving as a bridge to these areas: bringing mathematics to them, but also bringing problems to mathematics. That influence is going to be a dominating force, and will be wonderful for mathematics.

Anthony Bonato