Random mappings of scaled graphs

Given a connected finite graph Γ with a fixed base point O and some graph G with a based point we study random 1-Lipschitz maps of a scaled Γ into G. We are mostly interested in the case where G is a Cayley graph of some finitely generated group, where the construction does not depend on the choice of base points. A particular case of Γ being a graph on two vertices and one edge corresponds to the random walk on G, and the case where Γ is a graph on two vertices and two edges joining them corresponds to Brownian bridge in G. We show, that unlike in the case ${G=\mathbb Z^d}$ , the asymptotic behavior of a random scaled mapping of Γ into G may differ significantly from the asymptotic behavior of random walks or random loops in G. In particular, we show that this occurs when G is a free non-Abelian group. Also we consider the case when G is a wreath product of ${\mathbb Z}$ with a finite group. To treat this case we prove new estimates for transition probabilities in such wreath products. For any group G generated by a finite set S we define a functor E from category of finite connected graphs to the category of equivalence relations on such graphs. Given a finite connected graph Γ, the value E _G,S (Γ) can be viewed as an asymptotic invariant of G.     

Stationary measures for randomly chosen maps

A Markov process on a compact metric space,X is given by random transformations.S is a finite set of continuous transformations ofX to itself. A random evolution onX is defined by lettingx inX evolve toT(x) forT inS with probability that depends onx andT but is independent of any other past measurable events. This type of model is often called a place dependent iterated function system. The transformations are assumed to have either monotone or contractive properties. Theorems are given to describe the number and types of ergodic invariant measures. Special emphasis is given to learning models and self-reinforcing random walks.Supported in part by AFOSR Grant No. 91-0215, the Alexander von Humboldt Foundation and SFB 170, University of Göttingen.     

Commutative Schur Rings of Maximal Dimension

A commutative Schur ring over a finite group G has dimension at most s _G  = d ₁ + … +d _r , where the d _i are the degrees of the irreducible characters of G. We find families of groups that have S-rings that realize this bound, including the groups SL(2, 2 ⁿ ), metacyclic groups, extraspecial groups, and groups all of whose character degrees are 1 or a fixed prime. We also give families of groups that do not realize this bound. We show that the class of groups that have S-rings that realize this bound is invariant under taking quotients. We also show how such S-rings determine a random walk on the group and how the generating function for such a random walk can be calculated using the group determinant.     

Expanders obtained from affine transformations

