On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance

The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.Received March 16, 2004     

Admissible slopes for monotone and convex interpolation

Summary In many applications, interpolation of experimental data exhibiting some geometric property such as nonnegativity, monotonicity or convexity is unacceptable unless the interpolant reflects these characteristics. This paper identifies admissible slopes at data points of variousC ¹ interpolants which ensure a desirable shape. We discuss this question, in turn for the following function classes commonly used for shape preserving interpolations: monotone polynomials,C ¹ monotone piecewise polynomials, convex polynomials, parametric cubic curves and rational functions.     

On the electron energy spectrum in heavily doped non-parabolic semiconductors

An attempt is made to present a simple theoretical analysis of the energy-wave vector dispersion relation of the conduction electrons in heavily doped non-parabolic semiconductors forming band tails. We observe that the complex energy spectrum in doped small-gap materials whose unperturbed conduction band is described by the three band model of Kane is due to the interaction of the impurity atoms in the tail with the spin-orbit splitting constant of the valence band (Δ), For band-gap (E_g)<Δ the imaginary part predominates which tails in to the conduction band. For the opposite inequality the real part comes in to play which tails in to the split-off band. In the absence of the band tailing effect, the imaginary part of the complex energy spectrum vanishes and the same is also true for doped two-band Kane-type and parabolic energy bands respectively. The present formulation helps us in investigating the Boltzmann transport equation dependent transport properties of degenerate semiconductors and are expected to agree better with experiments. The well-known results of unperturbed three and two band models of Kane together with wide-gap parabolic energy bands have been obtained as special cases of our generalized analysis under certain limiting conditions.     

On a conjecture of Fefferman and Graham

In 1985, Fefferman and Graham have constructed a local embedding of an arbitrary real-analytic manifold, of odd dimension n, into a Ricci-flat manifold of dimension n+2 admitting a homothety. They conjectured that their result remains valid in even dimensions, if logarithms are allowed in the expansion of the metric. In this paper, we (i) prove that such expansions exist and converge and (ii) establish the degree of non-uniqueness of the solution in terms of the coefficients in the expansion.     

Long Abelian ideals

We study Abelian ideals of a Borel subalgebra consisting of long roots. It is shown that methods of Cellini and Papi can be extended to this situation. A uniform expression for the number of long Abelian ideals is given. We also show that there is a one-to-one correspondence between the long Abelian ideals and B-stable commutative subalgebras in the little adjoint representation of the Langlands dual Lie algebra.     

A geometrical constraint for capillary jet breakup

The formation of thinning filaments is commonly observed previously to the break-up of a very viscous jet. This paper shows that a fluid under capillary forces cannot break-up through the uniform collapse of a filament.     

Multilinear interpolation between adjoint operators

Multilinear interpolation is a powerful tool used in obtaining strong-type boundedness for a variety of operators assuming only a finite set of restricted weak-type estimates. A typical situation occurs when one knows that a multilinear operator satisfies a weak L^q estimate for a single index q (which may be less than one) and that all the adjoints of the multilinear operator are of similar nature, and thus they also satisfy the same weak L^q estimate. Under this assumption, in this note we give a general multilinear interpolation theorem which allows one to obtain strong-type boundedness for the operator (and all of its adjoints) for a large set of exponents. The key point in the applications we discuss is that the interpolation theorem can handle the case q?1. When q>1, weak L^q has a predual, and such strong-type boundedness can be easily obtained by duality and multilinear interpolation (cf. Interpolation Spaces, An Introduction, Springer, New York, 1976; Math. Ann. 319 (2001) 151; in: Function Spaces and Applications (Lund, 1986), Lecture Notes in Mathematics, Vol. 1302, Springer, Berlin, New York, 1988; J. Amer. Math. Soc. 15 (2002) 469; Proc. Amer. Math. Soc. 21 (1969) 441).