Embedding theorems for graphs establishing negative partition relations (Q1247324)

The graph \(G_1\) is said to embed into the graph \(G_1\) if \(G_0\) is isomorphic to a spanned subgraph of \(G_1\). Given cardinal numbers \(\varkappa\) and \(\lambda\), the symbol \([\varkappa]\) denotes the complete graph on \(\varkappa\) vertices, \([\varkappa\lambda]\) the complete \((\varkappa\lambda)\)-bipartite graph and , \([\varkappa/\varkappa]\) the half \((\varkappa/\varkappa)\)-bipartite graph (where the set of vertices is a disjoint union \(G_0\cup G_1\) with \(|G_0| = |G_1| = \varkappa\) and there are one-to-one enumerations \(G_0 = \{x_{\alpha};\alpha< \varkappa\}\), \(G_1=\{y_{\beta};\beta< \varkappa\}\) such that for each \(x_{\alpha}\), the set of vertices adjacent to \(x_{\alpha}\) is \(\{y_{\beta};\alpha< \beta< \varkappa\}\)). Let \(\triangle_0\), \(\triangle_1\) be symbols of these types: The graph \(G\) is said to establish the negative partition relation \(\varkappa\nrightarrow(\triangle_0,\triangle_1)^2\) if \(G\) is a graph on \(\varkappa\) vertices such that \(G\) contains no subgraph of type \(\triangle_0\) and the complement of \(G\) contains no subgraph of type \(\triangle_1\). The main aim of this paper is to characterize the class of all countable graphs which embed into all graphs \(G\) establishing \(\aleph_1\nrightarrow(\triangle_0,\triangle_1)^2\) when \(\triangle_0\), \(\triangle_1\) are any of \([\aleph_1]\), \([\aleph_1,\aleph_1]\), \([\aleph_1/\aleph_1]\), \([\aleph_0,\aleph_1]\), The authors prove their theorems in ZFC, and then try to show that they are ''best possible'' assuming the continuum hypothesis or the existence of a Souslin tree. Occasionally Souslin's axiom is invoked instead.