Countable unions of triangle free graphs

Question

Call a graph $G = (V, E)$ nice if for every countable partition $\{V_n: n < \omega\}$ of $V$, there exists an $n < \omega$ such that $(V_n, E)$ contains a copy of $K_3$.

Does every nice graph contain a copy of $K_4$? Here $K_n$ is the complete graph on $n$ vertices.

Answer 1

Here is an example of a nice $K_4$-free graph on $\aleph_1$ vertices. It uses the same idea as the classical construction, due to Erdős and (Hajnal or Rado, I forget which), of an $\aleph_1$-chromatic $K_3$-free graph on $\aleph_1$ vertices.

Define a graph $G=(V,E)$ as follows: $$V=\{(\alpha_1,\alpha_2,\alpha_3,\alpha_4):\alpha_1\lt\alpha_2\lt\alpha_3\lt\alpha_4\lt\omega_1,$$ and $E=E_1\cup E_2$ where $$E_1=\{\{(\alpha_1,\alpha_2,\alpha_3,\alpha_4),(\beta_1,\beta_2,\beta_3,\beta_4)\}:\alpha_1\lt\alpha_2\lt\beta_1\lt\alpha_3\lt\beta_2\lt\alpha_4\lt\beta_3\lt\beta_4\},$$ $$E_2=\{\{(\alpha_1,\alpha_2,\alpha_3,\alpha_4),(\beta_1,\beta_2,\beta_3,\beta_4)\}:\alpha_1\lt\alpha_2\lt\alpha_3\lt\beta_1\lt\alpha_4\lt\beta_2\lt\beta_3\lt\beta_4\}.$$ It's easy to see that $G$ is $K_4$-free; we have to show that $G$ is nice. Consider any partition $V=\bigcup_{n\in\omega}V_n.$ Define:
$$(\alpha_1,\alpha_2,\alpha_3)\in V'_n\iff(\alpha_1,\alpha_2,\alpha_3,\alpha_4)\in V_n\text{ for uncountably many }\alpha_4,$$ $$(\alpha_1,\alpha_2)\in V''_n\iff(\alpha_1,\alpha_2,\alpha_3)\in V'_n\text{ for uncountably many }\alpha_3,$$ $$\alpha_1\in V'''_n\iff(\alpha_1,\alpha_2)\in V''_n\text{ for uncountably many }\alpha_2.$$ Fix $n\in\omega$ so that $V'''_n$ is uncountable. Now choose ordinals $$\alpha_1\lt\alpha_2\lt\beta_1\lt\alpha_3\lt\beta_2\lt\gamma_1\lt\alpha_4\lt\beta_3\lt\gamma_2\lt\beta_4\lt\gamma_3\lt\gamma_4$$ so that $(\alpha_1,\alpha_2,\alpha_3,\alpha_4),(\beta_1,\beta_2,\beta_3,\beta_4),(\gamma_1,\gamma_2,\gamma_3,\gamma_4)\in V_n;$ namely, we choose $\alpha_1\in V'''_n,$ then we choose $\alpha_2\gt\alpha_1$ with $(\alpha_1,\alpha_2)\in V''_n,$ then $\beta_1\gt\alpha_2$ with $\beta_1\in V'''_n,$ then $\alpha_3\gt\beta_1$ with $(\alpha_1,\alpha_2,\alpha_3)\in V'_n,$ and so forth.

Now $(\alpha_1,\alpha_2,\alpha_3,\alpha_4),(\beta_1,\beta_2,\beta_3,\beta_4),(\gamma_1,\gamma_2,\gamma_3,\gamma_4)$ are vertices of a triangle in $G.$

Answer 2

Here is an example of a nice $K_4$-free graph on $\left(2^{2^{\aleph_0}}\right)^+$ vertices.

Let $\kappa=\left(2^{2^{\aleph_0}}\right)^+.$ By the Erdős–Rado theorem we have $\kappa\to(\aleph_0)^3_{\aleph_0}$ and so a fortiori $\kappa\to(5)^3_{\aleph_0},$ that is, for any partition of the $3$-element subsets of $\kappa$ into countably many classes, there is a
$5$-element subset of $\kappa$ whose $3$-element subsets all belong to the same class.

Define a graph $G=(V,E)$ as follows: $$V=\{(\alpha,\beta,\gamma)\in\kappa\times\kappa\times\kappa:\alpha\lt\beta\lt\gamma\},$$ $$E=\{\{(\alpha,\beta,\gamma),(\beta,\gamma,\delta)\}:\alpha\lt\beta\lt\gamma\lt\delta\}\cup\{(\alpha,\beta,\gamma),(\gamma,\delta,\epsilon)\}:\alpha\lt\beta\lt\gamma\lt\delta\lt\epsilon\}.$$ For any partition of $V$ into countably many classes, there will be a $5$-element set $\{\alpha,\beta,\gamma,\delta,\epsilon\}$ with $\alpha\lt\beta\lt\gamma\lt\delta\lt\epsilon$ such that all of its $3$-element subsets are in the same class, in particular $(\alpha,\beta,\gamma),\ (\beta,\gamma,\delta),\ (\gamma,\delta,\epsilon)$, which are vertices of a triangle in $G.$ On the other hand, you can easily verify that there is no $K_4$ in $G.$