Stably ergodic diffeomorphisms which are not partially hyperbolic

We show stable ergodicity of a class of conservative diffeomorphisms ofT ⁿ which do not have any hyperbolic invariant subbundle. Moreover, the uniqueness of SRB (Sinai-Ruelle-Bowen) measure for non-conservativeC ¹ perturbations of such diffeomorphisms is verified. This class strictly contains non-partially hyperbolic robustly transitive diffeomorphisms constructed by Bonatti-Viana [4] and so we answer the question posed there on the stable ergodicity of such systems.     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

Oriented matroids with few mutations

This paper defines a “connected sum” operation on oriented matroids of the same rank. This construction is used for three different applications in rank 4. First it provides nonrealizable pseudoplane arrangements with a low number of simplicial regions. This contrasts the case of realizable hyperplane arrangements: by a classical theorem of Shannon every arrangement ofn projective planes in ℝP ^d-1 contains at leastn simplicial regions and every plane is adjacent to at leastd simplicial regions [17], [18]. We construct a class of uniform pseudoarrangements of 4n pseudoplanes in ℝP³ with only 3n+1 simplicial regions. Furthermore, we construct an arrangement of 20 pseudoplanes where one plane is not adjacent to any simplicial region. Finally we disprove the “strong-map conjecture” of Las Vergnas [1]. We describe an arrangement of 12 pseudoplanes containing two points that cannot be simultaneously contained in an extending hyperplane.     

Lengths of cycles in halin graphs

A Halin graph is a plane graph H = T U C, where T is a plane tree with no vertex of degree two and at least one vertex of degree three or more, and C is a cycle connecting the endvertices of T in the cyclic order determined by the embedding of T. We prove that such a graph on n vertices contains cycles of all lengths l, 3 ≤ l n, except, possibly, for one even value m of l. We prove also that if the tree T contains no vertex of degree three then G is pancyclic.     

Induced trees in graphs of large chromatic number

Gyárfás and Sumner independently conjectured that for every tree T and integer k there is an integer f(k, T) such that every graph G with χ(G) > f(k, t) contains either K_k or an induced copy of T. We prove a ‘topological’ version of the conjecture: for every tree T and integer k there is g(k,T) such that every graph G with χ(G) > g(k,t) contains either K_k or an induced copy of a subdivision of T. © 1997 John Wiley & Sons, Inc.     

Augmented Teichmüller spaces and orbifolds

