Generator sets of a subgroup of $S_n$ with $O(n)$ total support - do they always exist ?

Question

For a permutation of a finite set $X$, define its supporting set as the complement in $X$ of its fixed-point set. The term support describes the size of a supporting set. For example, a $k$-cycle has support $k$.

Consider a subgroup $H$ of $S_n$, such as $H=Aut(G)$ for an $n$-vertex graph $G$. We are interested in small generating sets of $H$. But rather than count the generators, we are going to add up their supports and call the result the total support of a generating set.

1. $H$ can always be generated by at most $n-1$ generators. An elegant proof, anyone?

2. Is it true that a generating set of $H$ exists with $O(n)$ total support ? If not, an example of the form $Aut(G)$ would be most useful. If yes, can total support be limited by $Cn$ for a known $C>0$ ?

3. Same question with at most $n-1$ generators.

As an illustration, take $S_n$. It can be generated by $n-1$ transpositions whose total support is $2n-2$. Or by one transposition and a full cycle, whose total support is $n+2$.

Answer 1

About Q1, this is standard. Take a strong generating set. List the strong generators in inverse order of the length of their stabiliser. I.e., first come the generators that fix all but the last point in the base, and last come the generators that move the first element of the base. Now delete every generator whose cycles are subsets of the orbits of the subgroup generated by the generators coming before it in the list. You are left with at most $n-1$ generators that still generate the group. Proof by induction on the length of the base.

Incidentally, programs for computing $Aut(G)$ like nauty, bliss, saucy, always find at most $n-1$ generators.

Answer 2

The answer to Q2 is no. Let $H$ be an elementary abelian $2$-group, in its regular action, so $n=2^a$ for some $a$. Clearly, to generate $H$, we need $a$ elements with full support, so the total support is $an= n \log_2 n$. Moreover, it is known that, for $a\geq 5$, $H=\mathrm{Aut}(G)$ for some graph $G$. (In other words, an elementary abelian $2$-group of order at least $32$ admits a graphical regular representation.)