On the Combinatorics of Rooted Binary Phylogenetic Trees

We study subtree-prune-and-regraft (SPR) operations on leaf-labelled rooted binary trees, also known as rooted binary phylogenetic trees. This study is motivated by the problem of graphically representing evolutionary histories of biological sequences subject to recombination. We investigate some basic properties of the induced SPR-metric on the space of leaf-labelled rooted binary trees with n leaves. In contrast to the case of unrooted trees, the number |U(T)| of trees in which are one SPR operation away from a given tree depends on the topology of T. In this paper, we construct recursion relations which allow one to determine the unit-neighbourhood size |U(T)| efficiently for any tree topology. In fact, using the recursion relations we are able to derive a simple closed-form formula for the unit-neighbourhood size. As a corollary, we construct sharp upper and lower bounds on the size of unit-neighbourhoods and investigate the diameter of . Lastly, we consider an enumeration problem relevant to population genetics.AMS Subject Classification: 05C05, 92D15.     

Embeddings and Other Mappings of Rooted Trees Into Complete Trees

Let T ⁿ be the complete binary tree of height n, with root 1 _n as the maximum element. For T a tree, define and . We disprove a conjecture of Kubicki, Lehel and Morayne, which claims that for any fixed n and arbitrary rooted trees T ₁ T ₂. We show that A(n; T) is of the form where l is the number of leaves of T, and each q _j is a polynomial. We provide an algorithm for calculating the two leading terms of q _l for any tree T. We investigate the asymptotic behaviour of the ratio A(n; T)/C(n; T) and give examples of classes of pairs of trees T ₁, T ₂ where it is possible to compare A(n; T ₁)/C(n; T ₁) and A(n; T ₂)/C(n; T ₂). By calculating these ratios for a particular class of pairs of trees, we show that the conjecture fails for these trees, for all sufficiently large n. Kubicki, Lehel and Morayne have proved the conjecture when T ₁, T ₂ are restricted to being binary trees. We also look at embeddings into other complete trees, and we show how the result can be viewed as one of many possible correlation inequalities for embeddings of binary trees. We also show that if we consider strict order-preserving maps of T ₁, T ₂ into T ⁿ (rather than embeddings) then the corresponding correlation inequalities for these maps also generalise to arbitrary trees.     

Modified mann iterations for nonexpansive semigroups in Banach space

