# Barrier and finite size effects on the extension of topological surface-
states into magnetic insulators

Eirik Holm Fyhn  Center for Quantum Spintronics, Department of Physics,
Norwegian
University of Science and Technology, NO-7491 Trondheim, Norway  Hendrik
Bentmann  Center for Quantum Spintronics, Department of Physics, Norwegian
University of Science and Technology, NO-7491 Trondheim, Norway  Jacob Linder
Center for Quantum Spintronics, Department of Physics, Norwegian
University of Science and Technology, NO-7491 Trondheim, Norway

###### Abstract

The interplay between magnetic and topological order can give rise to
phenomena such as the quantum anomalous Hall effect. The extension of
topological surface states into magnetic insulators (MIs) has been proposed as
an alternative to using intrinsically magnetic topological insulators (TIs).
Here, we theoretically study how this extension of surface states into a
magnetic insulator are influenced both by the interface barrier potential
separating a topological insulator and a magnetic insulator and by finite size
effects in such structures. We find that the the gap in the surface states
depends non-monotonically on the barrier strength. A small, but finite,
barrier potential turns out to be advantageous as it permits the surface
states to penetrate even further into the MI. Moreover, we find that due to
finite size effects in thin samples, increasing the spin-splitting in the MI
can actually decrease the gap of the surface states, in contrast to the usual
expectation that the gap opens as the spin-splitting increases.

##  I Introduction

Topological insulators (TIs) are materials that are insulating in the bulk and
have topologically protected conducting surface states [1, 2, 3]. Combining
the topological properties of TIs with magnetic order can give rise to the
quantum anomalous hall effect (QAHE) as a result of broken time-reversal
symmetry in the TI [4, 3, 5, 6, 7], which could have applications in low-
dissipation spintronics devices. Magnetic TIs are also discussed as an avenue
to the realization of Majorana quasi-particles with potential relevance for
implementations of quantum-computation platforms [6]. The first observation of
the QAHE was in 2013, where the effect was achieved by doping a TI with
magnetic impurities [8, 9]. However, achieving QAH resistance quantization at
zero magnetic field has remained limited to temperatures of the order of tens
of mK in these systems, which was explained by thermally activated bulk
conductance [10]. An interesting alternative way to produce the QAHE would be
to use an intrinsic magnetic TI, such as the van der Waals magnet MnBi2Te4
[11]. Yet, while signatures of the QAHE were reported in thin exfoliated
flakes of odd-layer thickness [12], the antiferromagnetic order in MnBi2Te4,
in general, does not provide ideal prerequisites for a robust QAHE.

Another approach to break time-reversal symmetry at the surface of a TI is to
proximize the TI to a magnetic insulator (MI) [3]. This should induce an
exchange gap in the Dirac cone of the topological surface state. Various TI-MI
heterostructures have been investigated experimentally [13], but the
observation of magnetic topological behavior and of an exchange gap in the
surface state has remained challenging. More recently, it has been proposed
that the topological surface state can be extended into the MI in van der
Waals heterostructures with weak potential modulation at the interface [14,
15]. That is, instead of inducing a weak magnetization at the surface of the
TI, interface effects give rise to a relocation of the surface state from the
TI into the MI. This ferromagnetic extension requires similar atomic
structures for the TI and MI. Compared to a mere proximity effect, such
relocation of the surface state into the MI would drastically enhance the
exchange gap [14, 15]. A ferromagnetic extension was experimentally achieved
in Bi2Te3/MnBi2Te4 heterostructures [16], where it was possible to observe an
exchange gap in the surface state up to the critical temperature of 15 K.

Here we theoretically study how the topological surface states in TI/MI
heterostructures are affected by the barrier potential at the TI/MI interface,
the magnitude of the spin-splitting, and finite size effects due to the finite
thickness of the materials. We find that the energy gap of the surface states
has a non-monotonic dependence on the barrier strength. Below a critical
value, the barrier potential actually turns out to be advantageous as it
permits the surface states to penetrate further into the MI compared to an
ideal, barrier-free interface. In addition, we find that due to finite size
effects in thin samples, an increase in the spin-splitting in the MI can
diminish the gap of the surface states at certain thicknesses. This stands in
contrast to the usual expectation that the gap opens as the spin-splitting
increases. These results might prove useful for optimizing experimental
efforts aiming to achieve extension of topological surface states into a time-
reversal symmetry-breaking magnetic environment.

##  II Model

To model the TI/MI bilayer we adopt an effective 4-band low-energy model [17]
for momenta near the $\Gamma$ point,

$H=\varepsilon_{k}+V+\begin{pmatrix}M_{k}\tau_{z}+A_{k}\tau_{x}+h&B_{k}\tau_{x}\\\
B_{k}^{*}\tau_{x}&M_{k}\tau_{z}-A_{k}\tau_{x}-h\end{pmatrix},$ (1)

where the basis is a set of four orbitals,

$\Psi=\begin{pmatrix}\lvert P1_{z}^{+},\uparrow\rangle&\lvert
P2_{z}^{-},\uparrow\rangle&\lvert P1_{z}^{+},\downarrow\rangle&\lvert
P2_{z}^{-},\downarrow\rangle\end{pmatrix}^{T},$ (2)

For simplicity, we have assumed the same $g$-factor for both orbitals in Eq.
1.

The parameters $\varepsilon_{k}$, $M_{k}$, $A_{k}$, and $B_{k}$ are functions
of momentum parallel to the interface, $k_{\parallel}$ and momentum orthogonal
to the interface, $k_{z}$. As the translational symmetry is broken in the
direction orthogonal to the interface, we perform a Peierls substitution,
$k_{z}\to-i\partial_{z}$. With this,

$\displaystyle\varepsilon_{k}$
$\displaystyle=C_{0}(z)+\frac{1}{2}\left\\{C_{1}(z),\,(-i\partial_{z})^{2}\right\\}+C_{2}(z)k_{\parallel}^{2},$
(3a) $\displaystyle M_{k}$
$\displaystyle=M_{0}(z)+\frac{1}{2}\left\\{M_{1}(z),\,(-i\partial_{z})^{2}\right\\}+M_{2}(z)k_{\parallel}^{2},$
(3b) $\displaystyle A_{k}$
$\displaystyle=\frac{1}{2}\left\\{A_{1}(z),\,-i\partial_{k}\right\\},$ (3c)
$\displaystyle B_{k}$ $\displaystyle=B_{1}(z)(k_{x}+ik_{y}),$ (3d)

where $\\{C_{j},M_{j},A_{1},B_{1}\\}$ are material specific parameters and
$j\in\\{0,1,2\\}$. The anticommutators are added to ensure that the
Hamiltonian is Hermitian. We let the interface be located at $z=0$ and to
allow for a smooth numerical solution we use a sigmoid function,

$\theta(z)=\frac{1}{1+\mathrm{e}^{-x/$0.14\text{\,}\mathrm{\SIUnitSymbolAngstrom}$}},$
(4)

to define the transition between the TI and the MI that extends over a length
of around $1\text{\,}\mathrm{\SIUnitSymbolAngstrom}$. That is,

$M_{0}(z)=M_{0}^{L}(1-\theta(z))+M_{0}^{R}\theta(z),$ (5)

and similarly for all the other parameters, where
$\\{C_{j}^{L},M_{j}^{L},A_{1}^{L},B_{1}^{L}\\}$ is the set of material
parameters for the TI and $\\{C_{j}^{R},M_{j}^{R},A_{1}^{R},B_{1}^{R}\\}$ is
the set of material parameters for the MI. Additionally, Eq. 1 includes the
Zeeman exchange energy

$h(z)=h_{0}\theta(z),$ (6)

and a potential barrier

$V(z)=V_{0}(\partial_{z}\theta)(z).$ (7)

Note that

$\int_{-\infty}^{\infty}\mathrm{d}z\,V(z)=V_{0}$ (8)

by construction.

For the TI we choose parameters that correspond to Bi2Se3, meaning that
$C_{0}^{L}=$-6.8\text{\times}{10}^{-3}\text{\,}\mathrm{eV}$$,
$C_{1}^{L}=$1.3\text{\,}\mathrm{eV}\text{\,}{\mathrm{\SIUnitSymbolAngstrom}}^{2}$$,
$C_{2}^{L}=$19.6\text{\,}\mathrm{eV}\text{\,}{\mathrm{\SIUnitSymbolAngstrom}}^{2}$$,
$M_{0}^{L}=$0.28\text{\,}\mathrm{eV}$$,
$M_{1}^{L}=$-10\text{\,}\mathrm{eV}\text{\,}{\mathrm{\SIUnitSymbolAngstrom}}^{2}$$,
$M_{2}^{L}=$-56.6\text{\,}\mathrm{eV}\text{\,}{\mathrm{\SIUnitSymbolAngstrom}}^{2}$$,
$A_{1}^{L}=$2.2\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
and
$B_{1}^{L}=$4.1\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$.
We vary the parameters of the MI, but set
$C_{0}^{R}=$-4.8\text{\times}{10}^{-3}\text{\,}\mathrm{eV}$$,
$C_{1}^{R}=$2.7232\text{\,}\mathrm{eV}\text{\,}{\mathrm{\SIUnitSymbolAngstrom}}^{2}$$,
$C_{2}^{R}=$17\text{\,}\mathrm{eV}\text{\,}{\mathrm{\SIUnitSymbolAngstrom}}^{2}$$,
$M_{1}^{R}=$-11.9048\text{\,}\mathrm{eV}\text{\,}{\mathrm{\SIUnitSymbolAngstrom}}^{2}$$,
$M_{2}^{R}=$-9.4048\text{\,}\mathrm{eV}\text{\,}{\mathrm{\SIUnitSymbolAngstrom}}^{2}$$,
$A_{1}^{R}=$2.7023\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
and
$B_{1}^{R}=$3.1964\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$
fixed. These values correspond to MnBi2Te4 in the antiferromagnetic state
[18]. We also set $k_{y}=0$, such that $k_{\parallel}=k_{x}$. We denote by
$L_{TI}$ and $L_{MI}$ the lengths of the TI and MI respectively.

