Interview Editorial Consultant: Tai-Ping Liu
Interviewers: Xu-Ding Zhu (XDZ), Ko-Wei Lih (KWL), Tai-Ping Liu (TPL)
Interviewee: Jaroslav Nešetřil (JN)
Date: February 27th, 2009
Venue: Institute of Mathematics, Academia Sinica

Prof. Nešetřil was born on March 13, 1946, in Brno, Czech Republic. He graduated from Charles University in Prague in 1969 and obtained his master degree in the same year from McMaster University during his short visit in Canada. After loosening of restrictions of the Prague Spring, the Czech government forced overseas students to return home, so Prof. Nešetřil was back to Charles University in Prague and obtained his PhD degree under the supervision of Aleš Pultr in 1973 and became a full professor in 1993.
Prof. Nešetřil spent his academic career at Charles University, where he was the dean of Applied Mathematics Department from 1986 to 2000. In 1996, he founded the Institute of Discrete Mathematics, Theoretical Computer Science, and he also served as the director of the Institute for Theoretical Computer Science at Charles University. His research expertise includes combinatorics (combinatorial structures and Ramsey theory), graph theory (coloring problems), algebra (structural representation, category theory and homomorphism), partially ordered set (diagram and dimension problems) and computer science (complexity and NP-completeness). Prof. Nešetřil has published more than 300 papers, is an editorial member of more than ten journals and is the editor of Computer Science Review.

TPL: First let’s have some tea and relax a bit. We have a Confucius saying "a friend comes from far away, isn’t that nice. / It is such a delight to have friends coming from afar." 我建議「有朋自遠方來，不亦樂乎」翻譯為"What a pleasure to have a friend come from afar!" So this column in our Chinese magazine is called "Friends from afar". So we’ve interviewed quite a number of people, the earliest ones being interviewed included Robert Mimura, then we had Lax, Glimn, Varadhan. The latest one was Caffarelli in elliptic PDE.

JN: This is a very impressive list. Caffarelli just got a Steele Prize for life achievement in Washington at AMS annual meeting.

TPL: There is a nice sentence that they are saying that "We have something better than exact solution, we have Caffarelli." (laughs)

JN: I am organizing a colloquium series in Prague, which is quite distinguished, organized twice a year. Our last speaker was Juan Luis Vazquez. He considers Caffarelli as his scientific father.

TPL: So now Ko-Wei has arrived, so we can start. Okay. So, let’s start, who shall ask the first question? Let me start it. As we know, you are from Eastern Europe. I don’t know whether you want to be classified as an Eastern European?

JN: Ah ... it’s complicated ... no ... We consider ourselves as Central Europe. (laughs)

TPL: Okay ... Let’s say Central Europe. Yes ... We know that in that region the tradition is in functional analysis, Banach and Hausdorff and other people. But it is also known for combinatorics.

JN: That’s correct.

TPL: Ko-Wei came back from the last ICM and also several people have mentioned to me, that combinatorics was featured very prominently in it. Okay, so my question is a small one. Why is Central Europe, the Czechs, Hungarians, so strong in combinatorics? Why did you get into it?

JN: It is the result of many factors ... it’s not easily answered. For example, one shall say that the strongest group is the Hungarians. How they got into it? I believe by personal influence of key figures. There was Denes König, he came from logic, set theory, and topology and he wrote the first book before the War, the Second World War. Then came a strong generation of the Hungarians, Erdős, Turán, Rényi and then, they all had all the students. Then König’s book was well known in my country too. So actually the generation of our teachers, like Fiedler, Pultr and Hedrlin, they oriented students to this area. It was a good decision. But we also considered Erdős as our teacher. You know Central Europe is very compact and everything is very close. So if the political situation is favorable, then you can travel in one afternoon’s time. It’s like Kaohsiung to Taipei and back. It’s very close. So in the sixties, when I was a student, I travelled. In the seventies, when traveling was quite restricted for political reasons, we could still travel to Budapest, we went very often and people from Budapest traveled to Prague. Every month and much more, more often than now. So I think it is mostly along the personal connection. The first international meeting of combinatorics and graph theory was organized by Fiedler in the sixties, 1963 in Smolenice. That was attended by many mathematicians all over the world, From America, Western Europe. It was successful actually partly due the fact that it was in the center (in Central Europe). It was always difficult to say how some school developed ... but the main factor one could say is people.

