November 17, 3:30pm, Wean 8220

Colin Jahel, Carnegie Mellon University

Asymptotic theories and homomorphically-avoided structures

Colin Jahel, Carnegie Mellon University

Asymptotic theories and homomorphically-avoided structures

Abstract:

Joint work with Manuel Bodirsky. Given a class of finite graphs, one can consider $\mu_n$ the uniform measure on graphs in said class of size n. We study the asymptotic behavior, when n goes to infinity, of the family $(\mu_n)_n$. In particular, one can ask: which properties of graphs have converging probability, and when is this limit non-zero? I will present our results for classes of graphs and digraphs, in particular classes not containing any homorphic copies of certain sets of finite structures.