A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ _G (X)|≧(1+δ(1−|X|/n)) |X|, whereΓ _G (X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained from one-dimensional ones.     

Über Bewertungen,welche unter einer reduktiven Gruppe invariant sind

Summary LetG be a reductive group defined over an algebraically closed fieldk and letX be aG-variety. In this paper we studyG-invariant valuationsv of the fieldK of rational functions onX. These objects are fundamental for the theory of equivariant completions ofX. LetB be a Borel subgroup andU the unipotent radical ofB. It is proved thatv is uniquely determined by its restriction toK ^U . Then we study the set of invariant valuations having some fixed restrictionv ₀, toK ^B . Ifv ₀ is geometric (i.e., induced by a prime divisor) then this set is a polyhedron in some vector space. In characteristic zero we prove that this polyhedron is a simplicial cone and in fact the fundamental domain of finite reflection groupW ^X . Thus, the classification of invariant valuations is almost reduced to the classification of valuations ofK ^B .

Unterstützt durch den Schweizerischen Nationalfonds zur Förderung der wissenschaftlichen Forschung.     

Invariant measures and disintegrations with applications to Palm and related kernels

Consider a locally compact group G acting measurably on some spaces S and T. We prove a general representation of G-invariant measures on S and the existence of invariant disintegrations of jointly invariant measures on S × T. The results are applied to Palm and related kernels associated with a stationary random pair (ξ,η), where ξ is a random measure on S and η is a random element in T. An erratum to this article can be found at     

On calculation of moments of ladder heights

Let X,X ₁,X ₂, … be independent identically distributed random variables, F(x) = P{X < x}, S ₀ = 0, and S _n =Σ _i=1 ⁿ X _i . We consider the random variables, ladder heights Z ₊ and Z ₋ that are respectively the first positive sum and the first negative sum in the random walk {S _n }, n = 0, 1, 2, …. We calculate the first three (four in the case EX = 0) moments of random variables Z ₊ and Z ₋ in the qualitatively different cases EX > 0, EX < 0, and EX = 0. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 46, No. 2, pp. 159–179, April–June, 2006.     

On amenable groups of automorphisms on Von Neumann algebras

LetG ⊂ Aut ℳ be a countable group, ℳ a Von Neumann algebra. LetE be a set of pure states on ℳ such thatG*E ⊂E, S ^G be the set ofG invariant states on ℳ andS _E ^G =S ^G ∩w* cl coE. We investigate in this paper some geometric properties for the setS _E ^G which turn out to be equivalent to amenability for the groupG. For example, we show thatS _E ^G ⊂ ℳ_* (S _E ^G has the WRNP) implies that ℳ contains minimal projections (ê containsfinite G invariant orbits) hold true, for all ℳ iffG is amenable. Furthermore we show that ifG is amenable thenS ^G ∩M _* ^⊥ contains a big set, thus improving results obtained by Ching Chou in [2]. These results imply that no action of an amenable countable groupG on an arbitraryW* algebra ℳ iss — strongly ergodic. Moreover cardS ^G ∩M _* ^⊥ ≧2 ^c (see M. Choda [4], K. Schmidt [21] and compare with A. Connes and B. Weiss [5]). The author gratefully acknowledges the support of an Izaak Walton Killam Memorial Senior Fellowship.     

G‐invariant persistent homology

Classical persistent homology is a powerful mathematical tool for shape comparison. Unfortunately, it is not tailored to study the action of transformation groups that are different from the group Homeo(X) of all self‐homeomorphisms of a topological space X. This fact restricts its use in applications. In order to obtain better lower bounds for the natural pseudo‐distance d_G associated with a group G ? Homeo(X), we need to adapt persistent homology and consider G‐invariant persistent homology. Roughly speaking, the main idea consists in defining persistent homology by means of a set of chains that is invariant under the action of G. In this paper, we formalize this idea and prove the stability of the persistent Betti number functions in G‐invariant persistent homology with respect to the natural pseudo‐distance d_G. We also show how G‐invariant persistent homology could be used in applications concerning shape comparison, when the invariance group is a proper subgroup of the group of all self‐homeomorphisms of a topological space. In this paper, we will assume that the space X is triangulable, in order to guarantee that the persistent Betti number functions are finite without using any tameness assumption. Copyright © 2014 John Wiley & Sons, Ltd.     

Direct products of cyclic semigroups an unions of groups

We consider direct productsS×U_eεE G _e=S ₁×…×S _n × U_eεE G _e of non-group finite cyclic semigroupsS _i, 1 ≤i ≤n, and finite unions of finite groups U_eεE G _e We prove that if such a semigroup is isomorphic to another of the same form, sayT×U _fεF H _f =T ₁×…×U _fεF H _f , whereT _j are non-group cyclic semigroups, 1≤j≤l, and U _fεF H _f is a union of groups, thenS is isomorphic toT and U_eεE G _e is isomorphic to U_fεF H _f . We then determine when a finite semigroup has such a decomposition and show how the direct factors can be found.     

First Hitting Times for Some Random Walks on Finite Groups

We consider a random walk on a finite group G based on a generating set that is a union of conjugacy classes. Let the nonnegative integer valued random variable T denote the first time the walk arrives at the identity element of G, if the starting point of the walk is uniformly distributed on G. Under suitable hypotheses, we show that the distribution function F of T is almost exponential, and we give an error term.     

D n -normal semigroups of transformations

Given a subgroup G of the symmetric group S _n on n letters, a semigroup S of transformations of X _n is G-normal if G _S =G, where G _S consists of all permutations h∈S _n such that h ⁻¹ fh∈S for all f∈S. A semigroup S is G-normax if it is a maximal semigroup in the set of all G-normal semigroups. In 1996, I. Levi showed that the alternating group A _n can not serve as the group G _S for any semigroup of total transformations of X _n . In 2000 and 2001, I. Levi, D.B. McAlister and R.B. McFadden described all A _n -normal semigroups of partial transformations of X _n . Also, in 1994, I. Levi and R.B. McFadden described all S _n -normal semigroups. In this paper, we show that the dihedral group D _n may serve as the group G _S for semigroups of transformations of X _n . We characterize a large class of D _n -normax semigroups and describe certain D _n -normal semigroups.     

Equivalence systems with finitely many relations

We consider a setX with a finite totally ordered setE of equivalence relations onX. We describe the automorphism group of this system, that is, the group of all those permutations ofX that leave each relation inE invariant.     

Bands of invariantly extensible measures

Given two σ-algebrasU ⊂A, invariant under a fixed semigroupG of transformations, the following subsetC of the lattice coneM (U) _G ofG-invariant finite measures onU is shown to be (the positive part of) a band inM (U) _G : AG-invariant measure μ belongs toC iff the setexM Bμ) _G of extremalG-invariant extensions of μ toB is non-empty and eachG-invariant extensionv of μ admits a barycentric decompositionv=→v′ρ(dv′) with some representing probability ρ onexM U μ) _G .—Any band of extensible measures allows to study the corresponding extension problem locally.     

