Join us for coffee and tea at 15.30 p.m.
Tuesday, April 22nd 2014
Dr. Tobias Mueller,University Utrecht
Logic and random graphs
Random graphs have been studied for over half a century as usefulmathematical models of networks and as an attractive bit ofmathematics for its own sake.Almost from the very beginning of random graph theory there has beeninterest in studying the behaviour of graph properties that can beexpressed as sentences in some logic, on random graphs.
We say that a graph property is first order expressible if it can bewritten as a logic sentence using the universal and existential quantifiers withvariables ranging over the nodes of the graph, the usual connectivesAND, OR, NOT, parentheses and the relations = and ~, where x ~ y meansthat 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 onthe oldest and most commonly studied model of random graphs, theErdos-Renyi model.I will describe a number of striking results that have been obtainedfor the Erdos-Renyi model and some surprising links to other branches ofmath including number theory, before describing some of my own work ondifferent models of random graphs, including the random planar graphand 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:
Photo report on the most special and oldest books of the university.
On Monday, November 26, UG researcher Anouk Goossens receives the Shell Award. This prize is awarded annually to three (former) physics students. Goossens receives the prize for her investigation into using the material Nb-doped SrTiO3 for imitating...
A bountiful and healthy Wadden Sea is an indispensable link in the life cycles of many migratory birds and fish. This is why the Wadden Fund and the three Wadden provinces – Groningen, Friesland and Noord-Holland – strive for the creation of such a...