报告人： 吴耀琨（上海交通大学教授 ）
摘要: A character on $X$ is a set of disjoint nonempty subsets 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 character 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 character system fulfils some special requirements, we demonstrate that our algorithm applied to the corresponding $(0,1)$ array produces all ``minimum" trees which can display that character system. In the course of this research, we define a series of sparsity measures for $(0,1)$ arrays and investigate the interconnection between the sparseness of different margins of a high dimensional $(0,1)$ array. This is joint work with Yanzhen Xiong.