Separating Cycles in Doubly Toroidal Embeddings

 We show that every 4-representative graph embedding in the double torus contains a noncontractible cycle that separates the surface into two pieces. As a special case, every triangulation of the double torus in which every noncontractible cycle has length at least 4 has a noncontractible cycle that separates the surface into two pieces. Received: May 22, 2001 Final version received: August 22, 2002 RID="*" ID="*" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070613 RID="†" ID="†" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070430     

Simple and immune relations on countable structures

 Let 𝒜 be a computable structure and let R be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy ℬ of 𝒜 in which the image of R (?R, resp.) is simple (immune, resp.) relative to ℬ. We also establish, under certain effectiveness conditions on 𝒜 and R, a necessary and sufficient condition for the existence of a computable copy ℬ of 𝒜 in which the image of R (?R, resp.) is simple (immune, resp.). Received: 4 February 2001 Published online: 5 November 2002 RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899. RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899. RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899.     

Some new PDE methods for weak KAM theory

We discuss a new approximate variational principle for weak KAM theory. The advantage of this approach is that we build both a minimizing measure and a solution of the generalized eikonal equation at the same time. Furthermore the approximations are smooth, and so we can derive some interesting formulas upon differentiating the Euler-Lagrange equation. Our method is inspired by the ”calculus of variations in the sup-norm” ideas of Aronsson, Jensen, Barron and others. Received: 30 November 2001 / Accepted: 23 January 2002 / Published online: 5 September 2002 RID="*" ID="*" Supported in part by NSF Grant DMS-0070480 and by the Miller Institute for Basic Research in Science, UC Berkeley     

Morse theory on spaces of braids and Lagrangian dynamics

In the first half of the paper we construct a Morse-type theory on certain spaces of braid diagrams. We define a topological invariant of closed positive braids which is correlated with the existence of invariant sets of parabolic flows defined on discretized braid spaces. Parabolic flows, a type of one-dimensional lattice dynamics, evolve singular braid diagrams in such a way as to decrease their topological complexity; algebraic lengths decrease monotonically. This topological invariant is derived from a Morse-Conley homotopy index.?In the second half of the paper we apply this technology to second order Lagrangians via a discrete formulation of the variational problem. This culminates in a very general forcing theorem for the existence of infinitely many braid classes of closed orbits. Oblatum 11-V-2001 & 13-XI-2002?Published online: 24 February 2003 RID="*" ID="*"The first author was supported by NSF DMS-9971629 and NSF DMS-0134408. The second author was supported by an EPSRC Fellowship. The third author was supported by NWO Vidi-grant 639.032.202.     

Convergent adaptive finite elements for the nonlinear Laplacian

Summary. The numerical solution of the homogeneous Dirichlet problem for the p-Laplacian, , is considered. We propose an adaptive algorithm with continuous piecewise affine finite elements and prove that the approximate solutions converge to the exact one. While the algorithm is a rather straight-forward generalization of those for the linear case p=2, the proof of its convergence is different. In particular, it does not rely on a strict error reduction. Received December 29, 2000 / Revised version received August 30, 2001 / Published online December 18, 2001 RID="*" ID="*" Current address: Dipartimento di Matematica, Università degli Studi di Milano, Via C. Saldini 50, 20133 Milano, Italy; e-mail: veeser@mat.unimi.it     

Propagation of polarization in elastodynamics with residual stress and travel times

 We show that knowing the displacement-to-traction map associated to the equations of isotropic elastodynamics with residual stress we can determine the lens maps of compressional and shear waves. We derive several consequences of this for the inverse problem of determining the residual stress and the Lamé parameters from the displacement-to-traction map. Received: 6 December 2001 / Revised version: 29 October 2002 / Published online: 8 April 2003 RID="⋆" ID="⋆" The author thanks the Department of Mathematics at the University of Washington for its hospitality during his visit in fall 2000. RID="⋆⋆" ID="⋆⋆" Partly supported by NSF grant DMS-0070488 and a John Simon Guggenheim fellowship. The author also thanks MSRI for partial support and for providing a very stimulating environment during the inverse problems program in fall 2001.     