To numerically determine eigenstates and eigenvalues of the Hamiltonian, we
discretize the wave functions in space and approximate derivatives by finite
differences. In order to ensure sufficient resolution at the interface we also
perform a substitution $\zeta=f(z)$ and discretize $\zeta$ such that a uniform
$\zeta$-grid correspond to a high density of discretization points near $z=0$.

##  III Magnetic extension of surface states

First, we consider how the magnetic extension of surface states varies as a
function of $M^{R}_{0}$. Figure 1 shows the penetration depth,

$\langle
z\rangle=\int_{-L_{TI}}^{L_{MI}}\mathrm{d}z\,z\lvert\psi(z)\rvert^{2},$ (9)

where $\psi$ is the wave function corresponding to a surface state. We set
$k_{x}=0$ when evaluating wave functions of surface states. At $h_{0}=0$ and
$k_{x}=0$ the Hamiltonian is block-diagonal and the two blocks are related
through time-reversal. Therefore, the eigenfunctions come in pairs that are
related through time reversal. For this reason, there are two surface states
at both surfaces of the TI. The two surface states are no longer Kramer pairs
when $h\neq 0$, but we find that they have similar penetration depth and
spatial distribution for the parameters in Fig. 1. Therefore, although Fig. 1
only shows the penetration depth of one of the surface states, the results are
similar for the other surface state.

Figure 1: (a) Penetration depth, $\langle z\rangle$, associated with the
surface states as a function of $M_{0}^{R}$ with
$h_{0}=$0.1\text{\,}\mathrm{eV}$$, $V_{0}=0$,
$L_{TI}=$10\text{\,}\mathrm{nm}$$ and $L_{MI}=$13.7\text{\,}\mathrm{nm}$$. (b)
The square amplitude of the interfacial surface state at a selection of
$M_{0}^{R}$ values and the same parameters as in (a).

Figure 1 shows a sudden jump in $\langle z\rangle$ as $M_{0}^{R}$ crosses $0$.
This is reasonable because $M_{0}^{R}=0$ marks the transition from
topologically trivial ($M_{0}^{R}/M_{2}^{R}>0$) to topologically nontrivial
($M_{0}^{R}/M_{2}^{R}<0$). The MI is topologically trivial when $M_{0}^{R}<0$,
and the surface state is therefore located at the interface between the TI and
the MI at $z=0$. As $\lvert M_{0}^{R}\rvert$ is reduced, the bulk gap is
reduced and therefore energy difference between the surface states and the
bulk states is reduced. This leads to the surface states becoming more
delocalized until the state is fully delocalized inside the MI when
$M_{0}^{R}=0$. As $M_{0}^{R}$ is increased further, the surface state again
becomes more localized, but now it centers around the interface between the MI
and vacuum because the MI is also topologically nontrivial [3]

Figure 2 shows the energy spectra for different values of $V_{0}$, and with
the remaining parameters fixed at $L_{TI}=L_{MI}=$50\text{\,}\mathrm{nm}$$,
$M_{0}^{R}=$-0.5\text{\,}\mathrm{eV}$$ and $h_{0}=$50\text{\,}\mathrm{meV}$$.
For all values of $V_{0}$, there are four energy bands inside the bulk gap.
The two that cross around $E=0$ come from the topological surface states at
$z=-L_{TI}$ and are therefore unaffected by the interface potential
proportional to $V_{0}$. The two remaining surface states are gapped at
$k_{x}=0$, but this gap has an interesting, nonmonotonic dependence on
$V_{0}$. The interfacial surface states corresponding to $k_{x}=0$ are shown
in Fig. 3 for the same parameters as in Fig. 2.

As $V_{0}$ is increased, both of the energy bands corresponding to the
interfacial surface states are shifted upwards in energy. Simultaneously, the
gap is also increased. In Fig. 2(a), the gap between the interfacial surface
states is $23\text{\,}\mathrm{meV}$, and the gap in Fig. 2(b) is
$31\text{\,}\mathrm{meV}$. This increase can be understood from the fact that
the wave function is slightly shifted into the MI as $V_{0}$ increases. As the
interfacial surface state bands are shifted into the region bulk conduction
bands, new energy bands emerge from the valence bands.

Figure 2: Energy spectra for TI/MI heterostructures with
$L_{TI}=L_{MI}=$50\text{\,}\mathrm{nm}$$,
$M_{0}^{R}=$-0.5\text{\,}\mathrm{eV}$$, $h_{0}=$50\text{\,}\mathrm{meV}$$, and
(a) $V_{0}=$0\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(b) $V_{0}=$0.3\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(c) $V_{0}=$0.35\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(d) $V_{0}=$0.4\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(e) $V_{0}=$0.6\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(f) $V_{0}=$10\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$.
The blue lines correspond to the surface states at $z=-L_{TI}$.

This transition can be seen in Fig. 2(b)-(e), where two new energy bands
emerge into the bulk gap from below while the two energy bands corresponding
to the initial surface states leave the gap. As the new states enter the bulk
gap from the valence band, they also become localized at the interface, as can
be seen in Fig. 3. Moreover, the initial surface states become delocalized as
$V_{0}$ increases, and their energies are shifted into the conduction band. In
other words, as $V_{0}$ increases, the surface states are shifted into the MI
and are replaced by new surface states. These new states seem to emerge from
TI bulk states and they remain more localized in the TI side of the interface.
As a result, the energy gap associated with these states is much smaller. As
$V_{0}$ is increased further, the surface states are pushed further into the
TI, reducing the energy gap even more. This is as expected since the TI and MI
should become decoupled as $V_{0}\to\infty$. From Fig. 2(f), we can see that
the energy bands corresponding to the interfacial surface states start to
overlap with the energy bands associated with the surface states at
$z=-L_{TI}$.

These results indicate that the interfacial barrier potential must be smaller
than some cutoff in order to get an appreciable gap induced by the MI. This
can explain why it has been challenging to observe gaps in TI/MI
heterostructures before the introduction of lattice-matched van der Waals
structures. Interestingly, a small interfacial potential can be advantageous,
as it increases the energy gap and shifts the surface state further into the
MI.

Figure 3: Interfacial surface states in TI/MI heterostructures with
$L_{TI}=L_{MI}=$50\text{\,}\mathrm{nm}$$,
$M_{0}^{R}=$-0.5\text{\,}\mathrm{eV}$$, $h_{0}=$50\text{\,}\mathrm{meV}$$, and
(a) $V_{0}=$0\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(b) $V_{0}=$0.3\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(c) $V_{0}=$0.35\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(d) $V_{0}=$0.4\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(e) $V_{0}=$0.6\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(f) $V_{0}=$10\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$.

##  IV Finite size effects

Next, we consider how the ferromagnetically extended surface states at $z=0$
interact with the topological surface states at $z=-L_{TI}$ when $L_{TI}$ is
small. We let $L_{TI}=L_{MI}$ and determine the energy gap, $\Delta$, as a
function of $L=L_{TI}+L_{MI}$. The result is shown in Fig. 4 together with the
spectrum at some values of $L$. The gap closes and reopens as a function of
$L$, similar to the gap in pure Bi2Se3 [19, 20, 21]. This is not surprising,
as the TI is Bi2Se3 in our model. However, unlike the gap in Bi2Se3, the
values of $L$ for which the gap closes are not uniformly spaced in Fig. 4(a).

Figure 4: (a) Energy gap $\Delta$ i TI/MI bilayers as a function of
$L=L_{TI}+L_{MI}$ with $L_{TI}=L_{MI}$,
$M_{0}^{R}=$-0.2\text{\,}\mathrm{eV}$$, $h_{0}=$100\text{\,}\mathrm{meV}$$,
and $V_{0}=$0\text{\,}\mathrm{eV}\text{\,}\mathrm{\SIUnitSymbolAngstrom}$$,
(b) The energy spectrum for some values of $L$, illustrating that the gap
closes and reopens at $L=$4.0837\text{\,}\mathrm{nm}$$.

For more insight into why the ferromagnetically extended surface states give
rise to nonuniformly spaced roots in the gaps, we study how an additional
uniform exchange field affects the finite size effects in pure Bi2Se3. That
is, we set $L_{MI}=0$ and let the exchange field $h$ act also on the TI side.
The result is shown in Fig. 5. When $h=0$ the roots are uniformly spaced as
expected. However, as $h$ increases, the roots split, leaving a nonuniform
spacing between roots. We find that the gap as a function of $h$ in Fig. 5
satisfies

$\Delta(h)=\lvert\Delta(0)-2h\rvert.$ (10)

This can be understood by how the exchange field splits the two energy bands.
At $h=0$, the gapped energy bands are also spin-degenerate because of the
symmetries of the Hamiltonian, as explained above. That is, there are two
states with energies $E_{1}$ below the gap and two states with $E_{2}$ above
the gap, such that $E_{2}-E_{1}=\Delta(0)$. As $h$ is increased, each of the
bands is split such that the four states have energies $E_{1}\pm h$ and
$E_{2}\pm h$. Hence, the gap is $\Delta(h)=E_{2}-h-(E_{1}+h)=\Delta(0)-2h$.

