home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15035 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.3 KB
  1. Path: sparky!uunet!munnari.oz.au!uniwa!dima
  2. From: dima@maths.uwa.oz.au (Dima Pasechnik)
  3. Newsgroups: sci.math
  4. Subject: Re: Counting Families of Subsets
  5. Date: 16 Nov 1992 09:02:04 GMT
  6. Organization: The University of Western Australia
  7. Lines: 39
  8. Message-ID: <1e7o2cINNpbp@uniwa.uwa.edu.au>
  9. References: <1992Nov15.152951.44802@kuhub.cc.ukans.edu>
  10. NNTP-Posting-Host: madvax.maths.uwa.oz.au
  11.  
  12. kinnersley@kuhub.cc.ukans.edu (Bill Kinnersley) writes:
  13.  
  14. >Take a base set S with N elements.  There are 2^N subsets of S.
  15. >I want to consider families of these subsets.  All together there
  16. >are 2^{2^N} such families, but I want to impose a condition.
  17.  
  18. >Let F be a family such that all elements of F are distinct subsets,
  19. >and no element of F is a subset of another.
  20.  
  21. >How many families like this are there, for given N?
  22.  
  23. >If you call the number K(N), then the first few values are:
  24.  
  25. >N        K
  26.  
  27. >0        1
  28. >1        2
  29. >2        5
  30. >3       19
  31. >4      167
  32.  
  33. >Can you tell me even the order of magnitude for K(N)?  It appears to be
  34. >much less than 2^{2^N}.
  35.  
  36. Such families are called clutters, or antichains. The question on |K(N)|
  37. seems to be open. Few more values of K are known:
  38. N    K
  39. 4    7580
  40. 6    7828354
  41.  
  42. There is a result of computer search due to M.Deza, I.Faradjev and
  43. K.Fukuda.
  44.  
  45. See, say, Europ. J. Comb. for the last 5-6 years. (say, 7(1986), 271-82)
  46.  
  47.  
  48.  
  49. Dmitri Pasechnik.
  50.  
  51.