Monday, October 20, 2008
Technische Universität Berlin
Fak. II, Institut für Mathematik
Straße des 17. Juni 136
room MA 041
Lecture - 14:15
One of the main applications of graph theory outside pure mathematics is to provide mathematical models for a wide range of real-world networks, both physical and abstract. Very often, random graphs are used, since one cannot hope to produce a model that exactly reproduces a complex real-world network such as a social network.
A key question that is seldom addressed is the following: How good is the fit between the model and the real network? Of course, one can compare the values of various parameters (for example, degree distribution, or network diameter), but often the model can be `tuned' to match these parameters, which gives no guarantee that the model is accurate in other ways. It would be better to have one standard measure of similarity between graphs, and so be able to say that the model is a good fit if it produces graphs that are `globally similar' to the real-world networks.
In the dense case, for graphs with $n$ vertices and order $n^2$ edges, the work of Borgs, Chayes, Lov\'asz, S\'os, Szegedy and Vesztergombi gives a very nice answer to this question, that is closely related to (inhomogeneous) random graphs. The talk will start by briefly summarizing these results, and then turn to the (more realistic) sparse case. I will describe some initial results with B\'ela Bollob\'as, and also some of the (more numerous) open questions.
Colloquium - 16:00
Two important subspaces of the edge space of a graph are the cycle space and the cut space. Although these are orthogonal to each other, it is possible for an edge set to be an element of both, which is then called a _bicycle_.
In finite graphs, bicycles have been widely studied and a number of fundamental results involving them are known. But trying to extend these to infinite graphs fails, unless we allow infinite cycles as defined by Diestel and Kuehn.
We will look at the proof ideas and methods that were involved in extending three results to infinite, locally finite graphs: Read and Rosenstiehl's tripartition theorem, Shank's theorem that the residues of left-right tours generate the bicycle space and the planarity criterion of Archdeacon, Bonnington and Little.
This is joint work with H. Bruhn and S. Kosuch.