The ACO Seminar (2018–2019)

A graph property is first order expressible if it can be written as a formal 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.

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 graphs, e.g., G(n,p). A number of very attractive and surprising results have been obtained along the years. In the talk I'll present some of the main results, demonstrate different techniques and mention some new results and open problems. No knowledge of logic is assumed.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.