Alan Frieze (born 1945 in London, England) is one of the world’s leading experts on random graphs and the probabilistic method in combinatorics. He is a Professor at the Department of Mathematical Sciences at Carnegie Mellon University in Pittsburgh.

Alan is very productive. At last count, he has 351 papers (and counting) referenced on Mathscinet. His interests are extremely broad, and overlap with all aspects of random graphs, structures, and algorithms. The list of topics he works on is too vast to list, but some of these are Hamiltonicity, coloring, connectivity, Ramsey theory, matching, complex networks, random walks, packing and covering, vertex pursuit games, network routing, randomized algorithms, and online auctions.

Alan has numerous awards and distinctions. He won the Fulkerson prize in 1991, and he is Guggenheim Fellow, AMS Fellow, SIAM Fellow, and Simons Fellow. In 2014, he gave a lecture at the International Congress of Mathematicians; the featured image of this blog is a still from his talk there.

My first encounter with Alan’s work was near the beginning of the century, when I was learning about random graph models for complex networks. Alan is a thought leader on the topic, and his early copying model with Colin Cooper (one of Alan’s early PhD student’s, who is now an eminent researcher in the field of random graphs) became highly influential. I’ve since met Alan many times of the years, and he is funny, modest, and brilliant.

Alan remains active researching, writing and supervising students. His book Introduction to Random Graphs, co-authored with Michał Karoński, came out in early 2016.

Enjoy!

 

AB: How did you first become interested in mathematics?

AF: It was in elementary school, and it was always my best subject.

AB: Did any one person have an early influence on your choice of career?

AF: In high school when I was around 16 years old, a teacher joined the school who encouraged me. He gave me the book by Courant and Robbins called What is Mathematics? and that turned me on to the subject.

I found mathematics the easiest subject to do, and I assumed I would go to university. So I chose mathematics.

AB: Did that interest carry through your university education?

AF: I was at Oxford for three years. I wasn’t sure I wanted an academic career or that I could even have one. No one talked to me about such a career. So I assumed that when I graduated, I would have to get a “proper job”.

When I finished Oxford, I had limited knowledge about what my opportunities were. I looked into becoming an actuary, but rescued myself from that.

AB: Fortunately for us!

AF: I decided to do a Masters in another university to take some time to figure out what I want to do. So I went to Sussex for a year.

I saw a book by Churchman, Ackoff, and Arnoff called Introduction to Operations Research. In it there was a description of the Hungarian algorithm for the assignment problem. I thought it looked quite neat so I thought that I would give operations research a try. I went to work for British Rail for a year in their operations research department. It wasn’t a great experience and I left after a year.  I then worked for a company called International Computers Limited, which is now defunct. It was Britain’s answer to IBM. I worked there for 18 months. It was useful, as I learned how to write computer programs. I realised that I didn’t want to spend my life writing machine code, so I decided to try to get into research.

Initially, I thought that going back to university would be too difficult, so I went to the Polytechnic of North London. At that time in England, there was a two-level system, with the polytechnics more teaching oriented. They were something like a community college.

I started teaching at PNL and I thought I that should do a PhD. I found Keith Wolfenden at the University of London Institute of Computer Science. At that time, computer science wasn’t established as a subject in universities. I did a part-time PhD with him in operations research.

Fortunately, at that time, Keith was filling in for a course in Queen Mary College on operations research. He suggested I apply, so I applied and got the job there. I was there from 1972 to 1987, with one gap when I was at Carnegie Mellon University in 1983, teaching the Mathematics of Operations Research in the business school.

AB: How did you end up at Carnegie Mellon University?

AF: The political situation at the time in England was getting bad for the universities. Margaret Thatcher and her henchmen were busy saving money by slashing university funding. The situation also wasn’t good for our children’s school, so I decided to leave Queen Mary College.

Also, there was a problem with promotions at Queen Mary College. I thought about leaving and going to the US. I didn’t know where to go. I knew Peter Hammer at Rutgers, and I knew plenty of people at Carnegie Mellon University. The Mathematics department at Carnegie Mellon was looking for someone to teach operations research and discrete mathematics, I fit the bill and I have been there ever since.

AB: Random structures and algorithms dominate almost all of your work. Can you tell us how you came to focus on this topic?

AF: When I started, I came out of operations research background. When I did a PhD, I did it in operations research. I was doing it on integer programming. It was difficult at the time to keep up with the literature. There was no internet, or at least we didn’t have it, and people would send papers to each other by letters. I was out of the loop and there was no one to talk to.

I was doing programming, trying to write algorithms that ran fast. The equipment wasn’t good; they upgraded the system and it got even worse. I decided to stop doing that.

I did some very early approximation algorithm work, which we called worst-case analysis at the time. It was all very negative.

About that time, we were organizing conferences on combinatorial optimization. The first one I went to was called Combinatorial Programming or something similar, I think in 1979 in Liverpool. I was sitting in the audience when Colin McDiarmid gave a talk on his work with Geoffrey Grimmett on random graphs, and it was a revelation!

I hadn’t been interested in probabilistic things, but Colin’s talk was positive, talking about graph coloring. I thought it was great and I wanted to study this.

