Some New Lattice Constructions in High R. E. Degrees

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable (r. e.) degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets (Lerman, Lachlan). In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction of simplicity- and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that (i) A has no dense simple superset, (ii) the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with (i), and (iii) A ?_T B if B is high, and A ≥_T B otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail.     

The Isolated D. R. E. Degrees are Dense in the R. E. Degrees

In the present paper we prove that the isolated differences of r. e. degrees are dense in the r. e. degrees. Mathematics Subject Classification: 03D25.     

Cupping the Recursively Enumerable Degrees by D.R.E. Degrees

We prove that there are two incomplete d.r.e. degrees (the Turingdegrees of differences of two recursively enumerable sets) suchthat every non-zero recursively enumerable degree cups at leastone of them to 0', the greatest recursively enumerable (Turing)degree. 1991 Mathematics Subject Classification: primary 03D25,03D30; secondary 03D35.     

Splittings of 0' into the Recursively Enumerable Degrees

Lachlan [9] proved that there exists a non-recursive recursively enumerable (r. e.) degree such that every non-recursive r. e. degree below it bounds a minimal pair. In this paper we first prove the dual of this fact. Second, we answer a question of Jockusch by showing that there exists a pair of incomplete r. e. degrees a₀, a₁ such that for every non-recursive r. e. degree w, there is a pair of incomparable r. e. degrees b₀, b₂ such that w = b₀ V b₁ and b_i for i = 0, 1. Mathematics Subject Classification: 03D25, 03D30.     

A nonlow2 R. E. Degree with the Extension of Embeddings Properties of a low2 Degree

We construct a nonlow₂ r.e. degree d such that every positive extension of embeddings property that holds below every low₂ degree holds below d . Indeed, we can also guarantee the converse so that there is a low r.e. degree c such that that the extension of embeddings properties true below c are exactly the ones true belowd.Moreover, we can also guarantee that no b ≤ d is the base of a nonsplitting pair.     

Embeddings of and into nerode semirings

Continuing the study of recursive ultrapowers launched by Hirschfeld in 1975 ([H]), we begin to investigate the more detailed embedding properties of these structures. Some related results in isol theory are noted.     

R0-代数(NM-代数)的模糊MP-滤子格

在R0-代数中,从模糊集出发构造了模糊MP-滤子,作为应用证明了如下结果:R0-代数的所有模糊MP-滤子构成一个完备模格。     

Embeddings ofC(Δ) andL 1[0, 1] in Banach lattices

It is proved that ifE is a separable Banach lattice withE′ weakly sequentially complete,F is a Banach space andT:E→F is a bounded linear operator withT′F′ non-separable, then there is a subspaceG ofE, isomorphic toC(Δ), such thatT _G is an isomorphism, whereC(Δ) denotes the space of continuous real valued functions on the Cantor discontinuum. This generalizes an earlier result of the second-named author. A number of conditions are proved equivalent for a Banach latticeE to contain a subspace order isomorphic toC(Δ). Among them are the following:L ¹ is lattice isomorphic to a sublattice ofE′;C(Δ)′ is lattice isomorphic to a sublattice ofE′; E contains an order bounded sequence with no weak Cauchy subsequence;E has a separable closed sublatticeF such thatF′ does not have a weak order unit. The research of both authors was partially supported by the National Science Foundation, NSF Grant No MPS 71-02839 A04.     

Degrees of nonlinearity in forbidden 0–1 matrix problems

A 0–1 matrix A is said to avoid a forbidden 0–1 matrix (or pattern) P if no submatrix of A matches P, where a 0 in P matches either 0 or 1 in A. The theory of forbidden matrices subsumes many extremal problems in combinatorics and graph theory such as bounding the length of Davenport–Schinzel sequences and their generalizations, Stanley and Wilf’s permutation avoidance problem, and Turán-type subgraph avoidance problems. In addition, forbidden matrix theory has proved to be a powerful tool in discrete geometry and the analysis of both geometric and non-geometric algorithms.Clearly a 0–1 matrix can be interpreted as the incidence matrix of a bipartite graph in which vertices on each side of the partition are ordered. Füredi and Hajnal conjectured that if P corresponds to an acyclic graph then the maximum weight (number of 1s) in an n×n matrix avoiding P is O(nlogn). In the first part of the article we refute of this conjecture. We exhibit n×n matrices with weight Θ(nlognloglogn) that avoid a relatively small acyclic matrix. The matrices are constructed via two complementary composition operations for 0–1 matrices. In the second part of the article we simplify one aspect of Keszegh and Geneson’s proof that there are infinitely many minimal nonlinear forbidden 0–1 matrices. In the last part of the article we investigate the relationship between 0–1 matrices and generalized Davenport–Schinzel sequences. We prove that all forbidden subsequences formed by concatenating two permutations have a linear extremal function.     

A Note on Closed Degrees of Difficulty of the Medvedev Lattice

We consider some nonprincipal filters of the Medvedev lattice. We prove that the filter generated by the nonzero closed degrees of difficulty is not principal and we compare this filter, with respect to inclusion, with some other filters of the lattice. All the filters considered in this paper are disjoint from the prime ideal generated by the dense degrees of difficulty. Mathematics Subject Classification: 03D30.     

