Proof. Let $(T,\leq )$ be a Suslin tree.

Define the notion of forcing $(P,\leq )$ as follows. $p\in P$ if $p=(s,g)$ where $s\in [T]^{<\omega }$ , $g\subseteq [s]^2$ , g obeys $(T,\leq )$ . $(s',g')\leq (s,g)$ iff $s'\supseteq s$ , $g=g'\cap [s]^2$ , and there are no $t_0,t_1\in s$ incomparable, $t\in s'-s$ such that $\{t,t_0\},\{t,t_1\}\in g'$ .⊣

Claim 1. $\leq $ is transitive.

Proof. Straightforward.⊣

Claim 2. If $t\in T$ , then $D_t=\{(s,g):t\in s\}$ is dense.

Proof. If $t\in T$ , $(s,g)\in P$ , then $(s\cup \{t\},g)$ is a condition and $(s\cup \{t\},g)\leq (s,g)$ .⊣

Claim 3. $(P,\leq )$ has the Knaster property.

Proof. Assume that $p_{\xi }\in P$ ( $\xi <\omega _1$ ). Using the pigeon hole principle and the ${\Delta }$ -system lemma, we can assume that $p_{\xi }=(s\cup s_{\xi },g_{\xi })$ with

$$ \begin{align*} \mathrm{ht}[s]<\mathrm{ht}[s_0]<\mathrm{ht}[s_1]<\cdots<\mathrm{ht}[s_{\xi}]<\cdots, \end{align*} $$

$g_{\xi }\cap [s]^2=g$ . If now $\xi <\eta $ , then $p'=(s',g')$ is a condition where $s'=s\cup s_{\xi }\cup s_{\eta }$ , $g'=g_{\xi }\cup g_{\eta }$ . The only possibility that $p'\leq p_{\xi },p_{\eta }$ does not hold is that there are incomparable $t_0,t_1 \in s_{\eta }$ , $t\in s_{\xi }$ , with $\{t,t_0\},\{t,t_1\}\in g'$ , which is not the case.⊣

Claim 4. $(T,\leq )$ remains Suslin in $V[G]$ .

Proof. Immediate from Claim 3.⊣

Claim 5. If $t_0,t_1\in T$ are incomparable, then $N(t_0,t_1)$ is finite.

Proof. Assume that $t_0,t_1\in T$ are incomparable. By Claim 2, there is $p=(s,g)\in G$ with $t_0,t_1\in s$ . By the definition of extension of conditions,

$$ \begin{align*} \{t\in s':\{t,t_0\},\{t,t_1\}\in g'\}=\{t\in s:\{t,t_0\},\{t,t_1\}\in g\} \end{align*} $$

holds for every $p'=(s',g')\leq p$ . But then, $N(t_0,t_1)\subseteq s$ , therefore $N(t_0,t_1)$ is finite.⊣

Claim 6. X has no uncountable independent subset.

Proof. Assume that p forces that $A\subseteq T$ is an uncountable independent set of X. For an uncountable set $B\subseteq T$ there are . Using again the pigeon hole principle and the ${\Delta }$ -system lemma, there is an uncountable $B'\subseteq B$ , such that $p_t=(s\cup s_t,g_t)$ where $g_t\cap [s]^2=g$ , $t\in s_t$ , if $t',t''\in B'$ then $\mathrm {ht}(t')\neq \mathrm {ht}(t'')$ and if $\mathrm {ht}(t')<\mathrm {ht}(t'')$ , then $\mathrm {ht}[s]<\mathrm {ht}[s_{t'}]<\mathrm {ht}[s_{t''}]$ .

As $(T,\leq )$ is a Suslin tree, there are $t',t''\in B'$ with $t'<t''$ . Define $p^*=(s^*,g^*)$ where

$$ \begin{align*} s^*=s\cup s_{t'}\cup s_{t''} \end{align*} $$

and

$$ \begin{align*} g^*=g_{t'}\cup g_{t''}\cup \{\{t',t''\}\}. \end{align*} $$

