COMPUTER SCIENCE/DISCRETE MATH II | |

Topic: | Strong Approximation in Random Towers of Graphs |

Speaker: | Yair Glasner |

Affiliation: | IAS |

Date: | Tuesday, March 7 |

Time/Room: | 10:30am - 12:30pm/S-101 |

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 =