Another look at the Erdős-Hajnal-Pósa results on partitioning edges of the Rado graph (Q5955203)

The Rado graph or universal graph \(\mathfrak R=(R;E(R))\) is the unique countable graph with the property that for every finite graph \(\mathfrak B=(G;E(G))\), vertex \(a\in G\) and embedding \(f:\mathfrak B-a\to \mathfrak R\) there is an extension of \(f\) to an embedding \(f^*:\mathfrak B \to \mathfrak R\). Given graphs \(\mathfrak B_0,\dots,\mathfrak B_{n-1}\), \(\mathfrak R\to (\mathfrak B_0,\dots,\mathfrak B_{n-1})^{\text{edges}}\) means: For every partition \(A_0,\dots,A_{n-1}\) of the set of edges of \(\mathfrak R\) there is some \(i\in n\) and an embedding \(f\) from \(\mathfrak B_i\) into \(\mathfrak R\) such that \(f[E(\mathfrak B_i)]\subseteq A_i\). \textit{P. Erdős, A. Hajnal}, and \textit{L. Pósa} [Infinite and finite sets, Colloq. Math. Soc. J. Bolyai 10, 585-595 (1975; Zbl 0312.05123)] exhibited a partition \((U,D)\) of the edges of the Rado graph \(\mathfrak R\), which is a counterexample to \(\mathfrak R\to (\mathfrak R)^{\text{edges}}_2\). The author now characterizes all countable graphs \(\mathfrak B_0,\dots,\mathfrak B_{n-1}\) so that \(\mathfrak R\to (\mathfrak B_0,\dots,\mathfrak B_{n-1})^{\text{edges}}\): This holds iff there is an index \(i\in n\) so that for every \(i\neq j\in n\) the graph \(\mathfrak B_j\) is \(0,1\)-orderable. This last notion is introduced in the following way: Let \(\Sigma\) denote the set of all finite \(0,1\)-sequences ending in a 1. This set is equipped with the strict lexicographic order \(\prec\). The \(0,1\)-right graph has \(\Sigma\) as the set of vertices, and edges so that for every \(n\in \omega\) and for every \(\varphi\in \Sigma\) of length \(n+1\) the set of sequences \(\gamma \in \Sigma\) which are no longer than \(\varphi\) and adjacent to \(\varphi\) is \(\{\gamma \in \Sigma \mid \gamma(n)=1\land \varphi\prec\gamma\}\). Then a graph is \(0,1\) right-orderable if it has an embedding into the \(0,1\)-right graph. Due to symmetry conditions, the word ``right'' can be omitted. From the main result of the paper follows a theorem of Erdős-Hajnal-Pósa (cited above).