Let E be a real reflexive Banach space which admits a weakly sequentially continuous duality mapping from E to E^＊, and C be a nonempty closed convex subset of E. Let {T（t） ： t ≥ 0} be a nonexpansive semigroup on C such that F ：=∩t≥0 Fix（T（t）） ≠ 0, and f ： C → C be a fixed contractive mapping. If {αn}, {βn}, {an}, {bn}, {tn} satisfy certain appropriate conditions, then we suggest and analyze the two modified iterative processes as：{yn=αnxn＋（1-αn）T（tn）xn,xn=βnf（xn）＋（1-βn）yn
{u0∈C,vn=anun＋（1-an）T（tn）un,un＋1=bnf（un）＋（1-bn）vn
We prove that the approximate solutions obtained from these methods converge strongly to q ∈∩t≥0 Fix（T（t））, which is a unique solution in F to the following variational inequality：
〈（I-f）q,j（q-u）〉≤0 u∈F Our results extend and improve the corresponding ones of Suzuki [Proc. Amer. Math. Soc., 131, 2133-2136 （2002）], and Kim and XU [Nonlear Analysis, 61, 51-60 （2005）] and Chen and He [Appl. Math. Lett., 20, 751-757 （2007）].     

Properties of Subtree-Prune-and-Regraft Operations on Totally-Ordered Phylogenetic Trees

We study some properties of subtree-prune-and-regraft (SPR) operations on leaflabelled rooted binary trees in which internal vertices are totally ordered. Since biological events occur with certain time ordering, sometimes such totally-ordered trees must be used to avoid possible contradictions in representing evolutionary histories of biological sequences. Compared to the case of plain leaf-labelled rooted binary trees where internal vertices are only partially ordered, SPR operations on totally-ordered trees are more constrained and therefore more difficult to study. In this paper, we investigate the unit-neighbourhood U(T), defined as the set of totally-ordered trees one SPR operation away from a given totally-ordered tree T. We construct a recursion relation for | U(T) | and thereby arrive at an efficient method of determining | U(T) |. In contrast to the case of plain rooted trees, where the unit-neighbourhood size grows quadratically with respect to the number n of leaves, for totally-ordered trees | U(T) | grows like O(n³). For some special topology types, we are able to obtain simple closed-form formulae for | U(T) |. Using these results, we find a sharp upper bound on | U(T) | and conjecture a formula for a sharp lower bound. Lastly, we study the diameter of the space of totally-ordered trees measured using the induced SPR-metric. Received May 18, 2004     

A presentation for the singular part of the full transformation semigroup

The (full) transformation semigroup T_n\mathcal{T}_{n} is the semigroup of all functions from the finite set {1,…,n} to itself, under the operation of composition. The symmetric group S_n í T_n{\mathcal{S}_{n}\subseteq \mathcal{T}_{n}} is the group of all permutations on {1,…,n} and is the group of units of T_n\mathcal{T}_{n}. The complement T_n\S_n\mathcal{T}_{n}\setminus \mathcal{S}_{n} is a subsemigroup (indeed an ideal) of T_n\mathcal{T}_{n}. In this article we give a presentation, in terms of generators and relations, for T_n\S_n\mathcal{T}_{n}\setminus \mathcal{S}_{n}, the so-called singular part of T_n\mathcal{T}_{n}.     

A 2-basic set of the alternating group

In this note, we construct a 2-basic set of the alternating group \mathfrakA_n{\mathfrak{A}_n}. To do this, we construct a 2-basic set of the symmetric group \mathfrakS_n{\mathfrak{S}_n} with an additional property, such that its restriction to \mathfrakA_n{\mathfrak{A}_n} is a 2-basic set. We adapt here a method developed by Brunat and Gramain (J. Reine Angew. Math., to appear) for the case when the characteristic is odd. One of the main tools is the generalized perfect isometries defined by Külshammer et al. (Invent. Math. 151, 513–552, (2003)).     

Some properties for a class of symmetric functions with applications

For x = (x ₁, x ₂, ..., x _n ) ∈ ℝ₊ ⁿ , the symmetric function ψ _n (x, r) is defined by $\psi _n (x,r) = \psi _n \left( {x_1 ,x_2 , \cdots ,x_n ;r} \right) = \sum\limits_{1 \leqslant i_1 < i_2 \cdots < i_r \leqslant n} {\prod\limits_{j = 1}^r {\frac{{1 + x_{i_j } }} {{x_{i_j } }}} } ,$\psi _n (x,r) = \psi _n \left( {x_1 ,x_2 , \cdots ,x_n ;r} \right) = \sum\limits_{1 \leqslant i_1 < i_2 \cdots < i_r \leqslant n} {\prod\limits_{j = 1}^r {\frac{{1 + x_{i_j } }} {{x_{i_j } }}} } ,     

Integral inequalities for self-reciprocal polynomials

Let n ≥ 1 be an integer and let P _n be the class of polynomials P of degree at most n satisfying z ⁿ P(1/z) = P(z) for all z ∈ C. Moreover, let r be an integer with 1 ≤ r ≤ n. Then we have for all P ∈ P _n :

On the zeros of a class of generalised Dirichlet series-XIV

We prove a general theorem on the zeros of a class of generalised Dirichlet series. We quote the following results as samples. Theorem A.Let 0<θ<1/2and let {a _n }be a sequence of complex numbers satisfying the inequality for N = 1,2,3,…,also for n = 1,2,3,…let α _n be real and |α_n| ≤ C(θ)where C(θ) > 0is a certain (small)constant depending only on θ. Then the number of zeros of the function in the rectangle (1/2-δ⩽σ⩽1/2+δ,T⩽t⩽2T) (where 0<δ<1/2)is ≥C(θ,δ)T logT where C(θ,δ)is a positive constant independent of T provided T ≥T ₀(θ,δ)a large positive constant. Theorem B.In the above theorem we can relax the condition on a _n to and |a_N| ≤ (1/2-θ)^-1.Then the lower bound for the number of zeros in (σ⩾1/3−δ,T⩽t⩽2T)is > C(θ,δ) Tlog T(log logT)^-1.The upper bound for the number of zeros in σ⩾1/3+δ,T⩽t⩽2T) isO(T)provided for every ε > 0. Dedicated to the memory of Professor K G Ramanathan     

Limit theorems for the ratio of the empirical distribution function to the true distribution function

Summary We consider almost sure limit theorems for and where _n is the empirical distribution function of a random sample ofn uniform (0, 1) random variables anda _n 0. It is shown that (1) ifna _n /log₂ n then both and converge to 1 a.s.; (2) ifna _n /log₂ n=d>0 (d>1) then has an almost surely finite limit superior which is the solution of a certain transcendental equation; and (3) ifna _n /log₂ n0 then and have limit superior + almost surely. Similar results are established for the inverse function _n ^–1 .Supported by the National Science Foundation under MCS 77-02255