KWL: Your birth place is Brno ... How do you pronounce it "burno"? Is that also a central place for intellectual activities? Because I know Gödel was born in Brno.

JN: That’s right. I was born forty years after Gödel in the place. Well Brno is a large town and it is the capital of Moravia. My country consists of two parts, Bohemia and Moravia. They were in the history and always together. Slovakia came up later. Bohemia and Moravia have been always together, we speak the same language; they differ only by the dialect. Prague is the capital of Bohemia, so there is always a tension between Prague and Brno. Brno is considered very important and is very industrialized. Brno is close to Vienna, which was a capital when the country belonged to Austria. It was then, that Brno was called Moravian Manchester, because it has strong textile industry. One of these factories belonged to Gödel’s family. Gödel was German. There was a large German minority in Brno. After the First World War, he could decide which country he wanted to live in. They decided to move to Austria, but his mother stayed. She stayed in Brno all the time and she even survived Nazi time. Gödel’s house still exists in Brno.

KWL: So when you were a high school student, did you ever hear the name Gödel?

JN: No.

KWL: No. Is this name now famous in Brno?

JN: Yes ... It’s ... Of course Gödel is part of the culture and tradition, but scientists are rarely popular. I have a good story: when my son was at the university, one of my American friends came to Prague. He went to see Jakub. Jakub is my son’s name. He said to Jakub, "Jakub how’s school?" My son said "Okay" then he said "Do you know who was Goodel? Goodel." Jakub said "I haven’t heard about him" He said "You should have. You are studying computer science" He said "Goodel" "Goodel" repeatedly and Jakub said "No, I haven’t heard." After several times, Jakub was uncomfortable as here was a famous mathematician and computer scientist, and he found that he was not in the school. So I interfered: "Joe, what do you want to know?" He said: "Well ... I was just asking Jakub whether he knows Goodel." I said "Well, I don’ t know either." But then I realized "Oh! You mean Gödel." (laughs)

XDZ: So now, high school students learn about Gödel.

JN: Maybe it’s mentioned. It’s sort of folklore ... certainly Gödel is one of the greatest scientists born in the area.

KWL: Was there any high school math teacher who inspired you very much?

JN: In my time there were no specialized high schools, like they are now. Now we have specialized high schools and a program for gifted kids. The program actually just started when I was finishing high school. So I was in a small town, Rakovnik, I went to high school there.

KWL: Did you call it Gymnasium?

JN: I went to a gymnasium in Rakovnik. At that time, I had a good math teacher. My mother was a mathematics teacher too. But somehow my main interest at that time was art. I was very fortunate to meet excellent artists in my high school time. One of them indirectly led me to science. His name was Lexa, which is easy to pronounce and his uncle was the founding father of Czech’s Egyptology. He was an Academician and was world famous and Czech Egyptologists are famous together with British, American and Germans. I think that they are in the same category. They still have an Institute in Cairo. My professor of art/painting/drawing was actually proudly telling me about it, and in this way put me into contacts with some of the scientists. So, I got an early experience about what it’s like to be an academician or a scientist. It really impressed me and influenced me a lot. It was very nice experiences. Lexa was very old at that time, I was young. I am grateful that my mother organized my meetings with him.

XDZ: So you are still doing art, right. Like painting and other paintings. So are there any impacts from the two sides, the art and mathematics?

