6 November 2007
A graph property is a first order property if it can be written as a logic sentence with variables ranging over the vertices of the graph. A sequence of random graphs (G_n)_n satisfies the zero-one law if the probability that G_n satisfies P tends to either zero or one for every first order property P. This is for instance the case for G(n,p) if p is fixed. I will survey some of the most important results on the G(n,p)-model and then proceed to discuss some work in progress on other graph models.
- Combinatorial Theory Seminar