Combinatorial limits (MAGIC104) |
GeneralDescription
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.
SemesterAutumn 2019 (Monday, October 7 to Friday, December 13) Hours
Timetable
PrerequisitesThere 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.
SyllabusThe 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
Other courses that you may be interested in: Lecturer
Bibliography
Note: Clicking on the link for a book will take you to the relevant Google Book Search page. You may be able to preview the book there. On the right hand side you will see links to places where you can buy the book. There is also link marked 'Find this book in a library'. This sometimes works well, but not always. (You will need to enter your location, but it will be saved after you do that for the first time.) AssessmentThe assessment for this course will be via a single take-home exam paper in January with 2 weeks to complete and submit online. There will be 6 questions and the students will need the equivalent of 4 correctly answered questions to pass.
No assignments have been set for this course. FilesFiles marked L are intended to be displayed on the main screen during lectures. Recorded LecturesPlease log in to view lecture recordings. |