In 1928 Frank Ramsey, an English mathematician,
showed that there are patterns implicit in any large
structure. The accompanying diagram (which resembles
the aestheometric design of Projects 7.2 and 7.3) typifies
the problems that Ramsey theory addresses.
"How many people does it take to form a group that always
contains either four mutual acquaintances or four mutual
strangers?"
In the diagram, points represent people. A red edge
connects people who are mutual acquaintances, and a blue
edge joins people who are mutual strangers. In the group
of 17 points shown, there are not four points whose network
of edges are either completely red or completely blue.
Therefore, it takes more than 17 people to guarantee that
there will always be four people who are either acquaintances
or strangers. Write a report on Ramsey theory.
What is Ramsey Tic-Tac-Toe?
Reference:
Ronald L. Graham and Joel H. Spencer, "Ramsey Theory,"
Scientific American, July 1990, pp. 112-117
