A consistent edge partition theorem for infinite graphs
For graphs \(X\) and \(Y\) and cardinal number \(\mu\), the relation \(X\rightarrowtail (Y)^ 2_ \mu\) means that whenever the edges of the graph \(X\) are coloured with \(\mu\) colours, there is always an induced subgraph isomorphic to \(Y\), all the edges of which have the same colour. The general problem is for which infinite graphs \(Y\) and cardinals \(\mu\) does there exist a graph \(X\) for which \(X\rightarrowtail (Y)^ 2_ \mu\); the answer is independent. \textit{A. Hajnal} and the first author [Trans. Am. Math. Soc. 307, No. 1, 395-409 (1988; Zbl 0659.03029)] showed that it is consistent that there is a \(Y\) (of size \(\aleph_ 1\)) such that there is no \(X\) for which \(X\rightarrowtail (Y)^ 2_ 2\), whereas the second author [Set theory and its applications, Proc. Conf., Toronto/Can. 1987, Lect. Notes Math. 1401, 167-193 (1989; Zbl 0683.04002)] proved that it is consistent that for every \(Y\) and \(\mu\) there is an \(X\) such that \(X\rightarrowtail (Y)^ 2_ \mu\). In the paper under review, this last result is improved by showing that \(X\) can be chosen so that any complete subgraph absent from \(Y\) is also absent from \(X\): it is consistent that for every \(Y\) and \(\mu\) there is \(X\) such that \(X\rightarrowtail (U)^ 2_ \mu\), and further for each cardinal \(\alpha\), if \(Y\) contains no complete subgraph on \(\alpha\) vertices then neither does \(X\). (This also establishes the consistency of the following solution to a long-standing problem of Erdős and Hajnal: there is a graph \(X\) such that \(X\to (\omega)^ 2_ \omega\) and \(X\) contains no uncountable complete subgraph).
scientific article; zbMATH DE number 633889
scientific article