# Introduction
See [[Coloring graphs]] for standard definitions.
>[!note] Notation
>Denote $G\to (H)_{\gamma}$ for the statement "If $E(G)$ is coloured with $\gamma$ many colours, then there is a (not necessarily spanned/induced) monochromatic copy of $H
quot;.
>In this context, $\alpha$ denotes the complete graph on $\alpha$ vertices, and $(\alpha,\beta)$ the complete bipartite graph on $\alpha,\beta$ vertices.
>[!question] Question (Hajnal)
>If $H,\gamma$ are given, for which cardinals $\kappa$ there is a graph $G$ of size $\kappa$ such that $G\to (H)_{\gamma}$ but for every subgraph $G'$ of cardinality lt;\kappa$, $G'\nrightarrow (H)_{\gamma}$.
**Theorem (Hajnal, unpublished).** If $H=(\omega,\omega)$, $\gamma=\omega$ this is true for $\kappa=\lambda^{+}$ where $\lambda$ is regular, GCH and $\square_{\lambda}$ hold.
**Theorem (Shelah).** If $\kappa=|V(G)|$ and $\mathrm{Col}(G)\leq \omega$ then $\kappa\to(G)_{n}\ (\forall n<\omega)$.
>[!note] Remark
>Subgraphs are not induced/spanned subraphs
# Basic tools
**Lemma 1.1 (Erdös and Hajnal).** For $\mu \geqslant \omega, \operatorname{Col}(G) \leqslant \mu$ if and only if there is an orientation of $G$ with out-degrees less than $\mu$, that is, there is an $f: V(G) \rightarrow[V(G)]^{<\mu}$ such that if $\{x, y\} \in G$ then either $x \in f(y)$ or $y \in f(x)$.
**Lemma 1.2 (Erdös and Hajnal).** If $|V(G)|=\kappa$ and $\operatorname{Col}(G)=\mu$, then there exists a well-ordering of $V(G)$ with the order-type $\kappa$ witnessing $\operatorname{Col}(G)=\mu$.
>[!note] Remark
>Using this lemma we usually assume that, if $|V(G)|=\kappa$ and $\operatorname{Col}(G)=\mu$, then $V(G)=\kappa$ and the ordinal order witnesses $\operatorname{Col}(G)=\mu$.
**Lemma 1.3 (Shelah, Singular cardinal compactness).** If $|V(G)|=\lambda>\operatorname{cf}(\lambda)$ and, for $G^{\prime} \subseteq G$ with $\left|G^{\prime}\right|<\lambda, \operatorname{Col}\left(G^{\prime}\right) \leqslant \mu$ holds, then $\operatorname{Col}(G) \leqslant \mu$ holds as well.
**Lemma 1.4.** Assume that $V(G)=\kappa>\omega$ is regular, and for every $G^{\prime} \subseteq G$ with $\left|G^{\prime}\right|<\kappa, \operatorname{Col}\left(G^{\prime}\right) \leqslant \mu$ holds, then $\operatorname{Col}(G) \leqslant \mu$ if and only if
$
X=X(G)=\{\alpha<\kappa: \exists \beta(\alpha) \geqslant \alpha,|\alpha \cap G(\beta(\alpha))| \geqslant \mu\}
$
is non-stationary.
# Compactness
>[!info] Definition
> If $\mu<\kappa$ are regular cardinals, then $A(\mu, \kappa)$ denotes that the following is true: there exists a sequence $\langle X(\alpha): \alpha<\kappa$, limit, $\operatorname{cf}(\alpha) \leqslant \mu\rangle$ such
> (2.1) $X(\alpha) \subseteq P(\alpha),|X(\alpha)|<\kappa$,
> (2.2) if $H \in X(\alpha)$ then $H$ is closed, unbounded in $\alpha$ ( $\operatorname{cf}(\alpha)=\omega$ is allowed),
> (2.3) if $H \in X(\alpha)$ and $\operatorname{cf}(\alpha)<\mu$ then $\operatorname{tp}(H)<\mu$,
> (2.4) if $\operatorname{cf}(\alpha)=\mu$, then $X(\alpha) \neq \varnothing$ and for $H \in X(\alpha), \operatorname{tp}(H)=\mu$,
> (2.5) if $H \in X(\alpha)$ and $\beta$ is a limit point of $H$, then $H \cap \beta \in X(\beta)$.
^komjathweakbox
>[!note] Remark
>This is very similar to the principle $\square_{\mu}(\kappa,<\kappa)$ (see [[Square principles#^general-square|general square notation]]) but there one requires $X(\alpha)$ for every limit $\alpha<\kappa$, which is impossible if $\mu^{+}<\kappa$.
Notice that $A(\mu, \kappa)$ is true if for $\alpha<\kappa, \alpha^{<\mu}<K$ holds, that is, it follows from GCH unless $\kappa=\lambda^{+}$with $\operatorname{cf}(\lambda)<\mu$, and it follows from $V=L$ in any case.
**Theorem (Komjáth).** $A(\mu, \kappa)$ for every regular $\kappa>\mu$ is consistent with the existence of a supercompact cardinal (beyond $\mu$).
**Lemma 2.1.** Assume $\kappa=\operatorname{cf}(\kappa)>\mu$. If $\mu>\omega$, assume $\mathrm{GCH}$ and $A(\operatorname{cf}(\mu), \kappa)$, as well. Let $G$ be a graph on $\kappa$ with $\operatorname{Col}(G) \geqslant \mu^{+}$ but every smaller subgraph $G^{\prime}$ having $\operatorname{Col}\left(G^{\prime}\right) \leqslant \mu$. Let $P$ be a $\mu^{+}$-[[Closed forcing|closed]] notion of forcing. Then $\operatorname{Col}(G)>\mu$ is still true after forcing with $P$. ^030680
>[!note] Remark
>If $\kappa>\omega$ and $G$ a graph on $\kappa$ with $\mathrm{Col}(G)>\omega$ but every smaller $G'\leq G$ has $\mathrm{Col}(G')\leq \omega$. If $P$ is an $\omega_{1}$-closed forcing then $\mathrm{Col}(G)>\omega$ also after forcing with $P$.
**Theorem 2.2.** If $\kappa>\mu^{+}$are cardinals and $\mathrm{cf}(\kappa)=\kappa$, then there is a generic extension in which $\kappa$ is the new $\mu^{++}$, and
1. if $\kappa$ (in the ground model) is weakly compact, then for any $G$ with $|V(G)|=\mu^{++}$ and $\operatorname{Col}(G)>\mu$, there is a $G^{\prime} \subseteq G$ with $\operatorname{Col}\left(G^{\prime}\right)=\left|V\left(G^{\prime}\right)\right|=\mu^{+}$,
2. if $\kappa$ (in the ground model) is supercompact, the following holds: for any $G$ with $\operatorname{Col}(G)>\mu$, there is a $G^{\prime} \subseteq G$ with $\operatorname{Col}\left(G^{\prime}\right)=\left|V\left(G^{\prime}\right)\right|=\mu^{+}$.
# Obligatory graphs
>[!info] Definition
> Assume that $\mu \geqslant \omega$ is a cardinal. We use the following notation:
> $A_\mu=\{f: \alpha \rightarrow \mu, \alpha<\mu, f(\beta)=0$ for all but finitely many $\beta<\alpha\}$;
> $B_\mu=\{f: \alpha \rightarrow \mu, \alpha \leqslant \mu, f(\beta)=0$ for all but finitely many $\beta<\alpha\}$;
> $C_\mu=A_\mu \times \mu^{+}$
>
> $\Gamma_\mu$ is the graph on $A_\mu \cup B_\mu$ with the edge set $\left\{\{f, g\}: f \in A_\mu, g \in B_\mu, f \subseteq g\right\};$
>$\Delta_\mu$ is the graph on $A_\mu \cup B_\mu \cup C_\mu$ with the edge-set
> $
> \Gamma_\mu \cup\left\{\{f,\langle g, \xi\rangle\}: f \subseteq g \in A_\mu, \xi<\mu^{+}\right\} .
> $
Notice that both $\Gamma_\mu$ and $\Delta_\mu$ are bipartite and $\left|\Gamma_\mu\right|=\mu,\left|\Delta_\mu\right|=\mu^{+}$.
**Theorem 3.1.** Assume that $\mu \geqslant \omega$ is a cardinal and if $\mu$ is uncountable, assume GCH and $A(\operatorname{cf}(\mu), \tau)$ for every regular $\tau$, as well. If $G$ is a graph with $\operatorname{Col}(G) \geqslant \mu^{+}$, then $\Delta_\mu \leqslant G$.
**Theorem 3.6.** If $\mu=\omega$ or $\mu>\omega$ and $V=L$ holds, then there are graphs $G, H$ with $\operatorname{Col}(G)=\operatorname{Col}(H)=\mu^{+}$ such that if $|\Gamma| \leqslant \mu, \Gamma \leqslant G$, and $\Delta \leqslant G, H$, then $\Gamma \leqslant \Gamma_\mu, \Delta \leqslant \Delta_\mu$
**Theorem 3.7.** Assume that $\mu>\omega$ is a limit cardinal and GCH holds. Let $T_\mu$ be the union of disjoint $(\alpha: \alpha)$ for $\alpha<\mu$. Then, if $\operatorname{Col}(G) \geqslant \mu, T_\mu \leqslant G$ holds; moreover, if $\Gamma$ is obligatory to the class of graphs with colouring/chromatic number at least $\mu$, then $\Gamma \leqslant T_\mu$ holds.
## Closure of the class of obligatory subgraphs
**Theorem 5.3.** Assume that $\mu$ is an infinite cardinal, and $\Gamma$ is a graph which is a subgraph of every graph $G$ with $\operatorname{Chr}(G)>\mu$. Then the graphs $\Gamma^{\prime}, \Gamma^{\prime \prime}$ also share this property, where $\Gamma^{\prime}$ is the union of $\mu^{+}$ disjoint copies of $\Gamma$, and $\Gamma^{\prime \prime}$ is made by joining every vertex $x$ of $\Gamma$ to $\mu^{+}$ new vertices, with different new vertices for each choice of $x$.