Amorphe Potenzen kompakter Räume

A set is amorphous, if it is not a union of two disjoint infinite subsets. The following variants of the Tychonoff product theorem are investigated in the hierarchy of weak choice principles. TA1: An amorphous power of a compactT ₂ space is compact. TA2: An amorphous power of a compactT ₂ space which as a set is wellorderable is compact. In ZF⁰TA1 is equivalent to the assertion, that amorphous sets are finite. RT is Ramsey's theorem, that every finite colouring of the set ofn-element subsets of an infinite set has an infinite homogeneous subset and PW is Rubin's axiom, that the power set of an ordinal is wellorderable. In ZF⁰RT+PW implies TA2. Since RT+PW is compatible with the existence of infinite amorphous sets, TA2 does not imply TA1 in ZF⁰. But TA2 cannot be proved in ZF⁰ alone. As an application, we prove a theorem of Stone, using a weak wellordering axiomD ₃ (a set is wellorderable, if each of its infinite subsets is structured) together with RT.

Diese Arbeit ist Teil der Habilitationsschrift des Verfassers im Fachgebiet Mathematische Analysis an der Technischen Universität Wien.     

The Ulam number of infinite graphs

The following is a conjecture of Ulam: In any partition of the integer lattice on the plane into uniformly bounded sets, there exists a set that is adjacent to at least six other sets. Two sets are adjacent if each contain a vertex of the same unit square. This problem is generalized as follows. Given any uniformly bounded partitionP of the vertex set of an infinite graphG with finite maximum degree, letP (G) denote the graph obtained by letting each set of the partition be a vertex ofP (G) where two vertices ofP (G) are adjacent if and only if the corresponding sets have an edge between them. The Ulam number ofG is defined as the minimum of the maximum degree ofP (G) where the minimum is taken over all uniformly bounded partitionsP. We have characterized the graphs with Ulam number 0, 1, and 2. Restricting the partitions of the vertex set to connected subsets, we obtain the connected Ulam number ofG. We have evaluated the connected Ulam numbers for several infinite graphs. For instance we have shown that the connected Ulam number is 4 ifG is an infinite grid graph. We have settled the Ulam conjecture for the connected case by proving that the connected Ulam number is 6 for an infinite triangular grid graph. The general Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6. We also describe some interesting geometric consequences of the Ulam number, mainly concerning good drawings of infinite graphs.     

Infinite paths in planar graphs II,structures and ladder nets

A graph is k‐indivisible, where k is a positive integer, if the deletion of any finite set of vertices results in at most k – 1 infinite components. In 1971, Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if and only if it is 3‐indivisible. In this paper, we prove a structural result for 2‐indivisible infinite planar graphs. This structural result is then used to prove Nash‐Williams conjecture for all 4‐connected 2‐indivisible infinite planar graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 247–266, 2005     

Exhaustive weakly wandering sequences

