« Logical and Natural Properties of Random Graphs
March 28, 2022, 2:00 PM - 3:00 PM
Location:
Hill Center-Room 705
Simi Haber, Bar-Ilan University
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). For example, it is known that in G(n,1/2) every first order expressible graph property has limiting probability zero or one, a phenomenon called a 0-1 law. Since many natural graph properties are not first order expressible, there has been an effort to extend first order logic while maintaining a 0-1 law. Along the years a number of very attractive and surprising results have been obtained. I will present some of these results and two tools enabling a new taxonomy of graph properties.
No background in logic is assumed. Based on joint works with Saharon Shelah.
COVID-19 Regulations: Please note that mask-wearing is still required indoors. All students and faculty must fill out the My Campus Pass when traveling to campus.
All other visitors must be registered online, contact Corrine Yap if you intend to visit for the seminar.