Model-companions and definability in existentially complete structures

The theory of model-companions and existentially complete structures is both reviewed and developed further. The review begins with A. Robinson’s work in the fifties and continues through the definability of second order structures in existentially complete groups. New results include necessary and sufficient conditions for the existence of a model-companion in terms of the definability of general elementary properties. The main theorem of the paper gives necessary and sufficient conditions for the existence of a model-companion for universal theories with finite presentations and the amalgamation property. This result generalizes the result of P. Eklof and G. Sabbagh that the theory ofR-modules has a model-completion if and only ifR is coherent. The author’s survey presentation at the Robinson Memorial Conference included the material in the first and fourth sections of this paper and Theorem 1 and its corollaries and examples in the second section. The other results in Section 2 and the results in Section 3 were obtained after the conference.     

On pseudolinearity and generic pairs

We continue the study of the connection between the “geometric” properties of SU ‐rank 1 structures and the properties of “generic” pairs of such structures, started in [8]. In particular, we show that the SU‐rank of the (complete) theory of generic pairs of models of an SU ‐rank 1 theory T can only take values 1 (if and only if T is trivial), 2 (if and only if T is linear) or ω, generalizing the corresponding results for a strongly minimal T in [3]. We also use pairs to derive the implication from pseudolinearity to linearity for ω ‐categorical SU ‐rank 1 structures, established in [7], from the conjecture that an ω ‐categorical supersimple theory has finite SU ‐rank, and find a condition on generic pairs, equivalent to pseudolinearity in the general case (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Boolean algebras of definable sets in weakly o‐minimal theories

We consider the sets definable in the countable models of a weakly o‐minimal theory T of totally ordered structures. We investigate under which conditions their Boolean algebras are isomorphic (hence T is p‐ω‐categorical), in other words when each of these definable sets admits, if infinite, an infinite coinfinite definable subset. We show that this is true if and only if T has no infinite definable discrete (convex) subset. We examine the same problem among arbitrary theories of mere linear orders. Finally we prove that, within expansions of Boolean lattices, every weakly o‐minimal theory is p‐ω‐categorical. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Linear space data structures for two types of range search

This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE ³ and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.This research was conducted while the first author was with Brown University and the second author was with the Technical University of Graz, Austria. The first author was supported in part by NSF Grant MCS 83-03925.     

A property of strictly singular one-to-one operators

We prove that ifT is a strictly singular one-to-one operator defined on an infinite dimensional Banach spaceX, then for every infinite dimensional subspaceY ofX there exists an infinite dimensional subspaceZ ofX such thatZ∩Y is infinite dimensional,Z contains orbits ofT of every finite length and the restriction ofT toZ is a compact operator. The research was partially supported by NSF.     

Minimum cost multiflows in undirected networks

LetN = (G, T, c, a) be a network, whereG is an undirected graph,T is a distinguished subset of its vertices (calledterminals), and each edgee ofG has nonnegative integer-valuedcapacity c(e) andcost a(e). Theminimum cost maximum multi(commodity)flow problem (*) studied in this paper is to find ac-admissible multiflowf inG such that: (i)f is allowed to contain partial flows connecting any pairs of terminals, (ii) the total value off is as large as possible, and (iii) the total cost off is as small as possible, subject to (ii). This generalizes, on one hand, the undirected version of the classical minimum cost maximum flow problem (when |T| = 2), and, on the other hand, the problem of finding a maximum fractional packing ofT-paths (whena 0). Lovász and Cherkassky independently proved that the latter has a half-integral optimal solution.A pseudo-polynomial algorithm for solving (*) has been developed earlier and, as its consequence, the theorem on the existence of a half-integral optimal solution for (*) was obtained. In the present paper we give a direct, shorter, proof of this theorem. Then we prove the existence of a half-integral optimal solution for the dual problem. Finally, we show that half-integral optimal primal and dual solutions can be designed by a combinatorial strongly polynomial algorithm, provided that some optimal dual solution is known (the latter can be found, in strongly polynomial time, by use of a version of the ellipsoid method).This work was partially supported by Chaire municipale, Mairie de Grenoble, France.     

Inverse Pattern Matching

Let a textstringTofnsymbols from some alphabet Σ and an integerm < nbe given. A patternPof lengthmover Σ is sought such thatPminimizes (alternatively, maximizes) the total number of pairwise character mismatches generated whenPis compared with allm-character substrings ofT. Two additional variants of the problem are obtained by adding the constraint thatPbe (respectively, not be) a substring ofT. Efficient sequential algorithms are proposed in this paper for the problem and its variants.     

Families of cuts with the MFMC-property

A family ℱ of cuts of an undirected graphG=(V, E) is known to have the weak MFMC-property if (i) ℱ is the set ofT-cuts for someT⊆V with |T| even, or (ii) ℱ is the set of two-commodity cuts ofG, i.e. cuts separating any two distinguished pairs of vertices ofG, or (iii) ℱ is the set of cuts induced (in a sense) by a ring of subsets of a setT⊆V. In the present work we consider a large class of families of cuts of complete graphs and prove that a family from this class has the MFMC-property if and only if it is one of (i), (ii), (iii).     

Model completeness for trivial, uncountably categorical theories of Morley rank 1

We show that if T is a trivial uncountably categorical theory of Morley Rank 1 then T is model complete after naming constants for a model.The second author was partially supported by NSF grant DMS-0300080.     

Extreme points and retractions in Banach spaces

ForT a completely regular topological space andX a strictly convex Banach space, we study the extremal structure of the unit ball of the spaceC(T,X) of continuous and bounded functions fromT intoX. We show that when dimX is an even integer then every point in the unit ball ofC(T, X) can be expressed as the average of three extreme points if, and only if, dimT< dimX, where dimT is the covering dimension ofT. We also prove that, ifX is infinite-dimensional, the aforementioned representation of the points in the unit ball ofC(T, X) is always possible without restrictions on the topological spaceT. Finally, we deduce from the above result that the identity mapping on the unit ball of an infinite-dimensional strictly convex Banach space admits a representation as the mean of three retractions of the unit ball onto the unit sphere. The author wishes to express his gratitude to Dr. Juan Francisco Mena Jurado for many helpful suggestions during the preparation of this paper.     

Range sets and partition sets in connection with congruences and algebraic invariants

With a semigroup of transformationsS, we associate a class of equivalence relations onR(S) (calledclosed under inclusion relations), the set of ranges ofS. We define a new notion of connectedness for semigroups of transformations (calledrange-connectedness). For a range-connectedS, the closed under inclusion relations and the left-zero congruences ofS are dually isomorphic. The ideas above are dualized for the partition sets ofS. We associate withS an ordered pair which measures its range and partition connectedness. We generalize to an arbitrary semigroupT by considering faithful representations ofT by semigroups of transformations. In so doing, we are able to define an algebraic invariant for semigroups.     

The quasitriangular structures for a class of<Emphasis Type="Italic">T</Emphasis>-smash product Hopf algebras

We study the quasitriangular structures ofT-smash product Hopf algebrasB _⋈ H which are constructed by Caenepeel, Ion, Militaru and Zhu. The necessary and sufficient conditions for a class ofT-smash product Hopf algebras to be quasitriangular Hopf algebras are given. As applications of our results, some corollaries and examples are given as well. This work was partially supported by the NSF grant of Henan Province, P. R. China.     

A note on injectiveC(T)-spaces and the Amir boundary

We sovle in the negative a problem of Wolfe ifC(T _A ) is an injective Banach space wheneverC(T) is injective,T compact, andT _A is the Amir boundary ofT (i.e., the complement of the maximal open extremally disconnected subset ofT). In particular, we findT such thatC(T) is aP ₃-space andT _A ∼βN\N. The author’s research was partially supported by a grant of MEN, Poland.     

On principal T-bands in a Banach lattice

It is shown that for every positive order continuous Riesz operatorT, defined on an order complete complex Banach latticeE which is separated by its Köthe dual, there exists a Frobenius decomposition ofE into a countable number of disjoint principalT-bands and a band on whichT is quasi-nilpotent. A basis for the generalized eigenspace ofT pertaining to its maximal eigenvalue is constructed and the positivity properties of its elements are studied. The distinguished eigenvalues ofT are characterized and it is also shown that the theory ofT-bands is symmetric with respect to the duality which exists betweenE and its Köthe dual. This generalizes aspects of work done by H.D. Victory and R.-J. Jang-Lewis.     

Almost stable spectra and limits of similarities

Suppose that {D _n } is a sequence of invertible operators on a Hilbert space, andD _n T D _n ^–1 converges in norm toT ₀. Recently, H. Bercovici, C. Foias, and A. Tannenbaum have shown that if {D _n ^±1 n=1, 2,...} is contained in a finite dimensional subspace of operators, thenT andT ₀ must have the same spectral radius. Using this result, R. Teodorescu proved that the resolvents ofT andT ₀ have the same unbounded component. We show that in fact the spectra differ only by certain eigenvalues ofT ₀, and the spectrum ofT ₀ is obtained by filling in holes in the spectrum ofT; i.e., by adjoining (all, some, or none of the) bounded components of the resolvent ofT to the spectrum ofT.     

Approximation du spectre d'un operateur lineaire; application aux operateurs differentiels elliptiques non autoadjoints

To be computed, the eigenvalues of a closed linear operatorT in a Banach space are usually approximated by the eigenvalues ofT h, a linear operator approximatingT in a finite dimensional space (for example, finite difference method, Galerkin method),h is a parameter which tends to 0. This approximation is studied in [2]; stability ofT h implies the continuity of the spectrum ofT h, whenh tends to 0.We present here a new kind of sufficient condition. For that purpose, we disconnect the continuity of the spectrum ofT h into lower and upper semicontinuities. And we give two different criteria for these semi-continuities. Applications to the approximation of nonselfadjoint elliptic operators by finite difference schemes, are given.     

Spectra of smash products

LetT=R #H be a smash product whereH is a finite dimensional Hopf algebra. We show that ideals ofT invariant under the dualH* ofH are extended fromH-invariant ideals ofR. This allows us to transport the study of ideals inT to invariant ideals. When the Hopf algebra is pointed the relationship between an ideal and its invariant ideal is shown to be manageable. Restricting to prime ideals, this yields results on the prime spectra ofR andT. We obtain Krull relations forR ⊆T for someH, including Incomparability wheneverH is commutative (or more generally whenH* is pointed after base extension). The results generalize and unify a number of results known in the context of group and restricted Lie actions.     

Extensions completes d'une theorie forcing complete

We give two examples of a universal theoryT such that the forcing companionT ^F (as defined by A. Robinson for infinite forcing) has some model which is not the elementary equivalent of a generic model ofT. Our examples answer in a negative way a question posed by E. Fisher and A. Robinson. In the first example, forT ^F, there is an extensionT′ which is complete and forcing comcomplete (that is, (T′) ^F=T′) not generated by a generic model ofT. In the second exampleT ^F has a complete extensionT′ which is not forcing complete.      

Analytic equivalence and similarity of operators

The analytic equivalence of two operators is a generalization of similarity. We prove that under some conditions the analytic equivalence between two Hilbert space operatorsT andR implies the similarity of their restrictions on generalized ranges. We also prove that, in certain cases, the similarity ofT to a contraction implies that ofR. An improvement of a well-known criterion of similarity to an isometry due to Sz.-Nagy is given and an extension of a result of Apostol is obtained.     

Theories of linear order

LetT be a complete theory of linear order; the language ofT may contain a finite or a countable set of unary predicates. We prove the following results. (i) The number of nonisomorphic countable models ofT is either finite or 2^ω. (ii) If the language ofT is finite then the number of nonisomorphic countable models ofT is either 1 or 2^ω. (iii) IfS ₁(T) is countable then so isS _n(T) for everyn. (iv) In caseS ₁(T) is countable we find a relation between the Cantor Bendixon rank ofS ₁(T) and the Cantor Bendixon rank ofS _n(T). (v) We define a class of modelsL, and show thatS ₁(T) is finite iff the models ofT belong toL. We conclude that ifS ₁(T) is finite thenT is finitely axiomatizable. (vi) We prove some theorems concerning the existence and the structure of saturated models. Most of the results in this paper appeared in the author’s Master of Science thesis which was prepared at the Hebrew University under the supervision of Professor H. Gaifman.