Chains and antichains in partial orderings

We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is or , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering has the feature that for every , there is an infinite chain or antichain that is relative to , then we have uniform dichotomy: either for all copies of , there is an infinite chain that is relative to , or for all copies of , there is an infinite antichain that is relative to .     

Partitions of large Rado graphs

Let κ be a cardinal which is measurable after generically adding many Cohen subsets to κ and let be the κ-Rado graph. We prove, for 2 ≤ m < ω, that there is a finite value such that the set [κ] ^m can be partitioned into classes such that for any coloring of any of the classes C _i in fewer than κ colors, there is a copy of in such that is monochromatic. It follows that , that is, for any coloring of with fewer than κ colors there is a copy of such that has at most colors. On the other hand, we show that there are colorings of such that if is any copy of then for all , and hence . We characterize as the cardinality of a certain finite set of types and obtain an upper and a lower bound on its value. In particular, and for m > 2 we have where r _m is the corresponding number of types for the countable Rado graph. Research of M. Džamonja and J. A. Larson were partially supported by Engineering and Physical Sciences Research Council and research of W. J. Mitchell was partly supported by grant number DMS 0400954 from the United States National Science Foundation.     

Duality gap of the conic convex constrained optimization problems in normed spaces

In this paper, motivated by a result due to Champion [Math. Program.99, 2004], we introduce a property for a conic quasi-convex vector-valued function in a general normed space. We prove that this property characterizes the zero duality gap for a class of the conic convex constrained optimization problem in the sense that if this property is satisfied and the objective function f is continuous at some feasible point, then the duality gap is zero, and if this property is not satisfied, then there exists a linear continuous function f such that the duality gap is positive. We also present some sufficient conditions for the property The work of this author was partially supported by the National Natural Sciences Grant (No. 10671050) and the Excellent Young Teachers Program of MOE,  P.R.C.     

Small weight codewords in LDPC codes defined by (dual) classical generalized quadrangles

We find lower bounds on the minimum distance and characterize codewords of small weight in low-density parity check (LDPC) codes defined by (dual) classical generalized quadrangles. We analyze the geometry of the non-singular parabolic quadric in PG(4,q) to find information about the LDPC codes defined by Q (4,q), and . For , and , we are able to describe small weight codewords geometrically. For , q odd, and for , we improve the best known lower bounds on the minimum distance, again only using geometric arguments. Similar results are also presented for the LDPC codes LU(3,q) given in [Kim, (2004) IEEE Trans. Inform. Theory, Vol. 50: 2378–2388]     

On Separation of Points from Additive Subgroups of Banach Spaces by Continuous Characters and Positive Definite Functions

Let G be an additive subgroup of a normed space X. We say that a point is weakly separated (resp. -separated) from G if it can be separated from G by a continuous character (resp. by a continuous positive definite function). Let T : X → Y be a continuous linear operator. Consider the following conditions: (ws) if , then x is weakly separated from G; (ps) if , then x is -separated from G; (wp) if Tx is -separated from T(G), then x is weakly separated from G. By (resp. , ) we denote the class of operators T : X → Y which satisfy (ws) (resp. (ps), (wp)) for all and all subgroups G of X. The paper is an attempt to describe the above classes of operators for various Banach spaces X, Y. It is proved that if X, Y are Hilbert spaces, then is the class of Hilbert-Schmidt operators. It is also shown that if T is a Hilbert-to-Banach space operator with finite ℓ-norm, then .      

Model theory of the regularity and reflection schemes

Abstract  This paper develops the model theory of ordered structures that satisfy Keisler’s regularity scheme and its strengthening REF (the reflection scheme) which is an analogue of the reflection principle of Zermelo-Fraenkel set theory. Here is a language with a distinguished linear order <, and REF consists of formulas of the form

Parameterized partition relations on the real numbers

