Adjacent Ideals to Simple Complete Ideals in Two-Dimensional Regular Local Rings

Let R be a two-dimensional regular local ring with infinite residue field, and ? be a simple complete residually rational ideal of R of order r which determines R _h . Let 𝒯 be the set of quadratic transforms T of R _h with [T: R _h ] = 1, and 𝒮 the set of simple complete ideals of R of order r which are adjacent to ? from below. If R _h is free respectively a satellite, then there exist T* ∈ 𝒯 respectively T*, T** ∈ 𝒯 and a bijective map between the set 𝒮 and the set 𝒯?{T*} respectively 𝒯?{T*, T**}.     

The Rees Valuations of Complete Ideals in a Regular Local Ring

Let I be a complete m-primary ideal of a regular local ring (R, m) of dimension d ≥ 2. In the case of dimension two, the beautiful theory developed by Zariski implies that I factors uniquely as a product of powers of simple complete ideals and each of the simple complete factors of I has a unique Rees valuation. In the higher dimensional case, a simple complete ideal of R often has more than one Rees valuation, and a complete m-primary ideal I may have finitely many or infinitely many base points. For the ideals having finitely many base points Lipman proves a unique factorization involving special *-simple complete ideals and possibly negative exponents of the factors. Let T be an infinitely near point to R with dim R = dim T and R/m = T/m _T . We prove that the special *-simple complete ideal P _RT has a unique Rees valuation if and only if either dim R = 2 or there is no change of direction in the unique finite sequence of local quadratic transformations from R to T. We also examine conditions for a complete ideal to be projectively full.     

Topologically Complete Representations of Inverse Semigroups

A representation of an inverse semigroup by means of partial open homeomorphisms of a topological T ₀ -space is called topologically complete if the domains of these partial homeomorphisms form a base of the topology. It is shown how to construct topologically complete representations on the base of a ternary relation satisfying some elementary axioms. This result makes it possible to obtain a pseudo-elementary axiomatization for inverse semigroups that have faithful topologically complete representations in T ₁ ,T ₂ and T ₃ -spaces. A topology is introduced on any antigroup; this topology is a concomitant of the algebraic structure and every topologically complete representation is continuous with respect to this topology.     

Nearly Model Complete Theories

A theory T of a language L is 1-model complete (nearly model complete) iff for every formula ρ of L there is a formula ? (χ) of L which is a ??-formula (a Boolean combination of universal formulas) such that T ? ?x [??θ]. The main results of the paper give characterizations of nearly model complete theories and of 1-model complete theories. As a consequence we obtain that a theory T is nearly model complete iff whenever ?? is a model of T and ???₁??, then T ∪ Δ¹_?? is a complete L(A)-theory, where Δ¹_?? is the 1-diagram of ??. We also point out that our main results extend to (n + l)-model complete and nearly ra-model complete theories for all n > 0.     

Packing graphs with odd and even trees

The Gyárfás-Lehel tree-packing conjecture asserts that any sequence T₁, T₂, …, T_n^?1 of trees with 1, 2, …, n - 1 edges packs into the complete graph K_n on n vertices. The present paper examines two conjectures that jointly imply the Gyárfás-Lehel conjecture: 1. For n even, any T₁, T₃, …, T_n^?1 pack into the half-complete graph Hn on n vertices.2. For n odd, any T₂, T₄, …, T_n^?1 pack into the half-complete graph Hn on n vertices. The H_n are uniquely defined by their degree sequences: H_n and H_n+1 are complements in K_n+1. It is shown that H_n and T_n+1 pack into H_n+2 if T_n+1 is a double star, unimodal triple star, interior-3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n ≤ 9, so that the Gyárfás-Lehel conjecture holds for n ≤ 9.     

Finitary reconstruction of a measure preserving transformation

