SFU Discrete Math Seminar: Pengyu Liu

  • Date: 03/17/2020
  • Time: 13:30
Pengyu Liu, SFU

Simon Fraser University


Polynomial tree analysis


Tree structures emerge in various sciences. It is challenging to compare and analyze tree structures as both the size and the number of trees are increasing and there are few tools to describe tree structures in a quantitive, accurate, comprehensive and easy-to-interpret way. Polynomials are important tools in mathematics to study discrete structures in interpretable ways, for example, the renowned Tutte polynomial for graphs and Jones polynomial for knots and links. In this talk, we introduce a polynomial for unlabeled trees and show that the polynomial is a complete isomorphism invariant for unlabeled trees. We generalize the polynomial for semi-labeled and fully-labeled trees. Then we define tree metrics for these trees and use the polynomial to estimate parameters of given trees and the best-fit model that generates the trees. Finally, we show some potential applications in biology and linguistics.

Other Information: 

SCK 9509