László Lovász im Gespräch – Wie nehmen mathematische Ideen Gestalt an?

Raffaella Mulas: Thank you so much for taking the time to meet me. It is an incredible honor and a privilege for me to interview one of the mathematicians I admire the most. I would like to start from the beginning. As a teenager, you earned three gold medals at the International Math Olympiad. You also won a Hungarian TV show in which students were placed in glass boxes and asked to solve mathematics problems. Is this true?

László Lovász: Yes!

Is this when your passion for mathematics started, and what drove you into mathematics at such a young age?

Well, it started a little earlier, maybe in the 8th grade, when I joined the math club of my elementary school. I really enjoyed working on the problems that were posed there, and the teacher of the math club, who was also the director of the elementary school, recommended us to subscribe to a Hungarian journal of mathematics for high school students. The journal was established in 1893, and I think it's the oldest one in the world which is still functioning. And that was a great experience! Paul Erdős used to write for the journal as well. He liked to pose some open problems that were easy to formulate but difficult to solve, and he always presented them together with some historical remarks. This was really very inspiring!

So, you were still in elementary school when you first read something written by Erdős for this journal, right?

Yes, I think so! One of the first issues that I was looking at had an article of Erdős about combinatorial geometry. Anyway, the teacher of the math club also recommended that I apply for the Fazekas Mihály Gimnázium, a high school that was starting a specialized class for mathematics. The Fazekas Mihály Gimnázium then became quite famous precisely for its mathematics classes, but it also attracted other good students in other areas. For instance, while I was there, in a parallel class there was Éva Kondorosi: she is a biologist and one of the Chief Scientific Advisors of the European Commission. So, it is a very good high school, in general.
There I met several other young people who were recruited for the same class, and that turned out to be an excellent community in which to learn and do mathematics. The four years I spent there were really fantastic in my life! And since the mathematics class was newly established when I joined, mathematicians from both the university and this institute [Alfréd Rényi Institute of Mathematics] were very interested in what was happening there. They used to give some afternoon classes at our school, and some of us started to regularly visit some of the professors, from whom we got new theory to read or problems to think about. So, many of us started doing some research during high school.

Wow! Well, this all worked out very well! Let's jump ahead now: Your work spans many areas of mathematics and theoretical computer science. What has been the most exciting research project for you, so far, in your career?

Oh, I think this has changed over time. Looking back, probably my largest project has been graph limit theory, which started in the early 2000s. When I was at Microsoft, several of us started to work on it, including my wife Kati [Katalin Vesztergombi], Balázs Szegedy, Vera Sós—who passed away a few months ago, very sadly—Jennifer Chayes, Christian Borgs and Lex Schrijver, whom you might have met or will meet in Amsterdam. And others have played some role or contributed at various stages too. I think that this has been my largest project. I have always liked things which connect different areas of mathematics, and the name "graph limits" already indicates that there is a connection going on between graphs and limits.
But I also liked, mostly in the 70s and 80s, when the theory of computing was developing. To me, it was clear that this was a mathematical theory, and that was a very exciting period. I am not sure I contributed so much to that, but I was interested, and I wrote papers. What was exciting as well is that it led to some new graph theory problems. I worked on them also together with Tibor Gallai, who was my mentor during university. There was no official PhD supervisor at the time, but he put in a lot of time and energy to help me to get ahead. I remember that he said, "Look at these two problems: the Hamilton cycle problem, and the matching problem. The matching problem has been solved in almost every possible sense, and the Hamilton cycle is very similar. Why is it so difficult, then?". And so, many of us started to think that maybe there was a reason for that. We started to think about it in terms of computational complexity, but we didn't get the right approach there. We then tried to work on Kolmogorov complexity, to see if there is any difference, but that also didn't work out.
Then, in 1972-73, I did what we would now call a postdoc. I went to the States, to Vanderbilt University, for one year, while my friend Peter Gacs, who was also interested in this topic, went to Moscow. There, he worked with Kolmogorov and with Leonid Levin, who was a student of Kolmogorov and who developed the P and NP theory essentially in the same way as (in the west), Stephen Cook and Richard Karp developed it. So, Peter Gacs and I both spent a year abroad, and when we met again, we immediately told each other that we could finally see the difference between the matching problem and the Hamilton cycle problem. We were very enthusiastic! And after that, for two weeks we even thought that we could prove that P is not equal to NP. Our proof was nice, but at the end it wasn't right, as it proved something weaker. But anyway, we kept focusing on this area, and we organized a seminar here [at the Alfréd Rényi Institute of Mathematics] and we kept trying to see how computational complexity could be handled mathematically.

Amazing! What is your creative process? How do your mathematical ideas take shape?

