Logical properties of random graphs

יום א', 19/05/2019 - 12:00
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 finite 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 mention some of the classic results, demonstrate proof techniques and present two new results and a few open problems. No knowledge of logic is assumed.