We consider several kinds of partition relations on the set of real numbers and its powers, as well as their parameterizations with the set of all infinite sets of natural numbers, and show that they hold in some models of set theory. The proofs use generic absoluteness, that is, absoluteness under the required forcing extensions. We show that Solovay models are absolute under those forcing extensions, which yields, for instance, that in these models for every well ordered partition of there is a sequence of perfect sets whose product lies in one piece of the partition. Moreover, for every finite partition of there is and a sequence of perfect sets such that the product lies in one piece of the partition, where is the set of all infinite subsets of X. The proofs yield the same results for Borel partitions in ZFC, and for more complex partitions in any model satisfying a certain degree of generic absoluteness. This work was supported by the research projects MTM 2005-01025 of the Spanish Ministry of Science and Education and 2005SGR-00738 of the Generalitat de Catalunya. A substantial part of the work was carried out while the second-named author was ICREA Visiting Professor at the Centre de Recerca Matemàtica in Bellaterra (Barcelona), and also during the first-named author’s stays at the Instituto Venezolano de Investigaciones Científicas and the California Institute of Technology. The authors gratefully acknowledge the support provided by these institutions.     

Première valeur propre du laplacien, volume conforme et chirurgies

We define a new differential invariant a compact manifold by , where V _c (M, [g]) is the conformal volume of M for the conformal class [g], and prove that it is uniformly bounded above. The main motivation is that this bound provides a upper bound of the Friedlander-Nadirashvili invariant defined by . The proof relies on the study of the behaviour of when one performs surgeries on M.      

The geometric invariants $${\Omega^{n}}$$ of a product of groups

We compute the geometric invariants of a product G × H of groups in terms of and . This gives a sufficient condition in terms of and for a normal subgroup of G × H with abelian quotient to be of type F _n . We give an example involving the direct product of the Baumslag–Solitar group BS_1,2 with itself.      

Embedding FD(ω) into {\mathcal{P}_s} densely

Let be the lattice of degrees of non-empty subsets of 2 ^ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in . Cenzer and Hinman proved that is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by Cenzer and Hinman, we improve on the result of Binns and Simpson by showing that for any , we can lattice embed FD(ω) into strictly between and . We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made. Thanks to my adviser Peter Cholak for his guidance in my research. I also wish to thank the anonymous referee for helpful comments and suggestions. My research was partially supported by NSF grants DMS-0245167 and RTG-0353748 and a Schmitt Fellowship at the University of Notre Dame.     

Semicrossed products of simple C*-algebras

Let and be C*-dynamical systems and assume that is a separable simple C*-algebra and that α and β are *-automorphisms. Then the semicrossed products and are isometrically isomorphic if and only if the dynamical systems and are outer conjugate. K. R. Davidson was partially supported by an NSERC grant. E. G. Katsoulis was partially supported by a summer grant from ECU     

Categoricity of computable infinitary theories

Computable structures of Scott rank are an important boundary case for structural complexity. While every countable structure is determined, up to isomorphism, by a sentence of , this sentence may not be computable. We give examples, in several familiar classes of structures, of computable structures with Scott rank whose computable infinitary theories are each -categorical. General conditions are given, covering many known methods for constructing computable structures with Scott rank , which guarantee that the resulting structure is a model of an -categorical computable infinitary theory. Work on this paper began at the Workshop on Model Theory and Computable Structure Theory at University of Florida Gainesville, in February, 2007. The authors are grateful to the organizers of this workshop. They are also grateful for financial support from National Science Foundation grants DMS DMS 05-32644, DMS 05-5484. The second author is also grateful for the support of grants RFBR 08-01-00336 and NSc-335.2008.1.     

Infinite-dimensionality of the automorphism groups of homogeneous Stein manifolds

We show that the group of holomorphic automorphisms of a Stein manifold X with dim X ≥ 2 is infinite-dimensional, provided X is a homogeneous space of a holomorphic action of a complex Lie group.     

On deformations of maps and curve singularities

