ACO 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.


Back to the ACO home page Back to the ACO Seminar schedule