JN: Well ... I am so used to think about it. I like to see the connections between various intellectual activities, I sometimes even write about it. I have a Ph. D. student now, who is working on what we call "mathematical aesthetics". We would like to try to device some programs; it’s in computer science, for generating harmonies. It’s like how to teach computers to recognize and to generate what is nice. It is very good and serious motivation. Perhaps it is very ambitious. Modestly, we are trying to understand what the aesthetics of web pages is, for example. It should be done automatically. It’s very different from art, because it does not have a fixed format and it’s also very complicated. Of course, we don’t aim for aesthetic in the artistic sense. I mean ... In art one has to surprise, to be shocking, there is too much context there. We aim just for harmonies ... I mean this is a very reasonable project. Perhaps it’s very ambitious too. I am serious about it and it’s certainly not a hobby.

KWL: What kind of mathematical tools you are using for this study?

JN: It’s of course inter-disciplinary. We use, for example, the integral geometry and some probabilistic properties for drawn figures. Then we use some tools which are already developed in image processing. People don’t realize it, but image processing is one of the fastest developing fields where a lot of things are being done ... but it’s mostly a different motivation.

KWL: Yes ... you’re right.

JN: So, for example, we study the morphology, which teaches us how to make a picture simpler and how to discover some syntax of the individual marks. Another related area is fractal theory. This picture here looks like a picture but there is a factor of its size. When you look closely and even more closely then the picture disappears. It’s seemingly only a mesh of random points. So there is a factal boundary and it can be measured. So by means of such studies we are slowly progressing. I like this research.

TPL: This just reminds me a small digression. Chinese has a period named Sung Dynasty, which is basically the height of Chinese civilization.

JN: You said Sung; we just saw some celadon porcelain in National Palace Museum which I admired very much.

KWL: Yeh ... We went to the National Palace Museum and he liked the porcelain a lot. (laughs)

TPL: Right ... Right, but I was referring to the poetry at that time. The poems could be sung. It’s a music, but that is lost to us now. Now you just mentioned your project, which is very ambitious. Perhaps one could have just taken from your example, try to recover this music in Sung dynasty. This is a great loss to Chinese culture. Chinese has lost two things. One is the Sung dynasty poetry - how to sing it. Another is the Yuan dynasty opera, and that is also lost to us. Okay ... Just a digressing ... you made me thinking of that.

JN: Yeh ... sure ... sure ... Once you somehow understand some of the rules and principles, you have to know something. If you know some hypothetical information or rules, then you can try to reconstruct that.

TPL: Yeh ... and it’s worthwhile thinking.

JN: For example, in paintings there is something like that and this is actually a good example. Who studies art or is an art connoisseur, can see the authorship from a tiny fragment. I mean, just show me one tiny fragment of a painting of Cézanne, and most likely I will identify it. Of course, you cannot distinguish original or a copy but you can see the style.

TPL: You would say "this is Cézanne".

JN: This is Cézanne or Cézannesque. Distinguish the copy from the real is another thing. For the case, it’s sometimes very difficult to identify a copy. But to find the style, how the things are formalized, marked or formed, this can be done but it is very difficult to explain. Some of these are actually guiding principles of how we want to "measure aesthetics".

TPL: Let us leave now this general philosophical discussion. My question is "why combinatorics now is recognized to be a core of mathematics? Is it important? Or ... Put it in another way ... What’s not recognized to be as important as it should be?"

JN: As you put it ... I would like that you say it twice ... say it again ... That we are a core of mathematics. (laughs)

TPL: Carleson, this great harmonic analyst from Sweden, he once said "how he proved this almost everywhere convergence of Fourier series for an L2 function". That is really a classical result in analysis for the second half of 20th century and he said that, "instead of using a lot of general theories you narrowed down to some combinatorial concepts".

JN: Yeh ... there is also a beautiful article by Gowers, a Fields medalist. He wrote a very nice article about "two cultures". I don’t know whether you have seen that article

XDZ: Yeh ... I did ...