It is clear that $p^*$ is a condition. The only trouble with $p^*\leq p_{t'},p_{t''}$ could be that there are incomparable $t_0,t_1\in s_{t''}$ , $t\in s_{t'}$ with $\{t,t_0\},\{t,t_1\}\in g^*$ . As there are no such elements, we have $p^*\leq p_{t'},p_{t''}$ and so

a contradiction.

By Claims 5 and 6, the proof of the Theorem is finished.⊣

Proof. Let $(T,\leq )$ be a Suslin tree and X be a graph on T, as in Theorem 1. We claim that X is as required.

Assume that A is an uncountable subset of T. As $(T,\leq )$ is Suslin, there are incomparable $t_0,t_1\in A$ . Let

$$ \begin{align*} s=\{t_0,t_1\}\cup (N(t_0,t_1)\cap A). \end{align*} $$

The finite set s satisfies the above property (A): if $t\in A-s$ , $\{t_0,t\},\{t_1,t\}\in X$ , then $t\in N(t_0,t_1)\cap A\subseteq s$ , a contradiction. As property (B) obviously holds, we are done.⊣

Proof. We refer to a model of Theorem A. In that model, if X is a graph on $\omega _1$ not containing an uncountable independent set, then there are $A\in [\omega _1]^{\omega }$ , $B\in [\omega _1]^{\omega _1}$ with $[A]^2\subseteq X$ and

$$ \begin{align*}\{\{x,y\}:x\in A,y\in B\}\subseteq X.\end{align*} $$

We claim that $A\cup B$ does not satisfy the condition in the Problem. For that, let $s\in [A\cup B]^{<\omega }$ . If now $x\in A-s$ , then x is joined to each element of s.⊣

Proof. Enumerate $[\omega _1]^{\omega }\times [\omega ]^{\omega }$ as $\{\langle A_{\alpha },B_{\alpha }\rangle :\alpha <\omega _1\}$ . Then define the partial function F with ${\mathrm {Dom}}(F)\subseteq [\omega _1]^2$ , $\mathrm {Ran}(F)\subseteq \omega $ such that

1. (a) $F(\beta ,\alpha )\neq F(\beta ',\alpha )$ ( $\beta <\beta '<\alpha $ ) and

2. (b) if $\beta <\alpha $ is such that $A_{\beta }\subseteq \alpha $ , then there are $\gamma \in A_{\beta }$ , $n\in B_{\beta }$ with $F(\gamma ,\alpha )=n$ .

One can immediately see that $X_n=F^{-1}(n)$ ( $n<\omega $ ) are as required.⊣

Proof. Assume that $X_0,X_1,\dots $ are circuitfree graphs on $\omega _1$ . Let D be a nonprincipal ultrafilter on $\omega $ . Set $e\in X$ iff $\{n<\omega :e\in X_n\}\in D$ . X is circuitfree: should $\{e_0,\dots ,e_k\}$ be a circuit, then we had $e_0,\dots ,e_k\in X_n$ for some n, a contradiction. X is a bipartite graph on $\omega _1$ , let V be one of the uncountable bipartition classes.

If we now restrict to V and redefine it to $\omega _1$ , then we obtain that $X_0,\dots $ are circuitfree graphs on $\omega _1$ and

(*) $\{n:e\in X_n\}\notin D$ for every $e\in [\omega _1]^2$ .

Define $(s,t)\in P$ if $s\in [\omega _1]^{<\omega }$ , $t\in [\omega ]^{<\omega }$ , and s is independent in $X_n$ ( $n\in t$ ). $(s',t')\leq (s,t)$ if $s'\supseteq s$ , $t'\supseteq t$ .

By (*), for each $n<\omega $ , the set $D_n=\{(s,t):|t|>n\}$ is dense.

In order to show ccc, assume that $p_{\alpha }\in P$ ( $\alpha <\omega _1$ ). Without loss of generality, $p_{\alpha }=(s\cup s_{\alpha },t)$ where $\{s,s_{\alpha }:\alpha <\omega _1\}$ are disjoint. If $(s\cup s_{\alpha },t)$ , $(s\cup s_{\beta },t)$ are incompatible, then there is an edge of $Y=\bigcup \{X_k:k\in t\}$ between $s_{\alpha }$ and $s_{\beta }$ . Using this, one obtains that Y contains a $K_{n+1,n^2}$ where $n=|t|$ . If the edges of this $K_{n+1,n^2}$ are colored with n colors, then there is a monocolored $C_4$ , i.e., some $X_i$ contains a $C_4$ , a contradiction.

By ccc, there is $\gamma <\omega _1$ , such that if $(s,t)\in P$ , $s\cap \gamma =\emptyset $ , then for every $\gamma <\alpha <\omega _1$ there is $(s',t')\leq (s,t)$ , $s'\cap \gamma =\emptyset $ , $s'\not \subseteq \alpha $ . We can now redefine P by adding the condition $s\cap \gamma =\emptyset $ to the definition of $(s,t)\in P$ .

Finally, a standard application of $\mathrm {MA}_{\omega _1}$ gives the result.⊣

Proof. Immediate.⊣

Proof. Let $A\subseteq {}^{\kappa }2$ be a Lusin set, i.e., $|A|=\kappa ^+$ and every $B\subseteq [A]^{\kappa ^+}$ is somewhere dense in the lexicographically ordered ${}^{\kappa }2$ . Define $H(f,g)<\kappa $ as the place of the least difference of $f,g\in A$ . If $B\in [A]^{\kappa ^+}$ , then the range of H on $[B]^2$ contains an end-segment of $\kappa $ , by the Lusin property. If $g:\kappa \to \kappa $ is such that $g^{-1}(\alpha )$ is cofinal in $\kappa $ for each $\alpha <\kappa $ , then $F=g\circ H$ is as required by Lemma 6 and the above observation.⊣

Proof. Let $t_0,t_1$ , and $t_2$ be three distinct elements of T. It suffices to show that some two of $t_0\land t_1,t_0\land t_2,t_1\land t_2$ are equal. As we have $t_0\land t_1,t_0\land t_2\leq t_0$ , the nodes $t_0\land t_1$ and $t_0\land t_2$ are comparable. As we are done if they are equal, we can assume that $t_0\land t_1<t_0\land t_2$ . If $t'=t_0\land t_1$ , then $t'\leq t_1$ , $t'<t_0\land t_2\leq t_2$ . If $x,y$ are the immediate successors of $t'$ with $x\leq t_0$ , $y\leq t_1$ , then $t_1\land t_2=t'$ , and we are finished.⊣

Proof. Assume indirectly that H is nowhere dense. Let $A\subseteq T$ be a maximal antichain consisting of elements $t\in T$ such that $t\!\uparrow \cap H=\emptyset $ . As $(T,\leq )$ is $\kappa $ -Suslin, $|A|<\kappa $ , consequently, $A\subseteq T_{<\alpha }$ for some $\alpha <\kappa $ .⊣

Claim. $H\subseteq T_{<\alpha }$ .

Proof. Assume not, and so $s\in H\cap T_{\geq \alpha }$ . As $s\in H$ , we cannot have $t<s$ for some $t\in A$ . Also, $s<t$ is impossible by height considerations. Let $s'>s$ be such that $(s'\!\uparrow )\cap H=\emptyset $ (exists by the indirect assumption). As $s'$ is incomparable by any element of A, $A\cup \{s'\}$ would properly extend A, a contradiction.