The splitting of the roots in TI/MI heterostructures is similar, although
there are some important differences. In particular, Eq. 10 is not true for
the TI/MI structures. While the gap in pure magnetic TIs goes to $2h$, the gap
in the TI/MI structures goes to 0 as $L\to\infty$. Moreover, because the gap
amplitude is much smaller near the second root in the pure TIs, the second
root is split much more as a function of $L_{TI}$ when the exchange field is
applied compared to the first root. In contrast, the difference between the
third and fourth roots in Fig. 4 is not much larger than the difference
between the first and second roots.

In both cases, it is interesting to note that, depending on the sample length,
the gap can actually be reduced or even closed by increasing $h$. This means
that, although one usually expects the gap to open when reducing the
temperature and going from the paramagnetic phase to the ferromagnetic phase,
the opposite can happen in thin samples.

Figure 5: Energy gap in Bi2Se3 with an added constant spin splitting field $h$
as a function of $L_{TI}$.

##  V Conclusion

Summarizing, we have studied the effects of a (i) finite barrier and (ii)
finite thickness on the surface states of a topological insulator/magnetic
insulator (TI/MI) bilayer, as well as the effect of (ii) on an intrinsic
topological magnetic insulator. We find that the energy gap of the surface
states has a non-monotonic dependence on the barrier strength. Below a
critical value, the barrier potential permits the surface states to extend
further into the MI compared to a barrier-free interface. We also find that
due to finite size effects in thin samples, an increase in the spin-splitting
in the MI can diminish the gap of the surface states at certain thicknesses.
This stands in contrast to the usual expectation that the gap opens as the
spin-splitting increases. We hope these findings may be of use in terms of
designing experiments aiming to realize extension of topological surface
states into a magnetic material.

###### Acknowledgements.

This work was supported by the Research Council of Norway through Grant No.
323766 and its Centres of Excellence funding scheme Grant No. 262633 “QuSpin.”
Support from Sigma2 - the National Infrastructure for High-Performance
Computing and Data Storage in Norway, project NN9577K, is acknowledged.

## References

  * König  _et al._ [2007] M. König, S. Wiedmann, C. Brüne, A. Roth, H. Buhmann, L. W. Molenkamp, X. Qi, and S. Zhang, Science 318, 766 (2007).
  * Hasan and Kane [2010] M. Z. Hasan and C. L. Kane, Rev. Mod. Phys. 82, 3045 (2010).
  * Qi and Zhang [2011] X.-L. Qi and S.-C. Zhang, Rev. Mod. Phys. 83, 1057 (2011).
  * Yu  _et al._ [2010] R. Yu, W. Zhang, H.-J. Zhang, S.-C. Zhang, X. Dai, and Z. Fang, Science 329, 61 (2010).
  * Nomura and Nagaosa [2011] K. Nomura and N. Nagaosa, Phys. Rev. Lett. 106, 166802 (2011).
  * Tokura  _et al._ [2019] Y. Tokura, K. Yasuda, and A. Tsukazaki, Nat. Rev. Phys. 1, 126 (2019).
  * Bernevig  _et al._ [2022] B. A. Bernevig, C. Felser, and H. Beidenkopf, Nature 603, 41 (2022).
  * Chang  _et al._ [2013] C.-Z. Chang, J. Zhang, X. Feng, J. Shen, Z. Zhang, M. Guo, K. Li, Y. Ou, P. Wei, L.-L. Wang, Z.-Q. Ji, Y. Feng, S. Ji, X. Chen, J. Jia, X. Dai, Z. Fang, S.-C. Zhang, K. He, Y. Wang, L. Lu, X.-C. Ma, and Q.-K. Xue, Science 340, 167 (2013).
  * Chang  _et al._ [2015] C.-Z. Chang, W. Zhao, D. Y. Kim, H. Zhang, B. A. Assaf, D. Heiman, S.-C. Zhang, C. Liu, M. H. W. Chan, and J. S. Moodera, Nat. Mater 14, 473 (2015).
  * Fijalkowski  _et al._ [2021] K. M. Fijalkowski, N. Liu, P. Mandal, S. Schreyeck, K. Brunner, C. Gould, and L. W. Molenkamp, Nat. Comm. 12, 5599 (2021).
  * Otrokov  _et al._ [2019] M. M. Otrokov, I. I. Klimovskikh, H. Bentmann, D. Estyunin, A. Zeugner, Z. S. Aliev, S. Gaß, A. U. B. Wolter, A. V. Koroleva, A. M. Shikin, M. Blanco-Rey, M. Hoffmann, I. P. Rusinov, A. Y. Vyazovskaya, S. V. Eremeev, Y. M. Koroteev, V. M. Kuznetsov, F. Freyse, J. Sánchez-Barriga, I. R. Amiraslanov, M. B. Babanly, N. T. Mamedov, N. A. Abdullayev, V. N. Zverev, A. Alfonsov, V. Kataev, B. Büchner, E. F. Schwier, S. Kumar, A. Kimura, L. Petaccia, G. Di Santo, R. C. Vidal, S. Schatz, K. Kißner, M. Ünzelmann, C. H. Min, S. Moser, T. R. F. Peixoto, F. Reinert, A. Ernst, P. M. Echenique, A. Isaeva, and E. V. Chulkov, Nature 576, 416 (2019).
  * Deng  _et al._ [2020] Y. Deng, Y. Yu, M.-Z. Shi, Z. Guo, Z. Xu, J. Wang, X. Chen, and Y. Zhang, Science 367, 895 (2020).
  * Liu and Hesjedal [2023] J. Liu and T. Hesjedal, Advanced Materials 35, 2102427 (2023).
  * Otrokov  _et al._ [2017a] M. M. Otrokov, T. V. Menshchikova, M. G. Vergniory, I. P. Rusinov, A. Y. Vyazovskaya, Y. M. Koroteev, G. Bihlmayer, A. Ernst, P. M. Echenique, A. Arnau, _et al._ , 2D Mater. 4, 025082 (2017a).
  * Otrokov  _et al._ [2017b] M. Otrokov, T. V. Menshchikova, I. Rusinov, M. Vergniory, V. M. Kuznetsov, and E. V. Chulkov, JETP Lett. 105, 297 (2017b).
  * Kagerer  _et al._ [2023] P. Kagerer, C. I. Fornari, S. Buchberger, T. Tschirner, L. Veyrat, M. Kamp, A. V. Tcakaev, V. Zabolotnyy, S. L. Morelhão, B. Geldiyev, S. Müller, A. Fedorov, E. Rienks, P. Gargiani, M. Valvidares, L. C. Folkers, A. Isaeva, B. Büchner, V. Hinkov, R. Claessen, H. Bentmann, and F. Reinert, Phys. Rev. Res. 5, L022019 (2023).
  * Zhang  _et al._ [2009] H. Zhang, C.-X. Liu, X.-L. Qi, X. Dai, Z. Fang, and S.-C. Zhang, Nat. Phys. 5, 438 (2009).
  * Zhang  _et al._ [2019] D. Zhang, M. Shi, T. Zhu, D. Xing, H. Zhang, and J. Wang, Phys. Rev. Lett. 122, 206401 (2019).
  * Linder  _et al._ [2009] J. Linder, T. Yokoyama, and A. Sudbø, Phys. Rev. B 80, 205401 (2009).
  * Liu  _et al._ [2010] C.-X. Liu, H. Zhang, B. Yan, X.-L. Qi, T. Frauenheim, X. Dai, Z. Fang, and S.-C. Zhang, Phys. Rev. B 81, 041307 (2010).
  * Lu  _et al._ [2010] H.-Z. Lu, W.-Y. Shan, W. Yao, Q. Niu, and S.-Q. Shen, Phys. Rev. B 81, 115407 (2010).


# Borel Colouring Bad Sequences

Keegan Dasilva Barbosa

###### Abstract

Every better quasi-order codifies a Borel graph that does not contain a copy
of the shift graph. It is known that there is a better quasi-order that codes
a Borel graph with infinite Borel chromatic number, though one has yet to be
explicitly constructed. In this paper, we show that examples cannot be
constructed via standard methods. Moreover, we show that most of the known
better quasi-orders are non-examples, suggesting there is still a class of
better quasi-orders with interesting combinatorial properties who’s
elements/members still remain unknown.

##  1 Introduction

In [8], it was discovered that there is a graph with uncountable Borel
chromatic number which is minimal with respect to Borel graph homomorphism. It
was then questioned whether or not the shift graph was minimal in this regard
in the class of Borel graphs generated by a single Borel function.
Interestingly, Pequignot showed in [17] that the shift graph contained a Borel
subgraph with infinite Borel chromatic number, but could not embed the shift
graph in a Borel manner. These graphs were codified by better quasi-orders
(BQO). Further work was done by Todorcevic and Vidnyanszky, and it was further
proved that no finite basis could exist, let alone a singular minimal element
[19]. However, there is a deep question that still remains unanswered in [17].
While it is known a BQO can codify a graph with infinite Borel chromatic
number, by the nature of the proof relying on a complexity argument of Marcone
[13],a concrete BQO has yet to be identified or explicitly constructed. There
were some conjectures made by Pequignot. In this paper, we show that these
BQOs fail to codify a graph with infinite Borel chromatic number. Moreover, we
show that a BQO recursively constructed from simpler BQOs by the classical
means of labeling trees or linear orders [10] [11] [18] also fails to produce
graphs with infinite Borel chromatic number. As a consequence, even any
countable collection of $\sigma$-scattered linear orders under the embedding
relation fails to be complex enough to code a graph with infinite Borel
chromatic number. This suggests there is still a wealth of BQOs with strong
indecomposability properties that have yet to be explicitly constructed.

