Model Theory Seminar

November 10
Alexander Van Abel, Wesleyan University
Asymptotics of the Spencer-Shelah Random Graph Sequence

In combinatorics, the Spencer-Shelah random graph sequence is a variation on the independent-edge random graph model. We fix an irrational number $a \in (0,1)$, and we probabilistically generate the n-th Spencer-Shelah graph (with parameter $a$) by taking $n$ vertices, and for every pair of distinct vertices, deciding whether they are connected with a biased coin flip, with success probability $n^{-a}$. On the other hand, in model theory, an $R$-mac is a class of finite structures, where the cardinalities of definable subsets are particularly well-behaved. In this talk, we will introduce the notion of 'probabalistic $R$-mac' and present an incomplete proof that the Spencer Shelah random graph sequence is an example of one.