Complete embeddings of linear orderings and embeddings of lattice-ordered groups

An infinite linearly ordered set (S,≦) is called doubly homogeneous, if its automorphism group Aut(S,≦) acts 2-transitively on it. We study embeddings of linearly ordered sets into Dedekind-completions of doubly homogeneous chains which preserve all suprema and infima, and obtain necessary and sufficient conditions for the existence of such embeddings. As one of several consequences, for each lattice-ordered groupG and each regular uncountable cardinalκ≧|G | there are 2⋉ non-isomorphic simple divisible lattice-ordered groupsH of cardinalityκ all containingG as anl-subgroup.     

Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.     

Metrizable compacta in the space of continuous functions with the topology of pointwise convergence

We prove that every point-finite family of nonempty functionally open sets in a topological space X has the cardinality at most an infinite cardinal κ if and only if w(X) ≦ κ for every Valdvia compact space Y C _p (X). Correspondingly a Valdivia compact space Y has the weight at most an infinite cardinal κ if and only if every point-finite family of nonempty open sets in C _p (Y) has the cardinality at most κ, that is p(C _p (Y)) ≦ κ. Besides, it was proved that w(Y) = p(C _p (Y)) for every linearly ordered compact Y. In particular, a Valdivia compact space or linearly ordered compact space Y is metrizable if and only if p(C _p (Y)) = ℵ₀. This gives answer to a question of O. Okunev and V. Tkachuk.      

The uniform approximation property in Orlicz spaces

It is proved that for every reflexive Orlicz spaceX there is a functionn(k,ε) so that wheneverE is ak-dimensional subspace ofX there exists an operatorT: X→X such thatT _1E=identity, ‖T‖≦1+ε and dimTX≦n(k,ε). Some general facts concerning the uniform approximation property are also presented. Research of the first named author was partially supported by NSF Grant MPS 74-07509-A01.     

On the Existence of Towers in Pseudo-Tree Algebras

A tower in a Boolean algebra (BA) is a strictly increasing sequence, of regular order type, of elements of the algebra different from 1 but with sum 1. A pseudo-tree is a partially ordered set T such that the set T↓t = {s ∈ T:s < t} is linearly ordered for every t ∈ T. If that set is well-ordered, then T is a tree. For any pseudo-tree T, the BA Treealg(T) is the algebra of subsets of T generated by all of the sets T↑t = {s ∈ T:t ≤ s}. The main theorem of this note is a characterization in tree terms of when Treealg(T) has a tower of order type κ (given in advance).     

Trees with Equal Domination and Restrained Domination Numbers

Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γ_r(T); (ii) T is a γ-excellent tree and T ≠ K₂; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γ_r(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality.     

Extension of positive functionals on certain ordered spaces

An ordered linear spaceL is said to satisfy extension property (E1) if for every directed subspaceM ofL and positive linear functional ϕ onM, ϕ can be extended toL. A Riesz spaceL is said to satisfy extension property (E2) if for every sub-Riesz spaceM ofL and every real valued Riesz homomorphism ϕ onM, ϕ can be extended toL as a Riesz homomorphism. These properties were introduced by Schmidt in [5]. In this paper, it is shown that an ordered linear space has extension property (E1) if and only if it is order isomorphic to a function spaceL′ defined on a setX′ such that iff andg belong toL′ there exists a finite disjoint subsetM of the set of functions onX′ such that each off andg is a linear combination of the points ofM. An analogous theorem is derived for Riesz spaces with extension property (E2).     

Espaces de Banach stables

We define the notion of “stable Banach space” by a simple condition on the norm. We prove that ifE is a stable Banach space, then every subspace ofL ^p(E) (1≦p<∞) is stable. Our main result asserts that every infinite dimensional stable Banach space containsl ^p, for somep, 1≦p<∞. This is a generalization of a theorem due to D. Aldous: every infinite dimensional subspace ofL ¹ containsl ^p, for somep in the interval [1, 2].     

The ordering of commutative terms

By a commutative term we mean an element of the free commutative groupoid F of infinite rank. For two commutative terms a, b write a ⩽ b if b contains a subterm that is a substitution instance of a. With respect to this relation, F is a quasiordered set which becomes an ordered set after the appropriate factorization. We study definability in this ordered set. Among other things, we prove that every commutative term (or its block in the factor) is a definable element. Consequently, the ordered set has no automorphisms except the identity.     

Partitioning infinite trees

A graph G is bisectable if its edges can be colored by two colors so that the resulting monochromatic subgraphs are isomorphic. We show that any infinite tree of maximum degree Δ with infinitely many vertices of degree at least Δ −1 is bisectable as is any infinite tree of maximum degree Δ ≤ 4. Further, it is proved that every infinite tree T of finite maximum degree contains a finite subset E of its edges so that the graph T − E is bisectable. To measure how “far” a graph G is from being bisectable, we define c(G) to be the smallest number k > 1 so that there is a coloring of the edges of G by k colors with the property that any two monochromatic subgraphs are isomorphic. An upper bound on c(G), which is in a sense best possible, is presented. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 113–127, 2000     

Weyl’s Theorem for Algebraically Quasi-class A Operators

If T or T* is an algebraically quasi-class A operator acting on an infinite dimensional separable Hilbert space then we prove that Weyl’s theorem holds for f(T) for every f ∈ H(σ(T)), where H(σ(T)) denotes the set of all analytic functions in an open neighborhood of σ(T). Moreover, if T* is algebraically quasi-class A then a-Weyl’s theorem holds for f(T). Also, if T or T* is an algebraically quasi-class A operator then we establish that the spectral mapping theorems for the Weyl spectrum and the essential approximate point spectrum of T for every f ∈ H(σ(T)), respectively. This research was supported by the Kyung Hee University Research Fund in 2007 (KHU- 20071605).     

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)     