Error bounds for minimal energy bivariate polynomial splines

Summary. We derive error bounds for bivariate spline interpolants which are calculated by minimizing certain natural energy norms. Received March 28, 2000 / Revised version received June 23, 2000 / Published online March 8, 2002 RID="*" ID="*" Supported by the National Science Foundation under grant DMS-9870187 RID="**" ID="**" Supported by the National Science Foundation under grant DMS-9803340 and by the Army Research Office under grant DAAD-19-99-1-0160     

On the convergence of the Weiszfeld algorithm

In this work we analyze the paper “Brimberg, J. (1995): The Fermat-Weber location problem revisited. Mathematical Programming 71, 71–76” which claims to close the question on the conjecture posed by Chandrasekaran and Tamir in 1989 on the convergence of the Weiszfeld algorithm. Some counterexamples are shown to the proofs showed in Brimberg’s paper. Received: January 1999 / Accepted: December 2001?Published online April 12, 2002 RID="*" ID="*"Partially supported by PB/11/FS/97 of Fundación Séneca of the Comunidad Autónoma de la Región de Murcia RID="**" ID="**"Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+I+D), project TIC2000-1750-C06-06 RID="*" RID="**"     

Intersecting Curves in the Plane

 We prove that for every family of n pairwise intersecting simple closed planar curves in general position, at least (4/5)n ²−O(n) points lie on more than one curve. This improves the previous lower bound of (3/4)n ²−O(n) due to Richter and Thomassen. Received: March 29, 2000 Final version received: August 30, 2001 RID="*" ID="*" Research supported in part by NSF grant DMS-9970325 Acknowledgments. I thank Bruce Richter for informing me about this problem, Gelasio Salazar for reading a preliminary version of the paper, and a Referee for useful comments. Current Address: Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, USA. e-mail: mubayi@microsoft.com 1991 Mathematics Subject Classification. 05C35, 52C10     

Some observations on Babu\vs}ka and Brezzi theories

Summary. Some observations are made on abstract error estimates for Galerkin approximations based on Babuška-Brezzi conditions. A basic error estimate due to Babuška is sharpened by means of an identity that for any nontrivial idempotent operator P. Some remarks are also made on the Brezzi's theory for mixed variational problems and their Galerkin approximations. Received March 1, 2000 / Revised version received September 28, 2000 / Published online June 17, 2002 RID="*" ID="*" This work was partially supported by NSF DMS-9706949, NSF ACI-9800244 and NASA NAG2-1236 Correspondence to: J. Xu     

Effects of uncertainties in the domain on the solution of Dirichlet boundary value problems

Summary. A domain with possibly non-Lipschitz boundary is defined as a limit of monotonically expanding or shrinking domains with Lipschitz boundary. A uniquely solvable Dirichlet boundary value problem (DBVP) is defined on each of the Lipschitz domains and the limit of these solutions is investigated. The limit function also solves a DBVP on the limit domain but the problem can depend on the sequences of domains if the limit domain is unstable with respect to the DBVP. The core of the paper consists in estimates of the difference between the respective solutions of the DBVP on two close domains, one of which is Lipschitz and the other can be unstable. Estimates for starshaped as well as rather general domains are derived. Their numerical evaluation is possible and can be done in different ways. Received October 16, 2001 / Revised version received January 16, 2002 / Published online: April 17, 2002 RID="*" ID="*" The research was funded partially by the National Science Foundation under the grants NSF–Czech Rep. INT-9724783 and NSF DMS-9802367 RID="**" ID="**" Support for Jan Chleboun coming from the Grant Agency of the Czech Republic through grant 201/98/0528 is appreciated     

A new proof of regularity of weak solutions of the <Emphasis Type="Italic">H</Emphasis>-surface equation

