home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 18072 < prev    next >
Encoding:
Text File  |  1993-01-13  |  2.4 KB  |  52 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: Combinatorical problem
  5. Message-ID: <1993Jan13.054525.7721@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department,  Stanford University.
  8. References: <1j04niINNe98@news.cerf.net>
  9. Date: Wed, 13 Jan 1993 05:45:25 GMT
  10. Lines: 40
  11.  
  12. In article <1j04niINNe98@news.cerf.net> jcbhrb@nic.cerf.net (Jacob Hirbawi) writes:
  13. >I know of a form that has a number of nice features. (I'm not sure how it
  14. >relates to the two forms suggested by Vaughan Pratt but chances are good it's
  15. >a close relative). I'll look at permutations of degree 4 but all the results
  16. >are easily extended:
  17. >
  18. >First let the transpositions T(4)={a1,b1,b2,c1,c2,c3} be defined by:
  19. >
  20. >    a1 = (1,2),   b1 = (1,3),    c1 = (1,4),    ...
  21. >                  b2 = (2,3),    c2 = (2,4),
  22. >                                 c3 = (3,4),
  23. >then every permutation can be written uniquely as
  24. >
  25. >     (ai^ri)(bj^rj)(ck^rk)  with     ri,rj,rk = 0 or 1
  26. >                            and i=1,j=1 or 2,k=1,2, or 3, ...
  27.  
  28. This coicides with my first form, if both the permutation and the
  29. string of generators are read in the opposite order to mine.  The ci's
  30. correspond to the first transposition in my scheme, and rk=0 just when
  31. A1=1 in my notation (A1 A2 ... An).  And so on with 0 or 1 instances of
  32. bj, then 0 or 1 of ai.
  33.  
  34. Since posting my message it occurred to me that there is a universal
  35. optimal algorithm: just keep transposing pairs from the same cycle as
  36. long as there exist nontrivial cycles.  This is optimal since each
  37. transposition breaks its cycle into two cycles.  Furthermore it is
  38. universal in the sense that every optimal algorithm is a special case
  39. of this, since every transposition of an optimal run must break a cycle
  40. into two cycles at each transposition, the remaining distance being n-c
  41. where c is the number of cycles remaining.
  42.  
  43. >There is a connection which is either superficial or very deep (sometimes it's
  44. >hard to distinguish between the two ;-) ). These are also connected to 
  45. >semi-simple Lie algebras.
  46.  
  47. Extremely interesting.  I'd been hoping to learn about Lie algebras,
  48. now I have additional motivation *and* it suddenly looks a lot less
  49. intimidating.  Thanks!
  50. -- 
  51. Vaughan Pratt                There's no safety in large cardinals
  52.