This paper will be split into two sections excluding introduction and
acknowledgements. Section 2 will be focused on the necessary background
information required to understand the problem. This includes the basics of
Borel graph combinatorics, BQO theory, and the primary tools and techniques
used in these fields. It is suggested a reader skips through the parts of this
section they are familiar with. If one wants a deeper understanding of these
materials, the author suggests any of the following texts [5] [7] [9]
[14][12]. However, section 2.5 should not be skipped. It contains important
definitions specialized for this problem, as well as a very important lemma.
Section 3 is split into three components. Section 3.1 is where we will
introduce the colouring algorithm that will allow us to effectively Borel
$3$-colour graphs by splitting them into homogeneous pieces that are easy to
handle. Section 3.2 will be where we prove that if $Q$ codes a Borel
$3$-colourable graph (we call such $Q$ thin), then so does $Q^{<\omega}$ under
the Higman order [4]. Consequently, the same will be true of finite trees
labelled by members of $Q$, $\mathcal{FT}_{Q}$, under the standard orders [10]
[11] [18]. Finally, section 3.3 will be where we jump from finite to infinite,
and show that if $Q$ is thin, so is the class of $Q$ labeled
$\sigma$-scattered linear orders under $\leqq_{emb}$.

##  2 Notation

###  2.1 Basics of Descriptive Set Theory

######  Definition 2.1.

We call a topological space $X$ Polish if its topology is complete, separable,
and metrizable.

Not much on the finer combinatorics of Polish spaces will be relevant for us.
We’ll mostly be interested in the space of countable sequences of a countable
set under the topology of pointwise convergence. However, the reader is highly
encouraged to read [5] for more on the subject.

######  Definition 2.2.

Given a set $A$, $[A]^{\omega}=\\{B\subseteq A:|B|=\omega\\}$.

######  Fact 2.1.

Given a countable set $A$, $A^{\omega}$ under the topology of pointwise
convergence is Polish.

Note that if $A$ is countable, $[A]^{\omega}$ is also Polish with topology
determined by $X_{n}\rightarrow X$ if and only if
$\bigcap\limits_{n=1}^{\infty}\bigcup\limits_{j=n}^{\infty}X_{j}=X$.
Alternatively, after well ordering $A$, one can identify members from
$[A]^{\omega}$ with strictly increasing sequences in $A^{\omega}$ with the
subspace topology. These definitions are equivalent.

######  Fact 2.2.

Given a set $A$, we define $A^{<\omega}$ to be the set of functions with
domain $\\{0,...,n\\}$ for some $n\in\omega$ and codomain $A$.

Elements in this set are finite sequences of members from $A$. In fact,
considering the members as finite sequences will often be of more use to us
than thinking of them as functions.

######  Definition 2.3.

Given a set $A$, we define the set $[A]^{<\omega}=\\{B\subseteq
A:|B|<\omega\\}$.

######  Definition 2.4.

Given two Polish spaces $V_{1}$ and $V_{2}$, we say a function
$f:V_{1}\rightarrow V_{2}$ is Baire class 1 if and only if there is a sequence
of continuous functions $f_{k}:V_{1}\rightarrow V_{2}$, $f_{k}$ converges to
$f$ pointwise.

All Baire class 1 functions are Borel. Moreover, being Baire class 1
guarantees the preimage of every open set is $G_{\delta}$ (countable
intersection of open sets). One can check [6] for more on Baire class 1
functions. We will need that these functions are Borel, and not much else.
Their main appearance is in the construction of the $\partial^{\infty}$
operation in section 3.2.

###  2.2 Borel Graph Combinatorics

######  Definition 2.5.

A Borel graph $G$ is a pair $(V,E)$, where $V$ is a Polish space and
$E\subseteq[V]^{2}$ is Borel.

We give $[V]^{2}$ the topology it inherits when viewed as a subset of $V^{2}$.
Since we are working in the context of descriptive set theory, all properties
that we will be discussing from graph theory need to be Borel definable. By
this, we mean that we will not be interested in graph homomorphisms, but
rather Borel graph homomorphisms. Nor will we work with the standard chromatic
number. While it may seem as though this is a small requirement, it is
actually rather major. Some graphs that are bipartite in the classic sense may
have large Borel chromatic number. For more on this, see [8].

######  Definition 2.6.

Given Borel graphs $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$, a Borel
graph homomorphism is a Borel map $f:V_{1}\rightarrow V_{2}$ with the property
that $\forall x,y\in V_{1}$, $xE_{1}y\Rightarrow f(x)E_{2}f(y)$. If such a
homomorphism exists, we write $G_{1}\preceq_{B}G_{2}$.

######  Definition 2.7.

Given a Borel graph $G=(V,E)$, we define the Borel chromatic number of $G$ to
be

$\displaystyle\chi_{B}(G)$ $\displaystyle=\text{min}\\{|Y|:Y\text{
Polish},\;G\preceq_{B}(Y,[Y]^{2})\\}$

Note that the requirement that the graph $Y$ in the above definition be Polish
means that the only possibilities for $\chi_{B}(G)$ are
$\\{1,2,3,4,...,\aleph_{0},2^{\aleph_{0}}\\}$. We will be studying graphs
whose edge set is determined by Borel functions. The range of plausible Borel
chromatic numbers these graphs can achieve is finite. In particular, the Borel
chromatic number can either be $1$, $2$, $3$, or $\aleph_{0}$.

######  Definition 2.8.

We define $s:2^{\omega}\rightarrow 2^{\omega}$ via $\forall
k\in\omega,s(x)(k)=x(k+1)$.

######  Definition 2.9.

We say a Borel graph $G=(V,E_{f})$ is generated by the Borel function $f$ on
$V$ if $f:V\rightarrow V$ Borel and

$\displaystyle\forall x,y\in V,xE_{f}y\iff(x\neq y)\text{ and }(f(x)=y\text{
or }f(y)=x)$

######  Fact 2.3.

Given a Borel graph $G$ generated by a Borel function $f$ on a Polish space
$V$, the following are equivalent.

  * •

$\chi_{B}(G)\leq 3$

  * •

$G\preceq_{B}(2^{\omega},E_{s})$

  * •

$\exists A\subseteq X$ Borel and $f$ independent such that $\forall x\in X$
$\exists k\in\omega$, $f^{k}(x)\in A$ (such a set is called forward recurrent)
[14]

The universality property of $(2^{\omega},E_{s})$ is rather instrumental for
our colouring algorithm. The goal of the algorithm is to embed as much as we
can into $(2^{\omega},E_{s})$ in a Borel fashion, then work with the
homogeneous remainder. The third property of forward recurrence will also be
relevant. Consequently, familiarity with the above fact will be of high
importance. Note, not every Borel graph generated by a function needs finite
Borel chromatic number. The shift graph is a counterexample.

######  Definition 2.10.

We call the graph $([\omega]^{\omega},S)$ where $S(A)=A\setminus\text{min}A$
the shift graph.

######  Fact 2.4 (Galvin-Prikry).

Given a $k\in\omega$ and a Borel colouring
$c:[\omega]^{\omega}\rightarrow\\{1,...,k\\}$, there is an
$A\in[\omega]^{\omega}$ and $i\in\\{1,...,k\\}$ such that
$[A]^{\omega}\subseteq c^{-1}(i)$.

######  Fact 2.5.

$\chi_{B}(([\omega]^{\omega},S))=\aleph_{0}$.

###### Proof.

Simple application of the Galvin-Prikry theorem. ∎

######  Definition 2.11.

Let $f:X\rightarrow X$ and $g:Y\rightarrow Y$ be functions. We call the
mapping $h:X\rightarrow Y$ a factor map if $\forall x\in X$,
$h(f(x))=g(h(x))$.

######  Lemma 2.1.

Let $X$ and $Y$ be Polish spaces. Let $f:X\rightarrow X$ and $g:Y\rightarrow
Y$ be Borel with no fixed point. If $h:X\rightarrow Y$ is a Borel factor map,
then $\chi_{B}((X,E_{f}))\leq\chi_{B}((X,E_{g}))$.

###### Proof.

It suffices to show that $(X,E_{f})\preceq_{B}(Y,E_{g})$. The factor map
$h:X\rightarrow Y$ is a graph homomorphism. To see this, take $x,y\in X$ with
$xE_{f}y$. Since $f$ has no fixed point, either $f(x)=y$ or $f(y)=x$. Without
loss of generality, suppose $f(x)=y$. It follows that $h(y)=h(f(x))=g(h(x))$.
Since $g$ has no fixed point, $h(x)\neq h(y)$ and so it must be the case that
$h(x)E_{g}h(y)$. Hence, $h$ is a Borel graph homomorphism. ∎

Most of the graphs we will be interested in will have no fixed point. Note,
the shift operation $S$ on $[\omega]^{\omega}$ has no fixed point.

###  2.3 Basics of BQO Theory

######  Definition 2.12.

A quasi-order is a pair $(Q,\leqq_{Q})$ where the relation $\leqq_{Q}$ on $Q$
is reflexive and transitive.

######  Definition 2.13.

Given two quasi-orders $Q_{1}$ and $Q_{2}$, we assign an order
$\leqq_{Q_{1}\cup Q_{2}}$ to the disjoint union where $p\leqq_{Q_{1}\cup
Q_{2}}q\iff\exists i\in\\{1,2\\},p,q\in Q_{i}$ and $p\leqq_{Q_{i}}q$.

######  Definition 2.14.

We say a quasi-order $(Q,\leqq_{Q})$ is a better-quasi-order (BQO) if when $Q$
is endowed with the discrete topology, any Borel (equiv. continuous) map
$f:[\omega]^{\omega}\rightarrow Q$, $\exists A\in[\omega]^{\omega}$, $\forall
B\in[A]^{\omega}$, $f(B)\leqq_{Q}f(S(B))$.