This paper considers thefinitary reconstruction of an ergodic measure preserving transformationT of a complete separable metric spaceX from a single trajectoryx, Tx, …, or more generally, from a suitable reconstruction sequence x=x ₁,x ₂, … withx _i∈X. Ann-sample reconstruction is a functionT _n: X ⁿ⁺¹ →X; the map (·;x ₁, …,x _n)is treated as an estimate ofT(·) based on then initial elements of x. Given a reference probability measureμ ₀ and constantM>1, functionsT ₁,T ₂, … are defined, and it is shown that for everyμ with 1/M≤dμ/dμ ₀≤M, everyμ-preserving transformationT, and every reconstruction sequence x forT, the estimates (·;x ₁, …,x _nconverge toT in the weak topology. For the family of interval exchange transformations of [0, 1] a simple family of estimates is described and shown to be consistent both pointwise and in the strong topology. However, it is also shown that no finitary estimation scheme is consistent in the strong topology for the family of all ergodic Lebesgue measure preserving transformations of the unit interval, even if x is assumed to be a generic trajectory ofT. Supported in part by NSF Grant DMS-9501926.     

A reversal index for tournament matrices *

Given a tournament matrix T, its reversal indexi_R (T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R (T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R (T)≤[(n?1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n?1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

Abstract Characteristic Function

The characteristic function for a contraction is a classical complete unitary invariant devised by Sz.-Nagy and Foias. Just as a contraction is related to the Szego kernel k_S(z,w) = (1 - z [`(w)])^-1{k_S(z,w) = (1 - z {\overline {w}})^{-1}} for |z|, |w| < 1, by means of (1/k _S )(T, T*) ≥ 0, we consider an arbitrary open connected domain Ω in \mathbb Cⁿ{{\mathbb {C}}^n}, a kernel k on Ω so that 1/k is a polynomial and a tuple T = (T ₁, T ₂, . . . , T _n ) of commuting bounded operators on a complex separable Hilbert space H{\mathcal H} such that (1/k)(T, T*) ≥ 0. Under some standard assumptions on k, it turns out that whether a characteristic function can be associated with T or not depends not only on T, but also on the kernel k. We give a necessary and sufficient condition. When this condition is satisfied, a functional model can be constructed. Moreover, the characteristic function then is a complete unitary invariant for a suitable class of tuples T.     

Completion of merotopic spaces and extension of uniformly continuous maps

A general Riesz merotopic space (X, ν) determines a not necessarily topological closure operator c_ν on X. The space (X, ν) is said to be complete if every cluster on (X, ν) is contained in an adherence grill on (X, c_ν). We discuss a method of obtaining a large class of completions of a given Riesz merotopic space with induced T₁ closure space. As special cases we get the simple completion, which induces a simple closure space extension, and the strict completion, which induces a strict closure space extension. We show that the category of complete separated T₁ Riesz merotopic spaces is epireflective in the category of separated T₁ Riesz merotopic spaces, the reflection of an object being the simple completion. Similarly the category of complete clan-covered quasi-regular T₁ Riesz merotopic spaces is epireflective in the category of clan-covered quasi-regular T₁ Riesz merotopic spaces, the reflection of an object being the strict completion.     

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.     

A special class of T-matrices

We introduce a special class of T-matrices, say, T ₁, T ₂, T ₃, and T ₄ satisfying

Theories of linear order

LetT be a complete theory of linear order; the language ofT may contain a finite or a countable set of unary predicates. We prove the following results. (i) The number of nonisomorphic countable models ofT is either finite or 2^ω. (ii) If the language ofT is finite then the number of nonisomorphic countable models ofT is either 1 or 2^ω. (iii) IfS ₁(T) is countable then so isS _n(T) for everyn. (iv) In caseS ₁(T) is countable we find a relation between the Cantor Bendixon rank ofS ₁(T) and the Cantor Bendixon rank ofS _n(T). (v) We define a class of modelsL, and show thatS ₁(T) is finite iff the models ofT belong toL. We conclude that ifS ₁(T) is finite thenT is finitely axiomatizable. (vi) We prove some theorems concerning the existence and the structure of saturated models. Most of the results in this paper appeared in the author’s Master of Science thesis which was prepared at the Hebrew University under the supervision of Professor H. Gaifman.     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

Decompositions of graphs into trees

Let θ be a family of graphs. By a θ-decomposition of a graph G we mean a partition λ of the edge set of G such that every F ? π spans in G a subgraph isomorphic to a graph in θ. In this paper we state the following conjecture: If T₁ and T₂ are two trees having relatively prime sizes then there exists c = c(T₁ T₂) such that every graph G satisfying the condition δ(G) ? c has a {T₁, T₂}-decom-position. We prove this conjecture for some special pairs of trees. In particular, we prove it in the following cases: (i) T₁ and T₂ are stars having relatively prime sizes; (ii) T₁ and T₂ are paths having relatively prime sizes; and. (iii) T₁ = T₂ - {v}, where v is a terminal vertex in T ₂.     

On nonsingularity of combinations of two group invertible matrices and two tripotent matrices

Let T ₁ and T ₂ be two n?×?n tripotent matrices and c ₁, c ₂ two nonzero complex numbers. We mainly study the nonsingularity of combinations T?=?c ₁ T ₁?+?c ₂ T ₂???c ₃ T ₁ T ₂ of two tripotent matrices T ₁ and T ₂, and give some formulae for the inverse of c ₁ T ₁?+?c ₂ T ₂???c ₃ T ₁ T ₂ under some conditions. Some of these results are given in terms of group invertible matrices.     

On aschbacher’s localC(G; T) theorem

Aschbacher’s localC(G; T) theorem asserts that ifG is a finite group withF*(G)=O ₂(G), andTεSyl₂(G), thenG=C(G; T)K(G), whereC(G; T)=〈N _G (T ₀)|1≠T ₀ charT〉 andK(G) is the product of all near components ofG of typeL ₂(2 ⁿ ) orA ₂ ⁿ ₊₁. Near components are also known asχ-blocks or Aschbacher blocks. In this paper we give a proof of Aschbacher’s theorem in the case thatG is aK-group, i.e., in the case that every simple section ofG is isomorphic to one of the known simple groups. Our proof relies on a result of Meierfrankenfeld and Stroth [MS] on quadratic four-groups and on the Baumann-Glauberman-Niles theorem, for which Stellmacher [St2] has given an amalgam-theoretic proof. Apart from those results, our proof is essentially self-contained. For John Thompson Supported in part by NSF grant #DMS 89-03124, by DIMACS, an NSF Science and Technology Center, funded under contract STC-88-09648, and by NSA grant #MDA-904-91-H-0043. Prof. Gorenstein died on August 26, 1992.     

A simple map with no prime factors

An ergodic measure-preserving transformationT of a probability space is said to be simple (of order 2) if every ergodic joining λ ofT with itself is eitherμ×μ or an off-diagonal measureμ _S , i.e.,μ _S (A×B)=μ(A∩S ^;−n ;B) for some invertible, measure preservingS commuting withT. Veech proved that ifT is simple thenT is a group extension of any of its non-trivial factors. Here we construct an example of a weakly mixing simpleT which has no prime factors. This is achieved by constructing an action of the countable Abelian group ℤ⊕G, whereG=⊕ _i=1 ^∞ ℤ₂, such that the ℤ-subaction is simple and has centralizer coinciding with the full ℤ⊕G-action.     

An Asymptotic Ratio in the Complete Binary Tree

Let T _n be the complete binary tree of height n considered as the Hasse-diagram of a poset with its root 1 _n as the maximum element. For a rooted tree T, define two functions counting the embeddings of T into T _n as follows A(n;T)=|{S T _n  : 1 _n ∈S, S≅T}|, and B(n;T)=|{S T _n :1 _n ∉S, S≅T}|. In this paper we investigate the asymptotic behavior of the ratio A(n;T)/B(n;T), and we show that lim  _n→∞[A(n;T)/B(n;T)]=2^ℓ;−1−1, for any tree T with ℓ leaves. This revised version was published online in June 2006 with corrections to the Cover Date.     

Ordering Trees with Nearly Perfect Matchings by Algebraic Connectivity

Let T2k＋1 be the set of trees on 2k＋1 vertices with nearly perfect matchings and α（T） be the algebraic connectivity of a tree T. The authors determine the largest twelve values of the algebraic connectivity of the trees in T2k＋1. Specifically, 10 trees T2,T3,... ,T11 and two classes of trees T（1） and T（12） in T2k＋1 are introduced. It is shown in this paper that for each tree T^′1,T^″1∈T（1）and T^′12,T^″12∈T（12） and each i,j with 2≤i〈j≤11,α（T^′1）=α（T^″1）〉α（Tj）〉α（T^′12）=α（T^″12）.It is also shown that for each tree T with T∈T2k＋1／（T（1）∪{T2,T3,…,T11}∪T（12））,α（T^′12）〉α（T）.