home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / research / 659 < prev    next >
Encoding:
Text File  |  1993-01-25  |  1.6 KB  |  48 lines
  1. Newsgroups: sci.math.research
  2. Path: sparky!uunet!gatech!paladin.american.edu!howland.reston.ans.net!usc!sdd.hp.com!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
  3. From: sl25@cus.cam.ac.uk (Steve Linton)
  4. Subject: Re: combinatorics or coding theory question
  5. References: <RINKUS.93Jan24142753@park.bu.edu>
  6. Message-ID: <1993Jan25.155627.20097@infodev.cam.ac.uk>
  7. Originator: dan@symcom.math.uiuc.edu
  8. Sender: Daniel Grayson <dan@math.uiuc.edu>
  9. X-Submissions-To: sci-math-research@uiuc.edu
  10. Organization: U of Cambridge, England
  11. X-Administrivia-To: sci-math-research-request@uiuc.edu
  12. Approved: Daniel Grayson <dan@math.uiuc.edu>
  13. Date: Mon, 25 Jan 1993 15:56:27 GMT
  14. Lines: 32
  15.  
  16.  
  17. |> Suppose you have N groups of cells.  Each group contains K cells.
  18. |> Now suppose you make choices consisting of one cell chosen from
  19. |> each of the N groups.  Let each such choice be called a vector.
  20. |> Clearly there are K^N unique vectors.
  21. |> 
  22. |> My question is:  what is the largest set of vectors you can pick
  23. |> such that no two of the vectors overlap (i.e. have the same cell)
  24. |> at more than Q of the groups (where Q < N)?
  25.  
  26. In more usual language, you want your vectors to differ in at least N-Q places. I
  27. shall call this number D.
  28.  
  29. You are looking for the largest code with minimum distance D among your K^N
  30. vectors.
  31.  
  32. Each vector has       (N+D)   neighbours  at diostance less than D, so a 
  33.               ( D )
  34.         (K-1)^
  35.  
  36. simple upper bound on the size of your code is  
  37.  
  38.               -(N+D/2)    
  39.         K^N (K-1)^ ( D/2 )
  40.  
  41. (that's K to the N times (K-1) to the N+D/2 choose D/2).
  42.  
  43. Anyway, you want to look at Codes, Groups and Sphere Packings by J.H.Conway and
  44. N.J.A. Sloane.
  45.  
  46.         Steve Linton
  47.  
  48.