Well, I mean, it's of course always a back and forth between trying to solve a problem and then trying to apply the ideas. Maybe one thing which I like probably a little bit more than most of my colleagues is to, sort of, clean up a proof. I don't like to write it down until I get the most essential part of it. And that sometimes is useful because it can lead to a better understanding of the situation. I'll give you one example: I was still in high school, and I was not satisfied with the fact that graph theory was sort of very elementary, and therefore looked down upon by many mathematicians. So, I thought that there should be some kind of algebraic side to it. I reinvented how to multiply two graphs with a new type of strong multiplication, and I thought, "Okay, it's easy to check that this product is commutative and associative; but do we have the cancellation law? Does A x C being isomorphic to B x C imply that A is isomorphic to B?". I began to think about it, and eventually, around the end of high school, I came up with a proof. But it was quite complicated, so I wasn't satisfied with it. And I still remember when I realized that, if I don't count subgraphs, but instead I count homomorphisms in the proof, then the claim follows immediately. So, this reinforced my idea that you have to understand what moves the proof, not only to come up with the proof. And I think that is something I like to do all the way. If I prove something, I try to understand what is the best way of looking at it.

This is great advice! Why is Budapest the hometown of most of the greatest combinatorialists and discrete mathematicians in history, including yourself? Is there something in the water here?

Haha! Well, there are various explanations. For one thing, which I think is very important, I have to go back a long time. So, Hungary had struck a deal with Austria in 1867 to obtain a certain degree of independence. There was a liberal government in Hungary, and they did many important things, and two of these are relevant. One is that they established general public education for everybody. The other one is that they gave equal rights to Jews. So, there was a large Jewish immigration to Hungary around the end of the 19th century and early 20th century, and the Jewish people sort of created a city life and a scientific life. I'm not saying that Hungary was unprepared: There were already first-class scientists in Hungary, including János Bolyai in mathematics. But anyway, all of a sudden, this mathematical life began to take place, and this is when, for example, this high school mathematics journal which I mentioned was established. The Hungarian National Mathematical Olympiad was also established around the same time, in the 1890s. So, many talented young people were discovered, and this gave an important push.
Now, why discrete mathematics and graph theory? It started with Dénes Kőnig, whose father was also a mathematician; but the Kőnig's Theorem in graph theory is called after the son. Some version of this theorem came out of Frobenius' study of determinants. There is a famous Perron-Frobenius theory about non-negative matrices, and Frobenius was interested in knowing, for a matrix whose entries are variables and some of them are zero, whether the determinant is an irreducible polynomial of the variables. Then, Kőnig wrote a paper where he basically showed that this is all just a combinatorial problem about seeing which variable goes where, and he used bipartite graphs to illustrate the arguments. What's interesting is that he didn't prove "the" Kőnig Theorem (which in this special case amounts to characterizing when the determinant is identically zero), but he just reformulated Frobenius’ proof using graphs. Frobenius then wrote another paper in which he did not say very nice things about Kőnig, as he was very much against translating the problem into graph theory; although this is one example where you have to get rid of all the unnecessary signs, sums and everything, and it's all just about the perfect matchings. So anyway, Kőnig got interested in this and then he wrote a textbook in 1937, and he had at least two students, Paul Erdős and my advisor Tibor Gallai. And so, they moved the theory ahead, and many other Hungarian mathematicians got interested in graph theory as a result.

Well, just in case, I will bring a tank of water from Budapest with me back to Amsterdam! Now, you have mentioned Paul Erdős several times already, and you have been one of his main collaborators: how would you describe him?

He was a very unusual person. Unlike the general picture often painted of him, he was very much concerned about other people. He knew about everybody, what they were doing, and he helped whenever anybody needed either a little money, some recommendation letter, or anything like that. But he didn't care so much for himself.
He couldn't visit Hungary during the Stalinist times, so it was only maybe near the end of the 50s, when he came back to Hungary for the first time after the war or after the Stalinist regime ended. I remember when I was young, maybe a young university student or maybe even a high school student, he was staying in a hotel when visiting Budapest. He was sitting all day in the lobby of the hotel, surrounded by young people, who were between 18 and 35 years old, or something like that, and he was sort of simultaneously working with several people on different problems. "Do you have any idea how to solve this? Oh, I have this additional question, maybe that's easier, or maybe that's also interesting." And sometimes, at lunchtime, he invited whoever was there for lunch at a restaurant. This was very inspiring, and I learned a number of things from him; not only mathematically, of course, but also on the human side.
He always thought that mathematics should be done publicly. He thought that, if you have an idea or have a new result, you shouldn't be afraid of sharing it with other people, because if they contribute to it or carry it on, then it will just be a better result—so you shouldn't try to keep it to yourself! He was always very unselfish, and on at least two occasions, when I was young, he gave me credit which wasn't unjustified, but it was maybe more than I deserved. The first case was when I first met Erdős, and he was already working with Lajos Pósa; you probably know the name. They had almost finished a paper. Pósa was a classmate of mine, and a good friend, and he asked me whether I could prove one of the results in the paper. So, I thought about it, and after a couple of days, I was able to prove their claim. Now, of course, if you know that something is true, then it's much easier to prove it. But anyway, Erdős added a footnote in their paper saying that this result was independently proved by László Lovász, which is not quite true.
The other case was (what is still called) the Lovász Local Lemma, which appeared in a joint paper of ours. Erdős emphasized that this particular lemma was mine, as he realized that it had broader implications compared to the rest of the paper, so he called the lemma after me. But it appeared in a joint paper, so, according to the standard rules, the lemma should be called Erdős-Lovász Lemma, if a name is needed at all. So, he was a very interesting person!

