Necessary and sufficient conditions for the convergence of convolution products of non-identical distributions on finite abelian semigroups

Given a sequence of probability measures ( _n ) on a finite abelian semigroup, we present necessary and sufficient conditions which guarantee the weak convergence of the convolution products _{k,n k+1}*···* _n (k<n), asn for allk0. These conditions are verifiable in the sense that they are based entirely on the individual measures in the sequence ( _n ).     

The Spectral Theory of Amenable Actions and Invariants of Discrete Groups

Let G denote a semisimple group, a discrete subgroup, B=G/P the Poisson boundary. Regarding invariants of discrete subgroups we prove, in particular, the following:(1) For any -quasi-invariant measure on B, and any probablity measure on , the norm of the operator () on L ²(B,) is equal to (), where is the unitary representation in L ²(X,), and is the regular representation of .(2) In particular this estimate holds when is Lebesgue measure on B, a Patterson–Sullivan measure, or a -stationary measure, and implies explicit lower bounds for the displacement and Margulis number of (w.r.t. a finite generating set), the dimension of the conformal density, the -entropy of the measure, and Lyapunov exponents of .(3) In particular, when G=PSL₂() and is free, the new lower bound of the displacement is somewhat smaller than the Culler–Shalen bound (which requires an additional assumption) and is greater than the standard ball-packing bound.We also prove that ()=_G() for any amenable action of G and L ¹(G), and conversely, give a spectral criterion for amenability of an action of G under certain natural dynamical conditions. In addition, we establish a uniform lower bound for the -entropy of any measure quasi-invariant under the action of a group with property T, and use this fact to construct an interesting class of actions of such groups, related to 'virtual' maximal parabolic subgroups. Most of the results hold in fact in greater generality, and apply for instance when G is any semi-simple algebraic group, or when is any word-hyperbolic group, acting on their Poisson boundary, for example.     

On the Movement of Transitive Permutation p-Groups

Let G be a transitive permutation group on a set and m a positive integer. If | – | m for every subset of and all g G, then || 2mp/(p – 1) where p is the least odd prime dividing |G|. It was shown by Mann and Praeger [13] that, for p = 3, the 3-groups G which attain this bound have exponent p. In this paper we will show a generalization of this result for any odd primes.AMS Subject Classification (2000), 20BXX     

A property of a system of functions close to exponential functions

