Reverse mathematics of some topics from algorithmic graph theory

Peter Clote; Jeffry Hirst

The search session has expired. Please query the service again.

Displaying similar documents to “Reverse mathematics of some topics from algorithmic graph theory”

On backward stability of holomorphic dynamical systems

Genadi. Levin (1998)

Fundamenta Mathematicae

Similarity:

For a polynomial with one critical point (maybe multiple), which does not have attracting or neutral periodic orbits, we prove that the backward dynamics is stable provided the Julia set is locally connected. The latter is proved to be equivalent to the non-existence of a wandering continuum in the Julia set or to the shrinking of Yoccoz puzzle-pieces to points.

The geometry of laminations

Robbert Fokkink, Lex Oversteegen (1996)

Fundamenta Mathematicae

Similarity:

A lamination is a continuum which locally is the product of a Cantor set and an arc. We investigate the topological structure and embedding properties of laminations. We prove that a nondegenerate lamination cannot be tree-like and that a planar lamination has at least four complementary domains. Furthermore, a lamination in the plane can be obtained by a lakes of Wada construction.

Each nowhere dense nonvoid closed set in Rn is a σ-limit set

Andrei Sivak (1996)

Fundamenta Mathematicae

Similarity:

We discuss main properties of the dynamics on minimal attraction centers (σ-limit sets) of single trajectories for continuous maps of a compact metric space into itself. We prove that each nowhere dense nonvoid closed set in $ℝ^{n}$ , n ≥ 1, is a σ-limit set for some continuous map.

Paul Erdős’s (1913-1996)

András Sárközy (1997)

Acta Arithmetica

Similarity:

Recursive expansions

C. Ash, J. Knight (1994)

Fundamenta Mathematicae

Similarity:

Let A be a recursive structure, and let ψ be a recursive infinitary $Π_{2}$ sentence involving a new relation symbol. The main result of the paper gives syntactical conditions which are necessary and sufficient for every recursive copy of A to have a recursive expansion to a model of ψ, provided A satisfies certain decidability conditions. The decidability conditions involve a notion of rank. The main result is applied to prove some earlier results of Metakides-Nerode and Goncharov. In these...

Connected covers and Neisendorfer's localization theorem

C. McGibbon, J. Møller (1997)

Fundamenta Mathematicae

Similarity:

Our point of departure is J. Neisendorfer's localization theorem which reveals a subtle connection between some simply connected finite complexes and their connected covers. We show that even though the connected covers do not forget that they came from a finite complex their homotopy-theoretic properties are drastically different from those of finite complexes. For instance, connected covers of finite complexes may have uncountable genus or nontrivial SNT sets, their Lusternik-Schnirelmann...

Dimensionsgrad for locally connected Polish spaces

Vitaly Fedorchuk, Jan van Mill (2000)

Fundamenta Mathematicae

Similarity:

It is shown that for every n ≥ 2 there exists an n-dimensional locally connected Polish space with Dimensionsgrad 1.

Continuous images and other topological properties of Valdivia compacta

Ondřej Kalenda (1999)

Fundamenta Mathematicae

Similarity:

We study topological properties of Valdivia compact spaces. We prove in particular that a compact Hausdorff space K is Corson provided each continuous image of K is a Valdivia compactum. This answers a question of M. Valdivia (1997). We also prove that the class of Valdivia compacta is stable with respect to arbitrary products and we give a generalization of the fact that Corson compacta are angelic.

Are initially $ω_{1}$ -compact separable regular spaces compact?

Alan Dow, Istvan Juhász (1997)

Fundamenta Mathematicae

Similarity:

We investigate the question of the title. While it is immediate that CH yields a positive answer we discover that the situation under the negation of CH holds some surprises.