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.