Mathematics – Combinatorics
Scientific paper
2009-05-01
Mathematics
Combinatorics
30 pages, 3 figures
Scientific paper
The term "strong approximation" is used to describe phenomena where an arithmetic group as well as all of its Zariski dense subgroups have a large image in the congruence quotients. We exhibit analogues of such phenomena in a probabilistic, rather than arithmetic, setting. Let T be the binary rooted tree, Aut(T) its automorphism group. To a given m-tuple a = {a_1,a_2,...,a_m} in Aut(T), we associate a tower of 2m-regular Schreier graphs ...X_n-->X_{n-1}-->...-->X_0. The vertices of X_n are the n^{th} level of the tree and two such are connected by an edge if a generator takes one to the other. When {a_i} are independent Haar-random elements of Aut(T) we retrieve the standard model for iterated random 2-lifts studied, for example by Bilu-Linial. If w={w_1,w_2,...,w_l} are words in the free group F_m, the random substitutions w(a) := {w_1(a),...,w_l(a)} give rise to new models for random towers of 2l-regular graphs: ...Y_n-->Y_{n-1}-->...-->Y_0. With the above notation, the following hold almost surely, for every non cyclic subgroup D in F_m: (i) the graphs $Y_n$ have a bounded number of connected components, (ii) these connected components form a family of expander graphs, (iii) the closure of D has positive Hausdorff dimension as a subgroup of the (metric) group Aut(T).
No associations
LandOfFree
Strong approximation in random towers of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Strong approximation in random towers of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong approximation in random towers of graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-100729