Dear Gap Forum and Istvan:

----------
From: I. T. Hernadvolgyi[SMTP:istvan@csi.uottawa.ca]
Sent: Wednesday, August 06, 1997 8:40 PM
To: Multiple recipients of list
Subject: Size of Minimal Generating Sets

Hi everyone,

I am wondering whether some bound on the number of elements of
minimal generating sets is known. I seem to recall a theorem, I
believe due to Erdos, which would suggest that if G is a finite permutation
group then any minimal generating set for G has at most O(log |G|)
elements.

If G is a subgroup of Sn (the symmetric group on n letters) with
minimal generating set of size b then
2^b<=|G|<=n(n-1)...(n-b+1)<=n^b. (Dixon and Mortimer, Permutation
Groups, Springer-Verlag, page 76, section 3.3.
>
> This of course is not true if G has too many orbits, but is it true for
> (almost) transitive groups?

It's true for all finite permutation groups.
>
> The other question I have is, if it is known to be NP-complete to find the
> shortest word between two arbitrary elements in a permutation group for
> a given generating set.

I think this is not true, if I understand your question correctly. (It
depends on
what parameter you're using to measure the speed of the algorithm.) In
general,
for a graph with N vertices the shortest path problem has an O(N^3) -
time
algorithm. See Gibbons, Algorithmic Graph Theory, Cambridge Univ Press,
section 1.4, page 32. The Cayley graph of G has |G| vertices, of course,
so this algorithm is polynomial in |G| but exponential in b.
                                    - David Joyner
>
>
> References are greatly appreciated.
> 
>thanks, 
>
>-- 
>
> - Istvan
>
> Istvan T. Hernadvolgyi | WEB:   http://www.csi.uottawa.ca/~istvan
> istvan@csi.uottawa.ca  | home:               ( 613 ) - 237 - 0168 
> istvan@ottawa.com      | office: MCD 214, Tel: 562-5800 ext: 6782
>
>                Former Department of Computer Science
>          School of Information Technology and Engineering
>                       University of Ottawa
>                  Ottawa, Ontario K1N 6N5, Canada
>
>

Miles-Receive-Header: reply