Every separable metric space is Lipschitz equivalent to a subset ofc 0 +

It is shown that there is a constantK so that, for every separable metric spaceX, there is a mapT:X →c _o satisfyingd(x, y)≦‖Tx−Ty‖≦Kd(x, y) for everyx, y ∈ X. This is a part of the author's Ph.D. Thesis prepared at the Hebrew University of Jerusalem, under the supervision of Professor J. Lindenstrauss.     

Matrices with the edmonds—Johnson property

A matrixA=(a _ij ) has theEdmonds—Johnson property if, for each choice of integral vectorsd ₁,d ₂,b ₁,b ₂, the convex hull of the integral solutions ofd ₁≦x≦d ₂,b ₁≦Ax≦b ₂ is obtained by adding the inequalitiescx≦|δ|, wherec is an integral vector andcx≦δ holds for each solution ofd ₁≦x≦d ₂,b ₁≦Ax≦b ₂. We characterize the Edmonds—Johnson property for integral matricesA which satisfy for each (row index)i. A corollary is that ifG is an undirected graph which does not contain any homeomorph ofK ₄ in which all triangles ofK ₄ have become odd circuits, thenG ist-perfect. This extends results of Boulala, Fonlupt, Sbihi and Uhry. First author’s research supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.).     

Completion and finite embeddability property for residuated ordered algebras.

A residuated ordered algebra is a partially ordered set with additional ‘residuated’ operations. A construction is presented that, from any partial subalgebra of a residuated ordered algebra, constructs a complete algebra into which the partial subalgebra embeds. Conditions are given under which the constructed algebra is finite whenever a finite partial subalgebra is chosen. This implies the ‘finite embeddability property’ for the given class of residuated ordered algebras. In the case that the whole algebra is chosen as the partial subalgebra, the construction is a completion of the underlying order of the algebra. A scheme of inequalities is described that are shown to have the property of being preserved by the above construction. These preservation results thus extend the results on the finite embeddability property and completion.     

The spanning trees forced by the path and the star

A set S of trees of order n forces a tree T if every graph having each tree in S as a spanning tree must also have T as a spanning tree. A spanning tree forcing set for order n that forces every tree of order n. A spanning-tree forcing set S is a test set for panarboreal graphs, since a graph of order n is panarboreal if and only if it has all of the trees in S as spanning trees. For each positive integer n ≠ 1, the star belongs to every spanning tree forcing set for order n. The main results of this paper are a proof that the path belongs to every spanning-tree forcing set for each order n ∉ {1, 6, 7, 8} and a computationally tractable characterization of the trees of order n ≥ 15 forced by the path and the star. Corollaries of those results include a construction of many trees that do not belong to any minimal spanning tree forcing set for orders n ≥ 15 and a proof that the following related decision problem is NP-complete: an instance is a pair (G, T) consisting of a graph G of order n and maximum degree n - 1 with a hamiltonian path, and a tree T of order n; the problem is to determine whether T is a spanning tree of G. © 1996 John Wiley & Sons, Inc.     

A theorem on level lines of continuous functions

A property of a continuous functionf(x), x ∈ E ₂, similar to the classical intermediate value property is established. Namely, let a Jordan compactJ ⊂ E ₂ be the domain of definition off. Then, for each parametrizationx(t), 0≦t≦T,x(0)=x(T), of the boundary Fr(J) ofJ there exists a unique real λ and a unique connected component Φ of the level set {x ∈ J: f(x)=λ} with the following property: any connected subset Ω ofJ containing “opposite” points of Fr(J) (i.e. pointsx(t′) andx(t″) such thatt″−t′=T/2) has a common element with Φ.     

Robinson forcing is not absolute

Robinson (or infinite model theoretic) forcing is studied in the context of set theory. The major result is that infinite forcing, genericity, and related notions are not absolute relative to ZFC. This answers a question of G. Sacks and provides a non-trivial example of a non-absolute notion of model theory. This non-absoluteness phenomenon is shown to be intrinsic to the concept of infinite forcing in the sense that any ZFC-definable set theory, relative to which forcing is absolute, has the flavor of asserting self-inconsistency. More precisely: IfT is a ZFC-definable set theory such that the existence of a standard model ofT is consistent withT, then forcing is not absolute relative toT. For example, if it is consistent that ZFC+ “there is a measureable cardinal” has a standard model then forcing is not absolute relative to ZFC+ “there is a measureable cardinal.” Some consequences: 1) The resultants for infinite forcing may not be chosen “effectively” in general. This answers a question of A. Robinson. 2) If ZFC is consistent then it is consistent that the class of constructible division rings is disjoint from the class of generic division rings. 3) If ZFC is consistent then the generics may not be axiomatized by a single sentence ofL _w/w. In Memoriam: Abraham Robinson     

Club degrees of rigidity and almost Kurepa trees

A highly rigid Souslin tree T is constructed such that forcing with T turns T into a Kurepa tree. Club versions of previously known degrees of rigidity are introduced, as follows: for a rigidity property P, a tree T is said to have property P on clubs if for every club set C (containing 0), the restriction of T to levels in C has property P. The relationships between these rigidity properties for Souslin trees are investigated, and some open questions are stated.