Abstract. We give a new proof of a theorem of Bethuel, asserting that arbitrary weak solutions of the H-surface system are locally H?lder continuous provided that H is a bounded Lipschitz function. Contrary to Bethuel's, our proof completely omits Lorentz spaces. Estimates below natural exponents of integrability are used instead. (The same method yields a new proof of Hélein's theorem on regularity of harmonic maps from surfaces into arbitrary compact Riemannian manifolds.) We also prove that weak solutions with continuous trace are continuous up to the boundary, and give an extension of these results to the equation of hypersurfaces of prescribed mean curvature in , this time assuming in addition that decays at infinity like . Received: 10 May 2001 / Accepted: 7 June 2001 / Published online: 18 January 2002 The author gratefully acknowledges the generous support of Alexander von Humboldt Foundation, and the hospitality of Mathematisches Institut der Universit?t Bonn, where this research has been carried out. In particular, many thanks are due to Professor Stefan Hildebrandt.     

A likelihood-MPEC approach to target classification

In this paper we develop a method for classifying an unknown data vector as belonging to one of several classes. This method is based on the statistical methods of maximum likehood and borrowed strength estimation. We develop an MPEC procedure (for Mathematical Program with Equilibrium Constraints) for the classification of a multi-dimensional observation, using a finite set of observed training data as the inputs to a bilevel optimization problem. We present a penalty interior point method for solving the resulting MPEC and report numerical results for a multispectral minefield classification application. Related approaches based on conventional maximum likehood estimation and a bivariate normal mixture model, as well as alternative surrogate classification objective functions, are described. Received: October 26, 1998 / Accepted: June 11, 2001?Published online March 24, 2003 RID="***" ID="***"The authors of this work were all partially supported by the Wright Patterson Air Force Base via Veda Contract F33615-94-D-1400. The first and third author were also supported by the National Science Foundation under grant DMS-9705220. RID="*" ID="*"The work of this author was based on research supported by the U.S. National Science Foundation under grant CCR-9624018. RID="**" ID="**"The work of this author was supported by the Office of Naval Research under grant N00014-95-1-0777.     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

Subexponential decay of correlations

We describe a method for proving subexponential lower bounds for correlations functions, and apply it to study decay of correlations for maps with countable Markov partitions. One result is that LS Young’s upper estimates [Y2] are optimal in many situations. Our method is based on a general result concerning the asymptotics of renewal sequences of bounded operators acting on Banach spaces, which we apply to the iterates of the transfer operator. Oblatum 14-VII-2001 & 5-VI-2002?Published online: 6 August 2002 Dedicated to B. Weiss on the occasion of his 60th birthday RID="*" ID="*"This research was supported by the Nuffield Foundation, NUF-NAL 00.     

Curvature and uniformization

We approach the problem of uniformization of general Riemann surfaces through consideration of the curvature equation, and in particular the problem of constructing Poincaré metrics (i.e., complete metrics of constant negative curvature) by solving the equation Δu-e ^2u=K_o(z) on general open surfaces. A few other topics are discussed, including boundary behavior of the conformal factore ^2u giving the Poincaré metric when the Riemann surface has smoothly bounded compact closure, and also a curvature equation proof of Koebe's disk theorem. Research supported in part by NSF Grant DMS-9971975 and also at MSRI by NSF grant DMS-9701755. Research supported in part by NSF Grant DMS-9877077     

Unification of boolean,monotone, anti-monotone,and tensor independence and Lévy processes

The unification of the boolean and the tensor product of quantum probability spaces given by Lenczewski [Len98] is modified to include the monotone product and its mirror image, the anti-monotone product, and used to reduce the theories of boolean, monotone, and anti-monotone Lévy processes on dual semi-groups to the theory of Lévy processes on involutive bialgebras. This leads to a representation theorem for these processes. Further applications are a proof of the Schoenberg correspondence for boolean, monotone, and anti-monotone convolution semi-groups, a realization of boolean, monotone, and anti-monotone creation, annihilation, and conservation operators on boson Fock spaces, and a discussion of the Markov structure of these Lévy processes. Received: 25 April 2001 / Accepted in final form: 30 April 2002 /Published online: 24 February 2003