For graphs there are only four types of hereditary Ramsey classes (Q1812632): Difference between revisions

A Ramsey class is defined as a hereditary class \(K\) of structures which has the \(A\)-partition property for every \(A\in K\). This notion generalizes the classical Ramsey theorem which in this setting claims that the class of all finite complete graphs is Ramsey. Ramsey classes of graphs, relations, and set systems were studied earlier where several basic classes were proved to be Ramsey. Here we combine these results with a result of \textit{A.H. Lachlan} and \textit{R.E. Woodrow} [Trans. Am. Math. Soc. 262, 51-94 (1980; Zbl 0471.03025){]} and we obtain a complete list of Ramsey classes of graphs. As we shall see there are exactly four basic types of classes of graphs which are Ramsey. All other classes may be obtained by unions. It should be stressed that being a Ramsey class is a very restrictive property and usually it is not easy to establish this fact. We define below a much weaker property (``pair-Ramsey class''); nevertheless we prove that Ramsey and pair-Ramsey properties coincide. This is quite surprising and there is no direct proof of this fact (our proof is indirect via [loc. cit.]). The paper is organized as follows: Section 1 contains basic notions and properties of Ramsey classes of graphs; Section 2 reviews amalgams and amalgamation classes introduced in [loc. cit.]; in Section 3 we define the notion of a pair-Ramsey class and derive basic properties. In Section 4 we prove the main result.