Combinatorics Seminar 2018

Speaker: Yanzhen Xiong (熊彦禛), Shanghai Jiao Tong University

Date: Thu, Oct 04, 2018

Time: 11:10 - 12:10

Venue: Large Meeting Room

Title: Sparse partition system and perfect phylogeny


A character on a set $X$ is a set of disjoint nonempty subsets of $X$. A character on $X$ of which the union of all elements equals $X$ is known as a partition of $X$. We say that a character on $X$ can be displayed on a tree $T$ if the leaf set of $T$ contains $X$ and that the convex hulls of those parts of the character in $T$ are pairwise disjoint. A character system has a perfect phylogeny if they can be displayed on a common tree. Each family of characters on $X$, say $\pi_1,\ldots,\pi_n$, naturally corresponds to an $n$-dimensional $(0,1)$ array of size $a_1\times \cdots \times a_n$, where $a_i$ is the number of parts of $\pi_i$, of which the $(t_1,\ldots ,t_n)$-entry is $1$ if and only if there is an element of $X$ lying in the $t_i$th part of $\pi_i$ for all $i=1,\ldots,n$. For each $(0,1)$ array, we propose an algorithm to associate with it a set of graphs. We show that a partition system of size $n$ has a perfect phylogeny if and only if its corresponding $(0,1)$ $n$-dimensional array is sparse in certain sense. When the partition system fulfils some special requirements, we demonstrate that our algorithm applied to the $(0,1)$ array corresponding to the partition system produces all ``minimum" trees which can display the partition system. In the course of this research, we define a series of sparsity measures for $(0,1)$ arrays and investigate their mutual relations.

This is joint work with Yaokun Wu.

Slides: View slides