Embeddings and Other Mappings of Rooted Trees Into Complete Trees

Let T ⁿ be the complete binary tree of height n, with root 1 _n as the maximum element. For T a tree, define and . We disprove a conjecture of Kubicki, Lehel and Morayne, which claims that for any fixed n and arbitrary rooted trees T ₁ T ₂. We show that A(n; T) is of the form where l is the number of leaves of T, and each q _j is a polynomial. We provide an algorithm for calculating the two leading terms of q _l for any tree T. We investigate the asymptotic behaviour of the ratio A(n; T)/C(n; T) and give examples of classes of pairs of trees T ₁, T ₂ where it is possible to compare A(n; T ₁)/C(n; T ₁) and A(n; T ₂)/C(n; T ₂). By calculating these ratios for a particular class of pairs of trees, we show that the conjecture fails for these trees, for all sufficiently large n. Kubicki, Lehel and Morayne have proved the conjecture when T ₁, T ₂ are restricted to being binary trees. We also look at embeddings into other complete trees, and we show how the result can be viewed as one of many possible correlation inequalities for embeddings of binary trees. We also show that if we consider strict order-preserving maps of T ₁, T ₂ into T ⁿ (rather than embeddings) then the corresponding correlation inequalities for these maps also generalise to arbitrary trees.     

Uniformly cross intersecting families

Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be ℓ-cross-intersecting iff |A∩B|=ℓ for all A∈ A and B∈B. Denote by P _e (n) the maximum value of |A||B| over all such pairs. The best known upper bound on P _e (n) is Θ(2 ⁿ ), by Frankl and R?dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2ℓ, a simple construction of an ℓ-cross-intersecting pair (A,B) with |A||B| = $ \left( {{*{20}c} {2\ell } \\ \ell \\ } \right) $ \left( {\begin{array}{*{20}c} {2\ell } \\ \ell \\ \end{array} } \right) 2 ^n−2ℓ = Θ(2 ⁿ /$ \sqrt \ell $ \sqrt \ell ), and conjectured that this is best possible. Consequently, Sgall asked whether or not P _e (n) decreases with ℓ.     

Strongly approximative similarity of operators

Two operators A, B ∈ B（H） are said to be strongly approximatively similar, denoted by A -sas B, if （i） given ε 〉 0, there exist Ki ∈ B（H） compact with ｜｜Ki｜｜ 〈ε（i = 1,2） such that A＋K1 and B ＋ K2 are similar; （ii） σ0（A） = σ0（B） and dim H（λ; A） = dim H（λ; B） for each λ ∈ σ0（A）. In this paper, we prove the following result. Let S,T ∈ B（H） be quasitriangular satisfying： （i） σ（T） = σ（S） = σw（S） is connected and σe（S） = σlre（S）; （ii） ρs-F（S） ∩ σ（S） consists of at most finite components and each component Ω satisfies that Ω = int Ω, where int Ω is the interior of Ω. Then, S -sas T if and only if S and T are essentially similar.     

Étale descent for hochschild and cyclic homology

IfB is an étale extension of ak-algebraA, we prove for Hochschild homology thatHH _*(B)≅HH_*(A)⊗_AB. For Galois descent with groupG there is a similar result for cyclic homology:HC _*≅HC_*(B)^G if . In the process of proving these results we give a localization result for Hochschild homology without any flatness assumption. We then extend the definition of Hochschild homology to all schemes and show that Hochschild homology satisfies cohomological descent for the Zariski, Nisnevich and étale topologies. We extend the definition of cyclic homology to finite-dimensional noetherian schemes and show that cyclic homology satisfies cohomological descent for the Zariski and Nisnevich topologies, as well as for the étale topology overQ. Finally we apply these results to complete the computation of the algebraicK-theory of seminormal curves in characteristic zero. Partially supported by National Science Foundation grant DMS-8803497 Partially supported by National Security Agency grant MDA904-90-H-4019     

Strong separativity over exchange rings