We consider the system {f _n=xⁿ[l+_n]} in the interval [a,b] (0 a n > 0 and _n(x) such as the condition, we obtain a bound for the coefficients of the polynomial P(x)=#x2211;c_n f _n(x) in terms of P(x)L_p[a,b]. It is found that this bound is not valid without this condition (assuming the other conditions to remain the same).Translated from Matematicheskie Zametki, Vol. 12, No. 1, pp. 29–36, July, 1972.     

Isomorphismen von rechtseiträumen

Spaces called rectangular spaces were introduced in [5] as incidence spaces (P,G) whose set of linesG is equipped with an equivalence relation and whose set of point pairs P² is equipped with a congruence relation , such that a number of compatibility conditions are satisfied. In this paper we consider isomorphisms, automorphisms, and motions on the rectangular spaces treated in [5]. By an isomorphism of two rectangular spaces (P,G, , ) and (P,G, , ) we mean a bijection of the point setP onto P which maps parallel lines onto parallel lines and congruent points onto congruent points. In the following, we consider only rectangular spaces of characteristic 2 or of dimension two. According to [5] these spaces can be embedded into euclidean spaces. In case (P,G, , ) is a finite dimensional rectangular space, then every congruence preserving bijection ofP onto P is in fact an isomorphism from (P,G, , ) onto (P,G, , ) (see (2.4)). We then concern ourselves with the extension of isomorphisms. Our most important result is the theorem which states that any isomorphism of two rectangular spaces can be uniquely extended to an isomorphism of the associated euclidean spaces (see (3.2)). As a consequence the automorphisms of a rectangular space (P,G, , ) are precisely the restrictions (onP) of the automorphisms of the associated euclidean space which fixP as a whole (see (3.3)). Finally we consider the motions of a rectangular space (P,G, , ). By a motion of(P. G,, ) we mean a bijection ofP which maps lines onto lines, preserves parallelism and satisfies the condition((x), (y)) (x,y) for allx, y P. We show that every motion of a rectangular space can be extended to a motion of the associated euclidean space (see (4.2)). Thus the motions of a rectangular space (P,G, , ) are seen to be the restrictions of the motions of the associated euclidean space which mapP into itself (see (4.3)). This yields an explicit representation of the motions of any rectangular plane (see (4.4)).

---

---

Herrn Professor Burau zum 85. Geburtstag gewidmet     

Perturbation of the poles of the scattering matrix under variation of the boundary condition

The behavior of the poles z_n(), n=1,2,... of the scattering matrix of the operatorl u=–u(x), x , (u/n)+(x)u|=0 as 0 is considered. It is proved that |z_n()–z_n|=0(^(1/2)qn), where q_n is the order of the pole of the scattering matrix for the operator ₀u=–u, u/=0.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 117, pp. 183–191, 1981.     

Approximation of the viability kernel

We study recursive inclusionsx ⁿ⁺¹ G(x ⁿ ). For instance, such systems appear for discrete finite-difference inclusionsx ⁿ⁺¹ G (x ⁿ) whereG :=1+F. The discrete viability kernel ofG , i.e., the largest discrete viability domain, can be an internal approximation of the viability kernel ofK underF. We study discrete and finite dynamical systems. In the Lipschitz case we get a generalization to differential inclusions of the Euler and Runge-Kutta methods. We prove first that the viability kernel ofK underF can be approached by a sequence of discrete viability kernels associated withx ⁿ⁺¹ (xⁿ) where (x) =x + F(x) + (ML/2) ². Secondly, we show that it can be approached by finite viability kernels associated withx _h ⁿ⁺¹ ( (x _h ⁿ⁺¹ ) +(h) X _h .     

Weight functions on the Kneser graph and the solution of an intersection problem of Sali

LetX, Y be finite sets and suppose thatF is a collection of pairs of sets (F, G),FX,GY satisfying |FF|s, |GG|t and |FF|+|GG|s+t+1 for all (F, G),F, GF. Extending a result of Sali, we determine the maximum ofF.     

Characterization,structure and analysis on abelian ℒ∞ groups

An abelian topological group is an group if and only if it is a locally -compactk-space and every compact subset in it is contained in a compactly generated locally compact subgroup. Every abelian groupG is topologically isomorphic to G ₀ where ₀ andG ₀ is an abelian group where every compact subset is contained in a compact subgroup. Intrinsic definitions of measures, convolution of measures, measure algebra,L ₁-algebra, Fourier transforms of abelian groups are given and their properties are studied.     

Lévy homeomorphic parametrization and exponential families

Summary Let P={P : } be an exponential family of probability distributions with the canonical parameter and consider the one to one mapping : P . It is shown that, under mild regularity assumptions, and ^–1 are continuous with respect to the Lévy metric in P and Euclidean metric in .     

Long paths and cycles in tough graphs

For a graphG, letp(G) andc(G) denote the length of a longest path and cycle, respectively. Let (t,n) be the minimum ofp(G), whereG ranges over allt-tough connected graphs onn vertices. Similarly, let (t,n) be the minimum ofc(G), whereG ranges over allt-tough 2-connected graphs onn vertices. It is shown that for fixedt>0 there exist constantsA, B such that (t,n)A·log(n) and (t,n)·log((t,n))B·log(n). Examples are presented showing that fort1 there exist constantsA, B such that (t,n)A·log(n) and (t,n)B· log(n). It is conjectured that (t,n) B·log(n) for some constantB. This conjecture is shown to be valid within the class of 3-connected graphs and, as conjectured in Bondy [1] forl=3, within the class of 2-connectedK _1.l-free graphs, wherel is fixed.     

Asymptotic Density and the Asymptotics of Partition Functions

Let A be a set of positive integers with gcd (A) = 1, and let p _A (n) be the partition function of A. Let c ₀ = 2/3. If A has lower asymptotic density and upper asymptotic density , then lim inf log p _A (n)/c ₀ n and lim sup log p _A (n)/c ₀ n . In particular, if A has asymptotic density > 0, then log p _A (n) c₀n. Conversely, if > 0 and log p _A (n) c ₀ n, then the set A has asymptotic density .     

Range of the posterior probability of an interval for priors with unimodality preserving contaminations

Range of the posterior probability of an interval over the -contamination class ={=(1–)₀+q:qQ} is derived. Here, ₀ is the elicited prior which is assumed unimodal, is the amount of uncertainty in ₀, andQ is the set of all probability densitiesq for which =(1–)₀+q is unimodal with the same mode as that of ₀. We show that the sup (resp. inf) of the posterior probability of an interval is attained by a prior which is equal to (1–)₀ except in one interval (resp. two disjoint intervals) where it is constant.     

An Inequality for Tail Probabilities of Martingales with Bounded Differences

Let M _n =X₁+...+X_n be a martingale with bounded differences X_m=M_m-M_m-1 such that {|X_m| _m}=1 with some nonnegative _m. Write ²= ₁ ² + ... + _n ² . We prove the inequalities {M _nx}c(1-(x/)), {M _n x} 1- c(1- (-x/)) with a constant . The result yields sharp inequalities in some models related to the measure concentration phenomena.     

Mixed graph colorings

A mixed graphG contains both undirected edges and directed arcs. Ak-coloring ofG is an assignment to its vertices of integers not exceedingk (also called colors) so that the endvertices of an edge have different colors and the tail of any arc has a smaller color than its head. The chromatic number (G) of a mixed graph is the smallestk such thatG admits ak-coloring. To the best of our knowledge it is studied here for the first time. We present bounds of (G), discuss algorithms to find this quantity for trees and general graphs, and report computational experience.     

Isotropic random walks in a tree

Summary Let T be an infinite homogeneous tree of order a+1. We study Markov chains {X _n} in T whose transition functions p(x, y)=A[d(x,y)] depend only on the shortest distance between x and y in the graph. The graph T can be represented as a symmetric space of a p-adic matrix group; we prove a series of results using essentially the spherical functions of this symmetric space. Theorem 1. d(X _n,x) n a.s., where >0 if A(0) 1, X ₀=x. Assuming {X _n} is strongly aperiodic, Theorem 2. p ₂(x, y)CRⁿ/n^3/2 for fixed x, y where R=(d) A(d)<1, and if E[d(X₁, X₀)²]<, Theorem 3. R(1–u, x, y) = (1–u)ⁿp_n(x, y)=Ca^–d[exp(–du/)+o_d(1)] as d=d(x,y) uniformly for 0u2. Using Theorem 3, we calculate the Martin boundary Dirichlet kernel of p(x, y) on T, which turns out to be independent of {itA(d)}. We also consider a stepping-stone model of a randomly-mating-and-migrating population on the nodes of T. If initially all individuals are distinct, then in generation n approximately half of the individuals of a given type are within n of a typical one and essentially all are within 2n.This work was partially supported by the National Science Foundation under grant number MCS 75-08098-A01For the academic year 1977–78: Department of Mathematics GN-50, University of Washington, Seattle, Washington 98195 USA     

The binding number of a graph and its circuits

In this paper we prove the following main results: Theorem A. If bind (G)3/2, thenG–u has a Hamiltonian circuit for every vertexu of graphG _i, unlessG belongs either to two classesH ₁ andH ₂ of graphs or to some smaller order graphs with |V(G)|17. Theorem B. If bind (G)3/2 and the maximum degree (G)>(n–1)/2, |V(G)|=n>17, thenG is pancyclic (i.e., it contains a circuit of every lengthm, 3m|V(G)|).     

The Topology of the Coloring Complex

In a recent paper, E. Steingrímsson associated to each simple graph G a simplicial complex _G, referred to as the coloring complex of G. Certain nonfaces of _G correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial _G of G, and the reduced Euler characteristic is, up to sign, equal to |_G(–1)|–1. We show that _G is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as polar coloring complexes. The h-vectors of these complexes are again affine transformations of _G, and their Euler characteristics coincide with _G(0) and –_G(1), respectively. We show for a large class of graphs—including all connected graphs—that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.Research financed by ECs IHRP Programme, within the Research Training Network Algebraic Combinatorics in Europe, grant HPRN-CT-2001-00272.     

Sur les équations fonctionnelles auxq-différences

Summary In this paper, we study the convergence of formal power series solutions of functional equations of the formP _k(x)(^[k](x))=(x), where ^[k] (x) denotes thek-th iterate of the function.We obtain results similar to the results of Malgrange and Ramis for formal solutions of differential equations: if(0) = 0, and(0) =q is a nonzero complex number with absolute value less than one then, if(x)=a(n)x ⁿ is a divergent solution, there exists a positive real numbers such that the power seriesa(n)q ^sn(n+1)2 x ⁿ has a finite and nonzero radius of convergence.

     

Remarks on ergodicity of stationary irreducible transient Markov chains

Summary Consider a stationary process {X _n(), – < n < . If the measure of the process is finite (the measure of the whole sample space finite), it is well known that ergodicity of the process {X _n(), - < n < and of each of the subprocesses {X _n(), 0 n < , {X _n(), – < n 0 are equivalent (see [3]). We shall show that this is generally not true for stationary processes with a sigma-finite measure, specifically for stationary irreducible transient Markov chains. An example of a stationary irreducible transient Markov chain {X _n(), - < n <} with {itX_n(), 0 n < < ergodic but {X _n(), < n 0 nonergodic is given. That this can be the case has already been implicitly indicated in the literature [4]. Another example of a stationary irreducible transient Markov chain with both {X _n(), 0 n < and {itX _n(),-< < n 0} ergodic but {X _n(), - < n < nonergodic is presented. In fact, it is shown that all stationary irreducible transient Markov chains {X _n(), - < n < < are nonergodic.This research was supported in part by the Office of Naval Research.John Simon Guggenheim Memorial Fellow.