We study complex analytic properties of the augmented Teichmüller spaces [`(T)]<sub>g,n</sub>{\overline{\mathcal{T}}_{g,n}} obtained by adding to the classical Teichmüller spaces T<sub>g,n</sub>{\mathcal{T}_{g,n}} points corresponding to Riemann surfaces with nodal singularities. Unlike T<sub>g,n</sub>{\mathcal{T}_{g,n}}, the space [`(T)]_g,n{\overline{\mathcal{T}}_{g,n}} is not a complex manifold (it is not even locally compact). We prove, however, that the quotient of the augmented Teichmüller space by any finite index subgroup of the Teichmüller modular group has a canonical structure of a complex orbifold. Using this structure, we construct natural maps from [`(T)]{\overline{\mathcal{T}}} to stacks of admissible coverings of stable Riemann surfaces. This result is important for understanding the cup-product in stringy orbifold cohomology. We also establish some new technical results from the general theory of orbifolds which may be of independent interest.     

Type-definable groups in C-minimal structures

This Note studies type-definable groups in C-minimal structures. We show first for some of these groups, that they contain a cone which is a subgroup. This result will be applied to show that in any geometric locally modular non-trivial C-minimal structure, there is a definable infinite C-minimal group.     

ℋ-theories, fragments of HA and PA-normality

For a classical theory T, ℋ(T) denotes the intuitionistic theory of T-normal (i.e. locally T) Kripke structures. S. Buss has asked for a characterization of the theories in the range of ℋ and raised the particular question of whether HA is an ℋ-theory. We show that T ⁱ ∈ range(ℋ) iff T ⁱ = ℋ(T). As a corollary, no fragment of HA extending iΠ ₁ belongs to the range of ℋ. A. Visser has already proved that HA is not in the range of H by different methods. We provide more examples of theories not in the range of ℋ. We show PA-normality of once-branching Kripke models of HA + MP, where it is not known whether the same holds if MP is dropped. Received: 15 August 1999 / Published online: 3 October 2001     

On the Boolean algebras of definable sets in weakly o‐minimal theories

We consider the sets definable in the countable models of a weakly o‐minimal theory T of totally ordered structures. We investigate under which conditions their Boolean algebras are isomorphic (hence T is p‐ω‐categorical), in other words when each of these definable sets admits, if infinite, an infinite coinfinite definable subset. We show that this is true if and only if T has no infinite definable discrete (convex) subset. We examine the same problem among arbitrary theories of mere linear orders. Finally we prove that, within expansions of Boolean lattices, every weakly o‐minimal theory is p‐ω‐categorical. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the largest tree of given maximum degree in a connected graph

We prove that every connected graph G contains a tree T of maximum degree at most k that either spans G or has order at least kδ(G) + 1, where δ(G) is the minimum degree of G. This generalizes and unifies earlier results of Bermond [1] and Win [7]. We also show that the square of a connected graph contains a spanning tree of maximum degree at most three.     

Topological dynamics and the complexity of strong types

We develop topological dynamics for the group of automorphisms of a monster model of any given theory. In particular, we find strong relationships between objects from topological dynamics (such as the generalized Bohr compactification introduced by Glasner) and various Galois groups of the theory in question, obtaining essentially new information about them, e.g., we present the closure of the identity in the Lascar Galois group of the theory as the quotient of a compact, Hausdorff group by a dense subgroup.We apply this to describe the complexity of bounded, invariant equivalence relations, obtaining comprehensive results, subsuming and extending the existing results and answering some open questions from earlier papers. We show that, in a countable theory, any such relation restricted to the set of realizations of a complete type over Ø is type-definable if and only if it is smooth. Then we show a counterpart of this result for theories in an arbitrary (not necessarily countable) language, obtaining also new information involving relative definability of the relation in question. As a final conclusion we get the following trichotomy. Let \(\mathfrak{C}\) be a monster model of a countable theory, p ∈ S(Ø), and E be a bounded, (invariant) Borel (or, more generally, analytic) equivalence relation on p(\(\mathfrak{C}\)). Then, exactly one of the following holds: (1) E is relatively definable (on p(\(\mathfrak{C}\))), smooth, and has finitely many classes, (2) E is not relatively definable, but it is type-definable, smooth, and has 2^?0 classes, (3) E is not type definable and not smooth, and has 2^?0 classes. All the results which we obtain for bounded, invariant equivalence relations carry over to the case of bounded index, invariant subgroups of definable groups.     

Tail field representations and the zero-two law

The zero-two law was proved for a positiveL ₁-contractionT by Ornstein and Sucheston, and gives a condition which impliesT ⁿ f−T ⁿ⁺¹ f → 0 for allf. Extensions of this result to the case of a positiveL _p -contraction, 1≤p<∞, have been obtained by several authors. In the present paper we prove a theorem which is related to work of Wittmann. We will say that a positive contractionT contains a circle of lengthm if there is a nonzero functionf such that the iterated valuesf, T f,…,T ^m-1 f have disjoint support, whileT ^m f=f. Similarly, a contractionT contains a line if for everym there is a nonzero functionf (which may depend onm) such thatf,…,T ^m-1 f have disjoint support. Approximate forms of these conditions are defined, which are referred to as asymptotic circles and lines, respectively. We show (Theorem 3) that if the conclusionT ⁿ f−T ⁿ⁺¹ f→0 of the zero-two law does not hold for allf inL _p , then eitherT contains an asymptotic circle orT contains an asymptotic line. The point of this result is that any condition onT which excludes circles and lines must then imply the conclusion of the zero-two law. Theorem 3 is proved by means of the representation of a positiveL _p -contraction in terms of anL _p -isometry. Asymptotic circles and lines forT correspond to exact circles and lines for the isometry on tail-measurable functions, and exact circles and lines for the isometry are obtained using the Rohlin tower construction for point transformations. Research supported in part by NSERC.     

χ‐bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P₄ (the path on four vertices) similar statements hold. We establish some positive and negative results.     

A pivoting strategy for symmetric tridiagonal matrices

The LBL^T factorization of Bunch for solving linear systems involving a symmetric indefinite tridiagonal matrix T is a stable, efficient method. It computes a unit lower triangular matrix L and a block 1 × 1 and 2 × 2 matrix B such that T=LBL^T. Choosing the pivot size requires knowing a priori the largest element σ of T in magnitude. In some applications, it is required to factor T as it is formed without necessarily knowing σ. In this paper, we present a modification of the Bunch algorithm that can satisfy this requirement. We demonstrate that this modification exhibits the same bound on the growth factor as the Bunch algorithm and is likewise normwise backward stable. Copyright © 2005 John Wiley & Sons, Ltd.     

Spaces without Nonconstant Maps into Y

Given a T ₁-space Y, we show that the category H(Y) of all nonvoid Y-connected regular T ₁ spaces contains arbitrarily large extremally semirigid spaces. It contains also two reflective subcategories the intersection of which is not reflective.     

Dense codense predicates and the NTP2

We show that if T is any geometric theory having the NTP₂ then the corresponding theories of lovely pairs of models of T and of H‐structures associated to T also have the NTP₂. We also prove that if T is strong then the same two expansions of T are also strong.     

On pseudolinearity and generic pairs

We continue the study of the connection between the “geometric” properties of SU ‐rank 1 structures and the properties of “generic” pairs of such structures, started in [8]. In particular, we show that the SU‐rank of the (complete) theory of generic pairs of models of an SU ‐rank 1 theory T can only take values 1 (if and only if T is trivial), 2 (if and only if T is linear) or ω, generalizing the corresponding results for a strongly minimal T in [3]. We also use pairs to derive the implication from pseudolinearity to linearity for ω ‐categorical SU ‐rank 1 structures, established in [7], from the conjecture that an ω ‐categorical supersimple theory has finite SU ‐rank, and find a condition on generic pairs, equivalent to pseudolinearity in the general case (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Unavoidable trees in tournaments

An oriented tree T on n vertices is unavoidable if every tournament on n vertices contains a copy of T. In this paper, we give a sufficient condition for T to be unavoidable, and use this to prove that almost all labeled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on vertices contains a copy of every oriented tree T on n vertices with polylogarithmic maximum degree, improving a result of Kühn, Mycroft, and Osthus.     

On Representing Concepts in Finite Models

We present a method of transferring Tarski's technique of classifying finite order concepts by means of truth‐definitions into finite mode theory. The other considered question is the problem of representability relations on words or natural numbers in finite models. We prove that relations representable in finite models are exactly those which are of degree ≤ o′. Finally, we consider theories of sufficiently large finite models. For a given theory T we define sl(T) as the set of all sentences true in almost all finite models for T. For theories of sufficiently large models our version of Tarski's technique becomes practically the same as the classica one. We investigate also degrees of undecidability for theories of sufficiently large finite models. We prove for some special theory ST that its degree is stronger than 0′ but still not more than Σ⁰₂.