Tag - Cayley graphs
This is a 21-lecture course, with each lecture being either one or two hours, given by Giulio Tiozzo. It gives an introduction to random walks on groups. This class will focus on properties of group actions from a probabilistic point of view, investigating the relations between the dynamics, measure theory and geometry of groups.
We will start with a brief introduction to ergodic theory, discussing measurable transformations and the basic ergodic theorems. Then we will approach random walks on matrix groups and lattices in Lie groups, following the work of Furstenberg. Topics of discussion will be: positivity of drift and Lyapunov exponents. Stationary measures. Geodesic tracking. Entropy of random walks. The Poisson-Furstenberg boundary. Applications to rigidity. We will then turn to a similar study of group actions which do not arise from homogeneous spaces, but which display some features of negatively curved spaces: for instance, hyperbolic groups (in the sense of Gromov) and groups acting on hyperbolic spaces. This will lead us to applications to geometric topology: in particular, to the study of mapping class groups and Out(FN).
Prerequisites: An introduction to measure theory and/or probability, basic topology and basic group theory. No previous knowledge of geometric group theory or Teichmüller theory is needed.
In the 1960s Higman was able to characterize the finitely generated subgroups of finitely presented groups, that is, groups defined using a finite set of generators and finite set of defining relations. His result, which is called the Higman Embedding Theorem, is a key result in combinatorial group theory which makes precise the connection between group presentations and logic. In this talk I will present a result of a similar flavour, proved in recent joint work with Mark Kambites (Manchester), in which we characterise the groups of units of inverse monoids defined by presentation where all the defining relators are of the form w=1. I will explain what an inverse monoid is, the motivation for studying this class of inverse monoids, and also outline some of the geometric ideas that we developed in order to prove our results.
A locally-finite simple connected graph is said to be k-geodetic for some k ≥ 1, if there are at most k distinct geodesics between any two vertices of the graph. We investigate the properties of hyperbolic groups with k-geodetic Cayley graphs. To begin, we show that k-geodetic graphs cannot have a "ladder-like" geodesic structure with unbounded length. Using this bound, we generalize a well-known result of Papasoglu that states hyperbolic groups with 1-geodetic Cayley graphs are virtually free. We then investigate which elements of the hyperbolic group with k-geodetic Cayley graph commute with a given infinite order element.
I will discuss the dictionary between the algebraic structure of a right-angled Artin group and the combinatorics of the defining graph. I will then use the cohomology of a right-angled Artin group to provide a characterization of Hamiltonicity of the underlying graph. Along the way, I will describe some linear algebraic facts which appear to have been previously unknown.
Zoltan Halasi: Babai’s conjecture for classical groups with generating sets containing transvections
A well-known conjecture of Babai states that if G is any finite simple group and X is a generating set of G, then the diameter of the Cayley graph Cay(G, X) is bounded by a polylogarithmic function of |G|. The goal of the talk is to sketch a proof of such a bound in the case that X contains a transvection.
Let G be a group and S a generating set. Then the group G naturally acts on the Cayley graph Cay(G,S) by left multiplications. The group G is said to be rigid if there exists an S such that the only automorphisms of Cay(G,S) are the ones coming from the action of G. While the classification of finite rigid groups was achieved in 1981, few results were known about infinite groups. In a recent work, with M. de la Salle we gave a complete classification of infinite finitely generated rigid groups. As a consequence, we also obtain that every finitely generated group admits a Cayley graph with countable automorphism group.
Babai's conjecture asserts that the diameter of the Cayley graph of any finite simple group G is bounded by (log |G|)O(1). This conjecture has been resolved for groups of bounded rank, but for groups of unbounded rank such as SLn(2) it is wide open. Even for random generators, only the case of alternating groups is resolved. In this talk we sketch the proof of Babai's conjecture for SLn(p), p = O(1), with at least three random generators. The proof extends to other classical groups over 𝔽q if we have at least q100 random generators. The heart of the proof consists of showing that the Schreier graph of SLn(q) acting on 𝔽qn with respect to q100 random generators is an expander graph.
Fix a word w in a free group on r generators. A w-random permutation in the symmetric group SN is obtained by sampling r independent uniformly random permutations σ1, . . .,σr ∈ SN and evaluating w(σ1, . . .,σr). Such w-random permutations have surprisingly rich structure with relation to deep results in geometric group theory. I'll survey some of this structure, state some conjectures, and explain how it is related to evaluating the spectral gap of random Schreier graphs of SN.
An LMS online lecture course in free groups and graph theory.
Free groups may be viewed as the fundamental groups of graphs. This observation allows for a very intuitive view of free groups and their subgroups. These lectures combine topological ideas, due to Stallings in the 1980s, with more combinatorial and computational ones to prove many of the fundamental results in free groups. These results include the Nielsen-Schreier Theorem (subgroups of free groups are free), Howson's Theorem (finitely generated subgroups have finitely generated intersection), and the decidability of the subgroup membership problem.
You must be logged in to post a comment.