Student Probability Seminar

First Order Sentences on G(N,P)​, Zero-One Laws, Almost Sure and Complete Theories

Speaker: Moumanti Podder

Location: Warren Weaver Hall 1314

Date: Thursday, February 11, 2016, 4 p.m.


We start with G(n, p)​, at first with a constant p​, and then examine the probability of the presence of some property, especially the limit as n​ goes to ∞​. We discuss the Fagin-GKLT theorem which shows that for constant p​, any first order property will hold almost surely or almost never in the above set-up. We informally discuss the intuition and the consquence of a well known result: when p(n) = n-α​, G(n, p)​ satisfies the Zero-One law if and only if α​ is irrational. Time permitting, we define almost sure and complete theories, and countable models. We look at examples of such theories for G(n, p)​ where p = p(n)​ varies over different ranges, especially in the case of very sparse random graphs.