Search

We study asymptotic invariants of metric spaces, defined in terms of the travelling salesman problem, and our goal is to classify groups and spaces depending on how well they can be ordered in this context. We characterize virtually free groups as those admitting an order which has some efficiency on 4-point subsets. We show that all δ -hyperbolic spaces can be ordered extremely efficiently, for the question when the number of points of a subset tends to ∞ . [ABSTRACT FROM AUTHOR]

For any countable group with infinite conjugacy classes we construct a family of forests on the group. For each of them there is a random walk on the group with the property that its sample paths almost surely converge to the geometric boundary of the forest in a way that resembles the simple random walks on trees. It allows us to identify the Poisson boundary of the random walk with the boundary of the forest and to show that the group action on the Poisson boundary is free (which, in particular, implies non-triviality of the Poisson boundary). As a consequence we obtain that any countable group carries a random walk such that the stabilizer of almost every point of the Poisson boundary coincides with the hyper-FC-centre of the group, and, more generally, we characterize all normal subgroups which can serve as the pointwise stabilizer of the Poisson boundary of a random walk on a given countable group. Our work is a development of a recent result of Frisch–Hartman–Tamuz–Vahidi Ferdowsi who proved that any group which is not hyper-FC-central admits a measure with a non-trivial Poisson boundary. [ABSTRACT FROM AUTHOR]

We prove the law of large numbers for the drift of random walks on the two-dimensional lamplighter group, under the assumption that the random walk has finite (2 + ϵ) -moment. This result is in contrast with classical examples of abelian groups, where the displacement after n steps, normalised by its mean, does not concentrate, and the limiting distribution of the normalised n-step displacement admits a density whose support is [ 0 , ∞) . We study further examples of groups, some with random walks satisfying LLN for drift and other examples where such concentration phenomenon does not hold, and study relation of this property with asymptotic geometry of groups. [ABSTRACT FROM AUTHOR]

On torsion Grigorchuk groups we construct random walks of finite entropy and power-law tail decay with non-trivial Poisson boundary. Such random walks provide near optimal volume lower estimates for these groups. In particular, for the first Grigorchuk group G we show that its growth v G , S (n) satisfies lim n → ∞ log log v G , S (n) / log n = α 0 , where α 0 = log 2 log λ 0 ≈ 0.7674 , λ 0 is the positive root of the polynomial X 3 - X 2 - 2 X - 4 . [ABSTRACT FROM AUTHOR]

We show that there is no iterated identity satisfied by all finite groups. For w being a non-trivial word of length l, we show that there exists a finite group G of cardinality at most exp(lC) which does not satisfy the iterated identity w. We also prove a more general statement concerning iterations of an endomorphism of a free group. The proof uses the approach of Borisov and Sapir, who used dynamics of polynomial mappings for the proof of non-residual finiteness of some groups. [ABSTRACT FROM AUTHOR]

We study the neighborhoods of a typical point Z n visited at n-th step of a random walk, determined by the condition that the transition probabilities stay close to μ ∗ n (Z n) . If such neighborhood contains a ball of radius C n , we say that the random walk has almost invariant transition probabilities. We prove that simple random walks on wreath products of Z with finite groups have almost invariant distributions. A weaker version of almost invariance implies a necessary condition of Ozawa's criterion for the property H FD . We define and study the radius of almost invariance. We estimate this radius for random walks on iterated wreath products and show this radius can be asymptotically strictly smaller than n / L(n), where L(n) denotes the drift function of the random walk. We show that the radius of individual almost invariance of a simple random walk on the wreath product of Z 2 with a finite group is asymptotically strictly larger than n / L(n). Finally, we show the existence of groups such that the radius of almost invariance is smaller than a given function, but remains unbounded. We also discuss possible limiting distribution of ratios of transition probabilities on non almost invariant scales. [ABSTRACT FROM AUTHOR]

We study the Poisson-Furstenberg boundary of random walks on permutational wreath products. We give a sufficient condition for a group to admit a symmetric measure of finite first moment with non-trivial boundary, and show that this criterion is useful to establish exponential word growth of groups. We construct groups of exponential growth such that all finitely supported (not necessarily symmetric, possibly degenerate) random walks on these groups have trivial boundary. This gives a negative answer to a question of Kaimanovich and Vershik. [ABSTRACT FROM AUTHOR]

We investigate the asymptotic behaviour of a class of self-interacting nearest neighbour random walks on the one-dimensional integer lattice which are pushed by a particular linear combination of their own local time on edges in the neighbourhood of their current position. We prove that in a range of the relevant parameter of the model such random walkers can be eventually confined to a finite interval of length depending on the parameter value. The phenomenon arises as a result of competing self-attracting and self-repelling effects where in the named parameter range the former wins. [ABSTRACT FROM AUTHOR]

We study the geometry of a class of group extensions, containing permutational wreath products, which we call 'permutational extensions'. We construct for all k∈ℕ a torsion group K with growth function and a torsion-free group H with growth function These are the first examples of groups of intermediate growth for which the asymptotics of their growth function is known. We construct a group of intermediate growth that contains the group of finitely supported permutations of a countable set as a subgroup. This gives the first example of a group of intermediate growth containing an infinite simple group as a subgroup. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We prove an isoperimetric inequality for wreath products of Markov chains with variable fibers. We use isoperimetric inequalities for wreath products to estimate the return probability of random walks on infinite groups and graphs, drift of random loops, the expected value E(exp(− tR n )), where R n is the number of distinct sites, visited up to the moment n, and, more generally, [InlineMediaObject not available: see fulltext.] (where L z,n is the number of visits of z up to the moment n and F( x, y) is some non-negative function). [ABSTRACT FROM AUTHOR]

We introduce a method to estimate the entropy of random walks on groups. We apply this method to exhibit the existence of compact manifolds with amenable fundamental groups such that the universal cover is not Liouville. We also use the criterion to prove that a finitely generated solvable group admits a symmetric measure with non-trivial Poisson boundary if and only if this group is not virtually nilpotent. This, in particular, shows that any polycyclic group admits a symmetric measure such that its boundary does not readily interprete in terms of the ambient Lie group. As another application we get a series of examples of amenable groups such that any finite entropy non-degenerate measure on them has non-trivial Poisson boundary. Since the groups in question are amenable, they do admit measures such that the corresponding random walks have trivial boundary; the above shows that such measures on these groups have infinite entropy. [ABSTRACT FROM AUTHOR]