Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.