Parity Splits by Triple Point Distances in X-Trees

At the conference Dress defined parity split maps by triple point distance and asked for a characterisation of such maps coming from binary phylogenetic X-trees. This article gives an answer to that question. The characterisation for X-trees can be easily described as follows: If all restrictions of a split map to sets of five or fewer elements is a parity split map for an X-tree, then so is the entire map. To ensure that the parity split map comes from an X-tree which is binary and phylogenetic, we add two more technical conditions also based on studying at most five points at a time. Received August 27, 2004     

The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials $F_{m,n,1}\left(x\right)$ and $F_{m,n,2}\left(x\right)$. Then, he defined $A_m(n,k)$ and $B_m(n,k)$ to be the polynomials satisfying $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{A}_m(n,k)x^{n?k}{(x+1)}^k$ and $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{B}_m(n,k)x^{n?k}{(x+1)}^k$. In this paper, we give a combinatorial interpretation of the coefficients of $A_{m+1}(n,k)$ and prove a symmetry of the coefficients, i.e., $\left[m^s\right]A_{m+1}(n,k)=\left[m^{n?s}\right]A_{m+1}(n,n?k)$. We give a combinatorial interpretation of $B_{m+1}(n,k)$ and prove that $B_{m+1}(n,n?1)$ is a polynomial in $m$ with non-negative integer coefficients. We also prove that if $n\ge 6$ then all coefficients of $B_{m+1}(n,n?2)$ except the coefficient of $m^{n?1}$ are non-negative integers. For all $n$, the coefficient of $m^{n?1}$ in $B_{m+1}(n,n?2)$ is $?(n?1)$, and when $n\le 5$ some other coefficients of $B_{m+1}(n,n?2)$ are also negative.     

A Structured Family of Clustering and Tree Construction Methods

A cluster A is an Apresjan cluster if every pair of objects within A is more similar than either is to any object outside A. The criterion is intuitive, compelling, but often too restrictive for applications in classification. We therefore explore extensions of Apresjan clustering to a family of related hierarchical clustering methods. The extensions are shown to be closely connected with the well-known single and average linkage tree constructions. A dual family of methods for classification by splits is also presented. Splits are partitions of the set of objects into two disjoint blocks and are widely used in domains such as phylogenetics. Both the cluster and split methods give rise to progressively refined tree representations. We exploit dualities and connections between the various methods, giving polynomial time construction algorithms for most of the constructions and NP-hardness results for the rest.     

On Whitney numbers of the order ideals of generalized fences and crowns

We solve some recurrences given by E. Munarini and N. Zagaglia Salvi proving explicit formulas for Whitney numbers of the distributive lattices of order ideals of the fence poset and crown poset. Moreover, we get a method to obtain explicit formulas for Whitney numbers of lattices of order ideals of fences with higher asymmetric peaks.     

The Cendian of a Tree

The eccentricity e(x) and the distance sum s(x) of a vertex x of a connected graph G are well-known functions which measure the centrality of the vertex x in G. The set of vertices which minimize e(x) is called the center of G and the set of vertices which minimize s(x) is known as the median. In this paper we introduce the idea of the so-called cendian of a graph, which unifies the concepts of center and median, and study its structure in trees.     

一致有界树指标马氏链的层频率的强大数定律

利用一致有界树指标马氏链的强大数定律,给出了一致有界树指标马氏链的关于状态和状态序偶出现的层频率的强大数定律.     

Ahlfors 正则空间上的开集分解与加倍测度

对于一致完全的加倍度量空间建立了 Whitney 分解定理. 作为应用, 借助于 Ahlfors 正则空间上的加倍测度描述了它的任意非空闭集的 Whitney 修正集上的加倍测度.     

关于树指标非齐次马氏链的广义熵遍历定理

主要研究了树指标非齐次马氏链的广义熵遍历定理.首先证明了树指标非齐次马氏链上的二元函数延迟平均的强极限定理.然后得到了树指标非齐次马氏链上状态出现延迟频率的强大数定律,以及树指标非齐次马氏链的广义熵遍历定理.作为推论,推广了一些已有结果.同时,证明了局部有限无穷树树指标有限状态随机过程广义熵密度的一致可积性.     

模糊有界变差函数全变差的积分表示与距离导数

定义和讨论了模糊数值函数的距离导数,给出了模糊有界变差函数全变差的积分表示.发现模糊绝对连续函数是几乎处处距离可导的,距离导数的积分等于其原函数的总变差,从而给出了模糊有界变差函数全变差的积分表示.     

Concerning the shape of a geometric lattice

A well-known conjecture states that the Whitney numbers of the second kind of a geometric lattice (simple matroid) are logarithmically concave. We show this conjecture to be equivalent to proving an upper bound on the number of new copoints in the free erection of the associated simple matroid M. A bound on the number of these new copoints is given in terms of the copoints and colines of M. Also, the points-lines-planes conjecture is shown to be equivalent to a problem concerning the number of subgraphs of a certain bipartite graph whose vertices are the points and lines of a geometric lattice.     

��������֦��������ǿ�������ɺ�Shannon-McMillan����

In this paper, we first study the strong law of large numbers for the frequencies of occurrence of random ordered couples of states for nonhomogeneous bifurcating Markov chains indexed by a binary tree. Then the strong law of large numbers are studied for functions of the nonhomogeneous bifurcating Markov chains indexed by a binary tree. As a corollary, we obtain the shannon-McMillan theorem for these Markov chains with finite state space.     

The Stochastic Location-Assignment Problem on a Tree

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.     

树映射的单侧γ-极限点集与拓扑熵

本文讨论了树映射的单侧γ-极限点集与吸引中心的关系，得到了树映射具有正拓扑熵的几个等价条件．此外，还得到了树映射是强非混沌以及逐片单调树映射的拓扑熵为零的几个等价条件．     

计算最小支撑出树的一种简便算法

本文通过对网络中有向支撑出树性质的研究,提出了在有向网络图中寻找以某一定点为根的最小有向支撑出树一种较简便的计算方法,并给出了应用该算法进行实际操作的一个算例．     

在有向网络中寻找最小支撑入树的计算方法

本文研究了有向网络中支撑入树的性质 ,提出了在有向网络图中寻找以某一指定点为根的最小支撑入树的一种较简便的算法 ,并给出了应用该算法的一个实际算例     

Prokhorov Radius of a Neighborhood of Zero Described by Three Moment Constraints

We determine the Prokhorov radius of the family of distributions surrounding the Dirac measure at zero whose first, second and fourth moments are bounded by given numbers. This provides the precise relation between the rates of weak convergence to zero and the rate of vanishing of the respective moments.     

正则树的双变量色多项式研究

最近Klaus Dohmen等人提出新的双变量色多项式概念,对此,本文提出—个—般性的减边公式.通过反复运用该公式,可以方便求得任何简单图的双变量色多项式.由此减边公式,研究了一些特殊图和多分支图的双变量色多项式公式.本文还研究了由互不相连的多个子图都与某个顶点相连而成的图的双变量色多项式计算的删点公式以及简单图的双变量色多项式系数和问题.进而,本文提出—个新概念—正则树.利用这个减边公式,研究了正则树的双变量色多项式计算公式和—些性质,以及正则树整子图的双变量色多项式公式及其有关性质.