Effectively and Noneffectively Nowhere Simple Sets

R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ? of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two (non) effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* (A) is effectively isomorphic to ?*, and that there is a nowhere simple set A such that L*(A) is not effectively isomorphic to ?*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L*(A) effectively isomorphic to ?*. Mathematics Subject Classification: 03D25, 03D10.     

Highness and bounding minimal pairs

We show the existence of a high r. e. degree bounding only joins of minimal pairs and of a high₂ nonbounding r. e. degree. MSC: 03D25.     

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.     

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.     

Trapezoid graphs and their coloring

We define trapezoid graphs, an extension of both interval and permutation graphs. We show that this new class properly contains the union of the two former classes, and that trapezoid graphs are equivalent to the incomparability graphs of partially ordered sets having interval order dimension at most two. We provide an optimal coloring algorithm for trapezoid graphs that runs in time O(nk), where n is the number of nodes and k is the chromatic number of the graph. Our coloring algorithm has direct applications to channel routing on integrated circuits.     

Recursively Enumerable Equivalence Relations Modulo Finite Differences

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th(Eq*) has the same computational complexity as the true first-order arithmetic. Mathematics Subject Classification: 03D25, 03D15, 03D35.     

Spectral partially ordered sets

We examine some topics related to (gold)spectral partially ordered sets, i.e., those that are order isomorphic to (Goldman) prime spectra of commutative rings. Among other results, we characterize the partially ordered sets that are isomorphic to prime spectra of rings satisfying the descending chain condition on radical ideals, and we show that a dual of a tree is isomorphic to the Goldman prime spectrum of a ring if and only if every chain has an upper bound. We also give some new methods for constructing (gold)spectral partially ordered sets.     

On a Class of Recursively Enumerable Sets

We define a class of so-called ∑(n)-sets as a natural closure of recursively enumerable sets W_n under the relation “∈” and study its properties.     

Multigraphs with quasiweak odd cycles

In this paper we define a class of multigraphs with chromatic index equal to the maximum degree d. They are characterized by a property of their elementary odd cycles. It is shown that these graphs are panchromatic (i.e., they have a good k-coloring for any k). In the partially ordered set of color-feasible sequences of these graphs, all maximal sequences have at most d + 1 terms.     

Friedberg Numberings of Families of n-Computably Enumerable Sets

We establish a number of results on numberings, in particular, on Friedberg numberings, of families of d.c.e. sets. First, it is proved that there exists a Friedberg numbering of the family of all d.c.e. sets. We also show that this result, patterned on Friedberg's famous theorem for the family of all c.e. sets, holds for the family of all n-c.e. sets for any n>2. Second, it is stated that there exists an infinite family of d.c.e. sets without a Friedberg numbering. Third, it is shown that there exists an infinite family of c.e. sets (treated as a family of d.c.e. sets) with a numbering which is unique up to equivalence. Fourth, it is proved that there exists a family of d.c.e. sets with a least numbering (under reducibility) which is Friedberg but is not the only numbering (modulo reducibility).     

On order structure of the set of one-point Tychonoff extensions of a locally compact space

If a Tychonoff space X is dense in a Tychonoff space Y, then Y is called a Tychonoff extension of X. Two Tychonoff extensions Y₁ and Y₂ of X are said to be equivalent, if there exists a homeomorphism which keeps X pointwise fixed. This defines an equivalence relation on the class of all Tychonoff extensions of X. We identify those extensions of X which belong to the same equivalence classes. For two Tychonoff extensions Y₁ and Y₂ of X, we write Y₂?Y₁, if there exists a continuous function which keeps X pointwise fixed. This is a partial order on the set of all (equivalence classes of) Tychonoff extensions of X. If a Tychonoff extension Y of X is such that Y\X is a singleton, then Y is called a one-point extension of X. Let T(X) denote the set of all one-point extensions of X. Our purpose is to study the order structure of the partially ordered set (T(X),?). For a locally compact space X, we define an order-anti-isomorphism from T(X) onto the set of all nonempty closed subsets of βX\X. We consider various sets of one-point extensions, including the set of all one-point locally compact extensions of X, the set of all one-point Lindelöf extensions of X, the set of all one-point pseudocompact extensions of X, and the set of all one-point ?ech-complete extensions of X, among others. We study how these sets of one-point extensions are related, and investigate the relation between their order structure, and the topology of subspaces of βX\X. We find some lower bounds for cardinalities of some of these sets of one-point extensions, and in a concluding section, we show how some of our results may be applied to obtain relations between the order structure of certain subfamilies of ideals of C^∗(X), partially ordered with inclusion, and the topology of subspaces of βX\X. We leave some problems open.     

