Games, Logic, and Random Structures
Katherine St. John
University of Pennsylvania

What fraction of graphs with 3 vertices contains a triangle? What is the fraction for graphs with 4 vertices? What happens to this fraction as the number of vertices gets large? This can be answered using work from finite model theory, a branch of logic. The answer changes, in surprising ways, if we allow the edges to occur randomly (i.e. with probability that depends on the number of vertices). We will discuss these results of Fagin, Spencer, and Shelah, some of the games used in finite model theory, and also what a random bit string looks like. For each probability, we let the almost sure theory be all the first order sentences that hold as the number of vertices becomes arbitrarily large. We will give a countable model for each almost sure theory and discuss the size of such models.

This is joint work with Joel Spencer (CIMS and IAS).

Games, Logic, and Random Structures Katherine St. John University of Pennsylvania

Games, Logic, and Random Structures
Katherine St. John
University of Pennsylvania