Barycentric systems and stretchability

Using a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least three free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible.     

Beyond Cartesian limits: Leibniz's passage from algebraic to “transcendental” mathematics

This article deals with Leibniz's reception of Descartes' “geometry.” Leibnizian mathematics was based on five fundamental notions: calculus, characteristic, art of invention, method, and freedom. On the basis of methodological considerations Leibniz criticized Descartes' restriction of geometry to objects that could be given in terms of algebraic (i.e., finite) equations: “Descartes's mind was the limit of science.” The failure of algebra to solve equations of higher degree led Leibniz to develop linear algebra, and the failure of algebra to deal with transcendental problems led him to conceive of a science of the infinite. Hence Leibniz reconstructed the mathematical corpus, created new (transcendental) notions, and redefined known notions (equality, exactness, construction), thus establishing “a veritable complement of algebra for the transcendentals”: infinite equations, i.e., infinite series, became inestimable tools of mathematical research.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.     

Invariant measures for equicontinuous semigroups of continuous transformations of a compact Hausdorff space

Equicontinuous semigroups of transformations of a compact Hausdorff space and their sets of all invariant (Borel, regular and probabilistic) measures are studied. Conditions equivalent to the existence of at least one invariant measure are given. The (algebraic and topological) structure of the set of invariant measures is researched.     

Estimating the largest singular values of large sparse matrices via modified moments

We describe a procedure for determining a few of the largest singular values of a large sparse matrix. The method by Golub and Kent which uses the method of modified moments for estimating the eigenvalues of operators used in iterative methods for the solution of linear systems of equations is appropriately modified in order to generate a sequence of bidiagonal matrices whose singular values approximate those of the original sparse matrix. A simple Lanczos recursion is proposed for determining the corresponding left and right singular vectors. The potential asynchronous computation of the bidiagonal matrices using modified moments with the iterations of an adapted Chebyshev semi-iterative (CSI) method is an attractive feature for parallel computers. Comparisons in efficiency and accuracy with an appropriate Lanczos algorithm (with selective re-orthogonalization) are presented on large sparse (rectangular) matrices arising from applications such as information retrieval and seismic reflection tomography. This procedure is essentially motivated by the theory of moments and Gauss quadrature.This author's work was supported by the National Science Foundation under grants NSF CCR-8717492 and CCR-910000N (NCSA), the U.S. Department of Energy under grant DOE DE-FG02-85ER25001, and the Air Force Office of Scientific Research under grant AFOSR-90-0044 while at the University of Illinois at Urbana-Champaign Center for Supercomputing Research and Development.This author's work was supported by the U.S. Army Research Office under grant DAAL03-90-G-0105, and the National Science Foundation under grant NSF DCR-8412314.     

Cohomological properties of the quantum shuffle product and application to the construction of quasi-Hopf algebras

For a commutative algebra the shuffle product is a morphism of complexes. We generalize this result to the quantum shuffle product, associated to a class of non-commutative algebras (for example all the Hopf algebras). As a first application we show that the Hochschild-Serre identity is the dual statement of our result. In particular, we extend this identity to Hopf algebras. Secondly, we clarify the construction of a class of quasi-Hopf algebras.     

A posteriori error estimators for the Stokes equations

Summary We present two a posteriori error estimators for the mini-element discretization of the Stokes equations. One is based on a suitable evaluation of the residual of the finite element solution. The other one is based on the solution of suitable local Stokes problems involving the residual of the finite element solution. Both estimators are globally upper and locally lower bounds for the error of the finite element discretization. Numerical examples show their efficiency both in estimating the error and in controlling an automatic, self-adaptive mesh-refinement process. The methods presented here can easily be generalized to the Navier-Stokes equations and to other discretization schemes.This work was accomplished at the Universität Heidelberg with the support of the Deutsche Forschungsgemeinschaft     

Multiderivations of Coxeter arrangements

Let V be an ℓ-dimensional Euclidean space. Let G⊂O(V) be a finite irreducible orthogonal reflection group. Let ? be the corresponding Coxeter arrangement. Let S be the algebra of polynomial functions on V. For H∈? choose α _H ∈V ^* such that H=ker(α _H ). For each nonnegative integer m, define the derivation module D ^(m) (?)={θ∈Der _S |θ(α _H )∈Sα ^m _H }. The module is known to be a free S-module of rank ℓ by K. Saito (1975) for m=1 and L. Solomon-H. Terao (1998) for m=2. The main result of this paper is that this is the case for all m. Moreover we explicitly construct a basis for D ^(m) (?). Their degrees are all equal to mh/2 (when m is even) or are equal to ((m−1)h/2)+m _i (1≤i≤ℓ) (when m is odd). Here m ₁≤···≤m _ℓ are the exponents of G and h=m _ℓ+1 is the Coxeter number. The construction heavily uses the primitive derivation D which plays a central role in the theory of flat generators by K. Saito (or equivalently the Frobenius manifold structure for the orbit space of G). Some new results concerning the primitive derivation D are obtained in the course of proof of the main result. Oblatum 27-XI-2001 & 4-XII-2001?Published online: 18 February 2002     

Characterization of supercommuting matrices

For a given n-by-n matrix A, we consider the set of matrices which commute with A and all of whose principal submatrices commute with the corresponding principal submatrices of A. The properties of this set are examined, with particular attention to its dimension.     

Deciding Frattini is NP-complete

We show that it is a NP-complete problem to decide whether a finite poset arises as the (Birkhoff) dual of the Frattini sublattice of some finite distributive lattice.This work was supported in part by Swiss NSF grant 20-32644.91.