Expected number of induced subtrees shared by two independent copies of a random tree

Publication date: 11 February 2021

Abstract: Consider a rooted tree

T

with leaf-set

[n]

, and with all non-leaf vertices having out-degree

2

, at least. A rooted tree

m a t h c a l T

with leaf-set

S s u b s e t [n]

is induced by

S

in

T

if

m a t h c a l T

is the lowest common ancestor subtree for

S

, with all its degree-2 vertices suppressed. A "maximum agreement subtree" (MAST) for a pair of two trees

T^{'}

and

is a tree

m a t h c a l T

with a largest leaf-set

S s u b s e t [n]

such that

m a t h c a l T

is induced by

S

both in

T^{'}

and

. Bryant et al. cite{BryMcKSte} and Bernstein et al. cite{Ber} proved, among other results, that for

T^{'}

and

being two independent copies of a random binary (uniform or Yule-Harding distributed) tree

T

, the likely magnitude order of

is

O (n^{1 / 2})

. We prove this bound for a wide class of random rooted trees :

T

is a terminal tree of a branching, Galton--Watson, process with an ordered-offspring distribution of mean

1

, conditioned on "total number of leaves is

n

".

This page was built for publication: Expected number of induced subtrees shared by two independent copies of a random tree