An exchange ring R is strongly separative provided that for all finitely generated projective right R-modules A and B, A ⊕ A ≅ A ⊕ B ⇒ A ≅ B. We prove that an exchange ring R is strongly separative if and only if for any corner S of R, aS + bS = S implies that there exist u, v ∈ S such that au = bv and Su + Sv = S if and only if for any corner S of R, aS + bS = S implies that there exists a right invertible matrix ∈ M ₂(S). The dual assertions are also proved.     

An interlacing theorem for matrices whose graph is a given tree

Let A and B be (n×n)-matrices. For an index set S ⊂ {1, …, n}, denote by A(S) the principal submatrix that lies in the rows and columns indexed by S. Denote by S′ the complement of S and define η(A, B) = det A(S) det B(S′), where the summation is over all subsets of {1, …, n} and, by convention, det A(∅) = det B(∅) = 1. C. R. Johnson conjectured that if A and B are Hermitian and A is positive semidefinite, then the polynomial η(λA,-B) has only real roots. G. Rublein and R. B. Bapat proved that this is true for n ⩽ 3. Bapat also proved this result for any n with the condition that both A and B are tridiagonal. In this paper, we generalize some little-known results concerning the characteristic polynomials and adjacency matrices of trees to matrices whose graph is a given tree and prove the conjecture for any n under the additional assumption that both A and B are matrices whose graph is a tree. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 10, No. 3, pp. 245–254, 2004.     

TC semigroups and inflations

An algebraA satisfiesTC (the term condition) if for any and anyn + 1-ary termp.TC algebras have been extensively studied. We previously determined the structure of allTC semigroups. We use this result to show that ifS is aTC semigroup thenS _E = {a ε S | ax is an idempotent for somex ε S} is an inflation ofS _Reg (the set of regular elements ofS) andS _Reg ≅H × A × B whereH is an abelian group,A is a left zero semigroup, andB is a right zero semigroup. As a corollary of this result, we show thatS is a semisimpleTC semigroup iffS ≅H × A × B whereH is an abelian group,A is a left zero semigroup, andB is a right zero semigroup.     

A general oscillation theorem for self-adjoint differential systems with applications to Sturm-Liouville eigenvalue problems and quadratic functionals

For given 2n×2n matricesS ₁₃,S ₂₄ with rank(S ₁₃,S ₂₄)=2n we consider the eigenvalue problem:u′=A(x)u+B(x)v,v′=C ₁(x;λ)u-A ^T(x)v with

Norm conditions for real-algebra isomorphisms between uniform algebras

Let A and B be uniform algebras. Suppose that α ≠ 0 and A ₁ ⊂ A. Let ρ, τ: A ₁ → A and S, T: A ₁ → B be mappings. Suppose that ρ(A ₁), τ(A ₁) and S(A ₁), T(A ₁) are closed under multiplications and contain expA and expB, respectively. If ‖S(f)T(g) − α‖_∞ = ‖ρ(f)τ(g) − α‖_∞ for all f, g ∈ A ₁, S(e ₁)⁻¹ ∈ S(A ₁) and S(e ₁) ∈ T(A ₁) for some e ₁ ∈ A ₁ with ρ(e ₁) = 1, then there exists a real-algebra isomorphism $ \tilde S $ \tilde S : A → B such that $ \tilde S $ \tilde S (ρ(f)) = S(e ₁)⁻¹ S(f) for every f ∈ A ₁. We also give some applications of this result.     

Generating Uniform Random Vectors in Z p k : The General Case

We consider the rate of convergence of the Markov chain X _n+1=A X _n +B _n (mod p), where A is an integer matrix with nonzero eigenvalues, and {B _n } _n is a sequence of independent and identically distributed integer vectors, with support not parallel to a proper subspace of Q ^k invariant under A. If for all eigenvalues λ _i of A, then n=O((ln p)²) steps are sufficient and n=O(ln p) steps are necessary to have X _n sampling from a nearly uniform distribution. Conversely, if A has the eigenvalues λ _i that are roots of positive integer numbers, |λ ₁|=1 and |λ _i |>1 for all , then O(p ²) steps are necessary and sufficient.      

r-Maximal major subsets

