Title: Teasing apart two trees
Speaker:  Laszlo Szekely

Abstract:
A widely-studied model for generating binary sequences is to  `evolve'
them on a tree according to a symmetric Markov process. This model is
known as the Cavender-Farris-Neyman model in phylogeny,  and
the `symmetric binary channel' and the `symmetric 2-state Poisson model'
in other areas. The CFN model provides a simple model for the evolution
of purine-pyrimidine sequences. The significance of this simple model
is, that phenomena shown for the CFN model often extend to more realistic
models of sequence evolution.
 The abstract phylogeny reconstruction problem is telling the true (model)
tree from the generated sequences with high probability (whp).
 We show that under the CFN model distinguishing the true  tree
from a false one whp, using sequences generated on the true tree, is
substantially `easier' (in terms of the sequence length needed) than
determining the true tree whp.
 This raises an interesting question if the decision problem whether
an input tree is true or false whp is still `easier' than determining the
true tree whp.
 The key tool is a new and tight  Ramsey-type result for binary trees.

Based on a joint work with Mike Steel.

Please contact Elchanan Mossel if you wish to join dinner following the seminar