# Combinatorics Seminar

When: Sunday, March 23, 10am

Where: Schreiber 309

Speaker: Simi Haber, Bar Ilan U.

Title: First order properties of random geometric graphs

## 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 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.

redesigned by barak soreq