Minimal numerations of positively computable families

It is proved that among computable numerations that are limit-equivalent to some positive numeration of a computable family of recursively enumerable sets, either there exists one least numeration, or there are countably many nonequivalent, minimal numerations. In particular, semilattices of computable numerations for computable families of finite sets and of weakly effectively discrete families of recursively enumerable sets either have a least element or possess countably many minimal elements.Translated fromAlgebra i Logika, Vol. 33, No. 3, pp. 233–254, May–June, 1994.     

Factorization theorems for cohomological dimension

The well-known factorization theorems for covering dimension dim and compact Hausdorff spaces are here established for the cohomological dimension dim using a new characterization of dim In particular, it is proved that every mapping f: X → Y from a compact Hausdorff space X with to a compact metric space Y admits a factorization f = hg, where g: X → Z, h: Z → Y and Z is a metric compactum with . These results are applied to the well-known open problem whether . It is shown that the problem has a positive answer for compact Hausdorff spaces X if and only if it has a positive answer for metric compacta X.     

Coincidence of the upper Kuratowski topology with the co-compact topology on compact sets, and the Prohorov property

For a Hausdorff space X, let F be the hyperspace of all closed subsets of X and H a sublattice of F. Following Nogura and Shakhmatov, X is said to be H-trivial if the upper Kuratowski topology and the co-compact topology coincide on H. F-trivial spaces are the consonant spaces first introduced and studied by Dolecki, Greco and Lechicki. In this paper, we deal with K-trivial spaces and Fin-trivial space, where K and Fin are respectively the lattices of compact and of finite subsets of X. It is proved that if C_k(X) is a Baire space or more generally if X has ‘the moving off property’ of Gruenhage and Ma, then X is K-trivial. If X is countable, then C_p(X) is Baire if and only if X is Fin-trivial and all compact subsets of X are finite. As for consonant spaces, it turns out that every regular K-trivial space is a Prohorov space. This result remains true for any regular Fin-trivial space in which all compact subsets are scattered. It follows that every regular first countable space without isolated points, all compact subsets of which are countable, is Fin-nontrivial. Examples of K-trivial non-consonant spaces, of Fin-trivial K-nontrivial spaces and of countably compact Prohorov Fin-nontrivial spaces, are given. In particular, we show that all (generalized) Fréchet–Urysohn fans are K-trivial, answering a question by Nogura and Shakhmatov. Finally, we describe an example of a continuous open compact-covering mapping f :X→Y, where X is Prohorov and Y is not Prohorov, answering a long-standing question by Topsøe.     

ContributionsGraph partitions with minimum degree constraints

Given a graph with n nodes and minimum degree δ, we give a polynomial time algorithm that constructs a partition of the nodes of the graph into two sets X and Y such that the sum of the minimum degrees in X and in Y is at least δ and the cardinalities of X and Y differ by at most δ(δ + 1 if n ≠ δ(mod 2)). The existence of such a partition was shown by Sheehan (1988).     

Some algebraic constructions in rational homotopy theory

In this note we describe constructions in the category of differential graded commutative algebras over the rational numbers Q which are analogs of the space F(X, Y) of continuous maps of X to Y, the component F(X, Y,ƒ) containing ƒ ε F(X, Y), fibrations, induced fibrations, the space Γ(π) of sections of a fibration π: E → X, and the component Γ(π,σ) containing σ ε Γ (π). As a focus, we address the problem of expressing π^*(F(X, Y, ƒ)) = Hom(π_*(F(X,Y, ƒ)),Q) in terms of differential graded algebra models for X and Y.     

Function-space compactifications of function spaces

If X and Y are Hausdorff spaces with X locally compact, then the compact-open topology on the set C(X,Y) of continuous maps from X to Y is known to produce the right function-space topology. But it is also known to fail badly to be locally compact, even when Y is locally compact. We show that for any Tychonoff space Y, there is a densely injective space Z containing Y as a densely embedded subspace such that, for every locally compact space X, the set C(X,Z) has a compact Hausdorff topology whose relative topology on C(X,Y) is the compact-open topology. The following are derived as corollaries: (1) If X and Y are compact Hausdorff spaces then C(X,Y) under the compact-open topology is embedded into the Vietoris hyperspace V(X×Y). (2) The space of real-valued continuous functions on a locally compact Hausdorff space under the compact-open topology is embedded into a compact Hausdorff space whose points are pairs of extended real-valued functions, one lower and the other upper semicontinuous. The first application is generalized in two ways.     

Arc-smooth generalized universal covering spaces

Let Y be a path-connected subset of a CAT(0) space Z, allowing for a map to a 1-dimensional separable metric space X, such that the nontrivial point preimages of f form a null sequence of convex subsets of Z. Such Y need not be homotopy equivalent to a 1-dimensional space.

