> < ^ From:

> < ^ Subject:

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

> < [top]