A sequence of integers {n_i : i = 0, 1…} is an exhaustive weakly wandering sequence for a transformation T if for some measurable set W, X=^∞_i=0TⁿⁱW(disj. We introduce a hereditary Property (H) for a sequence of integers associated with an infinite ergodic transformation T, and show that it is a sufficient condition for the sequence to be an exhaustive weakly wandering sequence for T. We then show that every infinite ergodic transformation admits sequences that possess Property (H), and observe that Property (H) is inherited by all subsequences of a sequence that possess it. As a corollary, we obtain an application to tiling the set of integers with infinite subsets.     

The number of infinite clusters in dynamical percolation

Summary. Dynamical percolation is a Markov process on the space of subgraphs of a given graph, that has the usual percolation measure as its stationary distribution. In previous work with O. H?ggstr?m, we found conditions for existence of infinite clusters at exceptional times. Here we show that for ℤ ^d , with p>p _c , a.s. simultaneously for all times there is a unique infinite cluster, and the density of this cluster is θ(p). For dynamical percolation on a general tree Γ, we show that for p>p _c , a.s. there are infinitely many infinite clusters at all times. At the critical value p=p _c , the number of infinite clusters may vary, and exhibits surprisingly rich behaviour. For spherically symmetric trees, we find the Hausdorff dimension of the set T ^k of times where the number of infinite clusters is k, and obtain sharp capacity criteria for a given time set to intersect T ^k . The proof of this capacity criterion is based on a new kernel truncation technique. Received: 5 May 1997 / In revised form: 24 November 1997     

On the Compatibility of Binary Sequences

An ordered pair of semi‐infinite binary sequences (η,ξ) is said to be compatible if there is a way of removing a certain number (possibly infinite) of ones from η and zeroes from ξ that would map both sequences to the same semi‐infinite sequence. This notion was introduced by Peter Winkler, who also posed the following question: η and ξ being independent i.i.d. Bernoulli sequences with parameters p′ and p, respectively, does there exist (p′, p) so that the set of compatible pairs has positive measure? It is known that this does not happen for p and p′ very close to . In the positive direction, we construct, for any ? > 0, a deterministic binary sequence η_? whose set of zeroes has Hausdorff dimension larger than 1 ? ? and such that ?_p {ξ : (η_?,ξ) is compatible } > 0 for p small enough, where ?_p stands for the product Bernoulli measure with parameter p. © 2014 Wiley Periodicals, Inc.     

The basic theory of infinite time register machines

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all P¹₁{\Pi^1_1} sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not n ? r{n \in r} with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs.     

A rigidity theorem for automorphism groups of trees

A group G is called unsplittable if Hom(G, ℤ) = 0 and this group is not a non-trivial amalgam. Let X be a tree with a countable number of edges incident at each vertex and G be its automorphism group. In this paper we prove that the vertex stabilizers are unsplittable groups. Bass and Lubotzky proved (see [3]) that for certain locally finite trees X, the automorphism group determines the tree X (that is, knowing the automorphism group we can “construct” the tree X). We generalize this Theorem of Bass and Lubotzky, using the above result. In particular we show that the Theorem holds even for trees which are not locally finite. Moreover, we prove that the permutation group of an infinite countable set is unsplittable and the infinite (or finite) cartesian product of unsplittable groups is an unsplittable group as well. This research was supported by the European Social Fund and National resources-EPEAEK II grant Pythagoras 70/3/7298.     

Infinite paths in planar graphs III, 1‐way infinite paths

An infinite graph is 2‐indivisible if the deletion of any finite set of vertices from the graph results in exactly one infinite component. Let G be a 4‐connected, 2‐indivisible, infinite, plane graph. It is known that G contains a spanning 1‐way infinite path. In this paper, we prove a stronger result by showing that, for any vertex x and any edge e on a facial cycle of G, there is a spanning 1‐way infinite path in G from x and through e. Results will be used in two forthcoming papers to establish a conjecture of Nash‐Williams. © 2005 Wiley Periodicals, Inc. J Graph Theory     

（0,1;0）-INTERPOLATION ON INFINITE INTERVAL （-∞, ＋∞）

In this paper, we study the explicit representation and convergence of （0, 1;0）-interpolation on infisite interval, which means to determine a polynomial of degree ≤ 3n - 2 when the function values areprescribed at two set of points namely the zeros of Hn（x） and H′n （x） and the first derivatives at the zerosof H′n（x）.     

Topological properties of definable sets in ordered Abelian groups of burden 2

We obtain some new results on the topology of unary definable sets in expansions of densely ordered Abelian groups of burden 2. In the special case in which the structure has dp-rank 2, we show that the existence of an infinite definable discrete set precludes the definability of a set which is dense and codense in an interval, or of a set which is topologically like the Cantor middle-third set (Theorem 2.9). If it has burden 2 and both an infinite discrete set D and a dense-codense set X are definable, then translates of X must witness the Independence Property (Theorem 2.26). In the last section, an explicit example of an ordered Abelian group of burden 2 is given in which both an infinite discrete set and a dense-codense set are definable.     

On quasi-amorphous sets

A set is said to be amorphous if it is infinite, but cannot be written as the disjoint union of two infinite sets. The possible structures which an amorphous set can carry were discussed in [5]. Here we study an analogous notion at the next level up, that is to say replacing finite/infinite by countable/uncountable, saying that a set is quasi-amorphous if it is uncountable, but is not the disjoint union of two uncountable sets, and every infinite subset has a countably infinite subset. We use the Fraenkel–Mostowski method to give many examples showing the diverse structures which can arise as quasi-amorphous sets, for instance carrying a projective geometry, or a linear ordering, or both; reconstruction results in the style of [1] are harder to come by in this case. Received: 8 April 1999 / Published online: 3 October 2001     

On some sets of dictionaries whose ω ‐powers have a given

A dictionary is a set of finite words over some finite alphabet X. The ω ‐power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [10] the complexity of the set of dictionaries whose associated ω ‐powers have a given complexity. In particular, he considered the sets ??( Σ ⁰k) (respectively, ??( Π ⁰_k), ??( Δ ¹₁)) of dictionaries V ? 2* whose ω ‐powers are Σ ⁰_k‐sets (respectively, Π ⁰_k‐sets, Borel sets). In this paper we first establish a new relation between the sets ??( Σ ⁰₂) and ??( Δ ¹₁), showing that the set ??( Δ ¹₁) is “more complex” than the set ??( Σ ⁰₂). As an application we improve the lower bound on the complexity of ??( Δ ¹₁) given by Lecomte, showing that ??( Δ ¹₁) is in Σ ¹ ₂(2^2*)\ Π ⁰₂. Then we prove that, for every integer k ≥ 2 (respectively, k ≥ 3), the set of dictionaries ??( Π ⁰_k+1) (respectively, ??( Σ ⁰_{k +1})) is “more complex” than the set of dictionaries ??( Π ⁰_k) (respectively, ??( Σ ⁰_k)) (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multiperiodic multifractal martingale measures

A nonnegative 1-periodic multifractal measure on is obtained as infinite random product of harmonics of a 1-periodic function W(t). Such infinite products are statistically self-affine and generalize certain Riesz products with random phases. They are martingale structures, therefore converge. The criterion on W for nondegeneracy is provided. It differs completely from those for other known random measures constructed as martingale limits of multiplicative processes. In particular, it is very sensitive to small changes in W(t). When these infinite products are interpreted in the framework of thermodynamic formalism for random transformations, logW is a potential function when W>0. For regular enough potentials, in case of degeneracy, the natural normalization makes the sequence of measures converge. Moreover, this normalization is neutral for nondegenerate martingales. The multifractal analysis of the limit martingale measure is performed for a class of potential functions having a dense countable set of jump points.     

Orthogonal invariants of skew-symmetric matrices

The algebra of invariants of d-tuples of n?×?n skew-symmetric matrices under the action of the orthogonal group by simultaneous conjugation is considered over an infinite field of characteristic different from two. For n?=?3 and d?>?0 a minimal set of generators is established. A homogeneous system of parameters (i.e. an algebraically independent set such that the algebra of invariants is a finitely generated free module over subalgebra generated by this set) is described for n?=?3 and d?>?0, for n?=?4 and d?=?2,?3, for n?=?5 and d?=?2.     

A GAME-THEORETIC PROOF OF ANALYTIC RAMSEY THEOREM

We give a simple game-theoretic proof of Silver's theorem that every analytic set is Ramsey. A set P of subsets of ω is called Ramsey if there exists an infinite set H such that either all infinite subsets of H are in P or all out of P. Our proof clarifies a strong connection between the Ramsey property of partitions and the determinacy of infinite games.     

Infinite Random Geometric Graphs

We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in \mathbbRⁿ{\mathbb{R}^n} equipped with the metric derived from the L _∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR _n , is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR _n . In contrast, we show that infinite random geometric graphs in \mathbbR²{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic.     

On generating countable sets of endomorphisms

Sierpiski proved that every countable set of mappings on an infinite set X is contained in a 2-generated subsemigroup of the semigroup of all mappings on X. In this paper we prove that every countable set of endomorphisms of an algebra which has an infinite basis (independent generating set) is contained in a 2-generated subsemigroup of the semigroup of all endomorphisms of .     

Menger’s theorem for infinite graphs

We prove that Menger’s theorem is valid for infinite graphs, in the following strong version: let A and B be two sets of vertices in a possibly infinite digraph. Then there exist a set of disjoint A–B paths, and a set S of vertices separating A from B, such that S consists of a choice of precisely one vertex from each path in . This settles an old conjecture of Erdős.     

Spanning paths in infinite planar graphs

Let G be a 4-connected infinite planar graph such that the deletion of any finite set of vertices of G results in at most one infinite component. We prove a conjecture of Nash-Williams that G has a 1-way infinite spanning path. © 1996 John Wiley & Sons, Inc.