JN: That article basically says that in mathematics there are two cultures: always in rough simplification, there is theory building and there is problem solving. Of course, problem solving type of mathematics is exemplified very clearly and very completely in combinatorics where this is the rule of thumb. Of course, there are parts of combinatorics, which are built as a theory. There are more and more such examples actually. This is one of the aspects why combinatorics is becoming, I think, popular or accepted by mathematicians. That it is having more structures and more theories. Maybe it’s my personal line, but I think it’s correct. We combinatorists are looking more like serious mathematicians. So maybe the two cultures are converging. But on the other hand, mathematicians are principled people and we don’t like compromises. This goes by the difficulty and nature of the subject, and then in the last ten or twenty years, there were found such fantastic theorems proved, which are of combinatorial nature. That’s simply amazing. And thus, even those people, who don’t like combinatorics, have to accept that. This is it.

TPL: Could you state a couple of such theorems?

JN: There are simply beautiful examples. I am now giving a series of lectures in Kaohsiung during my stay in Taiwan this time. This is called "Structural Graph Theory, 10 years after". This is ... I was here in 1999. I was in Hsinchu and Kaohsiung, and I gave a series of talks. From that I published a paper in Taiwanese Journal of Mathematics, by the title "Aspects of structural combinatorics (graph homomorphisms and their use)". That really sort of led to the development of mine and Pavol Hell. Subsequently, we published a book, which somehow was partially motivated by this survey. However, in the last ten years, the field developed so much, in a degree which we didn’t anticipate before. This is very easy to document. One could speak one semester about the developments which happened in last ten years. Structural combinatorics is really an expanding branch of mathematics. You find it everywhere. Today we just heard a colloquium about very different topics, partition functions. Partition function is about counting the homomorphisms. It’s counting the homomorphism with simple target. It’s come to the context of the non-commutative algebra, random walks, and the scaling limits, in the hands of people like Lovász, I would like to say that this probabilistic context is due to people like Oded Schramm , who unfortunately recently died. His coauthor Werner got a Fields medal in Madrid. So he got it for the work which is essentially of combinatorial nature. I mean for multidisciplinary work which is related to random graphs and walks. And this is no accident. Another example is number theory. Recently some of the deepest theorems in number theory are combinatorial nature. 30 years ago, or 50 years ago, certainly the core of number theory was analytical number theory. Recently this changed. I mean that certainly today the combinatorial number theory or as it is sometimes called additive combinatorics, is as important as everything else. But of course, it’s not simple development. One has to see that combinatorics is developing too. It differs very much from combinatorics which was in time of König, and later graph theory in the generation of Harary. This is a passé very much. Combinatorics has absorbed lot mathematics, and it’s also used by many mathematicians. By now, nearly every field has combinatorial something.

XDZ: Emm ... Emm ...

JN: So it’s not our monopoly anymore. Everybody speaks about graphs. But one important thing should be added. You asked why this development is. The principal factor in this development is computers. I mean ... Not too long ago, people did not understand algorithms. I mean, in Europe, 70 years ago, people did not know what’s an algorithm. Some 40 years ago, people still didn’t understand what is algorithm and what is a computer and its computability and effective computability. These are all very recent concepts. People who studied it, some were logicians and some more came from the logic. But essentially, the richness of the area was later shown by people from combinatorics. For example, consider finite model theory. That theory was the beginning discredited by counter examples. All the beauty which holds in logic was somehow demolished in the finite. But some years later, people find out that much of the beauty lies in the finite, the rich spectrum of counter examples, for example. This finiteness is essential restriction by computers. It’s not like 50 years ago, when people asked why one should do finite when every reasonable mathematician should do infinity? Now we have a motivation. We have to do the finite, because of our computer science. (laughs)

XDZ: Yeh ...

JN: We have an excuse when people ask. But on the other hand, the finite mathematics is going back to infinity and that’s beautiful. We don’t study graphs with five points. We have the random graphs, limit graphs, and asymptotic structure. It’s not only asymptotic like classical, where we have only potential infinity. We have actual infinity. We have these huge graphs which we cannot study. So we study finite samples which leads to quite interesting areas like property fessing and other areas. All this is related to probability, but even to the harmonic analysis. (laughs)

TPL: Yeh

JN: I am talking too much.