First order properties of random geometric graphs.

Seminar
Speaker
Simha Haber
Date
07/01/2014 - 14:00Add to Calendar 2014-01-07 14:00:00 2014-01-07 14:00:00 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)   אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Abstract

~~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