Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Twisted conjugacy classes in nilpotent groups

A group is said to have the R(infinity) property if every automorphism has an infinite number of twisted conjugacy classes. We study the question whether G has the R(infinity) property when G is a finitely generated torsion-free nilpotent group. As a consequence, we show that for every positive integer n >= 5, there is a compact nilmanifold of dimension n on which every homeomorphism is isotopic to a fixed point free homeomorphism. As a by-product, we give a purely group theoretic proof that the free group on two generators has the R(infinity) property. The R(infinity) property for virtually abelian and for C-nilpotent groups are also discussed.

On isomorphism classes of C(2(m) circle plus [0, alpha]) spaces

We provide a complete isomorphic classification of the Banach spaces of continuous functions on the compact spaces 2(m) circle plus [0, alpha], the topological sums of Cantor cubes 2(m), with m smaller than the first sequential cardinal, and intervals of ordinal numbers [0, alpha]. In particular, we prove that it is relatively consistent with ZFC that the only isomorphism classes of C(2(m) circle plus [0, alpha]) spaces with m >= N(0) and alpha >= omega(1) are the trivial ones. This result leads to some elementary questions on large cardinals.

TWISTED CONJUGACY CLASSES IN R. THOMPSON`S GROUP F

In this article, we prove that any automorphism of R. Thompson`s group F has infinitely many twisted conjugacy classes. The result follows from the work of Brin, together with standard facts about R. Thompson`s group F, and elementary properties of the Reidemeister numbers.

The classification and the conjugacy classes of the finite subgroups of the sphere braid groups

Let n >= 3. We classify the finite groups which are realised as subgroups of the sphere braid group B(n)(S(2)). Such groups must be of cohomological period 2 or 4. Depending on the value of n, we show that the following are the maximal finite subgroups of B(n)(S(2)): Z(2(n-1)); the dicyclic groups of order 4n and 4(n - 2); the binary tetrahedral group T*; the binary octahedral group O*; and the binary icosahedral group I(*). We give geometric as well as some explicit algebraic constructions of these groups in B(n)(S(2)) and determine the number of conjugacy classes of such finite subgroups. We also reprove Murasugi`s classification of the torsion elements of B(n)(S(2)) and explain how the finite subgroups of B(n)(S(2)) are related to this classification, as well as to the lower central and derived series of B(n)(S(2)).

Some classes of semisimple group (and loop) algebras over finite fields

We determine the structure of the semisimple group algebra of certain groups over the rationals and over those finite fields where the Wedderburn decompositions have the least number of simple components We apply our work to obtain similar information about the loop algebras of mdecomposable RA loops and to produce negative answers to the isomorphism problem over various fields (C) 2010 Elsevier Inc All rights reserved

SIGMA THEORY AND TWISTED CONJUGACY CLASSES

Using Sigma theory we show that for large classes of groups G there is a subgroup H of finite index in Aut(G) such that for phi is an element of H the Reidemeister number R(phi) is infinite. This includes all finitely generated nonpolycyclic groups G that fall into one of the following classes: nilpotent-by-abelian groups of type FP(infinity); groups G/G `` of finite Prufer rank; groups G of type FP(2) without free nonabelian subgroups and with nonpolycyclic maximal metabelian quotient; some direct products of groups; or the pure symmetric automorphism group. Using a different argument we show that the result also holds for 1-ended nonabelian nonsurface limit groups. In some cases, such as with the generalized Thompson`s groups F(n,0) and their finite direct products, H = Aut(G).

Twisted conjugacy classes in symplectic groups, mapping class groups and braid groups (with an appendix written jointly with Francois Dahmani)

We prove that the symplectic group Sp(2n, Z) and the mapping class group Mod(S) of a compact surface S satisfy the R(infinity) property. We also show that B(n)(S), the full braid group on n-strings of a surface S, satisfies the R(infinity) property in the cases where S is either the compact disk D, or the sphere S(2). This means that for any automorphism phi of G, where G is one of the above groups, the number of twisted phi-conjugacy classes is infinite.

UNIFORM APPROXIMATION ON IDEALS OF MULTILINEAR MAPPINGS

For each ideal of multilinear mappings M we explicitly construct a corresponding ideal (a)M such that multilinear forms in (a)M are exactly those which can be approximated, in the uniform norm, by multilinear forms in M. This construction is then applied to finite type, compact, weakly compact and absolutely summing multilinear mappings. It is also proved that the correspondence M bar right arrow (a)M. IS Aron-Berner stability preserving.

New classes of spatial central configurations for the n+3-body problem

In this paper, we show the existence of new families of spatial central configurations for the n + 3-body problem, n >= 3. We study spatial central configurations where n bodies are at the vertices of a regular n-gon T and the other three bodies are symmetrically located on the straight line that is perpendicular to the plane that contains T and passes through the center of T. The results have simple and analytic proofs. (c) 2010 Elsevier Ltd. All rights reserved.

Discontinuous Galerkin approximation of two-phase flows in heterogeneous porous media with discontinuous capillary pressures

We design and investigate a sequential discontinuous Galerkin method to approximate two-phase immiscible incompressible flows in heterogeneous porous media with discontinuous capillary pressures. The nonlinear interface conditions are enforced weakly through an adequate design of the penalties on interelement jumps of the pressure and the saturation. An accurate reconstruction of the total velocity is considered in the Raviart-Thomas(-Nedelec) finite element spaces, together with diffusivity-dependent weighted averages to cope with degeneracies in the saturation equation and with media heterogeneities. The proposed method is assessed on one-dimensional test cases exhibiting rough solutions, degeneracies, and capillary barriers. Stable and accurate solutions are obtained without limiters. (C) 2010 Elsevier B.V. All rights reserved.