home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15012 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.4 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!wupost!gumby!yale!hsdndev!husc-news.harvard.edu!zariski!kubo
  2. From: kubo@zariski.harvard.edu (Tal Kubo)
  3. Newsgroups: sci.math
  4. Subject: Re: Counting Families of Subsets
  5. Keywords: Dedekind, unsolved
  6. Message-ID: <1992Nov15.220836.17488@husc3.harvard.edu>
  7. Date: 16 Nov 92 03:08:35 GMT
  8. References: <1992Nov15.152951.44802@kuhub.cc.ukans.edu>
  9. Organization: Dept. of Math, Harvard Univ.
  10. Lines: 23
  11. Nntp-Posting-Host: zariski.harvard.edu
  12.  
  13. In article <1992Nov15.152951.44802@kuhub.cc.ukans.edu>
  14. kinnersley@kuhub.cc.ukans.edu (Bill Kinnersley) writes: 
  15. >Take a base set S with N elements.  There are 2^N subsets of S.
  16. >Let F be a family such that all elements of F are distinct subsets,
  17. >and no element of F is a subset of another.
  18. >
  19. >How many families like this are there, for given N?
  20.  
  21. You are asking for D(n), the number of antichains of subsets of 
  22. an N-element set. 
  23.  
  24.   1) Computing D(n) is an unsolved problem that goes back to 
  25.      Dedekind, if not earlier.
  26.  
  27.   2) It has been proved that for large N, almost all the antichains
  28.      have all their elements in the middle four layers (i.e. consist
  29.      of sets of size  n/2 - 2 to  n/2+2).
  30.  
  31. There is a journal called "Order", devoted to similar problems 
  32. involving partially ordered sets.  Check there for more recent
  33. information.
  34.  
  35. -tk    kubo@math.harvard.edu
  36.