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.

This of course is not true if G has too many orbits, but is it true for
(almost) transitive 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.

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