Problem of formation of quotients and base change

Let X/S be a semistable curve equipped with the action of a finite group G and let H be a normal subgroup of G. The main result of this paper is the following. If the action of G is free on an open dense set on any geometric fiber, then for any base change TS, (X/G)×_ST is isomorphic to (X×_ST)/G. As an application, this allows us to define induction and restriction morphisms between the G-equivariant deformation functor of X and the G/H-equivariant (resp. H-equivariant) deformation functor of X/H (resp. X).

---

Résumé. Soit X/S une courbe semi-stable munie de laction dun groupe fini G. Soit H un sous-groupe normal de G. Nous proposons une nouvelle condition sous laquelle (X/G)×_ST est isomorphe à (X×_ST)/G quel que soit le changement de base TS : il suffit que sur toutes les fibres géométriques, laction de G soit libre sur un ouvert dense. Comme application de ce résultat nous définissons des morphismes dinduction et de restriction entre le foncteur de déformations G-équivariantes de X et le foncteur de déformations G/H-équivariantes (resp. H-équivariantes) de X/H (resp. X).

     

Equivariant Reduction to Torus of a Principal Bundle

Let M be an irreducible projective variety, over an algebraically closed field k of characteristic zero, equipped with an action of a connected algebraic group S over k. Let E _G be a principal G-bundle over M equipped with a lift of the action of S on M, where G is a connected reductive linear algebraic group. Assume that E _G admits a reduction of structure group to a maximal torus TG. We give a necessary and sufficient condition for the existence of a T-reduction of E _G which is left invariant by the action of S on E _G .     

Boundaries of random walks on graphs and groups with infinitely many ends

Consider an irreducible random walk {Z _n} on a locally finite graphG with infinitely many ends, and assume that its transition probabilities are invariant under a closed group Γ of automorphisms ofG which acts transitively on the vertex set. We study the limiting behaviour of {Z _n} on the spaceΩ of ends ofG. With the exception of a degenerate case,Ω always constitutes a boundary of Γ in the sense of Furstenberg, and {Z _n} converges a.s. to a random end. In this case, the Dirichlet problem for harmonic functions is solvable with respect toΩ. The degenerate case may arise when Γ is amenable; it then fixes a unique end, and it may happen that {Z _n} converges to this end. If {Z _n} is symmetric and has finite range, this may be excluded. A decomposition theorem forΩ, which may also be of some purely graph-theoretical interest, is derived and applied to show thatΩ can be identified with the Poisson boundary, if the random walk has finite range. Under this assumption, the ends with finite diameter constitute a dense subset in the minimal Martin boundary. These results are then applied to random walks on discrete groups with infinitely many ends.     

Convergence of representation averages and of convolution powers

LetS be a locally compact (σ-compact) group or semi-group, and letT(t) be a continuous representation ofS by contractions in a Banach spaceX. For a regular probability μ onS, we study the convergence of the powers of the μ-averageUx=∫T(t)xdμ(t). Our main results for random walks on a groupG are:

1. if μ is adapted and strictly aperiodic, and generates a recurrent random walk, thenU ⁿ (U-I) converges strongly to 0. In particular, the random walk is completely mixing.
2. If μ×μ is ergodic onG×G, then for every unitary representationT(.) in a Hilbert space,U ⁿ converges strongly to the orthogonal projection on the space of common fixed points. These results are proved for semigroup representations, along with some other results (previously known only for groups) which do not assume ergodicity.
3. If μ is spread-out with supportS, then $\left\| {\mu ^{n + K} - \mu ^n } \right\| \to 0$ if and only if e $ \in \overline { \cup _{j = 0}^\infty S^{ - j} S^{j + K} } .$ .

     

Harmonic renewal measures and bivariate domains of attraction in fluctuation theory

Summary Each probability measure C on a first orthant is associated with a harmonic renewal measure G. Specifically we consider (N, S _N ) the ladder (time, place) of a random walk S _n. Using bivariate G we show that when S ₁ is in a domain of attraction so is (N, S _N). This unifies and generalizes results of Sinai, Rogosin.     

On the recurrence of edge-reinforced random walk on ℤ×G

Let G be a finite tree. It is shown that edge-reinforced random walk on ℤ×G with large initial weights is recurrent. This includes recurrence on multi-level ladders of arbitrary width. For edge-reinforced random walk on {0,1, . . . ,n}×G, it is proved that asymptotically, with high probability, the normalized edge local times decay exponentially in the distance from the starting level. The estimates are uniform in n. They are used in the recurrence proof.