The ACO Seminar (2022–2023)

November 17, 3:30pm, Wean 8220
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.