Computer Science/Discrete Mathematics Seminar II

Random covers of graphs, and random group actions on rooted trees, are different languages, that describe the same phenomenon. The former were studied by Amit, Linial. Matousek, Bilu. The latter were studied by Abert and Virag. Let T(n) be a binary tree of depth n, and G = G(A,B,C) a group generated by 3 independent random automorphisms of T(n). The deepest, and most difficult, discovery of Abert and Virag is that the group G is very large. They show that with high probability |G| = |Aut(T)| ^{1 - \epsilon} No deterministic constructions are known for such large subgroups with a bounded number of generators. Consider now a subgroup H < G generated by H = or any other two words in the generators of G. I will show that any such subgroup is still large, in the sense that there exists a constant a = a(H) > 0, such that with high probability |G| = |Aut(T)| ^a The concept of subgroups of random groups is new and very interesting. The generators of such subgroups are no longer uniformly distributed. Even worse they are no longer independent. And some new methods are required in their analysis. If time permits I will describe these results in the setting of graph coverings, and draw an analogy with the theory of arithmetic groups.