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.
- IstvanIstvan T. Hernadvolgyi | WEB: http://www.csi.uottawa.ca/~istvan firstname.lastname@example.org | home: ( 613 ) - 237 - 0168 email@example.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