Probabilistic botany: from rooted subgraph counts to leaves of random trees (faculty candidate talk)

Matas Sileikis

Abstract

In this talk I will present results on three topics of random discrete structures.

We will start with rooted subgraph counts in the random graph G(n,p). This generalizes the notion of degree sequence: instead of the number of edges at a vertex we count the number of copies of an arbitrary fixed graph containing the vertex. I will state a result (with L. Warnke) on the conditions when the counts for each vertex are asymptotically equal.

Further we will discuss the random m-ary search trees, which model data structures produced from a random input of comparable keys. In particular, we will consider an analogue of subgraph counts for these trees, say, number of leaves or vertices inducing a cherry as a subtree (work with C. Holmgren and S. Janson).

I will conclude with a result (joint with A. Dudek, A. Frieze and A. Rucinski) about embedding the random (k-