#graphs #coloring_graphs #definition **Def.** The *Shift graph* on a set $A\subseteq \mathrm{Ord}^{2}$ is the restriction of the relation $ \mathsf{Shift}= \{ \{ \{ \alpha,\beta \} , \{ \beta,\gamma \}\} \mid \alpha<\beta<\gamma\ \text{ are ordinals} \} $ **Theorem.** For every $A\subseteq \mathrm{Ord}^{2}$, the [[Coloring graphs#The Chromatic number|chromatic number]] of the shift graph is $ \mathrm{Chr}(A,\mathsf{Shift})=\min \{ \kappa \mid 2^{\kappa}\geq |A|\} $ Recall ![[Partition property#^Erdos-rado]] I.e. for every $f:[\beth_{n}(\kappa)^{+}]^{n+1} \to \kappa$ there is a homogeneous set of size $\kappa ^{+}$. In particular, the case $n=1$ means that $(2^{\kappa})^{+} \to (\kappa ^{+})^{2}_{\kappa}$ *Proof of theorem.* Assume $A\subseteq [\lambda]^{2}$, let $\kappa$ such that $2^{\kappa}<|A|$ and assume there is a chromatic coloring $f:A\to \kappa$. By the Erdős-Rado theorem, there is an $f$-homogeneous $H\subseteq \lambda$ of size $\kappa ^{+}$ . So we can find $\alpha,\beta, \gamma \in H$ such that $\{\alpha,\beta\},\{ \beta,\gamma\}\in A$, by contradiction. Now let $\kappa$ such that $2^{\kappa}\geq |A|$, let $\{ X_{\alpha} \mid \alpha\in \bigcup A \}$ be pairwise incomparable subsets of $\kappa$, and set $c(\{\alpha,\beta\})=\min (X_{\alpha}\smallsetminus X_{\beta})$ when $\alpha<\beta$. Then if $\alpha<\beta<\gamma$ then $c(\{\beta,\gamma\})\in X_{\beta}$ and so is different than $c(\{\alpha,\beta\})$.