论文标题
注入性拆分系统
Injective split systems
论文作者
论文摘要
有限套件上的拆分系统$ \ MATHCAL S $，$ x $，$ | x | \ ge3 $，是一组分两区或$ x $的拆分，其中包含$ \ {x，x，x- \ \ {x \} \ {x \} \ {x - \ {x \} \ {x，x \} $ x \ in x $ in x $的所有分裂。对于任何此类拆分系统$ \ MATHCAL S $，我们都可以将Buneman Graph $ \ Mathcal B（\ Mathcal S）$关联，该$本质上是一个中间图，带有叶式$ x $，以$ \ MATHCAL S $显示拆分。在本文中，我们考虑了注射式拆分系统的属性，即拆分系统$ \ MATHCAL S $与$ \ Mathrm {Medrm {Med} _ {\ Mathcal B（\ Mathcal S）}（y Mathcal s）}（y）\ neq \ neq \ neq \ Mathrm {Medrm {medrm {medrm {\ mathrm b（mathrm b（y Mathrm b）在$ x $中，其中$ \ mathrm {med} _ {\ mathcal b（\ nathcal s）}（y）$表示$ \ Mathcal b（\ Mathcal s）中的中位数在$ y $中被认为是$ y $的$ y $中的$ y $中的中位数。特别是，我们表明，对于任何集合$ x $，始终存在$ x $上的注入式拆分系统，我们还为何时置入式系统赋予了一个表征。我们还考虑了Buneman Graph $ \ Mathcal B（\ Mathcal S）$需要成为$ x $上的拆分系统$ \ Mathcal s $的复杂程度。我们通过引入$ | x | $的数量来做到这一点，该数量称为$ | x | $的注入尺寸，以及两个相关数量，称为Injective 2-Split和rooted Injextive dimension。我们为这三个维度提供了一些上限和下限，并且还证明了其中一些界限很紧。研究注射式拆分系统的潜在动机是，它们可用于获得符号树图的自然概括。结果的一个重要结果是，可以使用Buneman图表示$ x $上的任何三向符号地图。
A split system $\mathcal S$ on a finite set $X$, $|X|\ge3$, is a set of bipartitions or splits of $X$ which contains all splits of the form $\{x,X-\{x\}\}$, $x \in X$. To any such split system $\mathcal S$ we can associate the Buneman graph $\mathcal B(\mathcal S)$ which is essentially a median graph with leaf-set $X$ that displays the splits in $\mathcal S$. In this paper, we consider properties of injective split systems, that is, split systems $\mathcal S$ with the property that $\mathrm{med}_{\mathcal B(\mathcal S)}(Y) \neq \mathrm{med}_{\mathrm B(\mathcal S)}(Y')$ for any 3-subsets $Y,Y'$ in $X$, where $\mathrm {med}_{\mathcal B(\mathcal S)}(Y)$ denotes the median in $\mathcal B(\mathcal S)$ of the three elements in $Y$ considered as leaves in $\mathcal B(\mathcal S)$. In particular, we show that for any set $X$ there always exists an injective split system on $X$, and we also give a characterization for when a split system is injective. We also consider how complex the Buneman graph $\mathcal B(\mathcal S)$ needs to become in order for a split system $\mathcal S$ on $X$ to be injective. We do this by introducing a quantity for $|X|$ which we call the injective dimension for $|X|$, as well as two related quantities, called the injective 2-split and the rooted-injective dimension. We derive some upper and lower bounds for all three of these dimensions and also prove that some of these bounds are tight. An underlying motivation for studying injective split systems is that they can be used to obtain a natural generalization of symbolic tree maps. An important consequence of our results is that any three-way symbolic map on $X$ can be represented using Buneman graphs.