A weaker notion is that of a well quasi-order. They’re much easier to work
with, but do not code the type of graphs we are interested in. They’re also
not closed under as many operations as BQOs are. Note also the strong tie
between the Galvin-Prikry theorem and the definition of BQO.

######  Definition 2.15.

Given a BQO $Q$, we order $R=Q^{<\omega}$ via $t_{1}\leqq_{R}t_{2}\iff\exists
h:\text{dom}(t_{1})\rightarrow\text{dom}(t_{2})$ order preserving such that
$t_{1}(n)\leqq t_{2}(h(n))$. We call this order the Higman order.

######  Fact 2.6.

If $Q$ is a BQO, then $Q^{<\omega}$ is BQO under the Higman order.

######  Definition 2.16.

A tree is a pair $(T,\leq_{T})$ where $\leq_{T}$ is a partial order with the
property that $\forall t\in T$, $\\{v\in T:v\leq_{T}\\}$ is well ordered under
$\leq_{T}$, and $T$ has a $\leq_{T}$ minimal element called the root.

######  Definition 2.17.

Given a set $Q$, we define $\mathcal{FT}_{Q}$ to be the class of all pairs
$(T,l)$ where $T$ is a finite tree and $l:T\rightarrow Q$. We call members of
this class finite labeled trees and refer to the function $l$ as a labeling.

######  Definition 2.18.

Given a set $Q$, we define $\mathcal{T}_{Q}$ to be the class of all pairs
$(T,l)$ where $T$ is a tree of height $\leq\omega$ and $l:T\rightarrow Q$. We
call members of this class labeled trees and refer to the function $l$ as a
labeling.

######  Definition 2.19.

Let $Q$ be a quasi-order. We define two quasi-orderings, $\leqq_{1}$ and
$\leqq_{m}$ on $\mathcal{T}_{Q}$ via

  * •

$(T_{1},l_{1})\leqq_{1}(T_{2},l_{2})\iff$ $\exists f:T_{1}\rightarrow T_{2}$,
$\forall x,y\in T_{1}$, $x<_{T_{1}}y\Rightarrow f(x)<_{T_{2}}f(y)$ and
$l_{1}(x)\leqq_{Q}l_{2}(f(x))$.

  * •

$(T_{1},l_{1})\leqq_{m}(T_{2},l_{2})\iff$ $\exists f:T_{1}\rightarrow T_{2}$,
$\forall x,y\in T_{1}$, $x\leq_{T_{1}}y\Rightarrow f(x)\leq_{T_{2}}f(y)$ and
$l_{1}(x)\leqq_{Q}l_{2}(f(x))$.

The main distinction between $\leqq_{1}$ and $\leqq_{m}$ is $\leqq_{1}$
requires the function $f$ be injective. For $\leqq_{m}$, the function need
only preserve the tree ordering.

######  Fact 2.7.

(Laver) If $Q$ is BQO, then $\mathcal{T}_{Q}$ and $\mathcal{FT}_{Q}$ are BQO
under $\leqq_{1}$ and $\leqq_{m}$.

In the next subsection, we will briefly highlight results from Lavers work on
$\sigma$-scattered orders [10] [11]. Codifying objects on labeled trees is one
of the most natural ways to prove an order is a BQO. For example, consider
Pouzet’s theorem [18].

###  2.4 Basics of $\sigma$-scattered Orders

######  Definition 2.20.

Given linear orders $L_{1}$ and $L_{2}$, we say $L_{1}\leqq_{emb}L_{2}$ if
there exists a function $f:L_{1}\rightarrow L_{2}$, $\forall x,y\in L_{1}$,
$x<_{L_{1}}y\Rightarrow f(x)<_{L_{2}}f(y)$. We call such a map an embedding.
If $L_{1}\leqq_{emb}L_{2}$, we say $L_{2}$ embeds a copy of $L_{1}$.

######  Definition 2.21.

Given a linear order $L$, we define its reverse order $L^{*}$ to be the pair
$(L,<_{L^{*}})$ with $x<_{L^{*}}y\iff x<_{L}y$.

######  Definition 2.22.

A linear order is called scattered if it does not embed a copy of the
rationals $\mathbb{Q}$.

######  Definition 2.23.

A cardinal $\kappa$ is called regular if ever cofinal subset has cardinality
$\kappa$.

For more on the basics of cardinals, see [9].

######  Definition 2.24.

We define RC to be the class of regular cardinals.

Note that every regular cardinal is scattered. Moreover, RC is a BQO under
$\leqq_{emb}$.

######  Definition 2.25.

A linear order $L$ is called $\sigma$-scattered if it can be expressed as a
countable union $L=\bigcup\limits_{n=1}^{\infty}L_{n}$ such that $L_{n}$ are
scattered.

######  Definition 2.26.

A $Q$-labeled order is a pair $(L,l)$, where $L$ is a linear order and
$l:L\rightarrow Q$. We call such an $l$ a labeling.

######  Definition 2.27.

Given a set $Q$ and a cardinal $\kappa$, $Q^{\kappa}$ is the set of labeled
ordinals $\alpha$, where $\alpha<\kappa$.

######  Definition 2.28.

Let $Q$ be a quasi order. Given two labeled orders $(L_{1},l_{1})$ and
$(L_{2},l_{2})$, we say $(L_{1},l_{1})\leqq_{emb}(L_{2},l_{2})$ if there is an
embedding $f:L_{1}\rightarrow L_{2}$ with the property that $\forall x\in
L_{1}$ $l_{1}(x)\leqq_{Q}l_{2}(f(x))$.

######  Definition 2.29.

Given a quasi-order $Q$, we define the class $\mathcal{C}(Q)$ to be the class
of $Q$-labeled $\sigma$-scattered linear orders, ordered under $\leqq_{emb}$.

######  Fact 2.8.

Given $\alpha,\beta\in\textbf{RC}$ uncountable, there is a unique linear order
$\eta_{\alpha,\beta}$ that is $\leqq_{emb}$ maximal over the class of
$\sigma$-scattered orders $L$ that do not embed $\alpha^{*}$ or $\beta$.

Hausdorff showed that regular cardinals served as the building blocks of the
scattered linear orders. Laver showed via similar means that regular cardinals
paired with the above orders serve as the building blocks for all
$\sigma$-scattered orders. It is also interesting to not that
$\eta_{\omega_{1},\omega_{1}}$ is the rationals.

######  Definition 2.30.

Given a quasi order $Q$, we define $Q^{+}$ to be the disjoint union
$Q\cup\\{\kappa:\kappa\in\textbf{RC}\\}\cup\\{\kappa^{*}:\kappa\in\textbf{RC}\\}\cup\\{\eta_{\alpha,\beta}:\alpha,\beta\in\textbf{RC}\\}$.

######  Fact 2.9 (Laver).

Given a better quasi order $Q$, there is a class of $\sigma$-scattered linear
orders $\mathcal{H}(Q)$ and a mapping
$J:\mathcal{H}(Q)\rightarrow\mathcal{T}_{Q^{+}}$ with the property that
$\forall(L_{1},l_{1}),(L_{2},l_{2})\in\mathcal{H}(Q)$,
$(L_{1},l_{1})\nleqq_{emb}(L_{2},l_{2})\Rightarrow
J((L_{1},l_{1}))\nleqq_{1}J((L_{2},l_{2}))$.

######  Fact 2.10 (Laver).

There is a map $J:\mathcal{C}(Q)\rightarrow\mathcal{H}(Q)^{<\omega}$ such that
$(L_{1},l_{1})\nleqq_{emb}(L_{2},l_{2})\Rightarrow
J((L_{1},l_{1}))\nleqq_{\mathcal{H}(Q)^{<\omega}}J((L_{2},l_{2}))$.

These facts imply that if $Q$ is BQO, then so is the class of $Q$-labeled
$\sigma$-scattered linear orders under $\leqq_{emb}$.

###  2.5 Graphs Generated by BQO’s

######  Definition 2.31.

Given a better quasi order $Q$, we define $\vec{Q}=\\{X\in Q^{\omega}:\forall
k\in\omega,X(k)\nleqq_{Q}X(k+1)\\}$. We often conflate $\vec{Q}$ with the
shift graph $(\vec{Q},S)$.

One property these graphs have is they do not homomorphically embed the shift
graph $([\omega]^{\omega},S)$ as a consequence of $Q$ being BQO [17].
Pequignot began a search for a BQO $Q$ with the property that
$\chi_{B}(\vec{Q})=\aleph_{0}$. Since we’re also interested in this property,
we will give it a name.

######  Definition 2.32.

If $\chi_{B}(\vec{Q})\leq 3$, we call $Q$ thin. If $Q$ is not thin, we call it
thick.

We will later show that the name “thick” is rather appropriate when we discuss
a corollary to the colouring algorithm.

######  Lemma 2.2.

Suppose $Q_{1}$ and $Q_{2}$ are BQO and there is a map $f:Q_{1}\rightarrow
Q_{2}$ with $q\nleqq_{Q_{1}}p\Rightarrow f(q)\nleqq_{Q_{2}}f(p)$. Then $Q_{2}$
thin $\Rightarrow Q_{1}$ thin.

###### Proof.

Consider the map $\vec{f}:\vec{Q}_{1}\rightarrow\vec{Q}_{2}$ given by
$\vec{f}(X)(k)=f(X(k))$ for all $k\in\omega$. Note, for all $k\in\omega$,
$X(k)\nleqq_{Q_{1}}X(k+1)\Rightarrow f(X(k))\nleqq_{Q_{2}}f(X(k+1))$ so this
mapping is well defined. It is also continuous as $X_{n}\rightarrow X$ point-
wise in $\vec{Q}_{1}$ will imply that $\vec{f}(X_{n})\rightarrow\vec{f}(X)$
point-wise. Moreover, it is easy to check that $\vec{f}$ is a factor map. It
follows that $\vec{Q}_{1}\preceq_{B}\vec{Q}_{2}$. ∎

