Rooted binary trees are used in evolutionary biology to represent the evolution of a set of species where the leaves denote the existing species and the internal nodes denote the unknown ancestors. Maximum agreement subtree is used as a measure of discrepancy between two trees. In this talk, I will define the notion of “maximum agreement subtree” and state some of its properties. I will also present some techniques on how to obtain lower and upper bounds on the expected size of the maximum agreement subtree when two trees are of the same ‘tree shape’.
All necessary background will be provided so the talk will be accessible to everyone.