First Order Logic and Random (Geometric) Graphs
Tobias Müller
Mathematical Institute, Utrecht University, Utrecht, The Netherlands
2012/8/16 Thu 4PM-5PM (Room 3433, Bldg. E6-1)
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).
Starting from the sixties, first order expressible properties have been studied extensively on the most commonly studied model of random graphs, the Erdos-Renyi model. A number of very attractive and surprising results have been obtained, and by now we have a fairly full description of the behaviour of first order expressible properties on this model.
The Gilbert model of random graphs is obtained as follows. We take n points uniformly at random from the d-dimensional unit torus, and join two points by an edge if and only their distance is at most r.
In this talk I will discuss joint work with S. Haber which tells a nearly complete story on first order expressible properties of the Gilbert random graph model. In particular we settle several conjectures of McColm and of Agarwal-Spencer.
(Joint with S. Haber)