Monday, October 20, 2008
Technische Universität Berlin
Fak. II, Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
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
Abstract:
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.