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.
Synopsis:
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.