Logical properties of random graphs
Seminar
Speaker
Simcha Haber, Bar-Ilan University
Date
19/05/2019 - 13:00 - 12:00Add to Calendar
2019-05-19 12:00:00
2019-05-19 13:00:00
Logical properties of random graphs
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.
Department Seminar Room 216/201
אוניברסיטת בר-אילן - המחלקה למתמטיקה
mathoffice@math.biu.ac.il
Asia/Jerusalem
public
Place
Department Seminar Room 216/201
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 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.
תאריך עדכון אחרון : 13/05/2019
