Continuous Combinatorics

by Alexander Razborov (University of Chicago)

Wednesday 18 Mar 2015, 15:15 → 16:15 Europe/Stockholm

Oskar Klein

Combinatorics was conceived, and then developed over centuries as a discipline about finite structures. In the modern world, however, its applications increasingly pertain to structures that, although finite, are extremely large: the Internet network, social networks, statistical physics, to name just a few. Moreover, the numerical characteristics researchers are normally interested in are "continuous" in the sense that small perturbations in the structure do not change the output very much.

This makes it very natural to try to think of the "limit theory" of such objects by pretending that "very large" actually means "infinite". It turns out that this mathematical abstraction is very useful and instructive and leads to unexpected connections with many other things, both in mathematics and computer science.

Two complementing approaches to constructing such a theory and applying it elsewhere are known as graph limits and flag algebras, and in our talk we review as much of it as the time permits.