Skip to main content

Alperen Özdemir: Random processes and first-order limit laws

Time: Wed 2023-11-15 10.15 - 11.15

Location: KTH, 3721

Participating: Alperen Özdemir (KTH)

ABSTRACT: We will focus on two sequences of objects in this talk: 321-avoiding permutations and uniform attachment graphs as their sizes go to infinity. We say that the first-order limit law is satisfied if for all first-order logical sentences the limiting density for the number of objects satisfying that sentence exists. It will be shown why Markov chains do not apply in our examples and how other forms of random processes can be used to prove the limit law.