We consider finite rooted ordered trees in which every internal node has at least two children, sometimes called Schröder trees; the size |t| of such a tree t is the number of its leaves. An important concept with trees is that of inducing subtrees. Given a tree t of size k and a larger tree t’ of size n\geq k we define 0 \leq \theta(t,t’)\leq 1 to be the probability of obtaining t as a randomly induced subtree of size k in t’. One can think of \theta(t,t’) to be the *density of the pattern t in t’*. In this talk we consider two closely related questions concerning the nature of \theta:

1. A sequences of trees (t_n)_n with |t_n|\rightarrow\infty is called \theta-convergent, if \theta(t,t_n) converges for every fixed tree t. The limit of (t_n)_n is the function t\mapsto \lim_n\theta(t,t_n). What limits exist?

2. A Markov chain (X_n)_n with X_n being a random tree of size n is called a \theta-chain if P(X_k=t|X_n=t’)=\theta(t,t’) for all k \leq n. What \theta-chains exist?

Similar questions have been treated for many different types of discrete structures (words, permutations, graphs \dots); binary Schröder trees (Catalan trees) are considered in [1]. We present a De Finetti-type representation for \theta-chains and a homeomorphic description of limits of \theta-convergent sequences involving certain tree-like compact subsets of the square [0,1]^2. Questions and results are closely linked to the study of exchangeable hierarchies, see [2].

[1] Evans, Grübel and Wakolbinger. “Doob-Martin boundary of Rémy’s tree growth chain”. The Annals of Probability, 2017.

[2] Forman, Haulk and Pitman. “A representation of exchangeable hierarchies by sampling from random real trees”. Prob.Theory and related Fields, 2017.

[3] Gerstenberg. “Exchangeable interval hypergraphs and limits of ordered discrete structures”. arXiv, 2018.

**Date**: 8 October 2018, 12:00 (Monday, 1st week, Michaelmas 2018)**Venue**: Mathematical Institute

Woodstock Road OX2 6GGSee location on maps.ox**Details**: L4**Speaker**: Julian Gerstenberg (Leibniz Universität Hannover)**Organising department**: Department of Statistics**Organisers**: Christina Goldschmidt (Department of Statistics, University of Oxford), James Martin (Department of Statistics, University of Oxford)**Part of**: Probability seminar**Booking required?**: Not required**Audience**: Public- Editor: Christina Goldschmidt