home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13325 < prev    next >
Encoding:
Text File  |  1992-10-16  |  1.5 KB  |  38 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!snorkelwacker.mit.edu!mintaka.lcs.mit.edu!hal.gnu.ai.mit.edu!jamie
  3. From: jamie@hal.gnu.ai.mit.edu (Andrew John Radcliffe)
  4. Subject: Re: Combinatorics Problem (probably easy)
  5. Message-ID: <1992Oct16.185841.26130@mintaka.lcs.mit.edu>
  6. Summary: It's Sperner's lemma
  7. Sender: jamie@gnu.ai.mit.edu
  8. Organization: /etc/organization
  9. References: <1992Oct15.232815.26763@u.washington.edu>
  10. Date: Fri, 16 Oct 1992 18:58:41 GMT
  11. Lines: 25
  12.  
  13. In article <1992Oct15.232815.26763@u.washington.edu> cxu@milton.u.washington.edu (Chongguang Xu) writes:
  14. >
  15. >I have a conjecture about a combinatorics question which I have been 
  16. >unable to prove.  I'm hoping someone on the net knows the answer or
  17. >can give me a reference.
  18. >
  19. >Given a set S of k elements, let A be the largest family of subsets of S
  20. >such that for every two elements a and b of A, b is not a substet of a.  
  21. >My conjecture is that the cardinality of A is C(k, [k/2]), where C(p,q)
  22. >is the binomial coefficient, and [c] is the floor of c.  I can prove that 
  23. >the cardinality of A is at least that big, but I can't prove it can't 
  24. >be bigger.
  25. >
  26.  
  27. Your conjecture is true, and the result is known as Sperner's lemma.
  28. (Somewhat unfairly Sperner has >two< lemmas to his name.) There
  29. are several lovely proofs, none really short enough to give here.
  30. A good book that talks about Sperner's lemma, among other things, is
  31. B. Bollobas, Combinatorics, Cambridge University Press. I'll email
  32. you several proofs if you want.
  33.  
  34. Jamie Radcliffe
  35.  
  36.  
  37.  
  38.