Definability in the structure of words with the inclusion relation

We develop a theory of (first-order) definability in the subword partial order in parallel with similar theories for the h-quasiorder of finite k-labeled forests and for the infix order. In particular, any element is definable (provided that the words of length 1 or 2 are taken as parameters), the first-order theory of the structure is atomic and computably isomorphic to the first-order arithmetic. We also characterize the automorphism group of the structure and show that every predicate invariant under the automorphisms of the structure is definable in the structure.     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

Metric trees of generalized roundness one

Every finite metric tree has generalized roundness strictly greater than one. On the other hand, some countable metric trees have generalized roundness precisely one. The purpose of this paper is to identify several large classes of countable metric trees that have generalized roundness precisely one. At the outset we consider spherically symmetric trees endowed with the usual path metric (SSTs). Using a simple geometric argument we show how to determine reasonable upper bounds on the generalized roundness of finite SSTs that depend only on the downward degree sequence of the tree in question. By considering limits, it follows that if the downward degree sequence (d ₀, d ₁, d ₂, . . .) of an SST (T, ρ) satisfies ${|\{j \, | \, d_{j} > 1 \}| = \aleph_{0}}${|\{j \, | \, d_{j} > 1 \}| = \aleph_{0}} , then (T, ρ) has generalized roundness one. In particular, all complete n-ary trees of depth ∞ (n ≥ 2), all k-regular trees (k ≥ 3) and all inductive limits of Cantor trees are seen to have generalized roundness one. The remainder of the paper deals with two classes of countable metric trees of generalized roundness one whose members are not, in general, spherically symmetric. The first such class of trees are merely required to spread out at a sufficient rate (with a restriction on the number of leaves) and the second such class of trees resemble infinite combs. It remains an intriguing problem to completely classify countable metric trees of generalized roundness one.     

On the Countable Tightness of Product Spaces

In this paper, we discuss the countable tightness of products of spaces which are quotient simages of locally separable metric spaces, or k-spaces with a star-countable k-network. The main result is that the following conditions are equivalent： （1） b = ω1; （2） t（Sω×Sω1） 〉 ω; （3） For any pair （X, Y）, which are k-spaces with a point-countable k-network consisting of cosmic subspaces, t（X×Y）≤ω if and only if one of X, Y is first countable or both X, Y are locally cosmic spaces. Many results on the k-space property of products of spaces with certain k-networks could be deduced from the above theorem.     

Inf-sup stable non-conforming finite elements of arbitrary order on triangles

We introduce a family of scalar non-conforming finite elements of arbitrary order k≥1 with respect to the H¹-norm on triangles. Their vector-valued version generates together with a discontinuous pressure approximation of order k−1 an inf-sup stable finite element pair of order k for the Stokes problem in the energy norm. For k=1 the well-known Crouzeix-Raviart element is recovered.     

Final group topologies,Kac-Moody groups and Pontryagin duality

We study final group topologies and their relations to compactness properties. In particular, we are interested in situations where a colimit or direct limit is locally compact, a k _ω-space, or locally k _ω. As a first application, we show that unitary forms of complex Kac-Moody groups can be described as the colimit of an amalgam of subgroups (in the category of Hausdorff topological groups, and the category of k _ω-groups). Our second application concerns Pontryagin duality theory for the classes of almost metrizable topological abelian groups, resp., locally k _ω topological abelian groups, which are dual to each other. In particular, we explore the relations between countable projective limits of almost metrizable abelian groups and countable direct limits of locally k _ω abelian groups.     

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.     

Existence result for minimal hypersurfaces¶with a prescribed finite number of planar ends

Paralleling what has been done for minimal surfaces in ℝ³, we develop a gluing procedure to produce, for any k≥ 2 and any n≥ 3 complete immersed minimal hypersurfaces of ℝ ^{n +1} which have k planar ends. These surfaces are of the topological type of a sphere with k punctures and they all have finite total curvature. Received: 1 July 1999 / Revised version: 31 May 2000     

SCORE LISTS IN （h, k）-BIPARTITE HYPERTOURNAMENTS

Given non-negative integers m,n,h and k with m ≥ h ＞ 1 and n ≥ k ＞ 1, an (h, k)-bipartite hypertournament on m n vertices is a triple (U, V, A), where U and V are two sets of vertices with |U| = m and |V| = n, and A is a set of (h k)-tuples of vertices,called arcs, with at most h vertices from U and at most k vertices from V, such that for any h k subsets U1 ∪ V1 of U ∪ V, A contains exactly one of the (h k)! (h k)-tuples whose entries belong to U1 ∪ V1. Necessary and sufficient conditions for a pair of non-decreasing sequences of non-negative integers to be the losing score lists or score lists of some(h, k)-bipartite hypertournament are obtained.     