Embeddings and hyperplanes of the Lie incidence geometry of type E7,1

This paper continues a program to show that for most of the standard Lie incidence geometries, all geometric hyperplanes arise from a necessarily absolutely universal embedding, by addingE _7,1 to the list. It follows from [5, 12] that any projective embedding of this point line geometry is a homomorphic image of the one afforded by the 56-dimensional module for the groupE ₇(K).This work was supported by a grant from the National Science Foundation.     

The E.E.C. and the development of O.R.

The growth of the E.E.C. has brought about a change in the scale of many organizational problems and a change in the ways that they can be tackled. Accordingly it is plausible that the techniques of O.R. should develop in response to these changes. This paper examines some desirable developments and suggests ways in which they might be achieved by adapting methods devised in other fields for similar problems.     

Embeddings in the Strong Reducibilities Between 1 and npm

We consider the strongest (most restricted) forms of enumeration reducibility, those that occur between 1- and npm-reducibility inclusive. By defining two new reducibilities (which we call n1- and ni-reducibility) which are counterparts to 1- and i-reducibility, respectively, in the same way that nm- and npm-reducibility are counterparts to m- and pm-reducibility, respectively, we bring out the structure (under the natural relation on reducibilities strong with respect to') of the strong reducibilities. By further restricting n1- and nm-reducibility we are able to define infinite families of reducibilities which isomorphically embed the r. e. Turing degrees. Thus the many well-known results in the theory of the r. e. Turing degrees have counterparts in the theory of strong reducibilities. We are also able to positively answer the question of whether there exist distinct reducibilities ≤_y and ≤_a between ≤_e and ≤_m such that there exists a non-trivial ≤_y-contiguous ≤_z degree.     

Equivariant Embeddings of the n-Dimensional Space into a Hilbert Space

The present paper is devoted to the study of equivariant embeddings of the n-dimensional space into a Hilbert space. We consider a representation of a group of similarities. The existence of a cocycle for this representation implies the existence of an isometric embedding of a metric group into the Hilbert space. Then we describe all cocycles of a representation of the additive group of real numbers and construct an embedding of the n-dimensional space with metric d(x,y)=|x-y| into the Hilbert space. Bibliography: 5 titles.     

Embeddings of non-commutative Lp-spaces into non-commutative L1-spaces, 1 < p < 2

It will be shown that for 1 < p < 2 the Schatten p-class is isometrically isomorphic to a subspace of the predual of a von Neumann algebra. Similar results hold for non-commutative L_p(N, t) L_p(N, \tau) -spaces defined by a finite trace on a finite von Neumann algebra. The embeddings rely on a suitable notion of p-stable processes in the non-commutative setting.     

Pseudo-Riemannian Symmetric Spaces: Uniform Realizations and Open Embeddings into Grassmanians

This paper aims at two major observations. The first is that all 54 series of classical symmetric spaces admit simple uniform realizations. Namely, a point of a symmetric space is represented by a pair of complementary linear subspaces V₁, V₂ in ^k, ^k or ^k, subject to simple conditions (subspaces may be isotropic, or orthogonal, or rigged with an operator permuting V₁ and V₂). This observation allows one to work with arbitrary classical symmetric spaces by applying simple elementary methods. The second observation is that there always exists an open embedding of a classical symmetric space into a Grassmanian. Bibliography: 8 titles.     

Convex Embeddings and Bisections of 3-Connected Graphs1

Given two disjoint subsets T ₁ and T ₂ of nodes in an undirected 3-connected graph G = (V, E) with node set V and arc set E, where and are even numbers, we show that V can be partitioned into two sets V ₁ and V ₂ such that the graphs induced by V ₁ and V ₂ are both connected and holds for each j = 1,2. Such a partition can be found in time. Our proof relies on geometric arguments. We define a new type of convex embedding of k-connected graphs into real space R ^k-1 and prove that for k = 3 such an embedding always exists. ¹ A preliminary version of this paper with title Bisecting Two Subsets in 3-Connected Graphs appeared in the Proceedings of the 10th Annual International Symposium on Algorithms and Computation, ISAAC 99, (A. Aggarwal, C. P. Rangan, eds.), Springer LNCS 1741, 425&ndash;434, 1999.     

The First Three Levels of an Order Preserving Hamiltonian Path in the Subset Lattice

Consider the lattice whose elements are the subsets of the set of positive integers not greater than n ordered by inclusion. The Hasse diagram of this lattice is isomorphic to the n-dimensional hypercube. It is trivial that this graph is Hamiltonian. Let be a Hamiltonian path. We say it is monotone, if for every i, either (a) all subsets of S _i appear among S ₁,...,S _i − 1, or (b) only one (say S) does not, furthermore S _i + 1 = S. Trotter conjectured that if n is sufficiently large, then there are no monotone Hamiltonian paths in the n-cube. He also made a stronger conjecture that states that there is no path with the monotone property that covers all the sets of size at most three. In this paper we disprove this strong conjecture by explicitly constructing a monotone path covering all the 3-sets.