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.)
verret
- 3.3k
- 1
- 22
- 30