We study several deformation functors associated to the normalization of a reduced curve singularity . The main new results are explicit formulas, in terms of classical invariants of (X, 0), for the cotangent cohomology groups T ⁱ , i  =  0,1,2, of these functors. Thus we obtain precise statements about smoothness and dimension of the corresponding local moduli spaces. We apply the results to obtain explicit formulas, respectively, estimates for the -codimension of a parametrized curve singularity, where denotes the Mather–Wall group of left-right equivalence.     

Computable shuffle sums of ordinals

The main result is that for sets , the following are equivalent:

$${\mathcal{C}}_{0}$$ ( X)-algebras,stability and strongly self-absorbing $${\mathcal{C}}^{*}$$ -algebras

We study permanence properties of the classes of stable and so-called -stable -algebras, respectively. More precisely, we show that a (X)-algebra A is stable if all its fibres are, provided that the underlying compact metrizable space X has finite covering dimension or that the Cuntz semigroup of A is almost unperforated (a condition which is automatically satisfied for -algebras absorbing the Jiang–Su algebra tensorially). Furthermore, we prove that if is a K ₁-injective strongly self-absorbing -algebra, then A absorbs tensorially if and only if all its fibres do, again provided that X is finite-dimensional. This latter statement generalizes results of Blanchard and Kirchberg. We also show that the condition on the dimension of X cannot be dropped. Along the way, we obtain a useful characterization of when a -algebra with weakly unperforated Cuntz semigroup is stable, which allows us to show that stability passes to extensions of -absorbing -algebras. Research supported by: Deutsche Forschungsgemeinschaft (through the SFB 478), by the EU-Network Quantum Spaces - Noncommutative Geometry (Contract No. HPRN-CT-2002-00280), and by the Center for Advanced Studies in Mathematics at Ben-Gurion University     

KK-theoretic duality for proper twisted actions

Let be a smooth continuous trace algebra, with a Riemannian manifold spectrum X, equipped with a smooth action by a discrete group G such that G acts on X properly and isometrically. Then is KK-theoretically Poincaré dual to , where is the inverse of in the Brauer group of Morita equivalence classes of continuous trace algebras equipped with a group action. We deduce this from a strengthening of Kasparov’s duality theorem. As applications we obtain a version of the above Poincaré duality with X replaced by a compact G-manifold M and Poincaré dualities for twisted group algebras if the group satisfies some additional properties related to the Dirac dual-Dirac method for the Baum- Connes conjecture. This research was supported by the EU-Network Quantum Spaces and Noncommutative Geometry (Contract HPRN-CT-2002-00280) and the Deutsche Forschungsgemeinschaft (SFB 478) and by the National Science and Engineering Research Council of Canada Discovery Grant program.     

Some constructions on the Hermitian surface

In the geometric setting of commuting orthogonal and unitary polarities we construct an infinite family of complete (q + 1)²–spans of the Hermitian surface , q odd. A construction of an infinite family of minimal blocking sets of , q odd, admitting PSL ₂(q), is also provided.      

A family of easy polyhedra

Let E be a finite set and a family of subsets of E such that the symmetric difference of any two members of this family is at least 2. Let be the complement of in , the set of the subsets of E. In this paper we characterize the convex hull of the characteristic vectors of the elements of . We consider also the polar of these polyhedra and study their links with some well known polyhedra. Note from the Editors  This paper was originally submitted directly to a guest editor appointed for a planned special issue dedicated to the memory of Claude Berge. Unfortunately the issue never materialized and had to be canceled. It was only recently discovered that this paper was never processed.     

Generically finite morphisms and formal neighborhoods of arcs

Let f : X → Y be a morphism of pure-dimensional schemes of the same dimension, with X smooth. We prove that if is an arc on X having finite order e along the ramification subscheme R _f of X, and if its image δ = f _∞(γ) on Y does not lie in J _∞(Y _sing), then the induced map T _γ J _∞(X) → T _δ J _∞(Y) is injective, with a cokernel of dimension e. In particular, if Y is smooth too, and if we denote by and the formal neighborhoods of and , then the induced morphism is a closed embedding of codimension e.