And from what you are describing, it seems like he was also very generous, both as a person and as a mathematician.

He was very generous, yes!

And how old were you when you first met him?

I was in high school, and I think my friend, Lajos Pósa, introduced us. I don't remember actually where it happened: probably during one visit of Erdős to my school. He used to visit the school about once a year to give a talk for the students there.

So, he was a very active mentor for young people as well.

Yes!

Do you have any other particular memory about Erdős that you would like to share?

There were several occasions when either we were in the US, or he visited Budapest and stayed with us for a week or two. This was often a little strenuous because he slept very little, and he liked to work for the rest of the day. But of course, we had teaching duties, and kids, and everyday life, and he understood that—but it was clear that he was rather impatient, and he wanted to sit down with us and work as much as possible. He was much older than we were, so it was really a little bit embarrassing to say, "Sorry, we are already tired!"

Does an Abel Prize laureate ever have difficulties?

Well, I'm teaching a class, and many more students come than before, because they want to see what an Abel Prize laureate looks like. And of course, just like everyone else, Abel Prize winners also suffer from bureaucratical difficulties: do these count as difficulties?

Yes, definitely! And when proving theorems, do you still sometimes feel stuck?

Of course! In mathematics, 90% of the time you are on the wrong path. I mean, you can't see the end of the path, so you have to try! It's also important to be able to turn back.

You mentioned your wife Katalin Vesztergombi, to whom you dedicate all of your books, and if I'm not wrong you also have many children and grandchildren...

Yes, we have four children, if this counts as many, and we have seven grandchildren, so far. But our son just got married half a year ago, so we still hope to have even more!

Besides mathematics, your large graphs, and your (large) family, what makes you happy?

There is definitely nothing comparable to these! But I like to walk in the nature and just look around, and this is one thing which I try to do regularly with my wife.

This is nice! What are you looking forward to in the future?

Well, if you are 75, you have to realize that, mathematically, you cannot really expect to have a career change. But there are some areas that I'm interested in seeing if they lead anywhere, mostly in and around graph limit theory. I am interested in trying to develop limit theory for graphs that are neither very sparse nor very dense, but are sort of in the middle range. There are some papers, but it's still rather far from being able to call it a theory, or something. I've also been thinking about developing some limit theory for matroids, or at least to generalize some of this matroid theory to some kind of continuous rank function, in the spirit of John von Neumann's continuous geometry. So yeah, there are interesting questions in all areas, but at this moment, I am looking at these two areas seriously. Now I also have more time to do mathematics, and there are some very good people with whom I work here, so I really enjoy this.

Well, I'm looking forward to reading your future results! What advice would you give young mathematicians?

During my university years, I have always found it very good to get interested in all areas of mathematics, and not only in my research area. I think that this proved to be very useful in my life, in my research. My advice is to not specialize too early, if possible. But I also understand that our current system is different now, and students have to specialize earlier. Part of this simply comes from the fact that the subjects are growing, so you inevitably end up in one branch which is already difficult enough to learn. For instance, when I was young, graph theory consisted of one or two books, and much of it, if you read it today, would be considered to be very elementary. And other areas are, of course, growing just as fast. So, it's difficult, but I think it's good still, to have some idea of what kind of goals other areas have. What is the main thing that they try to say? What kind of goals do they have? What's the advantage of looking at it in one way and not the other? There are big areas of mathematics where I have very, very little idea about what's going on, but I try to understand a little bit of that, nevertheless.

I like this advice. My last question is, why do you think it is important to keep studying graphs today?

Erdős had this idea that, if there are questions, you have to ask them. And, especially in graph theory, he was great at finding good questions — questions that lead to other questions. Eventually, this led to many branches of graph theory that were developed based on his questions and conjectures. Nowadays, the use of large graphs and large networks in various parts of other sciences seems to be inevitable. We saw one example of this with the pandemic: if we have to think about who meets whom, then understanding network properties is crucial for being able to say anything about the spread of a pandemic. Networks are also needed, of course, in brain research and ecological research, for example. So, with or without limits, the study of very large graphs and their properties, the problem of how to model and study them, is very important. And these are all very difficult questions, so I think that the study of large graphs is an exciting new area.

I completely agree with you, of course. Thank you so much for this very interesting and inspiring interview!