Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Logical and natural properties of random graphs

Simi Haber (Bar-Ilan)

Location:  Hill Center Room 705
Date & time: Monday, 28 March 2022 at 2:00PM - 3:00PM

Abstract: 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

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.