Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

A note on the differentiable structure of generalized idempotents

For a fixed n > 2, we study the set Λ of generalized idempotents, which are operators satisfying T ⁿ⁺¹ = T. Also the subsets Λ _? , of operators such that T ^n?1 is the Moore-Penrose pseudo-inverse of T, and Λ*, of operators such that T ^n?1 = T* (known as generalized projections) are studied. The local smooth structure of these sets is examined.     

On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets

The monotone asymmetric travelling salesman polytope P?ⁿ_T is defined to be the convex hull of the incidence vectors of all hamiltonian circuits and all subsets of these in a complete diagraph of order n. We prove that certain hypohamiltonian diagraphs G=(V,E), i.e. diagraphs which are not hamiltonian but such that G–υ is hamiltonian for all υ?V, induce facets x(E)?n–1 of P?ⁿ_T. This result indicates that P?ⁿ_T has very complicated facets and that it is very unlikely that an explicit complete characterization of P?ⁿ_T can ever be given.     

Separating diffeomorphisms of the torus

There exists a diffeomorphism on the n-dimensional torus Tⁿ which is conjugate with a hyperbolic linear automorphism, but is not an Anosov diffeomorphism. A diffeomorphismf: Tⁿ→Tⁿ has such a property iff is separating and belongs to the C⁰ closure of the Anosov diffeomorphisms.     

On first passage time structure of random walks

For continuous time birth-death processes on {0,1,2,…}, the first passage time T⁺_n from n to n + 1 is always a mixture of (n + 1) independent exponential random variables. Furthermore, the first passage time T_0,n+1 from 0 to (n + 1) is always a sum of (n + 1) independent exponential random variables. The discrete time analogue, however, does not necessarily hold in spite of structural similarities. In this paper, some necessary and sufficient conditions are established under which T⁺_n and T_0,n+1 for discrete time birth-death chains become a mixture and a sum, respectively, of (n + 1) independent geometric random variables on {1,2,…};. The results are further extended to conditional first passage times.     

Derivations for a class of matrix function algebras

We study a class of matrix function algebras, here denoted T⁺(C_n). We introduce a notion of point derivations, and classify the point derivations for certain finite dimensional representations of T⁺(C_n). We use point derivations and information about n×n matrices to show that every T⁺(C_n)-valued derivation on T⁺(C_n) is inner.     

On power bounded operators

The main result asserts that, for any contraction T on an arbitrary Banach space X, ∥ Tⁿ − T^{n + 1} ∥ → 0 as n → ∞, if and only if the spectrum of T has no points on the unit circle except perhaps z = 1. This theorem is extended for ϑ(T)Tⁿ, where ϑ is a function of spectral synthesis on the unit circle. As an application, we generalize the so-called “zero-two” law of Ornstein and Sucheston and Zaharopol to positive contraction on a very large class of Banach lattices.     

Transposing a matrix by similarity operations

A matrix T is said to co-transpose a square matrix A if T^?1AT=A′ and T^?1A′T=A. For every n?3 there exists a real n×n matrix which cannot be co-transposed by any matrix. However, it is shown that the following classes of real matrices can be co-transposed by a symmetric matrix of order two: 2×2 matrices, normal matrices, and matrices whose square is symmetric.     

Every transformation is bilaterally deterministic

Every ergodic transformationT with a finite generator α, has another finite generator β, which refines α, and is bilaterally deterministic, i.e. V_|i|>n T ⁱβ is the full σ-algebra for everyn.     

Solution of systems with Toeplitz matrices generated by rational functions

We consider Toeplitz matrices T_n = (t_i−j)ⁿ_i,j=0, where Σ^∞_−∞t_jz^j is a formal Laurent series of a rational function R(z). A criterion is given for T_n to be invertible, in terms of the nonvanishing of a determinant D_n involving the zeros of R(z), and of order and form independent of n; i.e., n enters into D_n as a parameter, and not so as to complicate D_n as n increases. Explicit formulas involving similar determinants are given for the solution of the system T_nX = Y in the case where T_n is invertible. Formulas are also given for T⁻¹_n in the case where T_n−1 and T_n are both convertible Suggestions concerning possible computational procedures based on the results are included.     

Global hypoellipticity and global solvability in Gevrey classes on the n-dimensional torus

Let P be a linear partial differential operator with coefficients in the Gevrey class G^s(Tⁿ) where Tⁿ is the n-dimensional torus and s?1. We prove that if P is s-globally hypoelliptic in Tⁿ then its transposed operator tP is s-globally solvable in Tⁿ, thus extending to the Gevrey classes the well-known analogous result in the corresponding C^∞ class.     

An example concerning fixed points

An example is given of a contractionT defined on a bounded closed convex subset of Hilbert space for which ((I+T)/2) ⁿ does not converge.     

On the global solvability in Gevrey classes on the n-dimensional torus

