When: Sunday, March 23, 10am
Where: Schreiber 309
Speaker: Simi Haber, Bar Ilan U.
Title: 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 thevertices of the graph, the usual connectives and the relations = and ~, where x ~ y stands for adjacency.
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 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 a few results telling 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 Amit Agarwal and Joel Spencer.
Joint work with T. Muller.
