> < ^ Date: Wed, 06 Aug 1997 20:40:34 EDT
> < ^ From: I. T. Hernadvolgyi <istvan@csi.UOttawa.CA >
> ^ 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.

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.



- 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]