We prove that Y admits a generalized universal covering space, which we equip with an arc-smooth structure by consistently and continuously selecting one tight representative from each path homotopy class of Y. It follows that all homotopy groups of Y vanish in dimensions greater than 1.     

Stable 2-pairs and (X,Y)-intersection graphs

Given two fixed graphs X and Y, the (X,Y)-intersection graph of a graph G is a graph where

1. each vertex corresponds to a distinct induced subgraph in G isomorphic to Y, and

2. two vertices are adjacent iff the intersection of their corresponding subgraphs contains an induced subgraph isomorphic to X.

This notion generalizes the classical concept of line graphs since the (K₁,K₂)-intersection graph of a graph G is precisely the line graph of G.

Let ( , respectively) denote the family of line graphs of bipartite graphs (bipartite multigraphs, respectively), and refer to a pair (X,Y) as a 2-pair if Y contains exactly two induced subgraphs isomorphic to X. Then and , respectively, are the smallest families amongst the families of (X,Y)-intersection graphs defined by so called hereditary 2-pairs and hereditary non-compact 2-pairs. Furthermore, they can be characterized through forbidden induced subgraphs. With this motivation, we investigate the properties of a 2-pair (X,Y) for which the family of (X,Y)-intersection graphs coincides with (or ). For this purpose, we introduce a notion of stability of a 2-pair and obtain the desired characterization for such stable 2-pairs. An interesting aspect of the characterization is that it is based on a graph determined by the structure of (X,Y).     

Existence of families without positive numerations

An example is constructed of a computable family of recursively enumerable sets which does not have computable positive numerations but does possess a computable minimal numeration.Translated from Matematicheskie Zametki, Vol. 13, No. 4, pp. 597–604, April, 1973.     

Enumeration of difference graphs

A difference graph is a bipartite graph G = (X, Y; E) such that all the neighborhoods of the vertices of X are comparable by inclusion. We enumerate labeled and unlabeled difference graphs with or without a bipartition of the vertices into two stable sets. The labeled enumerations are expressed in terms of combinatorial numbers related to the Stirling numbers of the second kind.     

Index sets in the arithmetical Hierarchy

We prove the following results: every recursively enumerable set approximated by finite sets of some set M of recursively enumerable sets with index set in π₂ is an element of M, provided that the finite sets in M are canonically enumerable. If both the finite sets in M and in M̄ are canonically enumerable, then the index set of M is in σ₂∩π₂ if and only if M consists exactly of the sets approximated by finite sets of M and the complement M̄ consists exactly of the sets approximated by finite sets of M̄. Under the same condition M or M̄ has a non-empty subset with recursively enumerable index set, if the index set of M is in σ₂∩π₂.If the finite sets in M are canonically enumerable, then the following three statements are equivalent: (i) the index set of M is in σ₂\π₂, (ii) the index set of M is σ₂-complete, (iii) the index set of M is in σ₂ and some sequence of finite sets in M approximate a set in M̄.Finally, for every n ⩾ 2, an index set in σ_n \ π_n is presented which is not σ_n-complete.     

On analytic and coanalytic function spaces Cp(X)

Under the assumption (V = L) we construct countable completely regular spaces X and Y such that the spaces C_p(X) and C_p(Y) of real-valued continuous functions on X and Y, equipped with the pointwise convergence topology, are analytic noncoanalytic and they are not homeomorphic. We also give analogous examples of coanalytic nonanalytic function spaces.     

Isomorphisms in pro-categories

A morphism of a category which is simultaneously an epimorphism and a monomorphism is called a bimorphism. In (Dydak and Ruiz del Portal (Monomorphisms and epimorphisms in pro-categories, preprint)) we gave characterizations of monomorphisms (resp. epimorphisms) in arbitrary pro-categories, pro-C, where C has direct sums (resp. weak push-outs). In this paper, we introduce the notions of strong monomorphism and strong epimorphism. Part of their significance is that they are preserved by functors. These notions and their characterizations lead us to important classical properties and problems in shape and pro-homotopy. For instance, strong epimorphisms allow us to give a categorical point of view of uniform movability and to introduce a new kind of movability, the sequential movability. Strong monomorphisms are connected to a problem of K. Borsuk regarding a descending chain of retracts of ANRs. If f : X→Y is a bimorphism in the pointed shape category of topological spaces, we prove that f is a weak isomorphism and f is an isomorphism provided Y is sequentially movable and X or Y is the suspension of a topological space. If f : X→Y is a bimorphism in the pro-category pro-H₀ (consisting of inverse systems in H₀, the homotopy category of pointed connected CW complexes) we show that f is an isomorphism provided Y is sequentially movable.     

Effective Nonrecursiveness

