It is becoming more and more clear that many of the most exciting structures of our world can be described as large networks. The internet is perhaps the foremost example, modeled by different networks (the physical internet, a network of devices; the world wide web, a network of webpages and hyperlinks). Various social networks, several of them created by the internet, are studied by sociologists, historians, epidemiologists, and economists. Huge networks arise in biology (from ecological networks to the brain), physics, and engineering. While these networks are different, there are questions (like robustness, dispersion, down- and upscaling) which arise in almost every context.

The mathematical theory of networks (graphs) has been one of the fastest growing areas in mathematics. In the “classical” theory we know the full network, with an exact list of nodes and edges, and then we study parameters and properties like maximum flows, chromatic number, or planarity. Graph theory established deep connections between such properties, and developed sophisticated algorithms to determine them.

The huge networks at the center of interest lately represent a new kind of challenge: these networks are never completely known, and indeed often not even completely defined. At any time, we can only have partial information about them, through sampling locally, or observing the behavior of some global process.

Which questions about large graphs are meaningful at all? How to obtain information about them? How to model them? How to approximate them by smaller graphs (or by other objects) so that basic properties are preserved? How to run algorithms on such large graphs?

In joint work with Christian Borgs, Jennifer Chayes, Vera Sós, Balázs Szegedy and Katalin Vesztergombi, we worked out a mathematical theory of large dense graphs and their “limits”. The theory of large sparse graphs (graphs with bounded degree) was initiated by Benjamini and Schramm; here the questions are analogous, but more difficult.

The talk will give a feeling for this theory and some of its applications.

Bio: László Lovász serves as a Professor at the Department of Computer Science of the Eötvös Loránd University in Budapest, Hungary. He was awarded among others the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010. His research topics focus on combinatorial optimization, algorithms, complexity, graph theory, random walks. In 2012 he published his newest book entitled “Large networks and graph limits” at the American Mathematical Society. He worked before at the University of Szeged, was a professor at Yale University and a collaborative member of the Microsoft Research Center. He served as president of the International Mathematical Union.

Lovász has an Erdős number of one as co-author of 6 papers.