Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

Starlike domains of convergence for Newton's method at singularities

Summary Given a solutionx ^* of a system of nonlinear equationsf with singular Jacobian f(x ^*) we construct an open starlike domainR of initial points, from which Newton's method converges linearly tox ^*. Under certain conditions the union of those straight lines throughx ^*, that do not intersect withR is shown to form a closed set of measure zero, which is necessarily disjoint from any starlike domain of convergence. The results apply to first and higher order singularities.     

Minimal surfaces,Hopf differentials and the Ricci condition

We deal with minimal surfaces in a sphere and investigate certain invariants of geometric significance, the Hopf differentials, which are defined in terms of the complex structure and the higher fundamental forms. We discuss the holomorphicity of Hopf differentials and provide a geometric interpretation for it in terms of the higher curvature ellipses. This motivates the study of a class of minimal surfaces, which we call exceptional. We show that exceptional minimal surfaces are related to Lawson’s conjecture regarding the Ricci condition. Indeed, we prove that, under certain conditions, compact minimal surfaces in spheres which satisfy the Ricci condition are exceptional. Thus, under these conditions, the proof of Lawson’s conjecture is reduced to its confirmation for exceptional minimal surfaces. In fact, we provide an affirmative answer to Lawson’s conjecture for exceptional minimal surfaces in odd dimensional spheres or in S ^4m .     

Limit Sets as Examples in Noncommutative Geometry

The fundamental group of a hyperbolic manifold acts on the limit set, giving rise to a cross-product C^*-algebra. We construct nontrivial K-cycles for the cross-product algebra, thereby extending some results of Connes and Sullivan to higher dimensions. We also show how the Patterson–Sullivan measure on the limit set can be interpreted as a center-valued KMS state.     

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.     

On rings in which every maximal one-sided ideal contains a maximal ideal

Given a ring R, consider the condition: (^*) every maximal right ideal of R contains a maximal ideal of R. We show that, for a ring R and 0 ≠ e ² = e ∈ R such that ele ? eRe every proper ideal I of R R satisfies (^*) if and only if eRe satisfies (^*). Hence with the help of some other results, (^*) is a Morita invariant property. For a simple ring R R[x] satisfies (^*) if and only if R[x] is not right primitive. By this result, if R is a division ring and R[x] satisfies (^*), then the Jacobson conjecture holds. We also show that for a finite centralizing extension S of a ring R R satisfies (^*) if and only if S satisfies (^*).     

Laguerre Geometry of Surfaces in R^3

Let f ： M → R3 be an oriented surface with non-degenerate second fundamental form. We denote by H and K its mean curvature and Gauss curvature. Then the Laguerre volume of f, defined by L（f） = f（H2 - K）/KdM, is an invariant under the Laguerre transformations. The critical surfaces of the functional L are called Laguerre minimal surfaces. In this paper we study the Laguerre minimal surfaces in R^3 by using the Laguerre Gauss map. It is known that a generic Laguerre minimal surface has a dual Laguerre minimal surface with the same Gauss map. In this paper we show that any surface which is not Laguerre minimal is uniquely determined by its Laguerre Gauss map. We show also that round spheres are the only compact Laguerre minimal surfaces in R^3. And we give a classification theorem of surfaces in R^3 with vanishing Laguerre form.     

Prime and primary submodules of certain modules

In this paper we characterize all prime and primary submodules of the free R-module R ⁿ for a principal ideal domain R and find the minimal primary decomposition of any submodule of R ⁿ . In the case n = 2, we also determine the height of prime submodules.     

Homological properties of the perfect and absolute integral closures of Noetherian domains

For a Noetherian local domain R let R ⁺ be the absolute integral closure of R and let R _∞ be the perfect closure of R, when R has prime characteristic. In this paper we investigate the projective dimension of residue rings of certain ideals of R ⁺ and R _∞. In particular, we show that any prime ideal of R _∞ has a bounded free resolution of countably generated free R _∞-modules. Also, we show that the analogue of this result is true for the maximal ideals of R ⁺, when R has residue prime characteristic. We compute global dimensions of R ⁺ and R _∞ in some cases. Some applications of these results are given.     

Blow up of solutions to nonlinear wave equation in 2D exterior domains

This article proves the nonexistence of global solutions to a semilinear wave equation on an exterior domain in \mathbbR²,{\mathbb{R}^2,} which is a part of Strauss’ conjecture.     

On separating conformal annuli and Mori’s ring domain in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Given four pointsa, b, c, d inℝ ⁿ we find the conformal annulus of minimal capacity which separatesa, b fromc, d. This result shows that a conjecture of M. Vuorinen is true. We also give an upper bound for the capacity of Mori’s ring domain in ℝ ⁿ .     

A Euclidean Ramsey Problem

Abstract. Let C _n denote the set of points in R ⁿ whose coordinates are all 0 or 1 , i.e., the vertex set of the unit n -cube. Graham and Rothschild [2] proved that there exists an integer N such that for n ≥ N , any 2-coloring of the edges of the complete graph on C _n contains a monochromatic plane K ₄ . Let N ^* be the minimum such N . They noted that N ^* must be at least 6 . Their upper bound on N ^* has come to be known as Graham's number , often cited as the largest number that has ever been put to any practical use. In this note we show that N ^* must be at least 11 and provide some experimental evidence suggesting that N ^* is larger still.     

The geometry of the asymptotics of polynomial maps

