UCLA

We present some combinatorial results about finitely generated groups, particularly groups acting on rooted trees.

Given a finitely generated group G and a positive integer k, the product replacement graph Γ_k(G) is the graph whose vertices are generating k-tuples of G, and whose edges are Nielsen transformations between these generating k-tuples. We prove that if G has polynomial growth or G has exponential growth, then Γ_k(G) has exponential growth for sufficiently large k. We also prove with a direct combinatorial argument that Γ_k(G_ω) has exponential growth for k ≥ 5, where G_ω is the generalized Grigorchuk group.

We prove that Γ_k(G) is non-amenable for sufficiently large k in either of the following two cases: G is uniformly non-amenable, or G is virtually indicable. It follows that Γ_k(G) is non-amenable whenever G is a linear group, or a hyperbolic group, or an elementary amenable group.

We describe two Mealy automata, the Aleshin automaton and the Bellaterra automaton, whose Schreier graphs are conjectured to be expanders. We verify that these Schreier graphs have polylogarithmic diameter. We describe a class of Mealy automata for which the same is true. However, some members of this class do not give rise to expander graphs.