Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

29 May 2013, General Mathematics Colloquium, Tobias Mueller

Speaker: Tobias Mueller
Title: Logic and random graphs
Date: Wednesday 29 May 2013
Time: 11:15-12:15
Location: Room C1.112, Science Park 904, Amsterdam

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)

For more information, see http://www.science.uva.nl/research/math/Calendar/colloq/

Please note that this newsitem has been archived, and may contain outdated information or links.