Graduate Student

Event Information Logic on Random Graphs: 0-1 Laws and Order-Invariance
18:10 on Thursday March 23, 2017
19:00 on Thursday March 23, 2017
BA6183, Bahen Center, 40 St. George St.
Benjamin Rossman
University of Toronto

The 0-1 law of Fagin 1976 states that every first-order sentence in the language of graphs is either almost surely true or almost surely false for the Erdős–Rényi random graph G(n,1/2). A fascinating open question is whether a similar 0-1 law holds for *order-invariant* first-order logic (sentences in the language of ordered graphs whose semantics does not depend on the linear order). In this talk, I will present a proof of the classic 0-1 law and outline an approach to the order-invariant case via the Fourier analysis of Boolean functions. My goal is to recruit a student to work on this project. Background in logic is not required to understand the talk or the open problem.