题目:  Can you tell a tree from its branches?

报告人: 吴耀琨, 上海交通大学

时间: 4月12号下午 4：10-5：10

地点：五教5302

摘要: For each set $X$, an $X$-split  is a partition of  $X$ into two parts. For each $X$-split $\mathbf{S}$ and each $Y\subseteq X$, the restriction of $\mathbf S$ on $Y$ is the $Y$-split whose parts are obtained from  the parts of $\mathbf S$  by taking intersection with $Y$. For a graph $G$ with vertex set $V$, the $G$-coboundary size of a $V$-split $\mathbf S$ is the number of edges of $G$ having nonempty intersections with both parts of $\mathbf S$. Let $T$ be a tree without degree-two vertices. Let $V$ and  $L$ be its set of vertices and its set of leaves, respectively. For each positive integer $k$, a $k$-split of $L$ displayed by $T$ is an $L$-split which is the restriction of a $V$-split with $T$-coboundary size $k$,   while a score-$k$ split of $L$  displayed by $T$ is a $k$-split but not any $(k-1)$-split  of $L$ displayed by $T$. Buneman's  split equivalence theorem tells us that the tree $T$ is totally encoded by the  system of its   $1$-splits  of  $L$. We identify the finitely many exceptional cases in which the tree $T$ is not determined by its $2$-split system  or score-$2$ split system. In order to understand how this work may be generalized to   general $k$-split systems, we propose several conjectures and open problems on set systems and  generalized Buneman graphs.   

This is joint work with Chengyang Qian and Min Xie. A slides for this talk is available at https://math.sjtu.edu.cn/faculty/ykwu/data/Talk/2024split.pdf