László Lovász

Among the (sometimes) competitive community of mathematicians who (sometimes) happily self-identify as strange, László Lovász stands out. That’s because the only thing odd about Lovász, his colleagues say, is that he is normal and nice.

Lovász is a universally loved mathematician and combinatorialist — a professor at Eötvös Loránd University in his native Hungary and the recipient of a slew of international awards, including the Bolyai, Gödel, Knuth, Kyoto, Széchenyi and Wolf prizes.

As a high school student, Lovász won gold medals at the International Mathematical Olympiad three years running, starting in 1964. “In the land of prodigies and stars in Hungary, he shone from a very early age,” said collaborator and friend Avi Wigderson, a professor in the School of Mathematics at the Institute for Advanced Study in Princeton, N.J. “I have lots of Hungarian friends and everybody remembers him as a student.”

In particular, he is remembered for winning a televised mathematics competition. In the final, he faced Lajos Pósa, then and still a very good friend. “We were put in glass cages, both of us, and we got the same problem and three or four minutes to think about it,” Lovász recalled. When asked on camera how he came to the correct solution, he credited his competitor — the problem was similar to one that Pósa had shown him previously. “So it was a little embarrassing, to win with knowledge that I learned from him,” Lovász said. “But, of course, in a competition, your brain does not always work perfectly, just like in a sport.”

Lovász’s brain does, however, seem to work at a perfectly optimal speed. In addition to being normal and nice, Lovász is known for being highly productive, having authored or co-authored 10 books and published nearly 300 research and expository papers, including six with Paul Erdős (giving him an Erdős number of 1).

“If you look at his work, it’s hard to believe it’s one guy — he’s a master of writing,” said Wigderson, pulling from his bookshelf one of Lovász’s early titles, Combinatorial Problems and Exercises, published in 1979. “This book had a huge influence on combinatorics,” said Wigderson. “In the first part, the problems are classified by topics in discrete mathematics, and then the middle part is hints for all the problems, and the last part is complete solutions for all these problems. It’s a remarkable book, and he wrote it before he was 30.”

Lovász is also known for his generosity to the mathematics community. “He’s a fantastic advisor and a fantastic teacher, and he has a zillion collaborators,” said Wigderson. “One of the things that people rarely excel in is service to the academic or mathematical community. Very few people actually take the trouble to do this, especially if they are such fantastic researchers.” For example, Lovász recently stepped down from the presidency of the International Mathematical Union. During his term, he also served as chairman of his department at Eötvös Loránd, updating curricula and helping to restructure the university. Having completed both tenures, Lovász was due for a well-earned sabbatical.

•••

The hiatus, however, was not spent climbing mountains, attending concerts, playing Go or applying his carpentry skills to home-improvement projects — something he admits to abandoning over the years in order to keep up his productivity.

Knowing that Lovász’s administrative terms were coming to an end, the IAS School of Mathematics invited Lovász and his wife — Katalin Vesztergombi, also a renowned combinatorialist — to visit for the 2011-12 academic year. Hunkering down in the mathematics bunker of Simonyi Hall, which looks out onto a meadow and a peaceful pond, Lovász maintained his legendary productivity by writing his 10th book — Large Networks, Graphs, Homomorphisms, and Limits.

Lovász started research on this subject about 10 years ago, when he was a collaborative member at the Microsoft Research Center in Redmond, Wash., working with several members of and visitors to the Theory Group.. After two or three years, he began giving talks on the subject and then teaching courses. About four years ago, he wrote a 70-page piece for Contemporary Mathematics. “When I wrote that, I noticed that 70 pages were not really enough to give all the details that I thought should be given,” he recalled. “So I decided then that I would write a book.”

It is a mathematical book, he emphasized, and on a subject that quickly gets technical. “But the motivation comes from understanding large networks, which is a very hot topic because it’s a basic mathematical model in many areas of study,” he said, pointing to computer scientists’ desire to understand the structure of the Internet and biologists’ research on the brain.

In reality, these networks are much more complicated than mathematics can yet represent — to model such complicated networks requires much more than just the underlying graph, the underlying relation structure.

“But already that structure is interesting,” Lovász said, “and it brings completely new types of questions into graph theory: how to model such a network; how to determine what properties will allow you to say that some network is similar to another network… It’s an interesting graph theoretic subject in many ways, looking at the mathematical tools to handle these questions. And it connects to a number of other areas. It’s a rather broad topic with lots more to do.”

•••

Fittingly enough, making connections and cultivating networks within mathematics is signature Lovász. His style is to import techniques from different areas of mathematics into discrete math, into combinatorics.

