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 .     

$${\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     

Examples of a generalization of contact metric structures on fibre bundles

We consider a Riemannian manifold with a compatible f-structure which admits a parallelizable kernel. With some additional integrability conditions it is called (almost) -manifold and is a natural generalization of the (almost) contact metric and the Sasakian manifolds. There are presented various methods of constructing examples of such manifolds. There are used structures on the principal bundles and the pull-back bundles. Then there are considered relations between (almost) -manifolds and transverse almost Hermitian structures on the foliated manifolds. Research supported by the Italian MIUR 60% and GNSAGA.     

Finite lattices as relative congruence lattices of finite algebras

Let A be a finite algebra and a quasivariety. By A is meant the lattice of congruences θ on A with . For any positive integer n, we give conditions on a finite algebra A under which for any n-element lattice L there is a quasivariety such that . The author was supported by INTAS grant 03-51-4110.     

Codes defined by forms of degree 2 on non-degenerate Hermitian varieties in $${\mathbb{P}^{4}(\mathbb{F}_q)}$$

We study the functional codes of second order on a non-degenerate Hermitian variety as defined by G. Lachaud. We provide the best possible bounds for the number of points of quadratic sections of . We list the first five weights, describe the corresponding codewords and compute their number. The paper ends with two conjectures. The first is about minimum distance of the functional codes of order h on a non-singular Hermitian variety . The second is about distribution of the codewords of first five weights of the functional codes of second order on a non-singular Hermitian variety .      

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

Poset algebras over well quasi-ordered posets

A new class of partial order-types, class is defined and investigated here. A poset P is in the class iff the poset algebra F(P) is generated by a better quasi-order G that is included in L(P). The free Boolean algebra F(P) and its free distributive lattice L(P) have been defined in [ABKR]. The free Boolean algebra F(P) contains the partial order P and is generated by it: F(P) has the following universal property. If B is any Boolean algebra and f is any order-preserving map from P into a Boolean algebra B, then f can be extended to a homomorphism of F(P) into B. We also define L(P) as the sublattice of F(P) generated by P. We prove that if P is any well quasi-ordering, then L(P) is well founded, and is a countable union of well quasi-orderings. We prove that the class is contained in the class of well quasi-ordered sets. We prove that is preserved under homomorphic image, finite products, and lexicographic sum over better quasi-ordered index sets. We prove also that every countable well quasi-ordered set is in . We do not know, however if the class of well quasi-ordered sets is contained in . Additional results concern homomorphic images of posets algebras. The third author was supported by the following institutions: Israel Science Foundation (postdoctoral positions at Ben Gurion University 2000–2002), The Fields Institute (Toronto 2002–2004), and by The Nato Science Fellowship (University Paris VII, CNRS-UMR 7056, 2004).     

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.     

The Extremal Truncated Moment Problem

For a degree 2n real d-dimensional multisequence to have a representing measure μ, it is necessary for the associated moment matrix to be positive semidefinite and for the algebraic variety associated to β, , to satisfy rank card as well as the following consistency condition: if a polynomial vanishes on , then . We prove that for the extremal case , positivity of and consistency are sufficient for the existence of a (unique, rank -atomic) representing measure. We also show that in the preceding result, consistency cannot always be replaced by recursiveness of . The first-named author’s research was partially supported by NSF Research Grants DMS-0099357 and DMS-0400741. The second-named author’s research was partially supported by NSF Research Grant DMS-0201430 and DMS-0457138.     

Closedness properties of internal relations V: Linear Mal’tsev conditions

As J. W. Snow showed, every linear Mal’tsev condition on a variety of universal algebras, is equivalent to a relational condition on . Using slightly different relational reformulations of linear Mal’tsev conditions, we develop a purely categorical approach to these conditions. Received August 10, 2006; accepted in final form January 23, 2007.     

Quasiperiodic Group Factorizations

If is any ring or semi-ring (e.g., ) and G is a finite abelian group, two elements a, b of the group (semi-)ring are said to form a factorization of G if ab = rΣ _g∈G g for some . A factorization is called quasiperiodic if there is some element g ∈ G of order m > 1 such that either a or b – say b – can be written as a sum b ₀ + ... + b _m−1 of m elements of such that ab _h = g ^h ab ₀ for h = 0, ... , m − 1. Hajós [5] conjectured that all factorizations are quasiperiodic when and r = 1 but Sands [15] found a counterexample for the group . Here we show however that all factorizations of abelian groups are quasiperiodic when and that all factorizations of cyclic groups or of groups of the type are quasiperiodic when . We also give some new examples of non-quasiperiodic factorizations with for the smaller groups and . Received: May 12, 2006. Revised: October 3, 2007.     

Characterizing cryptogroups with a finite number of $${\mathcal{H}}$$ -classes in each $${\mathcal{D}}$$ -class by their subsemigroups

We construct a family of completely regular semigroups with the property that each completely regular semigroup S with a finite number of -classes in each -class is non-cryptic if and only if S contains an isomorphic image of a member of . Each member F of is an ideal extension of a Rees matrix semigroup J by a cyclic group B with a zero adjoined and the identity of B is the identity of F. Here with I and Λ finite, G is given by generators and relations, and P is given explicitly. Within completely regular semigroups, the cryptic property is equivalent to where is the natural partial order and a if and only if a ² = ab = ba. Hence the above result can be formulated in terms of and .      

On an Essentially Algebraic Theory for Locally Presentable Categories

This paper presents a general construction, defining for each given strong generator in any locally finitely presentable category an essentially algebraic, finitary theory – maximal in a certain sense – such that is equivalent to the category of models of . For regular generators , generalization to the non-finitary case is easily done, and yields a new proof of the famous characterization of many-sorted quasivarieties.     

On the Circumference of 2-Connected $$\mathcal{P}_{3}$$-Dominated Graphs

Let G be a connected graph. For at distance 2, we define , and , if then . G is quasi-claw-free if it satisfies , and G is P ₃-dominated() if it satisfies , for every pair (x, y) of vertices at distance 2. Certainly contains as a subclass. In this paper, we prove that the circumference of a 2-connected P ₃-dominated graph G on n vertices is at least min or , moreover if then G is hamiltonian or , where is a class of 2-connected nonhamiltonian graphs.     

<Emphasis Type="Italic">h</Emphasis>-Principles for curves and knots of constant curvature

We prove that curves of constant curvature satisfy, in the sense of Gromov, the relative -dense h-principle in the space of immersed curves in Euclidean space R ^{n ≥ 3}. In particular, in the isotopy class of any given knot f there exists a knot f͂ of constant curvature which is -close to f. More importantly, we show that if f is , then the curvature of f͂ may be set equal to any constant c which is not smaller than the maximum curvature of f. We may also require that f͂ be tangent to f along any finite set of prescribed points, and coincide with f over any compact set with an open neighborhood where f has constant curvature c. The proof involves some basic convexity theory, and a sharp estimate for the position of the average value of a parameterized curve within its convex hull. The author’s research was supported in part by NSF CAREER award DMS-0332333.     

Negatively Correlated Random Variables and Mason’s Conjecture for Independent Sets in Matroids

Mason’s Conjecture asserts that for an m-element rank r matroid the sequence is logarithmically concave, in which I _k is the number of independent k-sets of . A related conjecture in probability theory implies these inequalities provided that the set of independent sets of satisfies a strong negative correlation property we call the Rayleigh condition. This condition is known to hold for the set of bases of a regular matroid. We show that if ω is a weight function on a set system that satisfies the Rayleigh condition then is a convex delta-matroid and ω is logarithmically submodular. Thus, the hypothesis of the probabilistic conjecture leads inevitably to matroid theory. We also show that two-sums of matroids preserve the Rayleigh condition in four distinct senses, and hence that the Potts model of an iterated two-sums of uniform matroids satisfies the Rayleigh condition. Numerous conjectures and auxiliary results are included. Research supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392.     

The Unbalance of Set Systems

The unbalance of an intersecting family is defined as , where is the maximum degree of i.e. the maximum of over all vertices x. We show that the unbalance of a k-uniform intersecting family is at most when n ≥ 6k ³ and we determine all families achieving this bound.     

The Stokes operator in weighted Lq-spaces II: weighted resolvent estimates and maximal Lp-regularity

In this paper we establish a general weighted L ^q -theory of the Stokes operator in the whole space, the half space and a bounded domain for general Muckenhoupt weights . We show weighted L ^q -estimates for the Stokes resolvent system in bounded domains for general Muckenhoupt weights. These weighted resolvent estimates imply not only that the Stokes operator generates a bounded analytic semigroup but even yield the maximal L ^p -regularity of in the respective weighted L ^q -spaces for arbitrary Muckenhoupt weights . This conclusion is archived by combining a recent characterisation of maximal L ^p -regularity by -bounded families due to Weis [Operator-valued Fourier multiplier theorems and maximal L _p -regularity. Preprint (1999)] with the fact that for L ^q -spaces -boundedness is implied by weighted estimates.