I read Erdős and Rényi’s paper On the Evolution of Random Graphs. I started work with Trevor Fenner mainly on the m-out model. We managed to prove 23-out was Hamiltonian. This was the start of work on a problem that I didn’t finish until  some 25 years later in  2010. I got 23 down to 3 with Tom Bohman.

I remember sitting in my office in Queen Mary, College and the phone rang and it was Béla Bollobás. He invited Trevor and I up to Cambridge. I spent a few years working with Béla. I learned a lot working with him.

At this time, Dick Karp was writing papers on the probabilistic analysis of algorithms and I was captivated. I met Martin Dyer and we had a common interest in the area and we had a really great collaboration for several years.

AB: Why is randomness so important in modelling nature and networks?

AF: That is a difficult question. If a process produces varied outcomes, but you cannot explain exactly how it works then you can partially explain this way via randomness. It is somewhat of a mystery as to why probability theory is such a good model for actual real world processes.

AB: You are highly productive with hundreds of research articles spanning many areas of graph theory and theoretical computer science. What are your favorite results? Can you briefly summarize one or two?

AF: I do tend to write too many papers!

The paper with Martin Dyer and Ravi Kannan on estimating the volume of a convex body was probably the most important one. We were thinking about it together at the right time. Andrei Broder introduced the idea of using a Markov chain for counting things. Jerrum–Sinclair had corrected his argument, and brought out the idea of using conductance. Martin and I had been working on the hardness of computing the volumes of polyhedral. Ravi wanted to work on computing volumes.

The initial approach wasn’t going anywhere, so we tried the Markov chain method. We were stuck for a bit, but we eventually found a way through. The running time was polynomial, but with a large exponent O(n²⁶). Many people have improved that bound now so it is more feasible. The algorithms are now almost practical.

My result on spanning trees and ζ (3) was a nice one. The first proof was rather inelegant and definitely not the Book proof but I managed to make it work. At the time, there were few journals to submit to it to so I submitted to SIAM Journal of Applied Mathematics, and it was rejected on the basis that it wasn’t applied math. So I sent it to Discrete Applied Mathematics. My experience with this paper shows the need for sympathetic journals.

I should also mention my work with Ravi Kannan on a ”weak regularity lemma”. This seems to have turned out to have led to some useful concepts, for example, the cut-norm. There is also my work with Ravi and Santosh Vempala on estimating the singular value decomposition of a matrix. This line of work has blossomed since then.

AB: Can you tell us something about your recently published book Introduction to Random Graphs? Why did you decide to write it at this point in your career?

AF: For the community, the books available are a bit daunting and we wanted to write something that started more slowly, but which was as up to date as possible.

I wasn’t planning to write a book. I gave a course on random graphs at Carnegie Mellon University, and I had my notes written on a tablet. I put them on the web. I realised after the course that I had the basis for a book. I thought it would be nice to work with someone on it, and Michał seemed like a good partner.

It took a lot longer than we anticipated. I was working on other things, and he was in charge of organising a Polish version of the National Science Foundation.

It was difficult also as the subject has grown so much, and is still growing. I get a feed from arXiv, and nearly every day something new is coming out on random graphs. We have a spot in the back of the book where we try to reference as many topics as we can.

AB: Thank you for mentioning the game of Cops and Robbers there.

AF: That’s alright.

AB: I am fascinated by how mathematicians so often cite aesthetics as a guiding principle in their work. Do you tend to focus on pretty problems or solutions in your work?

AF: I like the problem to be natural, and not too contrived. The simpler the problem is to state, the better. The solution itself can be ugly.

AB: Is mathematics an art or science?

AF: I don’t think that is a very useful question. Giving it a label as an art or science doesn’t seem to help. Although obviously mathematics is much more important to science than it is to art.

AB: Do you have any hobbies distinct from your mathematical work?

AF: I used to be quite sporty, but less so now. Apart from family life, I read a lot, and I like movies. I rekindled my interest in soccer, I am a keen follower of the Premier League, Arsenal F.C. in particular.

AB: What advice would you give a young person thinking about studying mathematics?

AF: I have always been fascinated by mathematics. It is a subject of great beauty and it is a pity that most people do not get to appreciate this.  This interest has certainly been good for me. Everybody who is able should learn more of the subject.

If you want to take it further and be employed as a mathematician, then there are now many opportunities. You can work in Finance, Operations Research, etc.

An academic job at a research university is really quite pleasant. You can work with great freedom on things that interest you.

AB: Graph theory is now a rapidly evolving discipline, with deep connections to many disparate fields. What do you think are some of the major trends in graph theory and random graph theory?

AF: Modelling real-world networks is one area that has taken off. Another direction is the intersection of extremal graph theory and random graphs. Random graphs are now very much accepted in computer science. It is an important area in applied probability. We have leading probabilists taking an interest. The subject develops as part of probabilistic combinatorics. Nati Linial has been encouraging people to work on random simplicial complexes.

There is no doubt that the probabilistic approach will expand into other areas of mathematics.

 

Anthony Bonato