As by the Claim $|H|<\kappa $ holds, we have reached the desired contradiction.⊣

Proof. Let $(T,\leq )$ be a normal $\kappa $ -Suslin tree. Set $F_0(t_0,t_1)=\mathrm {ht}(t_0\land t_1)$ . Let $g:\kappa \to \kappa $ be such that $|g^{-1}(\alpha )|=\kappa $ ( $\alpha <\kappa $ ). We claim the $F=g\circ F_0$ is as required. F has no three-colored triangle by Lemmas 6 and 8.

In order to prove that F establishes $T\not \to [\kappa ]^2_{\kappa }$ , let $H\in [T]^{\kappa }$ .⊣

Claim. $\mathrm {Ran}(F_0|[H]^2)$ contains an end segment of $\kappa $ .

Proof. By Lemma 9, H is somewhere dense, say, above $t\in T$ . Set $\alpha =\mathrm {ht}(t)$ . As T is normal, if $\gamma>\alpha $ , there is $t'>t$ , $\mathrm {ht}(t')=\gamma $ . Let $t_0,t_1$ be two immediate successors of $t'$ (exist, as T is normal). As H is dense above t, there are $x_0>t_0$ , $x_1>t_1$ , $x_0,x_1\in H$ . Now $F_0(x_0,x_1)=\mathrm {ht}(x_0\land x_1)=\mathrm {ht}(t')=\gamma $ .

