> < ^ From:

> ^ Subject:

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

> < [top]