Please note that this newsitem has been archived, and may contain outdated information or links.
29 May 2013, General Mathematics Colloquium, Tobias Mueller
Abstract.
Random graphs have been studied for over half a century as
useful mathematical models for networks and as an attractive
bit of mathematics for its own sake. Almost from the very
beginning of random graph theory there has been interest in
studying the behaviour of graph properties that can be
expressed as sentences in some logic, on random graphs. We say
that a graph property is first order expressible if it can be
written as a logic sentence using the universal and
existential quantifiers with variables ranging over the nodes
of the graph, the usual connectives AND, OR, NOT, parentheses
and the relations = and ~, where x ~ y means that x and y
share an edge. For example, the property that G contains a
triangle can be written as Exists x,y,z : (x ~ y) AND (x ~ z)
AND (y ~ z). First order expressible properties have been
studied extensively on the oldest and most commonly studied
model of random graphs, the Erdos-Renyi model, and by now we
have a fairly full description of the behaviour of first order
expressible properties on this model. I will describe a number
of striking results that have been obtained for the
Erdos-Renyi model with surprising links to number theory,
before describing some of my own work on different models of
random graphs, including random planar graphs and the Gilbert
model. (based on joint works with: P. Heinig, S. Haber,
M. Noy, A. Taraz)
Please note that this newsitem has been archived, and may contain outdated information or links.