The aim of this paper is to develop a theory for the asymptotic behavior of polynomials and of polynomial maps overR and overC and to apply it to the Jacobian conjecture. This theory gives a unified frame for some results on polynomial maps that were not related before. A well known theorem of J. Hadamard gives a necessary and sufficient condition on a local diffeomorphismf: R ⁿ →R ⁿ to be a global diffeomorphism. In order to show thatf is a global diffeomorphism it suffices to exclude the existence of asymptotic values forf. The real Jacobian conjecture was shown to be false by S. Pinchuk. Our first application is to understand his construction within the general theory of asymptotic values of polynomial maps and prove that there is no such counterexample for the Jacobian conjecture overC. In a second application we reprove a theorem of Jeffrey Lang which gives an equivalent formulation of the Jacobian conjecture in terms of Newton polygons. This generalizes a result of Abhyankar. A third application is another equivalent formulation of the Jacobian conjecture in terms of finiteness of certain polynomial rings withinC[U, V]. The theory has a geometrical aspect: we define and develop the theory of etale exotic surfaces. The simplest such surface corresponds to Pinchuk's construction in the real case. In fact, we prove one more equivalent formulation of the Jacobian conjecture using etale exotic surfaces. We consider polynomial vector fields on etale exotic surfaces and explore their properties in relation to the Jacobian conjecture. In another application we give the structure of the real variety of the asymptotic values of a polynomial mapf: R ² →R ² .     

The natural functions on the cotangent bundle of higher order vector tangent bundles over fibered manifolds

For natural numbers r,s,q,m,n with s≥r≤q we determine all natural functions g: T ^*(J ^(r,s,q)(Y, R ^1,1)₀)^*→R for any fibered manifold Y with m-dimensional base and n-dimensional fibers. For natural numbers r,s,m,n with s≥r we determine all natural functions g: T ^*(J ^(r,s) (Y, R)₀)^*→R for any Y as above.     

Recasting the Elliott conjecture

Let A be a simple, unital, finite, and exact C^*-algebra which absorbs the Jiang–Su algebra tensorially. We prove that the Cuntz semigroup of A admits a complete order embedding into an ordered semigroup which is obtained from the Elliott invariant in a functorial manner. We conjecture that this embedding is an isomorphism, and prove the conjecture in several cases. In these same cases— -stable algebras all—we prove that the Elliott conjecture in its strongest form is equivalent to a conjecture which appears much weaker. Outside the class of -stable C^*-algebras, this weaker conjecture has no known counterexamples, and it is plausible that none exist. Thus, we reconcile the still intact principle of Elliott’s classification conjecture—that -theoretic invariants will classify separable and nuclear C^*-algebras—with the recent appearance of counterexamples to its strongest concrete form. Research supported by the DGI MEC-FEDER through Project MTM2005-00934, and the Comissionat per Universitats i Recerca de la Generalitat de Catalunya. A. S. Toms was also supported in part by an NSERC Discovery Grant.     

Uniform Families and Count Matroids

Given an r-graph G on [n], we are allowed to add consecutively new edges to it provided that every time a new r-graph with at least l edges and at most m vertices appears. Suppose we have been able to add all edges. What is the minimal number of edges in the original graph? For all values of parameters, we present an example of G which we conjecture to be extremal and establish the validity of our conjecture for a range of parameters. Our proof utilises count matroids which is a new family of matroids naturally extending that of White and Whiteley. We characterise, in certain cases, the extremal graphs. In particular, we answer a question by Erdős, Füredi and Tuza. Received: May 6, 1998 Final version received: September 1, 1999     

Construction of Gibbs measures for 1-dimensional continuum fields

We study 1-dimensional continuum fields of Ginzburg-Landau type under the presence of an external and a long-range pair interaction potentials. The corresponding Gibbs states are formulated as Gibbs measures relative to Brownian motion [17]. In this context we prove the existence of Gibbs measures for a wide class of potentials including a singular external potential as hard-wall ones, as well as a non-convex interaction. Our basic methods are: (i) to derive moment estimates via integration by parts; and (ii) in its finite-volume construction, to represent the hard-wall Gibbs measure on C(ℝ;ℝ⁺) in terms of a certain rotationally invariant Gibbs measure on C(ℝ;ℝ³).     

Projections and power reduction property for generalized identities of symmetric elements

Abstract. Let R be a finite-dimensional central simple C-algebra with involution * of the first kind, char R ≠ 2 and let E ^*(R)be the C-subspace of R, spanned by all projections. In this paper we prove a proposition concerning invariant submodules in prime rings with involution and then decide E ^*(R). As a consequence we prove the power reduction property for generalized identities of symmetric elements in a 2-torsion free semiprime ring with involution.     

Perturbazione dello spettro di un operatore ellittico di tipo variazionale,in relazione ad una variazione del campo

Summary Let Ω be an open bounded set in R^m and let E_Ω be an elliptic self-adjoint variational operator with Dirichlet's data zero. Changing suitably the shape of Ω, we obtain a new open set Ω* such that E_Ω* has only simple eigenvalues. Moreover choosing a suitable metric for the family of the open sets diffromorphic to Ω, the set of all Ω* such that E_Ω* has multiple eigenvalues, is of the first category.

---

---

Entrata in Redazione il 20 dicembre 1972.

---

Lavoro eseguito nell'ambito del contratto di ricerca del C.N.R. comitato per la matematica.     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.