First order properties of random geometric graphs.
~~A graph property is first order expressible if it can be written as a logical sentence using the universal and existential quantifiers with variables ranging over the vertices of the graph, the usual connectives and the relations = and ~, where x ~ y stands for adjacency. Starting from the sixties, first order expressible properties have been studied using random models. That is, by looking on the possible behavior of first order properties given a probability space of models. The most extensively studied probability space of graphs is the Erdos-Renyi probability space. 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 a few results 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 T. Muller)
תאריך עדכון אחרון : 05/01/2014