Seminar Details
Logical and Natural Properties of Random Graphs
- Start Date: March 28, 2022
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Simi Haber - Bar-Ilan University
- Event Location: Hill Center-Room 705
- Event Additional Info: <p><strong>COVID-19 Regulations</strong>: Please note that mask-wearing is still required indoors. All students and faculty must fill out the <a href="https://coronavirus.rutgers.edu/symptom-checker/" target="_blank">My Campus Pass</a> when traveling to campus.<br /> All other visitors must be registered online, contact Corrine Yap if you intend to visit for the seminar.</p> <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
- Presentation Type: Stand Alone Presentation
- 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.