The question of which r.e. setsA possess major subsetsB which are alsor-maximal inA (A⊂_rm B) arose in attempts to extend Lachlan’s decision procedure for the αε-theory of ℰ^*, the lattice of r.e. sets modulo finite sets, and Soare’s theorem thatA andB are automorphic if their lattice of supersets ℒ^*(A) and ℒ^*(B) are isomorphic finite Boolean algebras. We characterize the r.e. setsA with someB⊂_rm A as those with a Δ₃ function that for each recursiveR _i specifiesR _i or as infinite on and to be preferred in the construction ofB. There are r.e.A andB with ℒ^*(A) and ℒ^*(B) isomorphic to the atomless Boolean algebra such thatA has anrm subset andB does not. Thus 〈ℰ^*,A〉 and 〈ℰ^*,B〉 are not even elementarily equivalent. In every non-zero r.e. degree there are r.e. sets with and withoutrm subsets. However the classF of degrees of simple sets with norm subsets satisfies . The authors were partially supported by NSF Grants MCS 76-07258, MCS 77-04013 and MCS 77-01965 respectively.     

A generalization of peripherally-multiplicative surjections between standard operator algebras

Let A and B be standard operator algebras on Banach spaces X and Y, respectively. The peripheral spectrum σ_π (T) of T is defined by σ_π (T) = z ∈ σ(T): |z| = max_w∈σ(T) |w|. If surjective (not necessarily linear nor continuous) maps φ, ϕ: A → B satisfy σ_π (φ(S)ϕ(T)) = σ_π (ST) for all S; T ∈ A, then φ and ϕ are either of the form φ(T) = A ₁ TA ₂ ⁻¹ and ϕ(T) = A ₂ TA ₁ ⁻¹ for some bijective bounded linear operators A ₁; A ₂ of X onto Y, or of the form φ(T) = B ₁ T*B ₂ ⁻¹ and ϕ(T) = B ₂ T*B ⁻¹ for some bijective bounded linear operators B ₁;B ₂ of X* onto Y.      

Perturbations of differentiable semigroups

If (A, D(A)) generates a C ₀-semigroup T on a Banach space X and then (A + B, D(A)) is also the generator of a C ₀-semigroup, S _B . There are easy examples to show that if T is eventually differentiable then S _B need not be eventually differentiable. In 1995 an example was constructed to show that if T is immediately differentiable then S _B need not be immediately differentiable. In this paper we establish necessary and sufficient conditions on the generator (A, D(A)) of T which ensure that eventual or immediate differentiability of T is inherited by S _B for all . We are therefore able to give a characterization of the immediately and eventually differentiable C ₀-semigroups for which differentiability is a stable property under bounded perturbations of the generator. We also prove a characterization of the C ₀-semigroups for which the norm of the resolvent of the generator decays on vertical lines and a new characterization of the Crandall-Pazy class of semigroups. We are grateful to Charles Batty and Tom Ransford for helpful discussions and to the referee for their constructive comments.     

Rigidity of commutators and elementary operators on Calkin algebras

LetA=(A ₁,...,A _n ),B=(B ₁,...,B _n )εL(ℓ ^p ) ⁿ be arbitraryn-tuples of bounded linear operators on (ℓ ^p ), with 1<p<∞. The paper establishes strong rigidity properties of the corresponding elementary operators ε _a,b on the Calkin algebraC(ℓ ^p )≡L(ℓ ^p )/K(ℓ ^p ); , where quotient elements are denoted bys=S+K(ℓ ^p ) forSεL(ℓ ^p ). It is shown among other results that the kernel Ker(ε _a,b ) is a non-separable subspace ofC(ℓ ^p ) whenever ε _a,b fails to be one-one, while the quotient is non-separable whenever ε _a,b fails to be onto. These results extend earlier ones in several directions: neither of the subsets {A ₁,...,A _n }, {B ₁,...,B _n } needs to consist of commuting operators, and the results apply to other spaces apart from Hilbert spaces. Supported by the Academy of Finland, Project 32837.     

A Bipartite Analogue of Dilworth’s Theorem

Let m(n) be the maximum integer such that every partially ordered set P with n elements contains two disjoint subsets A and B, each with cardinality m(n), such that either every element of A is greater than every element of B or every element of A is incomparable with every element of B. We prove that . Moreover, for fixed ε ∈ (0,1) and n sufficiently large, we construct a partially ordered set P with n elements such that no element of P is comparable with other elements of P and for every two disjoint subsets A and B of P each with cardinality at least , there is an element of A that is comparable with an element of B.     

