ABSTRACT
Ramsey theory typically deals with problems of the following type. We are given a set S, a family F $ \mathcal{F} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math11_1.tif"/> of subsets of S, and a positive integer r. We would like to decide whether or not for every partition of S = C 1 ∪ ⋯ ∪ C r $ S= C_1 \cup \cdots \cup C_r $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math11_2.tif"/> into r subsets, it is always true that some C i $ C_i $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math11_3.tif"/> contains some F ∈ F $ F \in \mathcal{F} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math11_4.tif"/> . If so, we abbreviate this by writing S ⟶ r F $ S \mathop {\longrightarrow }\limits ^{r} \mathcal{F} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math11_5.tif"/> (and we say S is r-Ramsey). If not, we write S ⟶ / r F $ S \mathop {\longrightarrow \!\!\!\!\!\!\!\!/}\limits ^{r}\ \mathcal{F} $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math11_6.tif"/> . (For a comprehensive treatment of Ramsey theory, see [[GRS90]].)
