Graduate Seminar

Deepak Bal
Carnegie Mellon University
Title: 0-1 Laws in Random Graphs

Abstract: We say $p=p(n)$ satisfies the 0-1 law if for any first order graph property $A$, $Pr[G_{n,p}$ satisfies $A]$ tends to either 0 or 1 as n tends to infinity. Here $G_{n,p}$ is a graph on $n$ vertices where each potential edge appears independently with probability $p$. The question is which $p(n)$ satisfy such a law. In this talk I will discuss some basic results and tools used to answer such a question.

Date: Tuesday, October 9, 2012
Time: 5:30 pm
Location: Wean Hall 8220
Submitted by:  Brian Kell