An immediate corollary to the above is the unsurprising fact that the thin
property is hereditary. That is to say, if $Q$ is thin and
$Q^{\prime}\subseteq Q$ is given the order it inherits from $Q$, then
$Q^{\prime}$ is also thin. More interestingly, there has been historically
many instances where maps of this sort are used to prove an ordering is BQO.
For example, consider the previous facts of Laver from the last subsection. It
also allows us to reasonably extend the notion of thin to larger BQO’s that
may not be sets, but rather classes.

######  Definition 2.33.

Given a BQO $Q$, we say $Q$ is thin if and only if $\forall
Q^{\prime}\in[Q]^{\omega}$, $Q^{\prime}$ is thin.

Unless we are talking about a concrete BQO, we will always assume a thick or
thin BQO is countable when we work in the abstract.

##  3 Main Result

###  3.1 Colouring Algorithm

We begin this section by proving the colouring algorithm.

######  Lemma 3.1 (colouring algorithm).

Let $Q$ be a better quasi order and $\Phi$ be a relation of arity $n$ on $Q$.
$\vec{Q}$ is thin if and only if the following two properties hold

  * •

$\\{X\in\vec{Q}:\forall k\in\omega,\;\Phi(X(k),...,X(n+k))\\}$ is Borel
$3$-colourable.

  * •

$\\{X\in\vec{Q}:\forall k\in\omega,\;\neg\Phi(X(k),...,X(n+k))\\}$ is Borel
$3$-colourable.

###### Proof.

It is clear that if $\vec{Q}$ is thin, then the above two sets are Borel three
colourable as they are both proper induced subgraphs of $\vec{Q}$. For this
reason, we need only show the other direction.

Consider the function $f:\vec{Q}\rightarrow 2^{\omega}$ via

$\displaystyle f(X)(k)=1\iff\Phi(X(k),...,X(k+n))$

This function is continuous and is a factor map eg. $f(S(X))=s(f(X))$.
Moreover, if we let $Y=\\{x\in 2^{\omega}:\forall k\in\omega\;\exists m\geq
k,x(m)\neq x(k)\\}$ (the set of sequences which are never eventually
constant), then we see $f^{-1}(Y)\subseteq\vec{Q}$ is Borel, closed under $S$
and is Borel three colourable by lemma 2.1. By fact 2.3, there is an
$A_{1}\subseteq f^{-1}(Y)$ that is forward recurrent and $S$ independent.
$\vec{Q}\setminus f^{-1}(Y)$ is the set of all sequences $X\in\vec{Q}$ that
satisfy one of the following conditions.

  * •

$\exists m\in\omega$, $\forall j\geq m$, $S^{j}(X)\in\\{X\in\vec{Q}:\forall
k\in\omega,\;\Phi(X(k),...,X(n+k))\\}$

  * •

$\exists m\in\omega$, $\forall j\geq m$, $S^{j}(X)\in\\{X\in\vec{Q}:\forall
k\in\omega,\;\Phi(X(k),...,X(n+k))\\}$

By our hypothesis, $\\{X\in\vec{Q}:\forall
k\in\omega\;\Phi(X(k),...,X(n+k))\\}$ and $\\{X\in\vec{Q}:\forall
k\in\omega\;\neg\Phi(X(k),...,X(n+k))\\}$ admit forward recurrent $S$
independent sets $A_{2}$ and $A_{3}$ respectively. Since every $X\in\vec{Q}$
is either in $f^{-1}(Y)$ or eventually in $A_{2}$ or $A_{3}$, $A_{1}\cup
A_{2}\cup A_{3}$ is a witness to $\chi_{B}(\vec{Q})\leq 3$ as it is a Borel
$S$ independent forward recurrent set. Note, independence is a consequence of
each $A_{i}$ belonging to disjoint $S$ closed sets. ∎

Here are two simple applications of the lemma that will be of use later.

######  Lemma 3.2.

If $Q_{1}$ and $Q_{2}$ are thin, then the disjoint union $R=Q_{1}\cup Q_{2}$
is thin.

###### Proof.

Consider the unary relation $\Phi$ on $R$ given by $\Phi(q)\iff q\in Q_{1}$.
By our colouring algorithm, it suffices to consider whether or not the
subgraphs induced by the following subsets are Borel $3$-colourable.

$\displaystyle B_{1}$ $\displaystyle=\\{X\in R:\forall k\in\omega,X(k)\in
Q_{1}\\}$ $\displaystyle B_{2}$ $\displaystyle=\\{X\in R:\forall
k\in\omega,X(k)\in Q_{2}\\}$

Notice however, that the first is simply $\vec{Q}_{1}$ and the second is
$\vec{Q}_{2}$. As both $Q_{1}$ and $Q_{2}$ are thin, we are done. ∎

Note, this implies that finite disjoint unions, and potentially non-disjoint
unions, of thin BQOs are thin as well.

######  Lemma 3.3.

If $Q_{1}$ and $Q_{2}$ are thin, then $R=Q_{1}\times Q_{2}$ is thin.

###### Proof.

Consider the binary relation $\Phi$ on $R$ given by
$\Phi((p_{1},p_{2}),(q_{1},q_{2}))\iff p_{1}\leqq_{Q_{1}}q_{1}$. Let
$\pi_{1}:R\rightarrow Q_{1}$ and $\pi_{2}:R\rightarrow Q_{2}$ be canonical
projection maps ($\pi_{i}(p_{1},p_{2})=p_{i}$). By our colouring algorithm, we
need only consider the colourability of the subgraphs generated by the sets

$\displaystyle B_{1}$ $\displaystyle=\\{X\in\vec{R}:\forall
k\in\omega\;\Phi(X(k),X(k+1))\\}$ $\displaystyle B_{2}$
$\displaystyle=\\{X\in\vec{R}:\forall k\in\omega\;\neg\Phi(X(k),X(k+1))\\}$

Notice that if $(p_{1},q_{1})\nleqq_{R}(p_{2},q_{2})$, then either
$p_{1}\nleqq_{Q_{1}}q_{1}$ or $p_{2}\nleqq_{Q_{2}}q_{2}$. Consequently,
$\neg\Phi((p_{1},p_{2}),(q_{1},q_{2}))$ and
$(p_{1},p_{2})\nleqq_{R}(q_{1},q_{2})$ $\Rightarrow$
$p_{2}\nleqq_{Q_{2}}q_{2}$. It follows that for $i\in\\{1,2\\}$ the mappings
$\vec{\pi}_{i}:B_{i}\rightarrow\vec{Q}_{i}$ given by $\forall k\in\omega$
$\vec{\pi}_{i}(X)(k)=\pi_{i}(X(k))$ is a well defined continuous factor map.
Consequently, they are Borel graph homomorphisms and since $Q_{1}$ and $Q_{2}$
are thin, we are done. ∎

We can also use the colouring algorithm to deduce a property of thick graphs
that suggests the name is quite appropriate. First, note that being thick
means that the relation $\nleqq_{Q}$ must be complex. Consequently, given a
binary relation $\Phi\subseteq Q^{2}$, it is possible for the BQO
$\leqq_{Q}\cup\Phi$ to no longer be thick. For example, if $\Phi=Q^{2}$.
However, given the choice between $\Phi$ and its compliment $\neg\Phi$, one of
$\leqq_{Q}\cup\Phi$ or $\leqq_{Q}\cup(\neg\Phi)$ must be thick.

######  Proposition 1.

Let $Q$ be thick. Let $\mathcal{I}=\\{\Phi\subseteq
Q^{2}:\leqq_{Q}\cup\Phi\;\text{thick}\\}$. Then $\mathcal{I}$ satisfies the
following properties:

  * •

$\Psi\subseteq\Phi$, $\Phi\in\mathcal{I}$ $\Rightarrow$ $\Psi\in\mathcal{I}$.

  * •

$Q^{2}\notin\mathcal{I}$.

  * •

$\emptyset\in\mathcal{I}$.

  * •

$\Phi\notin\mathcal{I}\Rightarrow\neg\Phi\in\mathcal{I}$.

This suggests there is a link between thick BQOs and directed sets (eg.
filters and ideals).

###  3.2 From $Q$ to $Q^{<\omega}$

For this section, we will fix $Q$ to be a BQO and $R$ to be $Q^{<\omega}$
under Higman’s order. We also let $B=\\{X\in\vec{R}:\forall
k\in\omega,\text{len}(X(k))\leq\text{len}(X(k+1))\\}$.

######  Definition 3.1.

Given $X\in B$, we let $m_{k}(X)\in\omega$ be the largest integer such that
$X(k)\upharpoonright m_{k}(X)\leqq_{R}X(k+1)$. We let $n_{k}(X)$ be the
smallest integer such that $X(k)\upharpoonright
m_{k}(X)\leqq_{R}X(k+1)\upharpoonright n_{k}(X)$.

Note, for any $X$ as in the above, $m_{k}(X)\leq n_{k}(X)$. Also, if $X_{i}\in
B$ is a sequence that converges to $X$, then $\forall k\in\omega$
$n_{k}(X_{i})\rightarrow n_{k}(X)$ and $m_{k}(X_{i})\rightarrow m_{k}(X)$.
Thus, both $n_{k}$ and $m_{k}$ are continuous for any $k$. They also satisfy
$n_{k}(S(X))=n_{k+1}(X)$ and $m_{k}(S(X))=m_{k+1}(X)$.

######  Definition 3.2.

