Graphs of actions on R-trees

LetG be a finitely generated group acting on anR-treeT. First assume that the action is free, and minimal (there is no proper invariant subtree), or more generally that it satisfies a certain finiteness condition. Then it may be described as agraph of transitive actions: the action may be recovered from a finite graph, together with additional data; in particular, every vertexv carries an action (G _v, T_v) whose orbits are dense. For the action (G, T), it follows for instance that the closure of any orbit is a discrete union of closed subtrees: it cannot meet a segment in a Cantor set. Now let ℓ be the length function for an arbitrary action ofG. For ɛ>0 small enough, the subgroupG(ɛ)⊂G generated by elementsg withg is independent of ɛ, andG/G(ɛ) is free. Several interpretations are given for the rank ofG/G(ɛ).     

Alcune classi di gruppi abeliani misti di rango 1

Riassunto Si definisce una classe diZ _p-moduliQ _β, simili aip-gruppiP _β studiati daE. A. Walker, che danno una caratterizzazione delle sequenze esatte bilanciate diZ _p-moduli e degliZ _p-moduli bilanciati proiettivi. Si definiscono poi dei gruppi misti di rango 1,R _h, che sono un'estensione al caso globale deiQ _β e che generalizzano i gruppi razionali. Per gliR _h vale un teorema analogo a quello di classificazione coi tipi di Baer ed essi danno inoltre una caratterizzazione delle sequenze esatte bilanciate di gruppi e dei gruppi bilanciati proiettivi.

---

Summary We define a class ofZ _p-modulesQ _β, like thep-groupsP _β studied byE. A. Walker, that give a characterization of balanced exact sequence ofZ _p-modules and balanced projectiveZ _p-modules. We introduce also some mixed groups of rank one,R _h, which are an extension to the global case ofQ _β and which generalize rational groups. Moreover, forR _h, there is a theorem, which is analogous to Baer's theorem of classification by types. GroupsR _h give too a characterization of balanced exact sequence of groups and of balanced projective groups.

     

Asymptotic behaviour of trajectories of unipotent flows on homogeneous spaces

We show that ifG is a semisimple algebraic group defined overQ and Γ is an arithmetic lattice inG:=G _R with respect to theQ-structure, then there exists a compact subsetC ofG/Γ such that, for any unipotent one-parameter subgroup {u _t} ofG and anyg∈G, the time spent inC by the {u _t}-trajectory ofgΓ, during the time interval [0,T], is asymptotic toT, unless {g ⁻¹u_tg} is contained in aQ-parabolic subgroup ofG. Some quantitative versions of this are also proved. The results strengthen similar assertions forSL(n,Z),n≥2, proved earlier in [5] and also enable verification of a technical condition introduced in [7] for lattices inSL(3,R), which was used in our proof of Raghunathan’s conjecture for a class of unipotent flows, in [8].     

Tensor products, multiplications and Weyl’s theorem

Tensor productsZ=T ₁⊗T ₂ and multiplicationsZ=L _{T 1} R _{T 2} do not inherit Weyl’s theorem from Weyl’s theorem forT ₁ andT ₂. Also, Weyl’s theorem does not transfer fromZ toZ*. We prove that ifT _i,i=1, 2, has SVEP (=the single-valued extension property) at points in the complement of the Weyl spectrumσ _w(T_i) ofT _i, and if the operatorsT _i are Kato type at the isolated points ofσ(T_i), thenZ andZ* satisfy Weyl’s theorem.     

Existence of T*(3, 4,v)‐codes

A word of length k over an alphabet Q of size v is a vector of length k with coordinates taken from Q. Let Q^*₄ be the set of all words of length 4 over Q. A T^*(3, 4, v)‐code over Q is a subset C^*? Q^*₄ such that every word of length 3 over Q occurs as a subword in exactly one word of C^*. Levenshtein has proved that a T^*(3, 4, vv)‐code exists for all even v. In this paper, the notion of a generalized candelabra t‐system is introduced and used to show that a T^*(3, 4, v)‐code exists for all odd v. Combining this with Levenshtein's result, the existence problem for a T^*(3,4, v)‐code is solved completely. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 42–53, 2005.     

Central localization and Gelfand-Kirillov dimension

LetR be a factor ring of the enveloping algebra of a finite dimensional Lie algebra over a fieldk. If the centre ofR, Z, consists of non-zero divisors inR, the ringR _z obtained by localizing at the non-zero elements ofZ becomes a finitely generated algebra over the fieldK which arises as the field of fractions ofZ. The Gelfand-Kirillov dimension of anR-moduleM is denotedd(M). In this paper it is shown that ifR _Z ⊗ _R M ≠ 0 thend(M) ≧d(R _Z ⊗ _R M) + tr. deg _k Z, whered (R _z ⊗M) is the Gelfand-Kirillov dimension ofR _z ⊗M) viewed as anR _z -module andR _z is viewed as a finitely generatedK-algebra (not as ak-algebra). The result is primarily of a technical nature.     