As we proved that $(\alpha ,\kappa )\subseteq \mathrm {Ran}(F_0|[H]^2)$ , we are done.

By the definition of g, g assumes every value of $(\alpha ,\kappa )$ , we are finished.⊣

Proof. By Shelah’s theorem [Reference Todorcevic4], in the forced model there is a $\kappa ^+$ -Suslin tree and so we can apply Theorem 10.⊣

Proof. Let F be as in the Theorem. Set $h(\alpha )=\{F(\alpha ,\beta ):\alpha <\beta <\kappa \}$ for $\alpha <\kappa $ .⊣

Claim 1. $|h(\alpha )|<\kappa (\alpha <\kappa )$ .

Proof. Otherwise pick $\alpha <\beta _i$ for $0<i\in h(\alpha )$ such that $F(\alpha ,\beta _i)=i$ . If $i\neq j$ , then, as $F(\alpha ,\beta _i)=i$ and $F(\alpha ,\beta _j)=j$ , necessarily $F(\beta _i,\beta _j)\in \{i,j\}$ (as otherwise $\{\alpha ,\beta _i,\beta _j\}$ formed a three-colored triangle). This implies that F restricted to $\{\beta _i:i\in h(\alpha )-\{0\}\}$ misses color 0, a contradiction.⊣

Claim 2. $\bigcup \{V(t):t\in T_{\alpha }\}=\kappa -\{p(t):t\in T_{<\alpha }\}$ .

Proof. By induction on $\alpha $ , immediately from the definition.⊣

Claim 3. If $t\in T_{\alpha }$ , then $|\{t'<T_{\alpha +1}:t<t'\}|<\kappa $ .

Proof. As $|h(p(t))|<\kappa $ .⊣

Claim 4. $|T_{\alpha }|<\kappa $ ( $\alpha <\kappa $ ).

Proof. By induction on $\alpha $ . If this holds for $\alpha $ , then $T_{\alpha +1}$ is the union of $<\kappa $ sets each of size $<\kappa $ by Claim 3 and we are finished as $\kappa $ is regular.

Assume that $\alpha <\kappa $ is limit and we have the Claim for all $\beta <\alpha $ . Then $|T_{<\alpha }|<\kappa $ as $\kappa $ is regular. Assume indirectly that $|T_{\alpha }|=\kappa $ . Consider the set $P=\{p(t):t\in T_{\alpha }\}$ . If $t_0,t_1\in T_{\alpha }$ , then there are a $\beta <\alpha $ and $t\in T_{\beta }$ and there are $t^{\prime }_0,t^{\prime }_1\in T_{\beta +1}$ such that $t<t^{\prime }_0<t_0$ , $t<t^{\prime }_1<t_1$ and so by the construction

$$ \begin{align*} F(p(t_0),p(t_1))\in\left\{F(p(t),p(t^{\prime}_0)),F(p(t),p(t^{\prime}_1))\right\}. \end{align*} $$

Consequently, the values of F on $[P]^2$ are of the form $F(p(t),p(t'))$ for some $t<t'\in T_{<\alpha }$ and there are $<\kappa $ such possibilities by the inductive hypothesis, i.e., F misses some values on $[P]^2$ , contradicting our condition on F.⊣

Claim 5. $(T,\leq )$ has no $\kappa $ -branch.

Proof. Assume indirectly that $b=\{t_{\alpha }:\alpha <\kappa \}$ is a $\kappa $ -branch with $t_{\alpha }\in T_{\alpha }$ ( $\alpha <\kappa $ ). By the way we constructed T, we have $t_{\alpha }=g|\alpha $ for some function $g:\kappa \to \kappa $ . Further, $F(p(t_{\beta }),p(t_{\alpha }))=g(\beta )$ for $\beta <\alpha $ , i.e., the branch is end-homogeneous. There is some $i<\kappa $ such that $|\kappa -g^{-1}(i)|=\kappa $ and then the set $\{p(t_{\alpha }):g(\alpha )\neq i\}$ has cardinality $\kappa $ and it misses color i, a contradiction.

As by Claims 2, 4, and 5 $(T,\leq )$ is a $\kappa $ -Aronszajn tree, the proof is complete.⊣