On the structure of rotation-invariant semigroups

 We generalize the notions of Girard algebras and MV-algebras by introducing rotation-invariant semigroups. Based on a geometrical characterization, we present five construction methods which result in rotation-invariant semigroups and in particular, Girard algebras and MV-algebras. We characterize divisibility of MV-algebras, and point out that integrality of Girard algebras follows from their other axioms. Received: 7 January 2002 / Revised version: 4 April 2002 / Published online: 19 December 2002 RID="*" ID="*" Supported by the National Scientific Research Fund Hungary (OTKA F/032782). Mathematics Subject Classification (2000): 20M14, 06F05 Key words or phrases: Residuated lattice – Conjunction for non-classical logics     

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.     

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     

Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems

 Dantzig, Fulkerson, and Johnson (1954) introduced the cutting-plane method as a means of attacking the traveling salesman problem; this method has been applied to broad classes of problems in combinatorial optimization and integer programming. In this paper we discuss an implementation of Dantzig et al.'s method that is suitable for TSP instances having 1,000,000 or more cities. Our aim is to use the study of the TSP as a step towards understanding the applicability and limits of the general cutting-plane method in large-scale applications. Received: December 6, 2002 / Accepted: April 24, 2003 Published online: May 28, 2003 RID="*" ID="*" Supported by ONR Grant N00014-03-1-0040     

Numerical schemes for Hamilton-Jacobi equations on unstructured meshes

Summary.  In this paper, a numerical scheme is presented by applying the finite element method to the viscosity equations of the Hamilton-Jacobi equations on unstructured meshes. By improving the finite element scheme, another numerical scheme is constructed. Under certain limitations, the numerical solutions of the two schemes converge to the viscosity solutions of the Hamilton-Jacobi equations. The latter numerical scheme has weaker restrictions than the former scheme for convergence. Numerical examples are provided to test the stability, convergence and sensitivity to different meshes. Received November 5, 2001 / Revised version received March 5, 2002 / Published online October 29, 2002 RID="*" ID="*" Current address: Department of Applied Mathematics, University of Petroleum, Dongying 257062, Shandong, P.R.China; e-mail: xianggui_li@sina.com Mathematics Subject Classification (1991): 65M60     

Uniqueness of positive multi-lump bound states of nonlinear Schrödinger equations

In this paper we are concerned with multi-lump bound states of the nonlinear Schr?dinger equation for sufficiently small , where for and for . V is bounded on . For any finite collection of nondegenerate critical points of V, we show the uniqueness of solutions of the form for , where u is positive on and is a small perturbation of a sum of one-lump solutions concentrated near , respectively for sufficiently small . Received: 30 October 2001; in final form: 10 June 2002 /Published online: 2 December 2002 RID="*" ID="*" Research supported by Alexander von Humboldt Foundation in Germany and NSFC in China     

A primal all-integer algorithm based on irreducible solutions

 This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method. Received: April 23, 2001 / Accepted: May 2002 Published online: March 21, 2003 RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="#" ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202. Mathematics Subject Classification (1991): 90C10     

$L^p$ Approximation of maps by diffeomorphisms

It is shown that if then every map of class can be approximated in the -norm by a sequence of orientation-preserving diffeomorphims These conclusions hold provided that is open, bounded, and that In addition, is contained in the -neighborhood of the convex hull of All these conclusions fail for The main ingredients of the proof are the polar factorization of maps [4] and an approximation result for measure-preserving maps on the unit cube for which we provide a proof based on the concept of doubly stochastic measures (Corollary 1.1). Received: 25 My 2001 / Accepted: 25 October 2001 / Published online: 29 April 2002 RID="*" ID="*" en détachement de l'Université Paris 6, France The second author gratefully acknowledges the support of National Science Foundation grants DMS-99-70520, and DMS-00-74037     

The Baum-Connes conjecture for hyperbolic groups

We prove the Baum-Connes conjecture for hyperbolic groups and their subgroups. Oblatum 20-VI-2001 & 24-VIII-2001?Published online: 15 April 2002 RID="*" ID="*"The second author is partially supported by NSF and MSRI.     

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.     

A unimodularly invariant theory for immersions into the affine space

We develop a unimodularly invariant theory for immersions with higher codimension into the affine space. Received: 6 September 2001; in final form: 22 November 2001 / Published online: 29 April 2002 RID="*" ID="*" Supported by the Deutsche Forschungsgemeinschaft     

Weakly Gibbsian representations for joint measures of quenched lattice spin models

Can the joint measures of quenched disordered lattice spin models (with finite range) on the product of spin-space and disorder-space be represented as (suitably generalized) Gibbs measures of an “annealed system”? - We prove that there is always a potential (depending on both spin and disorder variables) that converges absolutely on a set of full measure w.r.t. the joint measure (“weak Gibbsianness”). This “positive” result is surprising when contrasted with the results of a previous paper [K6], where we investigated the measure of the set of discontinuity points of the conditional expectations (investigation of “a.s. Gibbsianness”). In particular we gave natural “negative” examples where this set is even of measure one (including the random field Ising model). Further we discuss conditions giving the convergence of vacuum potentials and conditions for the decay of the joint potential in terms of the decay of the disorder average over certain quenched correlations. We apply them to various examples. From this one typically expects the existence of a potential that decays superpolynomially outside a set of measure zero. Our proof uses a martingale argument that allows to cut (an infinite-volume analogue of) the quenched free energy into local pieces, along with generalizations of Kozlov's constructions. Received: 11 November 1999 / Revised version: 18 April 2000 / Published online: 22 November 2000 RID="*" ID="*" Work supported by the DFG Schwerpunkt `Wechselwirkende stochastische Systeme hoher Komplexit?t'     

Van Kampen’s embedding obstruction for discrete groups

We give a lower bound to the dimension of a contractible manifold on which a given group can act properly discontinuously. In particular, we show that the n-fold product of nonabelian free groups cannot act properly discontinuously on ℝ^{2 n −1}. Oblatum 19-I-2001 & 29-V-2002?Published online: 5 September 2002 RID="*" ID="*"All three authors gratefully acknowledge the support by the National Science Foundation.