Martin's axiom and ordinal graphs: Large independent sets or infinite paths (Q915725)

Given ordinals \(\alpha\) and \(\beta\), \(\alpha\to (\beta\), infinite \(path)^ 2\) (respectively \(\alpha \to (\beta,\omega)^ 2)\) means that every graph on \(\alpha\) either contains an infinite path (resp. an infinite complete subgraph) or an independent (edge-free) set of type \(\beta\). It is well-known that for all \(\alpha\geq \omega\), \(\alpha \to (| \alpha |,\omega)^ 2\) but \(\alpha \nrightarrow (| \alpha | +1,\omega)^ 2\). Besides, \(\alpha +n+1\nrightarrow (\alpha +1\), infinite \(path)^ 2\) whenever \(\alpha >0\) and \(n<\omega\). \textit{P. Erdős}, \textit{A. Hajnal} and \textit{E. C. Milner} [Combinat. Theory Appl., Colloq. Math. Soc. János Bolyai 4, 327-363 (1970; Zbl 0215.329) ] have proven that \(\alpha\to (\alpha\), infinite \(path)^ 2\) for all limit ordinals \(\alpha <\omega_ 1^{\omega +2}\). The author [J. Lond. Math. Soc., II. Ser. 33, 193-202 (1986; Zbl 0566.03030)] has shown that this relation also holds for \(\alpha =\omega_ 1^{\omega +2}\) under the assumption that there is no scale of order type \(\omega_ 1\) under eventual domination in \(^{\omega}\omega\). On the other hand, he has used [Trans. Am. Math. Soc. 303, 383-393 (1987; Zbl 0638.05002)] GCH to show that whenever \(2\leq n<\omega\), there are cofinally many limit ordinals \(\alpha\) below \(\omega_ n\) such that \(\alpha \nrightarrow (\alpha\), infinite \(path)^ 2\). The main result of the present paper is that under Martin's Axiom, \(\alpha\to (\alpha\), infinite \(path)^ 2\) for all limit ordinals \(\alpha <2^{\aleph_ 0}\). The article also contains the following useful reduction rule. Suppose \(\alpha =\alpha_ 0+\alpha_ 1+...+\alpha_{n-1}\), where \(\alpha >\alpha_ 0\geq \alpha_ 1\geq...\geq \alpha_{n-1}\) and for each \(i<n\), \(\alpha_ 1\) cannot be obtained as the sum of two smaller ordinals. Then \(\alpha\to (\alpha\), infinite \(path)^ 2\) if and only if for all \(i<n\), \(\alpha_ j\to (\alpha_ j\), infinite \(path)^ 2\).