Ramsey Numbers for Partially-Ordered Sets

We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains.     

Finite Paths are Universal

We prove that any countable (finite or infinite) partially ordered set may be represented by finite oriented paths ordered by the existence of homomorphism between them. This (what we believe a surprising result) solves several open problems. Such path-representations were previously known only for finite and infinite partial orders of dimension 2. Path-representation implies the universality of other classes of graphs (such as connected cubic planar graphs). It also implies that finite partially ordered sets are on-line representable by paths and their homomorphisms. This leads to a new on-line dimensions. *Supported by Grants LN00A56 and 1M0021620808 of the Czech Ministry of Education. The first author was partially supported by EU network COMBSTRU at UPC Barcelona.     

Suzuki?s type characterizations of completeness for partial metric spaces and fixed points for partially ordered metric spaces

Recently, Suzuki [T. Suzuki, A generalized Banach contraction principle that characterizes metric completeness, Proc. Amer. Math. Soc. 136 (2008) 1861-1869] proved a fixed point theorem that is a generalization of the Banach contraction principle and characterizes the metric completeness. In this paper we prove an analogous fixed point result for a self-mapping on a partial metric space or on a partially ordered metric space. Our results on partially ordered metric spaces generalize and extend some recent results of Ran and Reurings [A.C.M. Ran, M.C. Reurings, A fixed point theorem in partially ordered sets and some applications to matrix equations, Proc. Amer. Math. Soc. 132 (2004) 1435-1443], Nieto and Rodríguez-López [J.J. Nieto, R. Rodríguez-López, Contractive mapping theorems in partially ordered sets and applications to ordinary differential equations, Order 22 (2005) 223-239]. We deduce, also, common fixed point results for two self-mappings. Moreover, using our results, we obtain a characterization of partial metric 0-completeness in terms of fixed point theory. This result extends Suzuki?s characterization of metric completeness.     

Infimum Properties Differ in the Weak Truth-table Degrees and the Turing Degrees

Abstract We prove that there are non-recursive r.e. sets A and C with A < _T C such that for every set . Both authors are supported by “863” and the National Science Foundation of China     

Counting and ordering periodic stationary solutions of lattice Nagumo equations

We study the rich structure of periodic stationary solutions of Nagumo reaction diffusion equation on lattices. By exploring the relationship with Nagumo equations on cyclic graphs we are able to divide these periodic solutions into equivalence classes that can be partially ordered and counted. In order to accomplish this, we use combinatorial concepts such as necklaces, bracelets and Lyndon words.     

Local equivalence relations

In this paper, we investigate the concept of local equivalence relation, a notion suggested by Grothendieck. A local equivalence relation on a topological space X is a global section of the sheaf of germs of equivalence relations on X. We investigate the extent to which a local equivalence relation can be described by a global one and analogously when can a global equivalence relation be recovered from its associated local one. We also look at the notion of a fiber map, which sheds further light on these concepts. A motivating example is that of a foliation on a manifold.     

Netlike partial cubes I. General properties

A set A of vertices of a graph G is C-convex if the vertex set of any cycle of the subgraph of G induced by the union of the intervals between each pair of elements of A is contained in A. A partial cube (isometric subgraph of a hypercube) is a netlike partial cube if, for each edge ab, the sets U_ab and U_ba are C-convex (U_ab being the set of all vertices closer to a than to b and adjacent to some vertices closer to b than to a, and vice versa for U_ba). Particular netlike partial cubes are median graphs, even cycles, benzenoid graphs and cellular bipartite graphs. In this paper we give different characterizations and properties of netlike partial cubes. In particular, as median graphs and cellular bipartite graphs, these graphs have a pre-hull number which is at most one, and moreover the convex hull of any isometric cycle of a netlike partial cube is, as in the case of bipartite cellular graphs, this cycle itself or, as in the case of median graphs, a hypercube. We also characterize the gated subgraphs of a netlike partial cube, and we show that the gated amalgam of two netlike partial cubes is a netlike partial cube.     

On Beck’s coloring of posets

We study Beck-like coloring of partially ordered sets (posets) with a least element 0. To any poset P with 0 we assign a graph (called a zero-divisor graph) whose vertices are labelled by the elements of P with two vertices x,y adjacent if 0 is the only element lying below x and y. We prove that for such graphs, the chromatic number and the clique number coincide. Also, we give a condition under which posets are not finitely colorable.