Colloquium Mathematics, Dr. Tobias Mueller

Join us for coffee and tea at 15.30 p.m.

Title: Logic and random graphs

Abstract:

Random graphs have been studied for over half a century as useful
mathematical models of 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.
I will describe a number of striking results that have been obtained
for the Erdos-Renyi model and some surprising links to other branches of
math including number theory, before describing some of my own work on
different models of random graphs, including the random planar graph
and the random geometric graph.

Colloquium coordinators are Prof.dr. A.C.D. van Enter (e-mail : A.C.D.van.Enter@rug.nl) and
Dr. A.V. Kiselev (e-mail: a.v.kiselev rug.nl )

http://www.rug.nl/research/jbi/news/colloquia/mathematics-colloquia/