Remarques sur les systemes dynamiques donnes avec plusieurs facteurs

Two Bernoulli shifts are given, (X, T) and (X′, T′), with independent generatorsR=P ∨Q andR′=P′ ∨Q′ respectively. (R andR′ are finite). One can chooseR such that if (X′, T′) can be made a factor of (X, T) in such a way that (P′) _T′ and (Q′) _T′ are full entropy factors of (P) _T and (Q) _T respectively thend (P ∨Q)=d(P′ ∨Q′). In addition it is proved that if (X, T) is a Bernoulli shift and ifS is a measure preserving transformation ofX that has the same factor algebras asT thenS=T orS=T ⁻¹. A tool for this proof, which may be of independent interest is a relative version for very weak Bernoullicity.

---

---

Equipe de Recherche n^o 1 “Processus stochastique et applications” dépendant de la Section n^o 1 “Mathématiques, Informatique” associée au C.N.R.S.     

Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

On the finiteness of a field-theoretic invariant for commutative rings

If T is a (commutative unital) ring extension of a ring R, then Λ(T /R) is defined to be the supremum of the lengths of chains of intermediate fields between R _P /P R _P and T _Q /QT _Q , where Q varies over Spec(T) and P:= Q ∩ R. The invariant σ(R):= sup Λ(T/R), where T varies over all the overrings of R. It is proved that if Λ(S/R)< ∞ for all rings S between R and T, then (R, T) is an INC-pair; and that if (R, T) is an INC-pair such that T is a finite-type R-algebra, then Λ(T/R)< ∞. Consequently, if R is a domain with σ(R) < ∞, then the integral closure of R is a Prüfer domain; and if R is a Noetherian G-domain, then σ(R) < ∞, with examples showing that σ(R) can be any given non-negative integer. Other examples include that of a onedimensional Noetherian locally pseudo-valuation domain R with σ(R)=∞.     

A domain decomposition method for conformal mapping onto a rectangle

Letg be the function which maps conformally a rectangleR onto a simply connected domainG so that the four vertices ofR are mapped respectively onto four specified pointsz ₁,z ₂,z ₃,z ₄ onG. This paper is concerned with the study of a domain decomposition method for computing approximations tog and to an associated domain functional in cases where: (i)G is bounded by two parallel straight lines and two Jordan arcs. (ii) The four pointsz ₁,z ₂,z ₃,Z ₄, are the corners where the two straight lines meet the two arcs.Communicated by Dieter Gaier.     

Q-admissibility of certain nonsolvable groups

A finite groupG is calledQ-admissible if there exists a finite dimensional central division algebra overQ, containing a maximal subfield which is a Galois extension ofQ with Galois group isomorphic toG. It is proved thatS ₅ ⁻ , one of the two nontrivial central extensions ofS ₅ byZ/2Z, isQ-admissible. As a consequence of that result and previous results of Sonn and Stern, every finite Sylow-metacyclic group, havingA ₅ as a composition factor, isQ-admissible. This paper is part of a M.Sc. thesis written at the Technion — Israel Institute of Technology, under the supervision of Professor J. Sonn, whom the author wishes to thank for his valuable guidance.     

Universal entire functions with gap power series

Let be the family of all compact sets in which have connected complement. For K ε M we denote by A(K) the set of all functions which are continuous on K and holomorphic in its interior.Suppose that {z_n} is any unbounded sequence of complex numbers and let Q be a given sub-sequence of ₀.If Q has density Δ(Q) = 1 then there exists a universal entire function with lacunary power series

1. (1) (z) = ε^∞_{v = 0 v}Z^v, _v = 0 for v Q, which has for all K ε M the following properties simultaneously

2. (2) the sequence {(Z + Z_n)} is dense in A(K)

3. (3) the sequence { (ZZ_n)} is dense in A(K) if 0 K.

Also a converse result is proved: If is an entire function of the form (1) which satisfies (3), then Q must have maximal density Δ_max(Q) = 1.     

Resolvable and near-resolvable decompositions ofDK v into oriented 4-cycles