Given $X\in B$, if $\forall k\in\omega$, $m_{k}(X)\leq m_{k+1}(X)<n_{k}(X)\leq
n_{k+1}(X)$, then we define $\partial X\in B$ by $\forall k\in\omega$,
$\partial X(k)=X(k)\upharpoonright m_{k}$. This is well defined since $n_{k}$
was minimal and $m_{k+1}<n_{k}$. We call such $X$ $1$-derivable. We say
$\partial^{0}X=X$. Given $i\in\omega$, we recursively define
$\partial^{i}X=\partial(\partial^{i-1}X)$ when $\partial^{i-1}X$ is
$1$-derivable. We call such $X$ $i$-derivable

Derivations commute with $S$ i.e $\partial^{i}S(X)=S(\partial^{i}X)$. This is
a consequence of the previously noted fact $n_{k}(S(X))=n_{k+1}(X)$ and
$m_{k}(S(X))=m_{k+1}(X)$. It follows from $\partial$ commuting with $S$ that
if $X$ is $i$-derivable, then $S(X)$ is $i$-derivable.

######  Definition 3.3.

We let $D\subseteq B$ be the set of all $1$-derivable members from $B$.

The mapping $\partial:D\rightarrow\vec{R}$ is a continuous factor map.

######  Proposition 2.

$\forall X\in B$, there is a maximal $i$ such that $X$ is $i$-derivable.

###### Proof.

Suppose otherwise. Note
$\text{len}((\partial^{i}X)(0))=m_{0}(\partial^{i-1}X)$ decreases in length.
We then have an infinite decreasing sequence in $\omega$ which is impossible.
∎

######  Definition 3.4.

For an $X\in B$, let $M_{k}(X)\in\omega$ be the largest such ordinal such that
$S^{k}(X)$ is $M_{k}(X)$-derivable. We define $\partial^{\infty}X$ by
$\partial^{\infty}X(k)=(S^{k}(X))^{(M_{k})}(0)$.

Note that for every $k\in\omega$, the mappings $M_{k}(X)$ and
$\partial^{M_{k}(X)}X$ are continuous.

######  Lemma 3.4.

The mapping $X\in B$ defined by $X\rightarrow\partial^{\infty}X$ is well
defined and Baire class 1. Moreover, $\forall k\in\omega$
$S^{k}(\partial^{\infty}X)\in B\setminus D$

###### Proof.

First, since $X$ $i$-derivable $\Rightarrow$ $S(X)$ is $i$-derivable,
$M_{k}(X)$ is an increasing sequence. Moreover,
$S^{k}(\partial^{M_{k-1}(X)}X)$ is an initial segment of
$S^{k}(\partial^{M_{k}(X)}X)$. Consequently,
$\partial^{\infty}X(k)=(S^{(k)}(\partial^{M_{k}(X)}X))(0)\nleqq_{R}(S^{(k+1)}(\partial^{M_{k}(X)}X))(0)$
implies that $\partial^{\infty}X(k)\nleqq_{R}\partial^{\infty}X(k+1)$ as
$\partial^{\infty}X(k+1)$ is an initial segment of
$(S^{(k+1)}(\partial^{M_{k}(X)}X))(0)$.

To see the mapping $X\rightarrow\partial^{\infty}X$ is Baire class 1, consider
the mappings $f_{j}:\vec{R}\rightarrow\vec{R}$ via

$\displaystyle\forall i<j,f_{j}(X)(i)$
$\displaystyle=(S^{i}(\partial^{M_{i}(X)}X))(0)$ $\displaystyle f_{j}(X)(i)$
$\displaystyle=(S^{i}(\partial^{M_{j}(X)}X))(0)\;\text{otherwise}$

It is clear that these maps are continuous as finite derivations are
continuous. It is also clear that $f_{k}(X)\rightarrow\partial^{\infty}X$
point-wise.

Note that $S(\partial^{\infty}X)=\partial^{\infty}S(X)$ as derivation commutes
with $S$. The existence of a $k$ such that $S^{k}(\partial^{\infty}X)\in D$
would contradict the maximality of $M_{k}(X)$ as we could have taken one
further derivation. ∎

######  Lemma 3.5.

Given an $X\in B$, if $m_{k+1}(X)\geq n_{k}(X)$, the sequence
$Y(k)=X(k)(m_{k}(X)+1)$ is in $\vec{Q}$.

###### Proof.

Note, for all $d\geq n_{k}(X)$, $X(k)(m_{k}(X)+1)\nleqq_{Q}X(k+1)(d)$. Else,
the existence of such a $d$ would mean $X(k)\upharpoonright
m_{k}(X)+1\leqq_{R}X(k+1)\upharpoonright d\leqq_{R}X(k+1)$. Since
$m_{k}(X)\leq n_{k}(X)\leq m_{k+1}(X)$, $\forall k\in\omega$
$X(m_{k}(X)+1)\nleqq_{Q}X(m_{k+1}(X)+1)$ as desired. ∎

######  Theorem 3.6.

If $Q$ is thin, then so is $Q^{<\omega}$.

###### Proof.

By our colouring algorithm, it suffices to Borel $3$-colour the set $B$. To
see this, consider the relation $\Phi(r,t)\iff\text{len}(r)\leq\text{len}(t)$.
Since there is no infinite descending sequence in $\omega$, we only need to
worry about the $\Phi$ homogeneous members in $\vec{R}$ which is the set $B$.
By lemma 3.4 and lemma 2.1, the mapping $\partial^{\infty}:D\rightarrow
B\setminus D$ is a Borel graph homomorphism. Hence, it suffices to consider
$B\setminus D$. Applying our algorithm twice, we can reduce colourability to
the set of $X\in B\setminus D$ that have the parameters $m_{k}(X)$ and
$n_{k}(X)$ increasing.

$\displaystyle C$ $\displaystyle=\\{X\in B\setminus D:\forall
k\in\omega,m_{k}(X)\leq m_{k+1}(X),n_{k}(X)\leq n_{k+1}(X)\\}$

Again using the algorithm, we can reduce to the case where $\forall
k\in\omega$ $m_{k+1}(X)\geq n_{k}(X)$ or $\forall k\in\omega$,
$m_{k+1}(X)<n_{k}(X)$. Note, the latter is impossible for members of $C$, else
such an $X$ would be in $D$. By lemma 3.5, $\\{X\in C:m_{k+1}(X)\geq
n_{k}(X)\\}\preceq_{B}\vec{Q}$ by the mapping $f(X)(k)=X(m_{k}(X)+1)$. Since
$Q$ is thin, we have Borel $3$-colouring of $\vec{R}$. Thus, $Q$ thin implies
$Q^{<\omega}$ thin. ∎

######  Theorem 3.7.

If $Q$ is thin, then so is $\mathcal{FT}_{Q}$ under $\leqq_{1}$.

###### Proof.

For each $T\in\mathcal{FT}$, let $\hat{T}$ be a linear order extending the
order of $T$. Given $(T,l)\in\mathcal{FT}_{Q}$, we can identify the pair
$(\hat{T},l)$ with a sequence in $Q^{<\omega}$. This is because of course,
every finite linear order is uniquely determined by size and a $Q$ labeled
linear order is then just a $Q$ sequence. Notice that this mapping
$(T,l)\rightarrow(\hat{T},l)$ satisfies
$(S,m)\leqq_{1}(T,l)\Rightarrow(\hat{S},m)\leqq_{Q^{<\omega}}(\hat{T},l)$.
This naturally gives us a homomorphism from $\vec{\mathcal{FT}_{Q}}$ into
$\vec{Q^{<\omega}}$ via lemma 2.2. ∎

######  Corollary 3.7.1.

If $Q$ is thin, so are $[Q]^{<\omega}$ and $\mathcal{FT}_{Q}$ under
$\leqq_{m}$.

###### Proof.

First, well order $Q$. Then, given an $a\in[Q]^{<\omega}$, assign to it the
sequence $\hat{a}\in Q^{<\omega}$ of its members placed in order according to
the well order. Note that $\hat{a}\leqq_{Q^{\omega}}\hat{b}\Rightarrow
a\leqq_{m}b$. Consequently, $[Q]^{<\omega}$ is thin by theorem 3.6 and lemma
2.2. Similarly for trees, $(S,m)\leqq_{1}(T,l)\Rightarrow(S,m)\leqq_{m}(T,l)$
for $A,B\in[Q]^{<\omega}$ and $(S,m),(T,l)\in\mathcal{FT}_{Q}$. So, by lemma
2.2 and theorem 3.7 $\mathcal{FT}_{Q}$ is thin under $\leqq_{m}$. ∎

###  3.3 Finite To Infinite

Since Laver showed that labeled $\sigma$-scattered orders are in some sense,
no more complicated than finite labeled trees, it comes as no surprise that if
$Q$ is thin, so are $Q$-labeled $\sigma$-scattered orders. We will prove this
here. We start by showing that any countable collection of $Q$ labeled
ordinals where $Q$ is thin, is also thin under $\leqq_{emb}$.

######  Lemma 3.8.

Let $Q$ be thin. Then for any cardinal $\kappa$, $Q^{<\kappa}$ is thin under
$\leqq_{emb}$

###### Proof.

Let $R$ be a countable subset of $Q^{<\kappa}$. Applying our colouring
algorithm to $\vec{R}$, we need only consider

$\displaystyle A$
$\displaystyle=\\{X\in\vec{R}:\text{len}(X(k))\leq\text{len}(X(k+1))\\}$

