Common complements of two subspaces of a Hilbert space

In this paper we find a necessary and sufficient condition for two closed subspaces, and , of a Hilbert space to have a common complement, i.e. a subspace having trivial intersection with and and such that .Unlike the finite-dimensional case the condition is significantly more subtle than simple equalities of dimensions and codimensions, and non-trivial examples of subspaces without a common complement are possible.     

Approximating disjoint-path problems using packing integer programs

In a packing integer program, we are given a matrix $A$ and column vectors $b,c$ with nonnegative entries. We seek a vector $x$ of nonnegative integers, which maximizes $c^{T}x,$ subject to $Ax \leq b.$ The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multitude of applications in areas such as routing, scheduling and bin packing. These two categories of problems are known to be conceptually related, but this connection has largely been ignored in terms of approximation algorithms. We explore the topic of approximating disjoint-path problems using polynomial-size packing integer programs. Motivated by the disjoint paths applications, we introduce the study of a class of packing integer programs, called column-restricted. We develop improved approximation algorithms for column-restricted programs, a result that we believe is of independent interest. Additional approximation algorithms for disjoint-paths are presented that are simple to implement and achieve good performance when the input has a special structure.Work partially supported by NSERC OG 227809-00 and a CFI New Opportunities Award. Part of this work was done while at the Department of Computer Science, Dartmouth College and partially by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.This work was done while at the Department of Computer Science, Dartmouth College and partially supported by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.     

Convergence Groups, Hausdorff Dimension, and a Theorem of Sullivan and Tukia

We show that a discrete, quasiconformal group preserving ⁿ has the property that its exponent of convergence and the Hausdorff dimension of its limit set detect the existence of a non-empty regular set on the sphere at infinity to ⁿ . This generalizes a result due separately to Sullivan and Tukia, in which it is further assumed that the group act isometrically on ⁿ , i.e. is a Kleinian group. From this generalization we are able to extract geometric information about infinite-index subgroups within certain of these groups.     

On Asymptotic Dimension of Groups Acting on Trees

We prove the following.THEOREM. Let be the fundamental group of a finite graph of groups with finitely generated vertex groups G _v having asdim G _v n for all vertices v. Then asdim n+1.This gives the best possible estimate for the asymptotic dimension of an HNN extension and the amalgamated product.     

Growth of Self‐Similar Graphs

Locally finite self‐similar graphs with bounded geometry and without bounded geometry as well as non‐locally finite self‐similar graphs are characterized by the structure of their cell graphs. Geometric properties concerning the volume growth and distances in cell graphs are discussed. The length scaling factor ν and the volume scaling factor μ can be defined similarly to the corresponding parameters of continuous self‐similar sets. There are different notions of growth dimensions of graphs. For a rather general class of self‐similar graphs, it is proved that all these dimensions coincide and that they can be calculated in the same way as the Hausdorff dimension of continuous self‐similar fractals: . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 224–239, 2004     

Decomposition Rank of Subhomogeneous C*-Algebras

We analyze the decomposition rank (a notion of covering dimensionfor nuclear C*-algebras introduced by E. Kirchberg and the author)of subhomogeneous C*-algebras. In particular, we show that asubhomogeneous C*-algebra has decomposition rank n if and onlyif it is recursive subhomogeneous of topological dimension n,and that n is determined by the primitive ideal space. As an application, we use recent results of Q. Lin and N. C.Phillips to show the following. Let A be the crossed productC*-algebra coming from a compact smooth manifold and a minimaldiffeomorphism. Then the decomposition rank of A is dominatedby the covering dimension of the underlying manifold. 2000 MathematicsSubject Classification 46L85, 46L35.     

Real rank and squaring mappings for unital -algebras

It is proved that if is a compact Hausdorff space of Lebesgue dimension , then the squaring mapping , defined by , is open if and only if . Hence the Lebesgue dimension of can be detected from openness of the squaring maps . In the case it is proved that the map , from the selfadjoint elements of a unital -algebra into its positive elements, is open if and only if is isomorphic to for some compact Hausdorff space with .

     

Generalized Smash Products

In this paper．we study the ring #(D．B)and obtain two very interesting results. First we prove in Theorem 3 that the category of rational left BU-modules is equivalent to both the category of #-rational left modules and the category of all(B．D)-Hopf modules BM^D．Cai and Chen have proved this result in the case B=D=A．Secondly they have proved that if A has a nonzero left integral then A#A^*rat is a dense subring of Endk(A)．We prove that #(A,A) is a dense subring of Endk(Q),where Q is a certain subspace of #(A．A)under the condition that the antipode is bijective(see Theorem18).This condition is weaker than the condition that A has a nonzero integral.It is well known the antipode is bijective in case A has a nonzero integral．Furthermore if A has nonzero left integral,Q can be chosen to be A(see Corollary 19)and #(A,A)is both left and right primitive.Thus A#A^*rat #(A,A)-Endk(A)．Moreover we prove that the left singular ideal of the ring #(A,A)is zero．A corollary of this is a criterion for A with nonzero left integral to be finite-dimensional,namely the ring #(A,A)has a finite uniform dimension．     

On（N,U）-Coherence of Modules and Rings

Let U be a flat right R-module and N an infinite cardinal number.A left R-module M is said to be (N,U)-coherent if every finitely generated submodule of every finitely generated M-projective module in σ[M] is (N,U)-finitely presented in σ[M].It is proved under some additional conditions that a left R-module M is (N,U)-coherent if and only if Л^Ni∈I U is M-flat as a right R-module if and only if the (N,U)-coherent dimension of M is equal to zero.We also give some characterizations of left (N,U)-coherent dimension of rings and show that the left N-coherent dimension of a ring R is the supremum of (N,U)-coherent dimensions of R for all flat right R-modules U.     

$\Phi $-functions for complex 2D-objects

Within two-dimensional cutting and packing problems with irregular shaped objects, the concept of -functions has been proven to be very helpful for several solution approaches. In order to construct such -functions a previous work, in which so-called primary objects are considered, is continued. Now -functions are constructed for pairs of objects which can be represented as a finite combination (union, intersection, complement) of primary objects which allows the handling of arbitrary shaped objects by appropriate approximations of sufficient accuracy.Received: October 2002, Revised: October 2003, AMS classification: 65K05, 90C26, 90B06All correspondence to: Guntram Scheithauer