Mathematical Institute, Utrecht University, Utrecht, The Netherlands

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)

Tags: TobiasMuller