Summary A resolvableX-decomposition ofDK _v (the complete symmetric digraph onv vertices) is a partition of the arcs ofDK _v into isomorphic factors where each factor is a vertex-disjoint union of copies ofX and spans all vertices ofDK _v . There are four orientations ofC ₄ (the 4-cycle), only one of which has been considered: Bennett and Zhang, Aequationes Math.40 (1990), 248–260. We give necessary and sufficient conditions onv for resolvableX-decomposition ofDK _v , whereX is any one of the other three orientations ofC ₄. A near-resolvableX-decomposition ofDK _v is as above except that each factor spans all but one vertex ofDK _v . Again, one orientation ofC ₄ has been dealt with by Bennett and Zhang, and we provide necessary and sufficient conditions onv for the remaining three cases. The construction techniques used are both direct (for small values ofv) and recursive.The author thanks Simon Fraser University for its support during her graduate studies when the research for this paper was undertaken.The author acknowledges the Natural Sciences and Engineering Research Council of Canada for financial support under grant A-7829.     

P.I.G-rings and the contractability of primes

LetR=F{x ₁, …, x_k} be a prime affine p.i. ring andS a multiplicative closed set in the center ofR, Z(R). The structure ofG-rings of the formR _s is completely determined. In particular it is proved thatZ(R _s)—the normalization ofZ(R _s) —is a prüfer ring, 1≦k.d(R _s)≦p.i.d(R _s) and the inequalities can be strict. We also obtain a related result concerning the contractability ofq, a prime ideal ofZ(R) fromR. More precisely, letQ be a prime ideal ofR maximal to satisfyQϒZ(R)=q. Then k.dZ(R)/q=k.dR/Q, h(q)=h(Q) andh(q)+k.dZ(R)/q=k.dz(R). The last condition is a necessary butnot sufficient condition for contractability ofq fromR.     

A new area-maximization proof for the circle

Conclusion  Finally, we compare the trianglesT _i with the isosceles triangles which would be obtained by slicing the circle by the same procedure. Since they all have the same short base length and the same angle opposite the base, the isosceles triangles composing the circle have more area than the trianglesT _i. Because the latter triangles cover all ofR ₁ (perhaps even with overlap and/or extension beyondR ₁), we see that the area of the quarter-circle is greater than that ofR ₁, and thus the circle's entire area is greater than that of our original regionR.     

Triangular finite elements of HCT type and classC ρ

Let τ be some triangulation of a planar polygonal domain Ω. Given a smooth functionu, we construct piecewise polynomial functionsv∈C ^ρ(Ω) of degreen=3 ρ for ρ odd, andn=3ρ+1 for ρ even on a subtriangulation τ₃ of τ. The latter is obtained by subdividing eachT∈ρ into three triangles, andv/T is a composite triangular finite element, generalizing the classicalC ¹ cubic Hsieh-Clough-Tocher (HCT) triangular scheme. The functionv interpolates the derivatives ofu up to order ρ at the vertices of τ. Polynomial degrees obtained in this way are minimal in the family of interpolation schemes based on finite elements of this type.     

Separating subgraphs in k-trees: Cables and caterpillars

The class of k-trees has the property that the minimal sets of vertices separating two nonadjacent vertices u and v of a k-tree Q induce k-complete subgraphs. We show that the union T of these subgraphs belongs to a subclass of (k ? 1)-trees which generalizes caterpillars. The maximum order of a monochromatic set of vertices in the optimal coloring of this (k ? 1)-tree T determines the length of the minimal collection of k vertex-disjoint paths between the two vertices of Q, the u, v-cable, which is spanned on all vertices of T.     

On Cycle Sequences

. For each vertex v in a graph G, the maximum length of a cycle which passes through v is called the cycle number of v, denoted by c(v). A sequence a ₁,a ₂,…,a _n of nonnegative integers is called a cycle sequence of a graph G if the vertices of G can be labeled as v ₁,v ₂,…,v _n such that a _i =c(v _i ) for 1≤i≤n. We give some sufficient and necessary conditions for a sequence to be a cycle sequence. We can thereby derive a polynomial time procedure for recognizing cycle sequences. Received: July 14, 1997 Final version received: June 15, 1998     

Hamiltonian paths and cycles in hypertournaments

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v₁a₁v₂v₃···v_t−1v_t of distinct vertices v₁, v₂,⋖, v_t and distinct arcs a₁, ⋖, a_t−1 such that v_i precedes v_t−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as v_i's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997     

A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection

We provide a new technique for deriving optimal-sized polygonal schema for triangulated compact 2-manifolds without boundary inO(n) time, wheren is the size of the given triangulationT. We first derive a polygonal schemaP embedded inT using Seifert-Van Kampen's theorem. A reduced polygonal schemaQ of optimal size is computed fromP, where a surjective map from the vertices ofP is retained to the vertices ofQ. This helps detecting null-homotopic (contractible to a point) cycles. Given a cycle of lengthk, we determine if it is null-homotopic inO(n+k logg) time and in θ(n+k) space, whereg is the genus of the given 2-manifold. The actual contraction for a null-homotopic cycle can be computed in θ(nk) time and space. This is a considerable improvement over the previous best-known algorithm for this problem.