A two-grid method with expanded mixed element for nonlinear reaction-diffusion equations

Expanded mixed finite element approximation of nonlinear reaction-diffusion equations is discussed. The equations considered here are used to model the hydrologic and bio-geochemical phenomena. To linearize the mixed-method equations, we use a two-grid method involving a small nonlinear system on a coarse gird of size H and a linear system on a fine grid of size h. Error estimates are derived which demonstrate that the error is O(△t + h k+1 + H 2k+2 d/2 ) (k ≥ 1), where k is the degree of the approximating space for the primary variable and d is the spatial dimension. The above estimates are useful for determining an appropriate H for the coarse grid problems.     

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)     

Some Ramsey-type theorems for countably determined sets

 Let X be an infinite internal set in an ω¹-saturated nonstandard universe. Then for any coloring of [X] ^k , such that the equivalence E of having the same color is countably determined and there is no infinite internal subset of [X] ^k with all its elements of different colors (i.e., E is condensating on X), there exists an infinite internal set Z⊆X such that all the sets in [Z] ^k have the same color. This Ramsey-type result is obtained as a consequence of a more general one, asserting the existence of infinite internal Q-homogeneous sets for certain Q ⊆ [[X] ^k ] ^m , with arbitrary standard k≥ 1, m≥ 2. In the course of the proof certain minimal condensating countably determined sets will be described. Received: 17 October 2000 / Published online: 12 July 2002     

Uniqueness of minimal coverings of maximal partial clones

A partial function f on a k-element set E _k is a partial Sheffer function if every partial function on E _k is definable in terms of f. Since this holds if and only if f belongs to no maximal partial clone on E _k , a characterization of partial Sheffer functions reduces to finding families of minimal coverings of maximal partial clones on E _k . We show that for each k ≥ 2, there exists a unique minimal covering.     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Crossing Number of P(N, 3)

 It is proved that the crossing number of the Generalized Petersen Graph P(3k+h,3) is k+h if h∈{0,2} and k+3 if h=1, for each k≥3, with the single exception of P(9,3), whose crossing number is 2. Received: May 7, 1999 Final version received: April 8, 2000     

On countable stable structures which are homogeneous for a finite relational language

LetL be a finite relational language andH(L) denote the class of all countable structures which are stable and homogeneous forL in the sense of Fraissé. By convention countable includes finite and any finite structure is stable. A rank functionr :H(L) →ω is introduced and also a notion of dimension for structures inH(L). A canonical way of shrinking structures is defined which reduces their dimensions. The main result of the paper is that anyM ∈H(L) can be shrunk toM′ ∈H(L),M′ ⊆M, such that |M′| is bounded in terms ofr(M), and the isomorphism type ofM overM′ is uniquely determined by the dimensions ofM. Forr<ω we deduce thatH(L, r), the class of allM ∈H(L) withr(M)≦r, is the union of a finite number of classes within each of which the isomorphism type of a structure is completely determined by its dimensions. Dedicated to the memory of Abraham Robinson on the tenth anniversary of his death     

Extending partial isomorphisms for the small index property of many ω-categorical structures

Theorem:Let A be a finite K _m -free graph, p ₁ , …, p _n partial isomorphisms on A. Then there exists a finite extension B, which is also a K _m -free graph, and automorphisms f _i of B extending the p _i . A paper by Hodges, Hodkinson, Lascar and Shelah shows how this theorem can be used to prove the small index property for the generic countable graph of this class. The same method also works for a certain class of continuum many non-isomorphic ω-categorical countable digraphs and more generally for structures in an arbitrary finite relational language, which are built in a similar fashion. Hrushovski proved this theorem for the class of all finite graphs [Hr]; the proof presented here stems from his proof. Supported by EC-grant ERBCHBGCT 920013.     

Superconvergence of H 1-Galerkin Mixed Finite Element Methods for Second-Order Elliptic Equations

We derive superconvergence result for H ¹-Galerkin mixed finite element method for second-order elliptic equations over rectangular partitions. Compared to standard mixed finite element procedure, the method is not subject to the Ladyzhenskaya–Bab?ska–Brezzi (LBB) condition and the approximating finite element spaces are allowed to be of different polynomial degrees. Superconvergence estimate of order 𝒪(h ^k+3), where k ≥ 1 is the order of the approximating polynomials employed in the Raviart–Thomas elements, is established for the flux via a postprocessing technique.