home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 18051 < prev    next >
Encoding:
Text File  |  1993-01-12  |  2.6 KB  |  73 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!haven.umd.edu!decuac!pa.dec.com!iberia.cca.cr.rockwell.com!mlc
  3. From: mlc@iberia.cca.cr.rockwell.com ("Mike Cook, x2792, 124-211")
  4. Message-ID: <009667FC.25AB4800.16193@iberia.cca.cr.rockwell.com>
  5. Subject: RE: Ramsey Theory Games
  6. Date: Tue, 12 Jan 1993 12:18:36 CST
  7. X-Received: by usenet.pa.dec.com; id AA20763; Tue, 12 Jan 93 10:21:18 -0800
  8. X-Received: by inet-gw-1.pa.dec.com; id AA19609; Tue, 12 Jan 93 10:21:15 -0800
  9. X-Received: by iberia.cca.cr.rockwell.com (MX V2.3) id 16193; Tue, 12 Jan 1993
  10.           12:18:36 CST
  11. X-To: SCI.MATH.USENET
  12. X-Cc: mlc@iberia.cca.cr.rockwell.com
  13. Lines: 58
  14.  
  15. > In-reply-to: mjd@saul.cis.upenn.edu's message of 11 Nov 92 23:55:26 GMT
  16. > 
  17. > I don't know why it never occurred to me before, but you could take
  18. > nearly any result from Ramsey Theory and make a game out of it. 
  19. > 
  20. > For example:
  21. > 
  22. >     Ramsey's Theorem: For any positive integers C and S, there
  23. >     exists a positive integer N such that if the edges of the
  24. >     complete graph on N vertices are partitioned into C sets, then
  25. >     there is at least one complete graph on S vertices whose edges
  26. >     are all in one set.
  27. > 
  28. > When C=2 and S=6, we have N=3.  (Well-known proof left as exercise for
  29. > the interested reader.)  So when (C) two players take turns coloring the
  30. > edges of the complete graph on (S) 6 vertices (that is, putting the
  31. > edges into their own sets), at least one player will have a complete
  32. > graph with (N) 3 vertices---a triangle.  If whoever gets a triangle
  33. > first loses, there can be no draws.  This game is `sim'.
  34.  
  35. See:
  36. "A Strategy for the Ramsey Game of 'Tritip'",
  37. Michael L. Cook and Dr. Leslie Shader,
  38. Proceedings of the Tenth Southeastern Conference on
  39. Combinatorics, Graph Theory, and Computing,
  40. April 1979, pp 315-324.
  41.  
  42. The object of this 2-player game is to color edges of a Ramsey
  43. graph, trying to prevent the other player from coloring edges
  44. that would form the following graph (other orientations allowed,
  45. of course).
  46.  
  47.                 X---------------X
  48.                  \             /
  49.                   \           /
  50.                    \         /
  51.                     \       /
  52.                      \     /
  53.                       \   /
  54.                        \ /
  55.                         X
  56.                         |
  57.                         |
  58.                         |
  59.                         |
  60.                         |
  61.                         X
  62.  
  63. See also some other papers by Shader where graph theory plays a part.
  64.  
  65. --
  66.  
  67. Michael Cook
  68. Internet: MLC@IBERIA.CCA.CR.ROCKWELL.COM
  69. These are not the opinions of my employer.
  70.  
  71. RE: net.wisdom - "It's not what we don't know that hurts,
  72.                   it's what we know that ain't so." -- Will Rogers
  73.