Math Graduate Student Seminar

In this talk I will provide a basic introduction to the theory of random graphs and its surprising connection with mathematical logic. This interesting blend of graph theory, probability and logic leads to several unexpected and beautiful results. The most classical result is Fagin's theorem about the existence of a zero-one law for first order properties in the binomial random graph G(n,p). The main purpose of the talk is to explain the meaning of Fagin's theorem and present its proof. If time permits, I will also briefly introduce some of my work in this field.