Productive sets are sets which are “effectively non recursively enumerable”. In the same spirit, we introduce a notion of “effectively nonrecursive sets” and prove an effective version of Post's theorem. We also show that a set is recursively enumerable and effectively nonrecursive in our sense if and only if it is effectively nonrecursive in the sense of Odifreddi [1].     

Compact open topology and CW homotopy type

The class of spaces having the homotopy type of a CW complex is not closed under formation of function spaces. In 1959, Milnor proved the fundamental theorem that, given a space and a compact Hausdorff space X, the space Y^X of continuous functions X→Y, endowed with the compact open topology, belongs to . P.J. Kahn extended this in 1982, showing that if X has finite n-skeleton and π_k(Y)=0, k>n.

Using a different approach, we obtain a further generalization and give interesting examples of function spaces where is not homotopy equivalent to a finite complex, and has infinitely many nontrivial homotopy groups. We also obtain information about some topological properties that are intimately related to CW homotopy type.

As an application we solve a related problem concerning towers of fibrations between spaces of CW homotopy type.     

Algebras of Recursively Enumerable Sets and Their Applications to Fuzzy Logic

Algebras of operations defined on recursively enumerable sets of different kinds are considered. Every such algebra is specified by a list of operations involved and a list of basic elements. An element of an algebra is said to be representable in this algebra if it can be obtained from given basic elements by operations of the algebra. Two kinds of recursively enumerable sets are considered: recursively enumerable sets in the usual sense and fuzzy recursively enumerable sets. On binary, i.e., two-dimensional recursively enumerable sets of these kinds, algebras of operations are introduced. An algebra θ is constructed in which all binary recursively enumerable sets are representable. A subalgebra θ⁰ of θ is constructed in which all binary recursively enumerable sets are representable if and only if they are described by formulas of Presburger’s arithmetic system. An algebra Ω is constructed in which all binary recursively enumerable fuzzy sets are representable. A subalgebra Ω⁰ of the algebra Ω is constructed such that fuzzy recursively enumerable sets representable in Ω⁰ can be treated as fuzzy counterparts of sets representable by formulas of Presburger’s system. Bibliography: 16 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 304, 2003, pp. 75–98.     

Estimating the spectral measure of an extreme value distribution

Let (X₁, Y₁), (X₂, Y₂),…, (X_n, Y_n) be a random sample from a bivariate distribution function F which is in the domain of attraction of a bivariate extreme value distribution function G. This G is characterized by the extreme value indices and its spectral measure or angular measure. The extreme value indices determine both the marginals and the spectral measure determines the dependence structure. In this paper, we construct an empirical measure, based on the sample, which is a consistent estimator of the spectral measure. We also show for positive extreme value indices the asymptotic normality of the estimator under a suitable 2nd order strengthening of the bivariate domain of attraction condition.     

Efficient robust estimation of parameter in the random censorship model

For an open set Θ of ^k, let \s{P_θ: θ Θ\s} be a parametric family of probabilities modeling the distribution of i.i.d. random variables X₁,…, X_n. Suppose X_i's are subject to right censoring and one is only able to observe the pairs (min(X_i, Y_i), [X_i Y_i]), i = 1,…, n, where [A] denotes the indicator function of the event A, Y₁,…, Y_n are independent of X₁,…, X_n and i.i.d. with unknown distribution Q₀. This paper investigates estimation of the value θ that gives a fitted member of the parametric family when the distributions of X₁ and Y₁ are subject to contamination. The constructed estimators are adaptive under the semi-parametric model and robust against small contaminations: they achieve a lower bound for the local asymptotic minimax risk over Hellinger neighborhoods, in the Hájel—Le Cam sense. The work relies on Beran (1981). The construction employs some results on product-limit estimators.     

The extreme set condition of a graph

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c₀(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c₀(G−X)=def(G)+|X|. In this paper, we obtain the following:

(1) Let G be a simple graph containing an independent set of size i, where i2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G.

(2) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|i, and |Γ(Y)||U|−i+m+1 for any Y U, |Y|=m (1mi−1).

(3) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|m+1 for any Y U, |Y|=m (1mi−1).     

The equivariant Serre spectral sequence as an application of a spectral sequence of Spanier

E.H. Spanier (1992) has constructed, for a cohomology theory defined on a triangulated space and locally constant on each open simplex, a spectral sequence whose E₂-term consists of certain simplicial cohomology groups, converging to the cohomology of the space. In this paper we study a closed G-fibration ƒ: Y → X, where G is a finite group. We show that if the base-G-spaceX is equivariantly triangulated and Y is paracompact, then Spanier's spectral sequence yields an equivariant Serre spectral sequence for ƒ. The main point here is to identify the equivariant singular cohomology groups of X with appropriate simplicial cohomology groups of the orbit space X/G.