“For several centuries, mathematics has struggled with understanding the ‘continuous,’ ” said Lovász, providing a brief definition of discrete mathematics. “Analysis has been the cutting edge of mathematical research. But it has turned out that there are many interesting structures and models that are finite and whose properties cannot be understood by the ‘continuous’ methods of analysis. Living creatures are composed of cells; society consists of individuals; all material is composed of atoms; our communication, and more and more our photography too, is digital, which means that, say, voice is reduced to a finite number of signals. Discrete mathematics deals with finite structures, how to describe them, how to study them.”

Lovász makes contributions to essentially all facets of discrete mathematics. “And it is a big field,” Wigderson said. “But most people working in this field work within the field, whereas he introduced methods from topology and methods from algebra and methods from geometry. He has brought a lot of tools to this field, in which even today there are not too many tools.”

“That’s what I like most,” Lovász said. “If there is some unexpected connection with some seemingly distant field.”

Using these eclectic tools, he has solved many big problems, such as the so-called “weak perfect graph conjecture.”

“It’s not so crucial what the perfect graph conjecture is,” said Noga Alon, a collaborator and colleague at Tel Aviv University. “What is interesting is that he introduced ideas from polyhedral combinatorics, geometric ideas, and that it was not clear at all that these ideas were relevant.” Similarly, Lovász solved the Kneser conjecture and the question of the Shannon capacity of a graph, again with unexpected tools from topology and geometry.

Additionally, Lovász’s solutions are always deep, with beautiful, simple arguments. They’re proofs “straight from ‘The Book,’ ” as Paul Erdős used to say (“The Book” being Erdős’ mathematician edition of the Bible). “This is characteristic of Lovasz’s work through his professional life,” said another collaborator and colleague, Joel Spencer of New York University’s Courant Institute of Mathematical Sciences. “He gets right to the core of the subject, to something deep.” By way of example, Spencer mentions that he has one of Lovász’s results, known as the Lovász local lemma, on display in his office. “It is a probability result, with a very short proof,” Spencer said. “Indeed, I had a calligraphy done of it, and the calligraphy is one line — the proof is a little bit longer, though not much.”

The beauty of it, Spencer said, wasn’t so much that it was a probability theorem, but rather that at the time, it was exactly the necessary tool to greatly enhance the applicability of the probabilistic methodology. In the 1940s, Erdős had developed an approach now known as the probabilistic method, or simply Erdős Magic. Despite its name, the use of probability in the methodology was relatively elementary. Then, when Lovász came up with the Lovász local lemma, as Spencer described, “It led to a total transformation of the field.”

Spencer, a disciple of Erdős’ (as was Lovász), said he now regards Lovász as the Erdős of the their generation — the leader of the field, based both on the strength of his personality and the depth with which he looks at mathematics. Spencer added that there are significant differences between the two, including their approach to mathematics: Erdőswas primarily a problem solver, while Lovász (though he solves problems) is in a broader sense a field builder.

Lovász’s working style, as Szegedy noted, is to develop big topics consistently and continually over years. “He doesn’t just solve one particular problem, but he builds a theory, a bigger theory, around a problem. To me, he’s a visionary person; he sees a longer way ahead.”

“Mathematics always has a miracle part, the mystical part,” he said. “Somebody works on a problem and suddenly the miracle happens and the new result comes. And that is always a mystery. It’s hard to describe how it happens.” With Lovász, he said, “He tries many things but then at some point this miracle has to happen. And somehow this miracle happens to him very often.”

•••

Completing a book is less a miracle than a marathon. Lovász sent his 500-page manuscript to a number of friends and colleagues. The feedback necessitated revisions. Finally, the book was published in December by the American Mathematical Society, under a simplified title: Large Networks and Graph Limits.

Although Lovász benefited from his hiatus, he was in high demand to speak about his work on graph limits — at the Institute’s biweekly mathematics seminars, at a weeklong conference (with the theme “On Graphs and Analysis”), at Princeton University, at Rutgers University and beyond.

Aside from these commitments, he worked hard to indulge in the Institute’s intellectual seclusion and to resist seeking out too many connections. “I have been talking to the computer scientists and mathematicians here,” he said. “But I decided that I must not be distracted too much. Talking to somebody in another field means a lot of time that you have to commit.

“I got a lot of work done,” he said of his sabbatical. “I got a lot of inspiration from visitors who came and gave talks. I have lots of ideas filed away, which I will revisit, at some point.”