Akin to in the finite case, for $X\in A$ and $k\in\omega$, there is an
$\alpha_{k}(X),\beta_{k}(X)<\kappa$ where $\alpha_{k}(X)$ is minimal such that
$X(k)\upharpoonright\\{\beta:\beta<\alpha_{k}(X)\\}\nleqq_{emb}X(k+1)$ and
$\beta_{k}(X)$ is minimal such that
$X(k)\upharpoonright\alpha_{k}(X)\leqq_{emb}X(k+1)\upharpoonright\beta_{k}(X)$.
Note when $\kappa=\omega$, this is identical to the finite case. Since $R$ is
a countable subset, and members from $R$ may be uncountable labeled ordinals,
it may not be the case that for every $(\gamma,l)\in R$ and $\zeta<\gamma$,
$(\zeta,l\upharpoonright\zeta)\in R$. However, we may assume that $R$ is
closed under all relevant restrictions. First, we will prove this claim.

Given a pair $(\gamma_{1},l_{1}),(\gamma_{2},l_{2})\in Q^{<\kappa}$, we define
$\alpha((\gamma_{1},l_{1}),(\gamma_{2},l_{2}))$ to be the minimal $\alpha$
such that $(\alpha,l_{1}\upharpoonright\alpha)\leqq_{emb}(\gamma_{2},l_{2})$
and $\beta((\gamma_{1},l_{1}),(\gamma_{2},l_{2}))$ the minimal $\beta$ such
that
$(\alpha,l_{1}\upharpoonright\alpha)\leqq_{emb}(\beta,l_{2}\upharpoonright\beta)$.
Given $R\subseteq Q^{<\kappa}$, we define the following sets

$\displaystyle R_{l}$
$\displaystyle=\\{(\alpha,l):\exists(\gamma_{1},l_{1}),(\gamma_{2},l_{2})\in
R,\;(\alpha,l)=(\alpha((\gamma_{1},l_{1}),(\gamma_{2},l_{2})),l_{1}\upharpoonright\alpha((\gamma_{1},l_{1}),(\gamma_{2},l_{2})))\\}$
$\displaystyle R_{r}$
$\displaystyle=\\{(\alpha,l):\exists(\gamma_{1},l_{1}),(\gamma_{2},l_{2})\in
R,\;(\alpha,l)=(\alpha((\gamma_{1},l_{1}),(\gamma_{2},l_{2})),l_{2}\upharpoonright\alpha((\gamma_{1},l_{1}),(\gamma_{2},l_{2})))\\}$
$\displaystyle R^{\prime}$ $\displaystyle=R_{l}\cup R_{r}$

Note that if $R$ is countable, so is $R^{\prime}$ as $\alpha(\cdot,\cdot)$ is
parameterized over pairs from $R$ of which there are only countably many.
Given an $R$, we define recursively $\forall i\in\omega$, $R^{0}=R$,
$R^{i}=(R^{i-1})^{\prime}$. The set
$R_{fill}=\bigcup\limits_{i=0}^{\omega}R^{i}$ contains $R$ is a subset and has
the property that for any $(\gamma_{1},l_{1}),(\gamma_{2},l_{2})\in R_{fill}$,
$(\alpha((\gamma_{1},l_{1}),(\gamma_{2},l_{2})),l_{1}\upharpoonright\alpha((\gamma_{1},l_{1})$
and
$(\alpha((\gamma_{1},l_{1}),(\gamma_{2},l_{2})),l_{2}\upharpoonright\alpha((\gamma_{1},l_{1})$
are in $R_{fill}$. Consequently, we could define a derivative operation as we
did in the finite case on $\vec{R_{fill}}\supseteq\vec{R}$. We will explain
why this is the case next, but for now we’ve at least shown that we can assume
$R$ is sufficiently closed under restrictions.

Note that it is never the case that $\alpha_{k}(X)=\text{dom}(X(k))$. If it
were, then for each $\beta\in\text{dom}(X(k))$, there is an $h(\beta)$ such
that $X(k)(\beta)\leqq_{Q}X(k+1)(h(\beta))$ and $h$ strictly increasing. But
of course, this $h$ codifies that $X(k)\leqq_{R}X(k+1)$, a contradiction. It
is also the case that $\forall\gamma\geq\beta_{k}(X)$,
$X(k)(\alpha_{k}(X))\nleqq_{Q}X(k+1)(\gamma)$ akin to the finite case. This
means that the sequence $X(k)(\alpha_{k}(X))\in\vec{Q}$ when
$\alpha_{k}(X)\leq\beta_{k}(X)<\alpha_{k+1}(X)$.

Similar to before, we can say an $X$ is derivable if $\forall k\in\omega$,
$\alpha_{k}(X)\leq\alpha_{k+1}(X)\leq\beta_{k}(X)\leq\beta_{k+1}(X)$. We can
also define the derivation operation $\partial$ and it’s iterates by
restricting to $\alpha_{k}(X)$ coordinate-wise as before. Since we can assume
$R$ is closed under these coordinate-wise restrictions, the derivative
operation is well defined on $\vec{R}$. Moreover, $\partial$ is a Borel graph
homomorphisms, and every $X$ is at most $i$ derivable for some $i$ as there is
no infinite descending sequence of ordinals. Consequently, we can define the
operator $\partial^{\infty}$ for derivable members of $\vec{R}$. This mapping
is also well defined. It is also a Borel factor map and mimicking the argument
from the finite case, we have that $\vec{R}$ is thin. ∎

######  Theorem 3.9.

If $Q$ is thin, then so is $\mathcal{T}_{Q}$ under $\leqq_{1}$.

###### Proof.

Let $R$ be a countable subset of $\mathcal{T}_{Q}$. Let
$\mathcal{I}=\\{T:(T,l)\in R\\}$. Note that each tree $T\in\mathcal{I}$ can
have its order extended to a well order. Simply well order each set of
immediate successors from $T$ and then give $T$ the lexicographical order.
Given a $T\in\mathcal{I}$, we call the well order $\hat{T}$. Since
$\mathcal{I}$ is countable, there is a cardinal $\kappa$ such that each
$(\hat{T},l)\in Q^{<\kappa}$. Since the ordering extends the tree order, we
have
$(T_{1},l_{1})\nleqq_{R}(T_{2},l_{2})\Rightarrow(\hat{T}_{1},l_{1})\nleqq_{Q^{<\kappa}}(\hat{T}_{2},l_{2})$.
It follows that $\vec{R}$ is thin by our last lemma. Hence, $\mathcal{T}_{Q}$
is thin. ∎

######  Corollary 3.9.1.

If $Q$ is thin, then the class of $Q$ labeled $\sigma$-scattered linear orders
is thin.

###### Proof.

It suffices to show $Q^{+}$ is thin. Since the disjoint union of thin sets are
thin, it suffices to show that RC and $\textbf{RC}\times\textbf{RC}$ are thin.
Since products of thin sets are thin, we need only show that RC is thin. Given
any $R\subseteq\textbf{RC}$ countable, $\vec{R}$ is empty as there is no
infinite descending sequence of ordinals. Hence, RC is thin as desired. ∎

##  4 Acknowledgements

The author would like to thank Yann Pequignot for their email correspondence,
as well as for sharing some notes on the problem. The author would also like
to thank the Calgary discrete mathematics seminar for allowing the author to
present his initial findings. Finally, the author would like to thank Stevo
Todorcevic for introducing him to the problem, and supporting him through the
solution process.

## References

  * [1] R. Fraïssé, Sur la comparaison des types d’ordres. C. R. Acad. Sci. Paris 226 (1948)
  * [2] F. Galvin and K. Prikry. Borel sets and Ramsey’s theorem. The Journal of Symbolic Logic. 38:193–198, 6 1973.
  * [3] F. Hausdorff, Grundzüge einer Theorie der geordneten Mengen, Math. Ann. 65 (1908), 435-505.
  * [4] G. Higman, Ordering by divisibility in abstract algebras, Proc. of London Mathematical Society. 1952
  * [5] A. S. Kechris. Classical descriptive set theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.
  * [6] A. S. Kechris, A. Louveau. A Classification of Baire Class 1 Functions. Tansactions of the American Mathematical Society. Vol. 318 No. 1 pp 209-236. 1990
  * [7] A. S. Kechris and A. S. Marks. Descriptive graph combinatorics. 2015. Available at http://math.ucla.edu/ marks/
  * [8] A. S. Kechris, S. Solecki, and S. Todorcevic. Borel chromatic numbers. Adv. Math., 141(1):1-44, 1999.
  * [9] Kenneth Kunen, Set Theory. College Publications. 2011
  * [10] Richard Laver, On Fraïssé’s Order Type Conjecture. The Annals of Mathematics. 93 (1): 89-111.
  * [11] Richard Laver, An Order Type Decomposition Theorem. Annals of Mathematics, Second Series, Vol. 98, No. 1 (1973), pp. 96-119
  * [12] A. Marcone. Foundations of bqo theory. Trans. of the American Mathematical Society. 345(2):641-660, 1994
  * [13] A. Marcone. The set of better quasi-orderings is $\Pi_{2}^{1}$-complete. Mathematical Logic Quarterly. 41:373-383, 1995
  * [14] A. S. Marks. Effective Descriptive Set Theory. Available at https://www.math.ucla.edu/ marks/notes/edst_notes.pdf
  * [15] C. St. J. A. Nash-Williams, On well-quasi-ordering infinite trees. Mathematical Proceedings of the Cambridge Philosophical Society. 61 (3): 697-720, 1965
  * [16] C. St. J. A. Nash-Williams, On well-quasi-ordering transfinite sequence. Proc. Cambridge Phil. Soc. 61 (1965), 33-39.
  * [17] Y. Pequignot. Finite versus infinite: an insufficient shift. Adv. Math., 320(1): 244-249, 2017
  * [18] M. Pouzet. Applications of Well Quasi-Ordering and Better Quasi-Ordering. Graphs and Order. vol. 147. pp 503-519, 1984
  * [19] S. Todorcevic and Z. Vidnyanszky. A complexity problem for Borel graphs. submitted, 2017