On the Scope of Averaging for Frankl’s Conjecture

Let be a union-closed family of subsets of an m-element set A. Let . For b ∈ A let w(b) denote the number of sets in containing b minus the number of sets in not containing b. Frankl’s conjecture from 1979, also known as the union-closed sets conjecture, states that there exists an element b ∈ A with w(b) ≥ 0. The present paper deals with the average of the w(b), computed over all b ∈ A. is said to satisfy the averaged Frankl’s property if this average is non-negative. Although this much stronger property does not hold for all union-closed families, the first author (Czédli, J Comb Theory, Ser A, 2008) verified the averaged Frankl’s property whenever n ≥ 2 ^m  − 2 ^m/2 and m ≥ 3. The main result of this paper shows that (1) we cannot replace 2 ^m/2 with the upper integer part of 2 ^m /3, and (2) if Frankl’s conjecture is true (at least for m-element base sets) and then the averaged Frankl’s property holds (i.e., 2 ^m/2 can be replaced with the lower integer part of 2 ^m /3). The proof combines elementary facts from combinatorics and lattice theory. The paper is self-contained, and the reader is assumed to be familiar neither with lattices nor with combinatorics. This research was partially supported by the NFSR of Hungary (OTKA), grant no. T 049433, T 48809 and K 60148.     

A new characterization of Anderson’s inequality in <Emphasis Type="Italic">C</Emphasis><Subscript>1</Subscript>-classes

Let ℋ be a separable infinite dimensional complex Hilbert space, and let ℒ(H) denote the algebra of all bounded linear operators on ℋ into itself. Let A = (A ₁, A ₂,..., A _n), B = (B ₁, B ₂,..., B _n) be n-tuples of operators in ℒ(H); we define the elementary operators Δ _A,B : ℒ(H) ↦ ℒ(H) by

The First Three Levels of an Order Preserving Hamiltonian Path in the Subset Lattice

Consider the lattice whose elements are the subsets of the set of positive integers not greater than n ordered by inclusion. The Hasse diagram of this lattice is isomorphic to the n-dimensional hypercube. It is trivial that this graph is Hamiltonian. Let be a Hamiltonian path. We say it is monotone, if for every i, either (a) all subsets of S _i appear among S ₁,...,S _i − 1, or (b) only one (say S) does not, furthermore S _i + 1 = S. Trotter conjectured that if n is sufficiently large, then there are no monotone Hamiltonian paths in the n-cube. He also made a stronger conjecture that states that there is no path with the monotone property that covers all the sets of size at most three. In this paper we disprove this strong conjecture by explicitly constructing a monotone path covering all the 3-sets.     

Hypergraphs in which all disjoint pairs have distinct unions

Let ℓ be a set-system ofr-element subsets on ann-element set,r≧3. It is proved that if |ℓ|>3.5 then ℓ contains four distinct membersA, B, C, D such thatA∪B=C∪D andA∩B=C∩D=0.     

Frobenius Extensions and Tilting Complexes

Let n ≥ 1 be an integer and π a permutation of I = {1, ⋯ ,n}. For any ring R, we provide a systematic construction of rings A which contain R as a subring and enjoy the following properties: (a) 1 = ∑  _i ∈ I e _i with the e _i orthogonal idempotents; (b) e _i x = xe _i for all i ∈ I and x ∈ R; (c) e _i A e _j  ≠ 0 for all i, j ∈ I; (d) e _i A _A  ≇ e _j A _A unless i = j; (e) every e _i Ae _i is a local ring whenever R is; (f) e _i A _A  ≅ Hom _R (Ae _π(i),R _R ) and _A Ae _π(i) ≅  _A Hom _R (e _i A, _R R) for all i ∈ I; and (g) there exists a ring automorphism η ∈ Aut(A) such that η(e _i ) = e _π(i) for all i ∈ I. Furthermore, for any nonempty π-stable subset J of I, the mapping cone of the multiplication map is a tilting complex. Dedicated to Takeshi Sumioka on the occasion of his 60th birthday.