Little Grothendieck`s theorem for real JB*-triples

We prove that given a real JB*-triple E, and a real Hilbert space H, then the set of those bounded linear operators T from E to H, such that there exists a norm one functional and corresponding pre-Hilbertian semi-norm on E such that for all , is norm dense in the set of all bounded linear operators from E to H. As a tool for the above result, we show that if A is a JB-algebra and is a bounded linear operator then there exists a state such that for all . Received June 28, 1999; in final form January 28, 2000 / Published online March 12, 2001     

Two Tree-Width-Like Graph Invariants

In this paper we introduce two tree-width-like graph invariants. The first graph invariant, which we denote by ⁼(G), is defined in terms of positive semi-definite matrices and is similar to the graph invariant (G), introduced by Colin de Verdière in [J. Comb. Theory, Ser. B., 74:121–146, 1998]. The second graph invariant, which we denote by (G), is defined in terms of a certain connected subgraph property and is similar to (G), introduced by van der Holst, Laurent, and Schrijver in [J. Comb. Theory, Ser. B., 65:291–304, 1995]. We give some theorems on the behaviour of these invariants under certain transformations. We show that ⁼(G)=(G) for any graph G with ⁼(G)4, and we give minimal forbidden minor characterizations for the graphs satisfying ⁼(G)k for k=1,2,3,4.This paper is extracted from two chapters of [7]. This work was done while the author was at the Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.     

For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

Denote by the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix > 0 and let . If n/2 m (1 – ) t ₃, then almost all graphs in are not bipartite, whereas if m (1 + )t ₃, then almost all of them are bipartite. For m (1 + )t ₃, this allows us to determine asymptotically the number of graphs in . We also obtain corresponding results for C -free graphs, for any cycle C of fixed odd length. Forschergruppe Algorithmen, Struktur, Zufall supported by Deutsche Forschungsgemeinschaft grant FOR 413/1-1     

Weak compactness in certain star-shift invariant subspaces

The context of much of the work in this paper is that of a backward-shift invariant subspace of the form , where B is some infinite Blaschke product. We address (but do not fully answer) the question: For which B can one find a (convergent) sequence in K_B such that the sequence of real measures converges weak-star to some nontrivial singular measure on ? We show that, in order for this to hold, K_B must contain functions with nontrivial singular inner factors. And in a rather special setting, we show that this is also sufficient. Much of the paper is devoted to finding conditions (on B) that guarantee that K_B has no functions with nontrivial singular inner factors. Our primary result in this direction is based on the “geometry” of the zero set of B.     

Transversals in Uniform Hypergraphs with Property (p,2)

Dedicated to the memory of Paul Erdős Let f(r,p,t) (p > t >= 1, r >= 2) be the maximum of the cardinality of a minimum transversal over all r-uniform hypergraphs possessing the property that every subhypergraph of with p edges has a transversal of size t. The values of f(r,p,2) for p = 3, 4, 5, 6 were found in [1] and bounds on f(r,7,2) are given in [3]. Here we prove that for large p and huge r. Received September 23, 1999 RID="*" ID="*" This work was partially supported by the grant 99-01-00581 of the Russian Foundation for Fundamental Research and the Dutch–Russian Grant NWO-047-008-006.     

Relative equidimensionality and stability of actions¶of a reductive algebraic group

In order to inquire into invariants of non-semisimple groups, we introduce and study relative versions of equidimensionality and stabilty, which are called relative quasi-equidimensionality and relative stability, of actions of affine algebraic groups, especially of reductive groups, on affine varieties. As an application of our results, for complex reductive groups of semisimple rank one, we characterize, respectively, relatively stable representations and relatively equidimensional representations and, consequently, show that every equidimensional representation is cofree. Received: 23 October 1998     

Laguerre-Galerkin method for nonlinear partial differential equations on a semi-infinite interval

Summary. A Laguerre-Galerkin method is proposed and analyzed for the Burgers equation and Benjamin-Bona-Mahony (BBM) equation on a semi-infinite interval. By reformulating these equations with suitable functional transforms, it is shown that the Laguerre-Galerkin approximations are convergent on a semi-infinite interval with spectral accuracy. An efficient and accurate algorithm based on the Laguerre-Galerkin approximations to the transformed equations is developed and implemented. Numerical results indicating the high accuracy and effectiveness of this algorithm are presented. Received October 6, 1997 / Revised version received July 22, 1999 / Published online June 21, 2000     

On one-sided versus two-sided classification

One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the gven class. Such a classifier istwo-sided if the sequence of its output in addition converges to 0 on setsnot belonging to the class. The present work obtains the below mentionedresults for one-sided classes (= Σ⁰ ₂ classes) with respect to four areas: Turing complexity, 1-reductions, index sets and measure. There are one-sided classes which are not two-sided. This can have two reasons: (1) the class has only high Turing complexity. Then there are some oracles which allow to construct noncomputale two-sided classifiers. (2) The class is difficult because of some topological constraints and then there are also no nonrecursive two-sided classifiers. For case (1), several results are obtainedto localize the Turing complexity of certain types of one-sided classes. The concepts of 1-reduction, 1-completeness and simple sets is transferred to one-sided classes: There are 1-complete classes and simple classes, but no class is at the same time 1-complete nd simple. The one-sided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity Π¹ ₁: the index set of the class {0,1}^∞, the index set of the equality problem and the index set of all two-sided classes. On the other side the index set of the empty class has complexity Π⁰ ₂; Π⁰ ₂ and Σ⁰ ₂ are the least complexities any nontrivial index set can have. Lusin showed that any one-sided class is measurable. Concerning the effectiveness of this measure, it is shown that a one-sided class has recursive measure 0 if it has measure 0, but that thre are one-sided classes having measure 1 without having measure 1 effectively. The measure of a two-sided class can be computed in the limit. Received: 2 December 1999 / Revised version: 28 February 2000 / Published online: 15 June 2001     

Iterates of expanding maps

The iterates of expanding maps of the unit interval into itself have many of the properties of a more conventional stochastic process, when the expanding map satisfies some regularity conditions and when the starting point is suitably chosen at random. In this paper, we show that the sequence of iterates can be closely tied to an m-dependent process. This enables us to prove good bounds on the accuracy of Gaussian approximations. Our main tools are coupling and Stein's method. Received: 27 June 1997 / Revised version: 21 September 1998     

On the iterative solution of the algebraic equations in fully implicit Runge-Kutta methods

This paper deals with the iterative solution of stage equations which arise when some fully implicit Runge-Kutta methods, in particular those based on Gauss, Radau and Lobatto points, are applied to stiff ordinary differential equations. The error behaviour in the iterates generated by Newton-type and, particularly, by single-Newton schemes which are proposed for the solution of stage equations is studied. We consider stiff systems y'(t) = f(t,y(t)) which are dissipative with respect to a scalar product and satisfy a condition on the relative variation of the Jacobian of f(t,y) with respect to y, similar to the condition considered by van Dorsselaer and Spijker in [7] and [17]. We prove new convergence results for the single-Newton iteration and derive estimates of the iteration error that are independent of the stiffness. Finally, some numerical experiments which confirm the theoretical results are presented. This revised version was published online in June 2006 with corrections to the Cover Date.