Skip to main content
MathOverflow

Return to Question

deleted 36 characters in body; deleted 19 characters in body; added 3 characters in body; edited body
Source Link
Igor Markov
Igor Markov
  • 341
  • 1
  • 10

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. It seems that $H$ can always be generated generated by at most $n-1$ generators. An elegant proof, anyone?

  2. Is it true that a generating set of $H$ can always be chosenexists 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 somea known $C>0$ ?

  3. Same question with at most $n-1$ generators (assuming 1. holds)

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

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. It seems that $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$ can always be chosen 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 some $C>0$ ?

  3. Same question with at most $n-1$ generators (assuming 1. holds)

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

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

Source Link
Igor Markov
Igor Markov
  • 341
  • 1
  • 10

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

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. It seems that $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$ can always be chosen 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 some $C>0$ ?

  3. Same question with at most $n-1$ generators (assuming 1. holds)

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