Ramsey theory is the study of questions of the following type: given a combinatorial structure (e.g. a graph or a subset of the integers), how large does the structure have to be to guarantee the existence of some substructure (e.g. subgraph, subset) with a given property? The theory has applications in the design of communications networks and other purely graph-theoretical contexts, as well as interesting problems in elementary number theory.
Motivating example[edit | edit source]
The most well-known example of Ramsey theory is furnished by Ramsey's theorem, which generalizes the following brainteaser.
Examgle: Show that any party with at least 6 people will contain a group of three mutual friends or a group of three mutual non-friends.
Solution: Call the people A, B, C, D, E, F. Either A have three friends or three non-friends. Without loss of generality, suppose that B, C, D are all friends with A. Then if any pair of them are friends with each other, that pair plus A forms a group of three mutual friends. If no two of them are a group of three mutual non-friends.
Source: Ramsey Theory. Brilliant.org. Retrieved 08:21, May 10, 2021, from https://brilliant.org/wiki/ramsey-theory/