Let P be a linear partial differential operator with coefficients in the Gevrey class G^s(Tⁿ), where Tⁿ is the n-dimensional torus and s?1. We prove a necessary condition for the s-global solvability of P on Tⁿ. We also apply this result to give a complete characterization for the s-global solvability for a class of formally self-adjoint operators with nonconstant coefficients.     

Idempotence preserving maps on spaces of triangular matrices

SupposeF is an arbitrary field. Let |F| be the number of the elements ofF. LetT _n (F) be the space of allnxn upper-triangular matrices overF. A map Ψ: T _N (F) → T _N (F) is said to preserve idempotence ifA - λ B is idempotent if and only if Ψ(A) - λΨ(B) is idempotent for anyA, B ∈ T _n (F) and λ ∈ F. It is shown that: when the characteristic ofF is not 2, |F|>3 and n ≥ 3, Ψ:T _n (F) → T _n (F) is a map preserving idempotence if and only if there exists an invertible matrixP τ T _n (F) such that either ?(A) = PAP ^?1 for everyA ∈ T _n (F) or Ψ(A) = PJA ^t JP ^?1 for everyA ∈ T _n (F), whereJ = ∑ _n=1 ⁿ E _i,n+1?i and E_ij is the matrix with 1 in the (i,j)th entry and 0 elsewhere.     

A characterization of the minimal invariant sets of Alspach’s mapping

In 1981, Dale Alspach modified the baker’s transform to produce the first example of a nonexpansive mapping T on a weakly compact convex subset C of a Banach space that is fixed point free. By Zorn’s lemma, there exist minimal weakly compact, convex subsets of C which are invariant under T and are fixed point free.In this paper we produce an explicit formula for the nth power of T, Tⁿ, and prove that the sequence (Tⁿf)_n∈N converges weakly to , for all f∈C. From this we derive a characterization of the minimal invariant sets of T.     

Maps on matrices that preserve the spectrum

Let T be a continuous map of the space of complex n×n matrices into itself satisfying T(0)=0 such that the spectrum of T(x)-T(y) is always a subset of the spectrum of x-y. There exists then an invertible n×n matrix u such that either T(a)=uau^-1 for all a or T(a)=ua^tu^-1 for all a. We arrive at the same conclusion by supposing that the spectrum of x-y is always a subset of the spectrum of T(x)-Tt(y), without the continuity assumption on T.     

Embedding Tn-like continua in Euclidean space

Many authors have been concerned with embedding ∏-like continua in Rⁿ where ∏ is some collection of polyhedra or manifolds. A similar concern has been embedding ∏-like continua in Rⁿ up to shape. In this paper we prove two main theorems. Theorem: If n ? 2 and X is Tⁿ-like, then X embeds in R²ⁿ. This result was conjectured by McCord for the case H¹(X) finitely generated and proved by McCord for the case that H¹(X) = 0 using a theorem of Isbell. The second theorem is a shape embedding theorem. Theorem: If X is Tⁿ-like, then X embeds in Rⁿ⁺² up to shape. This theorem is proved by showing that an n-dimensional compact connected abelian topological group embeds in Rⁿ⁺². Any Tⁿ-like continuum is shape equivalent to a k-dimensional compact connected abelian topological group for some 0 ? k ? n.     

Continuity properties of the averaging projection onto the set of Hankel matrices

Some continuity properties of the averaging projection $\text{P}$ onto the set of Hankel matrices are investigated. It is proved that this projection is of weak type (1, 1) which means that for any nuclear operator T the s-numbers of $\text{P}$T satisfy S_n($\text{P}$T) ? const(n + 1). As a consequence it is obtained that $\text{P}$ maps the Matsaev ideal $\text{G}$_ω = {T:∑_n?0S_n(T)(2n + 1)^?1 < ∞} into the set of compact operators.     

Hyperbolicity of arborescent tangles and arborescent links

In this paper, we study the hyperbolicity of arborescent tangles and arborescent links. We will explicitly determine all essential surfaces in arborescent tangle complements with non-negative Euler characteristic, and show that given an arborescent tangle T, the complement X(T) is non-hyperbolic if and only if T is a rational tangle, T=Qm*T^′ for some m?1, or T contains Qn for some n?2. We use these results to prove a theorem of Bonahon and Siebenmann which says that a large arborescent link L is non-hyperbolic if and only if it contains Q₂.     

Packing two copies of a tree into its third power

A graph H of order n is said to be k-placeable into a graph G of order n, if G contains k edge-disjoint copies of H. It is well known that any non-star tree T of order n is 2-placeable into the complete graph K_n. In the paper by Kheddouci et al. [Packing two copies of a tree into its fourth power, Discrete Math. 213 (2000) 169-178], it is proved that any non-star tree T is 2-placeable into T⁴. In this paper, we prove that any non-star tree T is 2-placeable into T³.