Since 2006 the research of large networks and several other aspects of graph theory has been much influenced by the concept of graphon (also known as combinatorial limit), introduced by
Lovász and Szegedy. Graphons are certain limits of sequences of finite graphs and they are uncountable. This is in contrast with the well known class of countable limit graphs obtained as Fraïssé limits of a class of finite structures, such as the Rado graph. The limit graphon is a limit of a convergent sequence of finite graphs in the graphon space, which is the completion of the metric space consisting of the set of finite graphs endowed with the cut metric. The graphon space is a compact space and this fact is equivalent to strong forms of the Szemerédi Regularity Lemma from graph theory. Graphons can be realised as symmetric, Lebesgue measurable functions from [0,1]2 to [0,1], and we can also view them as certain weighted graphs on [0,1]. For a good reference on the subject one can consult, Lovasz’s book « Large networks and graph limits », which has already become a classic. It decribes the mathematical details of the theory, but it also gives examples of various areas of life that have motivated and benefited from research on graphons. These areas include the internet, social networks, ecological networks and statistical physics. The point is that all these phenomena can be modelled by networks consisting of individual interconnected elements, where to understand the situation one has to study not only the elements themselves but the
underlying system as a whole. One of the goals of the module will be to describe the theoretical aspects of the subject and another to describe some of the applications.
We will start by motivating and introducing the idea of a graphon. Then we will develop the basic theory and will prove some main theorems of combinatorial flavour. We shall then describe some applications and open questions.
There are no prerequisites for this course, except for a reasonable level of mathematical maturity. Having been exposed to a module in graph theory mathematical logic would be desirable but not necessary.
The module will include the following topics:
1. Introduction and connection to graphs and networks
2. Definitions and space of graphons
3. Cut metric and convergence
4. Szemeredi regularity Lemma
5. Compactness of the space of graphons
6. Hypergraphs
7. Sparse graphs
8. Other graphon-like objects