Pierrick Coupé

Thomas Tourdias

Pierre Linck

José E Romero

José V Manjón

LesionBrain: An Online Tool for White Matter Lesion Segmentation

Keywords: White Matter Lesion Segmentation, Patch-based Segmentation, Service as a Software

In this paper, we present a new tool for white matter lesion segmentation called lesionBrain. Our method is based on a 3-stage strategy including multimodal patch-based segmentation, patch-based regularization of probability map and patch-based error correction using an ensemble of shallow neural networks. Its robustness and accuracy have been evaluated on the MSSEG challenge 2016 datasets. During our validation, the performance obtained by le-sionBrain was competitive compared to recent deep learning methods. Moreover, lesionBrain proposes automatic lesion categorization according to location. Finally, complementary information on gray matter atrophy is included in the generated report. LesionBrain follows a software as a service model in full open access.

Introduction

The presence of white matter lesions (WML) is associated with different brain diseases such as multiple sclerosis (MS), small vessel disease or head injury among others, but it also occurs in normal aging. Magnetic resonance imaging (MRI), especially FLAIR images, has been found to be very sensitive in the detection of these WML. Therefore, MRI is the reference standard to identify WML and it plays a crucial role in the diagnosis and the monitoring of many neurological pathologies. Despite the importance of quantifying WML, this task remains mainly based on manual counting of lesions or semi quantitative scores such as Fazekas score. Manual delineation for volumetric analyses is extremely time-consuming and prone to errors due to inter-and intra-rater variability. As a result, the automation of WML segmentation has received a great deal of attention during the last decade and a wide range of methods have been proposed [START_REF] Garcia-Lorenzo | Review of automatic segmentation methods of multiple sclerosis white matter lesions on conventional magnetic resonance imaging[END_REF]. These methods are usually classified into two categories, unsupervised and supervised. Unsupervised methods do not require a training dataset with manual segmentation of the lesions. These methods estimate lesions mainly using MRI intensities and some anatomical knowledge. They can be based on Bayesian models, Graph-cut [START_REF] Beaumont | Multiple Sclerosis lesion segmentation using an automated multimodal Graph Cut[END_REF] or thresholding approaches [START_REF] Schmidt | An automated tool for detection of FLAIR-hyperintense white-matter lesions in multiple sclerosis[END_REF] among others. Supervised methods require a training dataset including manual segmentations of experts to learn from examples. Many different techniques have been proposed such as Random Forest [START_REF] Vera-Olmos | Random Forest for Multiple Sclerosis Lesion Segmentation[END_REF], Patch-based methods [START_REF] Guizard | Rotation-invariant multi-contrast non-local means for MS lesion segmentation[END_REF][START_REF] Mechrez | Patch-based segmentation with spatial consistency: application to MS lesions in brain MRI[END_REF] and more recently deep learning methods [START_REF] Hashemi | Tversky as a Loss Function for Highly Unbalanced Image Segmentation using 3D Fully Convolutional Deep Networks[END_REF][START_REF] Mckinley | Nabla-net: a deep dag-like convolutional architecture for biomedical image segmentation: application to white-matter lesion segmentation in multiple sclerosis[END_REF][START_REF] Valverde | Improving automated multiple sclerosis lesion segmentation with a cascaded 3D convolutional neural network approach[END_REF]. Although automatic methods are becoming more and more accurate, manual segmentation remains used especially in clinical research or clinical trials in which very accurate quantification is needed to use lesion load as judgement criteria. Several factors can explain the difficulty to apply automatic methods in clinical context. First, validating the accuracy of WML segmentation methods is challenging because of the difficulty to define a ground truth. Indeed, the high intra and inter-rater variability makes difficult to define a gold standard. Moreover, the lack of freely available annotated datasets leads to highly heterogeneous validation in the literature making methods comparison arduous. Therefore, it is difficult to appreciate the respective performances of automatic methods and their potential under clinical conditions. Recently, important efforts have been done to limit these aspects by sharing freely available datasets based on the consensus of several experts [START_REF] Commowick | MSSEG Challenge Proceedings: Multiple Sclerosis Lesions Segmentation Challenge Using a Data Management and Processing Infrastructure[END_REF]. As a result, evaluation and comparison of methods become easier and more reliable. In this paper, we propose a new tool called lesionBrain which is an extension of the rotationallyinvariant nonlocal means (RI-NLM) segmentation method [START_REF] Guizard | Rotation-invariant multi-contrast non-local means for MS lesion segmentation[END_REF]. To evaluate its performance compared to state-of-the-art methods, the validation is carried out on the MSSEG MICCAI Challenge 2016 dataset which is freely available providing a high quality ground truth based on the consensus of seven experts.

Second, few methods are freely available making their use in clinic research difficult. When available, these methods are usually distributed as packages that need to be downloaded, installed and configured. Installation steps can be complicated and thus may require experimented persons not always available in a research laboratory and especially in clinical context. In addition, users have to be trained to use the software and computational resources have to be allocated to run it. These requirements can make the use of these packages complex, especially the most recent and sophisticated ones requiring advanced hardware configuration (e.g., advanced GPU). To address this issue, lesionBrain is proposed as an online open access solution following the model of Software as a Service (SaaS). Our method works remotely through a web-interface and does not require any installation, resources or human interaction.

In addition, automatic methods generally provide the volume of WML as the sole output. However, complementary information can be relevant from a clinical point of view. Indeed, the location of lesions is useful to establish a diagnosis of multiple sclerosis after a first clinical episode according to the McDonald diagnosis criteria for MS [START_REF] Thompson | Diagnosis of multiple sclerosis: 2017 revisions of the McDonald criteria[END_REF]. To provide this information, lesionBrain proposes a lesion classification based on their proximity to lateral ventricles, cerebral cortex or cerebellum and brain stem. As a result, the lesion load in volume and also the number of lesions are provided for periventricular, juxtacortical, infratentorial and deep white matter areas.

Finally, most of the existing tools provide information focused on WML. However, complementary information from other structures might be needed to better study brain pathologies globally. For instance, gray matter (GM) atrophy can provide relevant information to investigate the neurodegenerative impact of MS or Alzheimer's Disease (AD). Therefore, lesionBrain not only provides volumetric measurement on WML but also a quantification of WM, GM and Cerebrospinal fluid (CSF). When age and gender of the subject are available, the volumes of these brain tissues are compared to reference values derived from lifespan models to detect abnormalities [START_REF] Coupe | Towards a unified analysis of brain maturation and aging across the entire lifespan: A MRI analysis[END_REF].

2

Material and Methods

Datasets

LesionBrain dataset: Our training dataset is composed of 43 patients who underwent 3T 3D-T1w MPRAGE and 3D-Fluid-Attenuated Inversion Recovery (FLAIR) MRI. The preprocessing steps described in the next subsection have been applied to all the images to align them into the MNI space and to normalize their intensities. Afterwards, a first expert performed manual segmentations in the MNI space for all the patients with ITKsnap [START_REF] Yushkevich | User-guided 3D active contour segmentation of anatomical structures: significantly improved efficiency and reliability[END_REF] using T1w and FLAIR images. Then, a second expert validated and/or corrected all the manual segmentations. At the end, all the images were flipped as done in [START_REF] Eskildsen | BEaST: brain extraction based on nonlocal segmentation technique[END_REF] to double the size of our training library (i.e., 86 training images).

MSSEG MICCAI Challenge 2016 dataset:

To evaluate our tools, we used the dataset of the MSSEG MICCAI Challenge 2016 [START_REF] Commowick | MSSEG Challenge Proceedings: Multiple Sclerosis Lesions Segmentation Challenge Using a Data Management and Processing Infrastructure[END_REF]. For this dataset, 15 patients underwent 3D-T1w MPRAGE, 3D-FLAIR, Gadolinium-enhanced T1w, Proton Density (PD), and T2w MRI. Only T1w and FLAIR MRI were used during our experiments. These 15 subjects consist in 3 groups of five subjects scanned with Philips Ingenia 3T, Siemens Aera 1.5T and Siemens Verio 3T. All the images have been manually delineated by seven experts. Finally, the experts' consensus is used as gold standard.

Pipeline description

Preprocessing: First, the images are preprocessed to normalize their intensity and to register them into the MNI space. A denoising step based on the adaptive nonlocal means filter is first applied to T1w and FLAIR images [START_REF] Manjon | Adaptive non-local means denoising of MR images with spatially varying noise levels[END_REF]. Both denoised MRI are then coarsely corrected for inhomogeneity [START_REF] Tustison | N4ITK: improved N3 bias correction[END_REF]. Afterwards, the T1w is registered into the MNI space using an affine transform [START_REF] Avants | A reproducible evaluation of ANTs similarity metric performance in brain image registration[END_REF]. FLAIR is then registered to T1w in the MNI space. A fine inhomogeneity correction is performed on both images [START_REF] Weiskopf | Unified segmentation based correction of R1 brain maps for RF transmit field inhomogeneities (UNICORT)[END_REF]. Finally, brain tissue maps (i.e., WM, GM and CSF) are obtained using [START_REF] Manjón | Improved estimates of partial volume coefficients from noisy brain MRI using spatial context[END_REF]. These tissue maps are used to perform intensity normalization based on a piece-wise linear scaling of intensity where the median intensity of each tissue is set to a fixed value [START_REF] Manjon | volBrain: An Online MRI Brain Volumetry System[END_REF].

Structure segmentation: The T1w is used to segment several anatomical structures. First, the intracranial cavity (ICC) is extracted using [START_REF] Manjon | Nonlocal intracranial cavity extraction[END_REF] and brainstem and cerebellum using [START_REF] Romero | NABS: non-local automatic brain hemisphere segmentation[END_REF]. Finally, lateral ventricles are segmented using [START_REF] Coupé | Patch-based segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF].

Candidate map:

To reduce computational time, the segmentation is performed only on areas which potentially contain lesions as defined below. As done in [START_REF] Vera-Olmos | Random Forest for Multiple Sclerosis Lesion Segmentation[END_REF][START_REF] Mechrez | Patch-based segmentation with spatial consistency: application to MS lesions in brain MRI[END_REF], the mean µ and the standard deviation σ of the GM FLAIR intensities are used to estimate a threshold (th = µ + ασ, with α = 0.5). All voxels above this threshold and within the ICC mask are considered as lesion candidates. However, FLAIR intensity within lesion may sometimes be below this threshold. Therefore, an atlas of lesions (average of all the manual lesion maps of the lesionBrain dataset in the MNI space) is also used to look for lesions at the most probable location. Voxels at locations with probability higher than 20% to contain a lesion are added to the map of candidates obtained by thresholding.

Lesions segmentation: Lesions are segmented using an extension of the RI-NLM method proposed in [START_REF] Guizard | Rotation-invariant multi-contrast non-local means for MS lesion segmentation[END_REF]. On the one hand, such voxel-wise method may produce false positive detections especially in cortical areas while implicit regularization of multipoint/patch-wise frameworks demonstrated better performance than voxel-wise approaches [START_REF] Manjon | volBrain: An Online MRI Brain Volumetry System[END_REF]. On the other hand, using patch-wise methods for lesion segmentation does not enable to efficiently capture heterogeneity of shape, size and location of lesions [START_REF] Guizard | Rotation-invariant multi-contrast non-local means for MS lesion segmentation[END_REF]. Therefore, in lesionBrain, we propose to apply first the RI-NLM method on T1w and FLAIR images to obtain the probability map of lesions. Second, we achieve a regularization of the probability map using a patch-wise NLM denoising filter [START_REF] Coupe | An optimized blockwise nonlocal means denoising filter for 3-D magnetic resonance images[END_REF]. The weights of the NLM filter are estimated on the FLAIR and then used to average the probabilities. The RI-NLM takes advantage of inter-subject similarity while patch-wise NLM regularization (NLMr) takes advantage of intra-subject similarity. Finally, a systematic error correction step is performed to obtain the final segmentation. Automatic correction of systematic errors was first proposed in [START_REF] Wang | A learning-based wrapper method to correct systematic errors in automatic image segmentation: consistently improved performance in hippocampus, cortex and brain segmentation[END_REF] with SegAdapter. In lesionBrain, we used the Patch-based Ensemble Corrector (PEC) proposed in [START_REF] Romero | HIPS: A new hippocampus subfield segmentation method[END_REF]. Contrary to SegAdapter which is based on a voxel-wise Adaboost classifier, PEC involves patch-wise ensemble of multilayer perceptron classifiers. Recently, second-pass strategy such as cascade of Convolutional Neural Networks (CNN) [START_REF] Valverde | Improving automated multiple sclerosis lesion segmentation with a cascaded 3D convolutional neural network approach[END_REF] demonstrated high performance to limit false positive detection.

Lesions classification: Once the lesions are segmented, a last step is performed to classify them into the following categories: periventricular, juxtacortical, deep white and infratentorial. Such classification might be clinically relevant since some diagnose criteria of MS are based on it [START_REF] Thompson | Diagnosis of multiple sclerosis: 2017 revisions of the McDonald criteria[END_REF]. Therefore, all the lesions located within 3 voxels (i.e., 3 mm in the MNI space) from the lateral ventricles, the GM map, and the union of brainstem and cerebellum are classified respectively as periventricular, juxtacortical and infratentorial. The remaining lesions located in WM map are classified as deep white.

Report generation: At the end, a pdf report is automatically generated providing the lesion load, the number of lesions for each class and screenshots of the processed images. Moreover, in case the gender and the age of the patient are provided, the estimated volumes of WM, GM and CSF are compared to expected normal values based on lifespan models [START_REF] Coupe | Towards a unified analysis of brain maturation and aging across the entire lifespan: A MRI analysis[END_REF]. The proposed lesionBrain tool has been integrated into the volBrain 1 platform in full open access [START_REF] Manjon | volBrain: An Online MRI Brain Volumetry System[END_REF].

Validation framework

First, the method parameters were validated using training lesionBrain dataset through a K-fold cross validation. For RI-NLM segmentation and NLMr of the probability map, the patch size was set to 3x3x3 voxels as proposed in the original papers [START_REF] Guizard | Rotation-invariant multi-contrast non-local means for MS lesion segmentation[END_REF][START_REF] Coupe | An optimized blockwise nonlocal means denoising filter for 3-D magnetic resonance images[END_REF]. The search area was set to 9x9x9 voxels for RI-NLM and NLMr although 11x11x11voxels is suggested in [START_REF] Guizard | Rotation-invariant multi-contrast non-local means for MS lesion segmentation[END_REF][START_REF] Coupe | An optimized blockwise nonlocal means denoising filter for 3-D magnetic resonance images[END_REF]. This enables to reduce computational time with marginal accuracy loss. The number of used training images was set to the maximum (i.e., 86 when testing on the MSSEG Challenge 2016 dataset). For PEC we used the default parameters [START_REF] Romero | HIPS: A new hippocampus subfield segmentation method[END_REF]. Therefore, the number of networks was set to 10 and the two patch scales to 3x3x3 voxels and 7x7x7 voxels. During the validation, we first evaluate the improvement in terms of mean DICE coefficient provided by each component of the proposed segmentation pipeline -RI-NLM, RI-NLM+NLMr and RI-NLM+NLMr+PEC (i.e., lesionBrain). Then, lesionBrain is compared with six stateof-the-art methods. To this end, we used the mean DICE coefficient published by authors who have evaluated their method on the 15 MS patients of the training MSSEG Challenge 2016 dataset as we did here. First, lesionBrain is compared with two unsupervised methods based on graph-cut [START_REF] Beaumont | Multiple Sclerosis lesion segmentation using an automated multimodal Graph Cut[END_REF] and thresholding as implemented in LST-LPA [START_REF] Schmidt | An automated tool for detection of FLAIR-hyperintense white-matter lesions in multiple sclerosis[END_REF]. In addition, the proposed method is compared with four supervised methods including Random Forest [START_REF] Vera-Olmos | Random Forest for Multiple Sclerosis Lesion Segmentation[END_REF] and recent advanced DL methods such as U-Net [START_REF] Hashemi | Tversky as a Loss Function for Highly Unbalanced Image Segmentation using 3D Fully Convolutional Deep Networks[END_REF], Nabla-Net [START_REF] Mckinley | Nabla-net: a deep dag-like convolutional architecture for biomedical image segmentation: application to white-matter lesion segmentation in multiple sclerosis[END_REF] and Dense-Net [START_REF] Hashemi | Tversky as a Loss Function for Highly Unbalanced Image Segmentation using 3D Fully Convolutional Deep Networks[END_REF]. Finally, the inter-expert variability estimated in [START_REF] Vera-Olmos | Random Forest for Multiple Sclerosis Lesion Segmentation[END_REF] between the seven experts is provided for reference purposes.

Results

First, Table 1 presents the mean DICE coefficient obtained with RI-NLM, RI-NLM+NLMr and lesionBrain of the MSSEG Challenge 2016 dataset. These results show that each component of the pipeline improved the segmentation accuracy. The mean DICE increased from 66.59% to 69.27% with the NLMr of the probability map and from 69.27% to 72.49% with PEC. Both improvements were found to be significant when tested with a paired t-test. This demonstrates the advantage of combining methods based on inter-subject similarity, intra-subject self-similarity and correction of systematic errors. Table 1 also shows the comparison of lesionBrain with six stateof-the-art methods. First, lesionBrain obtained the best mean DICE coefficient with 72.49 followed by the Dense-Net proposed in [START_REF] Coupe | An optimized blockwise nonlocal means denoising filter for 3-D magnetic resonance images[END_REF] which obtained 70.30. It has to be noted that lesionBrain only requires 2 contrasts while Dense-Net uses 5 contrasts.

Increasing the number of sequences has a negative impact on the acquisition time, the patient's comfort and the related costs. In addition, the Dense-Net has been trained using cross-validation which can introduce overfitting and thus overestimates the performance of the method. The Nabla-Net proposed in [START_REF] Mckinley | Nabla-net: a deep dag-like convolutional architecture for biomedical image segmentation: application to white-matter lesion segmentation in multiple sclerosis[END_REF] requires only one contrast and has been trained on external dataset. This method obtained a DICE of 67% which is similar to the accuracy obtained by RI-NLM with 2 contrasts, but less than the accuracy obtained with RI-NLM+NLMr or lesionBrain. Compared to Random Forest [START_REF] Vera-Olmos | Random Forest for Multiple Sclerosis Lesion Segmentation[END_REF] which obtained 63.80% of accuracy, RI-NLM, RI-NLM+NLMr and lesionBrain obtained higher accuracy while they require the same contrasts. All these methods obtained accuracy higher than inter-expert variability estimated at 63.02% contrary to the 3 remaining ones. The two unsupervised methods based on graph-cut [START_REF] Schmidt | An automated tool for detection of FLAIR-hyperintense white-matter lesions in multiple sclerosis[END_REF] and LST-LPA [START_REF] Schmidt | An automated tool for detection of FLAIR-hyperintense white-matter lesions in multiple sclerosis[END_REF] obtained a mean DICE of 57.09% and 61% respectively. Finally, the U-Net method proposed in [START_REF] Hashemi | Tversky as a Loss Function for Highly Unbalanced Image Segmentation using 3D Fully Convolutional Deep Networks[END_REF] obtained the worst accuracy with 56.42%. These results indicate that supervised methods are ranked among the best, better than inter-expert variability, while unsupervised methods failed to reach inter-expert variability. However, the use of CNN does not necessarily ensure a good accuracy since the worst method is based on a U-Net using 5 contrasts. Finally, Figure 1 shows examples of WML segmentation obtained by lesionBrain for three patients of the MSSEG Challenge 2016 dataset (for best, median and worst DICE).

Conclusion

In this paper, we present a new tool for WML segmentation using T1w and FLAIR MRI. Our method combined several complementary patch-based approaches to accurately segment WML. We evaluated its accuracy on the MSSEG challenge 2016 datasets with a strong ground truth based on the consensus of seven experts. During our validation, the performance obtained by lesionBrain were competitive compared to Dense-Net [START_REF] Hashemi | Tversky as a Loss Function for Highly Unbalanced Image Segmentation using 3D Fully Convolutional Deep Networks[END_REF], Nabla-Net [START_REF] Mckinley | Nabla-net: a deep dag-like convolutional architecture for biomedical image segmentation: application to white-matter lesion segmentation in multiple sclerosis[END_REF] and U-Net [START_REF] Hashemi | Tversky as a Loss Function for Highly Unbalanced Image Segmentation using 3D Fully Convolutional Deep Networks[END_REF]. Moreover, lesionBrain obtained a higher accuracy than the inter-expert variability. Finally, our tool is already integrated into a web-platform in open access.

Best DICE=89.35% Median DICE=74.14% Worst DICE=46.47%

Fig. 1 .

 1 Fig. 1. Examples of WML segmentation produced by lesionBrain for best, median and worst DICE obtained on the MSSEG Challenge 2016 dataset. True positives are in green, False Negatives in red and False Positives in blue.

Table 1 .

 1 Methods comparison on the 15 MS patients of the MSSEG challenge 2016 dataset in term of mean DICE coefficient.

	Methods	Mean DICE in %	Training	Modalities
	Inter-expert variability [4]	63.02
	lesionBrain	72.49	External	T1w and FLAIR
	Dense-Net [7]	70.30	Cross-validation	T1, T1Gd, T2, PD and FLAIR
	RI-NLM [5] + NLMr	69.27	External	T1w and FLAIR
	Nabla-Net [8]	67.00	External	FLAIR
	RI-NLM [5]	66.59	External	T1w and FLAIR
	Random Forest [4]	63.80	Cross-validation	T1w and FLAIR
	LST-LPA [3]	61.00	Unsupervised	FLAIR
	Graph-cut [2]	57.09	Unsupervised	T1, T2 and FLAIR
	U-Net [7]	56.42	Cross-validation	T1, T1Gd, T2, PD and FLAIR

http://volbrain.upv.es

Acknowledgement: This work benefited from the support of the project DeepVolBrain of the French National Research Agency (ANR). This study was achieved within the context of the Laboratory of Excellence TRAIL ANR-10-LABX-57 for the BigDataBrain project. Moreover, we thank the Investments for the future Program IdEx Bordeaux (ANR-10-IDEX-03-02, HL-MRI Project), Cluster of excellence CPU and the CNRS. This study has been also supported by the DPI2017-87743-R grant from the Spanish Ministerio de Economia, Industria y Competitividad.


Dominique Lecomte
email: dominique.lecomte@upmc.fr

Miroslav Zelen
email: zeleny@karlin.mff.cuni.cz

November

Analytic digraphs of uncountable Borel chromatic number under injective definable homomorphism

Keywords: 2010 Mathematics Subject Classification. 03E15, 54H05 Keywords and phrases. analytic, antichain, Borel, chromatic number, digraph, homomorphism, injective, minimal 1

We study the analytic digraphs of uncountable Borel chromatic number on Polish spaces, and compare them with the notion of injective Borel homomorphism. We provide some minimal digraphs incomparable with G 0 . We also prove the existence of antichains of size continuum, and that there is no finite basis.

Introduction

In this paper, A, B will be (binary) relations on some sets X, Y respectively. The diagonal of X is ∆(X) := {(x, x) | x ∈ X}. We will say that A is irreflexive, or a digraph, if A does not meet the diagonal (some authors call these relations simple digraphs). We set A -1 := {(x, y) ∈ X 2 | (y, x) ∈ A}. We say that A is symmetric if A = A -1 , and A is antisymmetric if A ∩ A -1 ⊆ ∆(X). The set s(A) := A ∪ A -1 is the symmetrization of A. We say that A is a graph if A is irreflexive and symmetric, and A is an oriented graph if A is irreflexive and antisymmetric. Recall that A is a subgraph of the digraph B if X ⊆ Y and A ⊆ B. An A-path is a finite sequence (x i ) i≤n of points of X such that (x i , x i+1 ) ∈ A if i < n. We say that A is connected if for any x, y ∈ X there is an A-path (x i ) i≤n with x 0 = x and x n = y. If A is a graph, then the connected component of x ∈ X is the set C(x) of points y ∈ X for which there is an A-path (x i ) i≤n with x 0 = x and x n = y. A graph A is acyclic if there is no injective A-path (x i ) i≤n with n ≥ 2 and (x n , x 0 ) ∈ A. If A is an acyclic graph and y ∈ C(x), then we denote by p A

x,y the unique injective A-path (x i ) i≤n with x 0 = x and x n = y. We say that A is locally countable if its horizontal and vertical sections are countable.

We write (X, A) (Y, B) when there is h : X → Y such that A ⊆ (h×h) -1 (B). If this holds, then we say that h is a homomorphism from (X, A) into (Y, B). When h can be injective, we write (X, A) inj (Y, B). The notion of injective homomorphism is very natural since it corresponds to the basic notion of subgraph. Indeed, if h is an injective homomorphism from (X, A) into (Y, B), then (h[X], (h×h) [A]) is a subgraph of (Y, B). Conversely, if (X, A) is a subgraph of (Y, B), then the canonical injection is an injective homomorphism from (X, A) into (Y, B). A coloring from (X, A) into some set Y is a map c : X → Y such that c(x) = c(x ) if (x, x ) ∈ A, i.e., a homomorphism from (X, A) into (Y, =).

The reader should see [K] for the standard descriptive set theoretic notions and notation. Let C be a class of functions between Polish spaces, e.g., continuous, Borel (denoted c, B respectively). If X, Y are Polish spaces and h can be in C, then we will use the notation C , inj C respectively. The study of definable colorings of analytic graphs was initiated in [K-S-T]. The C-chromatic number of a digraph A on a Polish space X is the smallest cardinality of a Polish space Y for which there is a C-coloring from (X, A) into Y .

Example. Let ψ : ω → 2 <ω be a natural bijection (ψ(0) = ∅, ψ(1) = 0, ψ(2) = 1, ψ(3) = 0 2 , ψ(4) = 01, ψ(5) = 10, ψ(6) = 1 2 , . . .). A crucial property of ψ is that ψ -1 (s) < ψ -1 (sε) if s ∈ 2 <ω and ε ∈ 2.

Note that |ψ(n)| ≤ n, so that we can define s n := ψ(n)0 n-|ψ(n)| . Some crucial properties of (s n ) are that it is dense (for each s ∈ 2 <ω , there is n such that s ⊆ s n ), and that |s n | = n. We set

G 0 := {(s n 0γ, s n 1γ) | n ∈ ω ∧ γ ∈ 2 ω }. The set s(G 0 ) is considered in [K-S-T],
where the following is essentially proved.

Theorem 1.1 (Kechris, Solecki, Todorčević) Let X be a Polish space and A be an analytic digraph on X. Then exactly one of the following holds:

(a) (X, A) B (ω, =) (i.e., (X, A) has countable Borel chromatic number), (b) (2 ω , G 0 ) c (X, A).

The minimal elements of (Q, ≤) are of particular importance since they have to be part of any basis, up to equivalence. The discussion after Theorem 1.1 shows that G 0 is inj c and inj B -minimal among analytic digraphs of uncountable Borel chromatic number. The main results in this paper are steps towards a positive answer to Question (4), and our paper is mentioned in the last version of [K-Ma].

Theorem 1.3 Let C ∈ {c, B}. There is a inj C -antichain {G 0 , G 1 , G -1 1 } made of digraphs inj Cminimal among analytic digraphs of uncountable Borel chromatic number.

Thus Theorem 1.2 holds for digraphs. Note that some antichains were already present in [L4]. The main result in the present paper is the minimality of G 1 , and thus a dichotomy result. We now provide a construction of the digraph G 1 . Note that G 0 can be viewed as the union of the graphs of the partial homeomorphisms h n : N sn0 → N sn1 given by h n (s n 0γ) := s n 1γ. In particular, the following picture holds if m < n and h m h n (α) , h m (α) are defined:

α hn hm / / h m (α) = h n (α) hm / / h m h n (α)
We define t n ∈ 2 <ω and maps g n : N tn0 → N tn1 , and G 1 will be the union of the graphs of the g n 's.

One of the crucial properties of the g n 's is that g m g n (α) = g m (α) if m < n and g m g n (α) , g m (α) are defined. In particular, the following picture holds and violates the previous one: This provides some cycles, which have to exist in examples orthogonal to G 0 , by the discussion after Theorem 1.1. The ≤ C -antichain mentioned before Question (4) was constructed with different configurations of cycles. We believe that some other algebraic conditions of this type could lead to a positive answer to Question (4). Our second main result is a weak version of this.

Theorem 1.4 Let C ∈ {c, B}.

(a) There is a inj C -antichain of size 2 ℵ 0 made of Σ 0 2 digraphs of uncountable Borel chromatic number.

(b) There is a inj C -strictly increasing chain of size ℵ 0 made of Σ 0 2 digraphs of uncountable Borel chromatic number.

These digraphs, in fact differences of two closed sets, are not all minimal. In fact, we first construct a inj B -antichain of size ℵ 0 made of digraphs in the style of G 1 , that could be minimal as in Theorem 1.3. We then consider suitable direct sums of these digraphs. This antichain of size ℵ 0 is in fact made of pairwise incompatible digraphs, which gives our third main result (recall that p, q ∈ Q are incompatible if there is no r ∈ Q with r ≤ p, q). Theorem 1.5 Let C ∈ {c, B}. Any inj C -basis for the class of analytic digraphs of uncountable Borel chromatic number on Polish spaces is infinite.

We now provide a concrete description of G 1 . We first define a sequence (q n ) n∈ω of natural numbers by setting q 0 := 0 and q n+1 := 32 qn . Note that (q n ) n∈ω is strictly increasing. In particular, |ψ(n)| ≤ n ≤ q n < 2 qn , so that t n := ψ(n)0 2 qn -|ψ(n)| is well-defined and has length 2 qn . We then set S n := {2 qn •j | j ≥ 1}, define θ n : ω → ω and g n by

θ n (k) := k if k / ∈ S n , 2 qn •(2j +1) if k = 2 qn •j, g n (α)(k) := 1 if k = 2 qn , α θ n (k) if k = 2 qn .
The next definition catches some of the crucial properties of the sequence (g n ) defining G 1 . As noted in [L4], a great variety of very different non-potentially closed relations appear at the level of differences of two closed sets. For the kind of examples we will consider, being non-potentially closed and having uncountable Borel chromatic number are equivalent properties. Let us make this more precise.

Notation. If (f n ) is a sequence of functions, then we set A f := n∈ω Graph(f n ). Definition 1.6 We say that X, (f n ) is a complex situation if (a) X is
(c) ∆(X) ⊆ A f \A f .
This kind of situations play an important role in the theory of potential complexity (see, for example, Definition 2.2 in [L3], and also Definitions 13, 26 and 31 in [L4]). These properties are sufficient to ensure that A f is a Σ 0 2 digraph of uncountable Borel chromatic number (see Corollary 2.2). We prove a result giving some additional motivation for introducing this notion, which is in fact very general.

Theorem 1.7 Let Y be a Polish space and B be an analytic digraph on Y . Then exactly one of the following holds:

(a) (Y, B) has countable Borel chromatic number, (b) there is a complex situation X, (f n ) such that the inequality (X,

A f ) inj c (Y, B) or (X, A f ) inj c (Y, B -1 ) holds.
We prove more than the minimality of G 1 .

Theorem 1.8 Let X, (f n ) be a complex situation satisfying the following additional property:

(d) f m f n (x) = f m (x) if m < n and f m f n (x) , f m (x) are defined. Then (2 ω , G 1 ) inj c (X, A f ).
The organization of this paper is as follows. In Section 2, we provide some basic properties of complex situations. In Section 3, we characterize when the digraph associated with a complex situation is minimal among analytic digraphs of uncountable Borel chromatic number, and prove Theorem 1.7. In Section 4, we prove a relatively general lemma ensuring the injectivity of the homomorphism h implicitly mentioned in the statement of Theorem 1.8.

In Section 5, we show that G 1 comes from a complex situation, introduce some finitary objects used in the construction of h, and prove their important properties. In particular, in many Cantorlike constructions of homomorphisms or reductions, we construct approximations, indexed by finite binary sequences, of the desired infinitary objects. The construction is usually made by induction on the length of the finite binary sequences. So we consider the partitions into basic clopen sets (N x ) x∈2 l of 2 ω , for each l ∈ ω. Here it will be more convenient to replace 2 l with some subset X l of 2 <ω containing sequences of different lengths since the g n 's "forget" some coordinates. In Section 6, we construct our homomorphism and prove Theorems 1.3 and 1.8. In Section 7, we prove Theorems 1.4 and 1.5, and show that our three main results also hold for graphs.

Some basic properties of complex situations

The next lemma is essentially Lemma 3.5 in [L1], and the crucial point of its proof.

Lemma 2.1 Let X be a nonempty Polish space and, for n ∈ ω, D n , R n be dense G δ subsets of some open subsets of X, and f n : D n → R n be a continuous, open and onto map.

(a) Let G be a dense G δ subset of X. Then Graph(f n ) ⊆ Graph(f n ) ∩ G 2 . (b) We assume that ∆(X) ⊆ A f \A f . Then (X, A f ) has uncountable Borel chromatic number.
Proof. (a) See Lemma 3.5 in [L1].

(b) As ∆(X) ⊆ ¬A f , (X, A f ) is a digraph and thus its Borel chromatic number is defined. We argue by contradiction to see that it is uncountable, which gives a countable partition (B n ) of X into Borel sets with A f ∩ B 2 n = ∅. By 13.5 in [K], there is a finer Polish topology τ on X such that the B n 's are clopen in (X, τ ). By 15.2 in [K], the identity of X equipped with its initial topology into (X, τ ) is Borel. By 11.5 in [K] it is Baire measurable. By 8.38, in [K], there is a dense G δ subset G of X on which the B n 's are clopen. We pick x ∈ G, which exists since X is Polish and nonempty. We choose n with x ∈ B n . By (a),

A f ∩ G 2 = A f ∩ G 2 ∩ G 2 , so that (x, x) ∈ A f ∩ G 2 ∩ (B n ∩ G) 2 . As B n ∩ G is clopen in G, A f ∩ (B n ∩ G) 2 is nonempty, which is absurd. Corollary 2.2 Let X, (f n ) be a complex situation. Then A f is a Σ 0 2 digraph of uncountable Borel chromatic number. Proof. Note that A f = n∈ω Graph(f n ) is Σ 0
2 since the f n 's are continuous with open domain. Moreover, Lemma 2.1 ensures that (X, A f ) has uncountable Borel chromatic number. Condition (d) in Theorem 1.8 is motivated by the following result, which is essentially Claim 1 in the proof of Theorem 10 in [L4]. This condition ensures that A f is inj B -incomparable with G 0 .

Notation. In the sequel, D n will be the domain of the function f n .

Lemma 2.3 Let X be a Polish space, and g 0 , g 1 , . . . : X → X be fixed point free Borel partial functions such that g m g n (x) = g m (x) if m < n and g m g n (x) , g m (x) are defined. Then every locally countable analytic subset of A g has countable Borel chromatic number.

Proof. Suppose that H is a locally countable analytic subset of A g . By 35.13 in [K] and Lemma 2.4.(a) in [L2], there are Borel partial injections f n on X such that H ⊆ A f ⊆ A g . By replacing each f n with its restrictions to the sets {x ∈ D n | f n (x) = g m (x)}, for m ∈ ω, we can assume that, for all n ∈ ω, there is k n ∈ ω such that f n = g kn | Dn . It is easily seen that the graph of a fixed point free Borel function has countable Borel chromatic number (see Proposition 4.5 of [K-S-T]). So, by replacing f n with its restriction to countably many Borel sets, we can also assume that D 2 n ∩ k≤kn Graph(g k ) = ∅ for all n ∈ ω. It only remains to note that D 2 n ∩ k>kn Graph(g k ) = ∅. In order to see this, simply observe that if k > k n and x, g k (x) ∈ D n , then f n (x) = g kn (x) = g kn • g k (x) = f n • g k (x), which contradicts the fact that f n is a partial injection.

Corollary 2.4 Let X, (f n ) be a complex situation satisfying Condition (d) in Theorem 1.8. Then

{G 0 , A f , (A f ) -1 } is a inj B -antichain. Proof. Assume that G 0 is inj B -below A f , with witness π. Then (π × π)[G 0 ] is a
, G 0 ) inj c (2 ω , G -1 0 ). Thus G 0 and (A f ) -1 are inj B -incomparable. If (2 ω , (A f ) -1 ) inj B (2 ω , A f ) with witness h, then (h×h)[(A f ) -1 ] is a locally countable subset of A f since A f has countable vertical sections, which contradicts Lemma 2.3.
The next two lemmas will be used in the proof of Theorem 1.8. Lemma 2.5 Let X, (f n ) be a complex situation satisfying Condition (d) in Theorem 1.8, V 0 , V 1 be subsets of X, and m < n be natural numbers such that

V 0 ⊆ D m ∩ D n and V 1 ⊆ f n [V 0 ] ∩ D m . Then f m [V 1 ] ⊆ f m [V 0 ]. Proof. Pick y ∈ V 1 , and x ∈ V 0 with y = f n (x). Note that f m f n (x) is defined, as well as f m (x). By Condition (d), f m f n (x) = f m (x). This implies that f m (y) = f m (x) ∈ f m [V 0 ].
Lemma 2.6 Let X, (f n ) be a complex situation such that X is zero-dimensional and the D n 's are clopen, V be a nonempty open subset of X, and m be a natural number. Then we can find n > m and nonempty clopen subsets and(x, y) in this intersection. In particular, x ∈ D n and y = f n (x). We choose a clopen subset

V 0 , V 1 of X such that V 0 ⊆ V ∩ D n and V 1 ⊆ V ∩ f n [V 0 ]. Proof. The assumption on X, (f n ) implies that ∆(X) ⊆ n>m Graph(f n ) since the Graph(f n )'s are closed. This gives n > m such that V 2 ∩ Graph(f n ) = ∅,
V 0 of X with x ∈ V 0 ⊆ V ∩ D n , and a clopen subset V 1 of X with y ∈ V 1 ⊆ V ∩ f n [V 0 ].

The characterization of the minimality

We will characterize when the set A f associated with a complex situation X, (f n ) is inj cminimal among analytic digraphs of uncountable Borel chromatic number. We will need a strengthening of the notion of a complex situation. Definition 3.1 We say that a complex situation X, (f n ) is a strongly complex situation if (a) X is a nonempty zero-dimensional perfect Polish space, (b) the f n 's are partial continuous and open maps whose domain and range are clopen in X, (c) the restriction of any f n to any nonempty open subset of its domain is not countable-to-one.

The reader should see [M] for the basic notions of effective descriptive set theory. Let X be a recursively presented Polish space. The topology ∆ X on X is generated by ∆ 1 1 (X). This topology is Polish (see the proof of Theorem 3.4 in [Lo]). The Gandy-Harrington topology Σ X on X is generated by Σ 1 1 (X). Recall that andΣ 1 1 , and (Ω X , Σ X ) is a zero-dimensional Polish space (in fact, the intersection of Ω X with any nonempty Σ 1 1 set is a nonempty clopen subset of (Ω X , Σ X )-see [L1]).

Ω X := {x ∈ X | ω x 1 = ω CK 1 } is Borel
Lemma 3.2 Let X, (f n ) be a complex situation such that (2 ω , G 0 ) inj c (X, A f ), P be a Borel subset of X, and (S n ) be a sequence of analytic subsets of X such that

A := n∈ω Graph(f n|S n ) ⊆ P 2
has uncountable Borel chromatic number. Then we can find a Borel subset S of P , a finer topology τ on S, and a sequence (C n ) of clopen subsets of Y := (S, τ ) such that Y, (f n|C n ) is a strongly complex situation and

C n ⊆ S ∩ f -1 n (S) ∩ S n for each n ∈ ω. Proof.
In order to simplify the notation, we will assume as usual that X is recursively presented,

(f n ) is ∆ 1 1 (so that A f is ∆ 1 1 too), P is ∆ 1 1 , and (S n ) is Σ 1 1 (so that A is Σ 1 1 ). We set, for each n ∈ ω and each W ⊆ X, Φ n (W ) ⇔ f n|D n∩W is countable-to-one. Note that Φ n is Π 1 1 on Σ 1 1 .
Indeed, let Z be a recursively presented Polish space, and S be in

Σ 1 1 (Z ×X). Then Φ n (S z ) ⇔ ∀x ∈ X f -1 n ({x}) ∩ S z is countable. Note that f -1 n ({x}) ∩ S z is Σ 1 1 (z, x). By 4F.1 in [M], f -1 n ({x}) ∩ S z is countable if and only if it is contained in ∆ 1 1 (z, x) ∩ X, which is a Π 1 1 condition (in (z, x)).
This argument shows that if

X n := {∆ ∈ ∆ 1 1 (X) | Φ n (∆)}, then (X n ) is Π 1 1
, and also that we can apply the effective version of the first reflection theorem (see 35.10 in [K]). Let us prove that if C ∈ Σ 1 1 (X) and C\X n is not empty, then f n|D n∩C is not countable-to-one. We argue by contradiction. As C\X n ∈ Σ 1 1 and Φ n (C\X n ) holds, the effective version of the first reflection theorem gives

∆ ∈ ∆ 1 1 such that C\X n ⊆ ∆ and Φ n (∆) holds. Thus ∆ ⊆ X n and C\X n ⊆ X n \X n is empty, which is absurd. Note that A = n∈ω Graph(f n|S n∩Xn ) ∪ n∈ω Graph(f n|S n\Xn ). As n∈ω Graph(f n|S n∩Xn ) is locally countable analytic, it has countable Borel chromatic number since (2 ω , G 0 ) inj c (X, A f ), by the discussion after Theorem 1.1. Thus A := n∈ω Graph(f n|S n\Xn ) is a Σ 1 1 relation on X with uncountable Borel chromatic number.
By 4D.2 and 4D.14 in [M],

D X := {x ∈ X | x ∈ ∆ 1 1 } is countable and Π 1 1 . We set S := {x ∈ P | (x, x) ∈ A ∆ 2 X } ∩ Ω X \D X , τ := Σ X |S and, for each n ∈ ω, C n := S ∩ f -1 n (S) ∩ S n \X n .
Note that S is a Borel and Σ 1 1 subset of X. Thus the C n 's are Σ 1 1 and clopen subsets of

Y . As S ∈ Σ 1 1 , Y is a zero-dimensional perfect Polish space. We set C := {x ∈ P | (x, x) ∈ A ∆ 2 X }.
Let us check that C \D X is nonempty. We argue by contradiction. Then C is Σ 1 1 and contained in D X . The effective separation result gives

∆ ∈ ∆ 1 1 (X) with C ⊆ ∆ ⊆ D X . If x ∈ P \∆, then there is U x ∈ ∆ 1 1 (X) containing x with A ∩ U 2 x = ∅.
This also holds if x ∈ ∆ with U x := {x}. But this contradicts the fact that A has uncountable Borel chromatic number.

Thus C \ D X is a nonempty Σ 1 1 subset of X, which therefore meets Ω X . This shows that S is not empty. Note also that (

x, x) ∈ A ∆ 2 X ∩ S 2 = A Σ 2 X ∩ S 2 = A ∩ S 2 Y 2 if x ∈ S. We proved that Y, (f n|C n ) is a strongly complex situation. Corollary 3.3 Let X, (f n ) be a complex situation such that (2 ω , G 0 ) inj c (X, A f ).
The following are equivalent: (a) A f is inj c -minimal among analytic digraphs of uncountable Borel chromatic number, (b) for any Borel subset S of X, any finer topology τ on S, and any sequence

(C n ) of clopen subsets of Y := (S, τ ), (X, A f ) inj c Y, n∈ω Graph(f n|C n ) if Y, (f n|C n ) is a strongly complex situation. Proof. (a) ⇒ (b) By Corollary 2.2, n∈ω Graph(f n|C n ) is an analytic digraph of uncountable Borel chromatic number. As (Y, n∈ω Graph(f n|C n ) inj c (X, A f ), we are done. (b) ⇒ (a)
Let Z be a Polish space, and A be an analytic digraph on Z of uncountable Borel chromatic number. We assume that (Z, A) inj B (X, A f ), with witness u : Z → X. We set

P := u[Z], so that P is a Borel subset of X. Note that A := (u × u)[A] ⊆ A f
is an analytic relation on P with uncountable Borel chromatic number, which gives a sequence (S n ) n∈ω of analytic subsets of X with A = n∈ω Graph(f n|S n ). Lemma 3.2 gives a Borel subset T of P , a finer topology σ on T , and a sequence (O n ) of clopen subsets of W := (T, σ) such that W, (f n|O n ) is a strongly complex situation and

O n ⊆ T ∩ f -1 n (T ) ∩ S n . We put A := n∈ω Graph(f n|O n ). Note that b := u -1 |W : W → u -1 (W ) is Borel and one-to-one. Let G be a dense G δ subset of W such that b| G is continuous. This function is a witness for the fact that (G, A ∩ G 2 ) inj c (Z, A). By Lemma 2.1, we get Graph(f n|O n ) ⊆ Graph(f n|O n ) ∩ G 2 . Thus A = A ∩ G 2 , and ∆(G) ⊆ A ∩ G 2 .
Let us prove that A ∩ G 2 has uncountable Borel chromatic number. We argue by contradiction, which gives a countable partition (B q ) of G into Borel sets. We can find q ∈ ω, a nonempty open subset O of W , and a dense

G δ subset H of W with O ∩ H ⊆ B q . The previous argument shows that ∆(G ∩ H) ⊆ A ∩ (G ∩ H) 2 . Therefore ∆(O ∩ G ∩ H) ⊆ A ∩ (O ∩ G ∩ H) 2 ⊆ A ∩ G 2 ∩ B 2 q = ∅, which is absurd. We apply Lemma 3.2 to W, (f n|O n ) , G and G ∩ f -1 n (G) ∩ O n
, which gives a Borel subset S of G, a topology τ on S finer than σ, and a sequence

(C n ) of clopen subsets of Y := (S, τ ) such that Y, (f n|C n ) is a strongly complex situation and C n ⊆ S ∩ f -1 n (S) ∩ O n . It remains to note that (X, A f ) inj c Y, n∈ω Graph(f n|C n ) inj c (G, A ∩ G 2 ) inj c (Z, A), by (b).
Remark. This proof also shows that (b) implies that A f is inj B -minimal among analytic digraphs of uncountable Borel chromatic number.

Proof of Theorem 1.7. By Corollary 2.2, (a) and (b) cannot hold simultaneously. So assume that (a) does not hold. Theorem 1.1 provides h : 2 ω → Y continuous with (h×h)[G 0 ] ⊆ B. Note that G 0 comes from a complex situation. By Corollary 2.2, G 0 is a Σ 0 2 relation on the compact space 2 ω . Thus G 0 and (h×h)[G 0 ] are K σ digraphs of uncountable Borel chromatic number. The canonical injection is a witness for the fact that Y, (h×h)[G 0 ] inj c (Y, B). So we may assume that B is K σ . Let (C n ) be a sequence of closed digraphs on Y whose union is B.

We now argue essentially as in the proof of Theorem 2.3 in [L2]. In order to simplify the notation, we will assume as usual that Y is recursively presented and

(C n ) is ∆ 1 1 . As in the proof of Theorem 1.1, we set X 1 := Y \ {S ∈ Σ 1 1 (Y ) | B ∩ S 2 = ∅} , so that X 1 is a nonempty Σ 1 1 subset of Y , disjoint from {y ∈ Y | y ∈ ∆ 1
1 }, and satisfies the following property:

∀S ∈ Σ 1 1 (Y ) (∅ = S ⊆ X 1 ⇒ B ∩ S 2 = ∅).
We set

Z := (X 1 ∩ Ω Y , Σ Y )
, so that Z is a nonempty zero-dimensional perfect Polish space. We also set S :

= {S ∈ Σ 1 1 (Z) | ∅ = S ⊆ Z}. If S ∈ S, then we can find n with C n ∩ S 2 = ∅. Note that C n ∩ S 2 is a closed relation on Z. Moreover, if U is an open relation on Z, then the projections of U ∩ C n ∩ S 2 are open subsets of Z.
Theorem 1.13 in [L2] provides, for each S ∈ S, dense G δ subsets F S , G S of some nonempty open subsets of Z and g S :

F S → G S onto, continuous and open such that Graph(g S ) ⊆ C n ∩ S 2 or Graph(g S ) ⊆ (C n ∩ S 2 ) -1 . We set G(g S ) := Graph(g S ) if Graph(g S ) ⊆ C n ∩ S 2 , Graph(g S ) -1 if Graph(g S ) ⊆ (C n ∩ S 2 ) -1 , so that G(g S ) ⊆ B ∩ S 2 .
Let α ∈ 2 ω such that Z is recursively in α presented and the sequence G(g

S ) S∈S is ∆ 1 1 (α). Let G be a dense G δ and Σ 1 1 (α) subset of Z on which Σ Y and ∆ α Z :=< ∆ 1 1 (α)(Z) > coincide, which exists by Lemma 2.1 in [L2]. Let Σ α Z :=< Σ 1 1 (α)(Z) >, which
gives Ω α Z like before Lemma 3.2. Moreover, the proof of Theorem 2.3 in [L2] shows that

Ω α Z is comeager in Z, as well as G ∩ Ω α Z . We set W := (G ∩ Ω α Z , Σ α Z ) and define, for S ∈ S, a partial function f S by G(f S ) := G(g S ) ∩ W 2 , so that W is a nonempty zero-dimensional Polish space and W, S∈S G(f S ) inj c (Y, B).
Moreover, for each S ∈ S, f S is a partial continuous and open map with clopen domain and range in W . We then note that

∆(W ) ⊆ S∈S G(g S ) Z 2 ∩ W 2 = S∈S G(g S ) (∆ α Z ) 2 ∩ W 2 = S∈S G(g S ) (Σ α Z ) 2 ∩ W 2 ⊆ S∈S G(f S ) W 2 . We set S 0 := {S ∈ S | Graph(g S ) ⊆ B}, S 1 := {S ∈ S | Graph(g S ) ⊆ B -1 } and, for ε ∈ 2, W ε := {w ∈ W | (w, w) ∈ S∈Sε G(f S )}.
Note that (W 0 , W 1 ) is a covering of W into closed sets, which gives a nonempty clopen subset X of W and ε ∈ 2 with X ⊆ W ε . Note that X is a nonempty Polish space, G(f S ) ∩ X 2 defines a partial continuous and open map with open domain and range in X if S ∈ S ε , and

∆(X) ⊆ S∈Sε G(f S ) ∩ X 2 X 2 \ S∈Sε G(f S ) ∩ X 2 . We enumerate (f n ) := (f S ) |X∩f -1 S (X) S∈Sε . If ε = 0, then X, (f n ) is a complex situation with (X, A f ) inj c (Y, B). If ε = 1, then X, (f n ) is a complex situation with (X, A f ) inj c (Y, B -1 ).
4 The lemma ensuring the injectivity

Recall the set X l mentioned at the end of the introduction. An oriented graph A l on X l will contain finite approximations of a subset of G 1 with acyclic symmetrization. We now isolate some important properties of A l leading to a relatively general lemma ensuring the injectivity of the homomorphism in Theorem 1.8.

Notation. Let X be a set, and A be an oriented graph on X. We set, for x ∈ X,

   Succ(x) := {y ∈ X | (x, y) ∈ A} and max X := {x ∈ X | Succ(x) = ∅}, Pred(x) := {y ∈ X | (y, x) ∈ A} and min X := {x ∈ X | Pred(x) = ∅}.
The following oriented graphs will be of particular importance in the sequel.

Definition 4.1 An oriented graph A on a set X is unambiguously oriented if |Succ(x)| ≤ 1 for each x ∈ X.
If moreover A has acyclic symmetrization, then we say that A is an uogas. Lemma 4.2 Let A be an uogas on a finite set X.

(a) Let l be a natural number,

(y i ) i≤l ∈ X l+1 such that y i+1 ∈ Succ(y i ) if i < l. Then (y i ) i≤l is injective. In particular, (y i ) i≤l = p s(A) y 0 ,y l . (b) Let y ∈ X, x ∈ C(y) ∩ max X , and p := p s(A) y,x . Then p(i), p(i+1) ∈ A if i < |p|-1. (c) The intersection of max X with each s(A)-connected component C is a singleton {x C }. (d) Let (y, x) ∈ A and p := p s(A) y,x C(y) . Then |p| ≥ 2 and p(1) = x. Proof. (a) It is enough to see that (y i ) i≤l is injective. This is clear if l = 0. As A is irreflexive, y i = y i+1 if i < l. As A is an oriented graph, y i = y i+2 if i < l -1. As s(A) is acyclic, (y i ) i≤l is injective, by induction on l.
(b) We argue by induction on m := |p|-i. For m = 2, we argue by contradiction, so that x, p(i) ∈ A. Thus p(i) ∈ Succ(x), which contradicts the fact that x ∈ max X . So assume that p(|p|-m), p(|p|-m+1) ∈ A.

We argue by contradiction, so that p(|p|-m), p(|p|-m-1) ∈ A. Thus p(|p|-m+1) and p(|p|-m-1) are different elements of Succ p(|p|-m) , which contradicts the fact that A is unambiguously oriented.

(c) Let C be a s(A)-connected component, and {x m | m < l} be an injective enumeration of C. We argue by contradiction to prove that max X meets C. This means that Succ(x m ) = ∅ if m < l. We define, inductively on i, a sequence (m i ) i≤l as follows. We first set m 0 := 0. Assume that i < l and m i has been defined. As Succ(x m i ) = ∅, there is m i+1 < l such that x m i+1 ∈ Succ(x m i ). By (a), (m i ) i≤l ∈ l l+1 is injective, which is absurd.

Assume now that, for example, x 0 , x 1 ∈ C ∩ max X . Let p 0 := p s(A)

x 0 ,x 1 and p 1 := p s(A)

x 1 ,x 0 , so that

p 1 (i) = p 0 (n-i-1) if i < n := |p 1 | = |p 0 |. By (b), p 0 (n-2), x 1 , x 1 , p 1 (1) ∈ A,
which contradicts the fact that A is an oriented graph.

(d) We set y 0 := y, y 1 := x, and choose y i+1 ∈ Succ(y i ) if this last set is not empty. After finitely many steps, this construction stops and provides (y i ) i≤l with l ≥ 1, by (a) and since X is finite. Note that y l = x C(y) and (y i ) i≤l = p, by construction and by (a) and (c).

The homomorphism h in Theorem 1.8 will be obtained thanks to a Cantor-like construction. In the inductive step of this construction, we will consider an uogas on a finite set X. We will associate open sets to the elements of X. As we want h to be injective, we will have to ensure the disjunction of these open sets. This will be achieved in Lemma 4.7 to come. Its proof will use the following objects.

Notation. Let A be an uogas on a finite set X. If y ∈ X, then Lemma 4.2 allows us to set p y := p s(A) y,x C(y) . We set L := |X|, and enumerate X := {x m |m < L} injectively in such a way that

(|p xm |) m<L is increasing. Let L 0 ≤ L be maximal such that x m ∈ max X if m < L 0 , so that {x m |m < L 0 } enumerates injectively max X .
The idea is to make, inductively on m, L copies of x m if m ≥ L 0 , keeping the A-relations. In order to do this, we will give labels to the elements of X. We set

X m := x k , (0) | k < L and A m := x k , (0) , x l , (0) | (x k , x l ) ∈ A if m < L 0 . Assume that L 0 ≤ m+1 < L.
We put the elements of X m whose X-coordinate is not x m+1 or one of its (iterated) predecessors in

R m+1 := (x k , σ) ∈ X m | x m+1 / ∈ p x k .
We also set, for σ ∈ L ≤m+1 and j < L,

X σ m+1 := (x k , σ) ∈ X m | x m+1 ∈ p x k , X σj m+1 := (x k , σj) ∈ X ×L <ω | (x k , σ) ∈ X m ∧ x m+1 ∈ p x k
(some of these sets can be empty). Then we set X m+1 := R m+1 ∪ σ∈L ≤m+1 ,j<L X σj m+1 and

A m+1 := (x k , σ), (x l , τ ) ∈ A m | k, l ≤ m ∪ (x m+1 , σj), (x i , σ) ∈ (X m+1 ) 2 | (x m+1 , σ), (x i , σ) ∈ A m ∧ j < L ∪ (x k , σ), (x l , σ) ∈ A m | k > m+1 ∧ x m+1 / ∈ p x l ∪ (x k , σj), (x l , σj) ∈ (X m+1 ) 2 | (x k , σ), (x l , σ) ∈ A m ∧ j < L ∧ x m+1 ∈ p x l . We enumerate injectively {σ ∈ L <ω | (x m+1 , σ) ∈ X m } by {σ n | n < N }. We set, for p ≤ N , X p m+1 := R m+1 ∪ n<p,j<L X σnj m+1 ∪ p≤n<N X σn m+1
, so that X 0 m+1 = X m and X N m+1 = X m+1 . We also define the corresponding intermediate versions of A m+1 as follows.

We set, for p ≤ N ,

A p m+1 := (x k , σ), (x l , τ ) ∈ A m | k, l ≤ m ∪ n<p (x m+1 , σ n j), (x i , σ n ) ∈ (X p m+1 ) 2 | (x m+1 , σ n ), (x i , σ n ) ∈ A m ∧ j < L ∪ p≤n<N (x m+1 , σ n ), (x i , σ n ) ∈ (X p m+1 ) 2 | (x m+1 , σ n ), (x i , σ n ) ∈ A m ∪ (x k , σ), (x l , σ) ∈ A m | k > m+1 ∧ x m+1 / ∈ p x l ∪ n<p (x k , σ n j), (x l , σ n j) ∈ (X p m+1 ) 2 | (x k , σ n ), (x l , σ n ) ∈ A m ∧ j < L ∧ x m+1 ∈ p x l ∪ p≤n<N (x k , σ n ), (x l , σ n ) ∈ A m | x m+1 ∈ p x l .
Lemma 4.3 Let A be an uogas on a finite set X. Then A m (respectively, A p m+1 ) is also an uogas on the finite set X m (respectively,

X p m+1 ) if m < L (respectively, L 0 ≤ m+1 < L and p ≤ N ). Proof. Note first that (X m , A m ) is a copy of (X, A) if m < L 0 .
In particular, X m is finite, A m is an oriented graph on X m with acyclic symmetrization, and |Succ(q)| ≤ 1 for each q ∈ X m (with respect to A m ). Then we assume that L 0 ≤ m + 1 < L. Note that X m+1 is finite, A m+1 is an oriented graph on X m+1 , and |Succ(q)| ≤ 1 for each q ∈ X m+1 (with respect to A m+1 ). Let us check that s(A m+1 ) is acyclic. The restriction of A m+1 to a fixed X σj m+1 is isomorphic to a subgraph of A m , and has therefore acyclic symmetrization. Note that the X σj m+1 's are pairwise disjoint and not s(A m+1 )-related, and that X σj m+1 contains (x m+1 , σj) if it is not empty (i.e., if (x m+1 , σ) is in X m ). The restriction of the oriented graph A m+1 to R m+1 is also isomorphic to a subgraph of A m . Moreover, the only possible s(A m+1 )-edge between an element of X σj m+1 and element of R m+1 is between (x m+1 , σj) and (x i , σ), where x i ∈ Succ(x m+1 ). This shows the acyclicity of s(A m+1 ). We argue similarly for (X p m+1 , A p m+1 ). Definition 4.4 We say that the tuple T := X, A, Z, (f n ) is a mapping tuple if A is an uogas on the finite set X and Z, (f n ) is a strongly complex situation.

Notation. Let T := X, A, Z, (f n ) be a mapping tuple. We set

   E T := u, (V x ) x∈X ∈ ω X ×(Σ 0 1 (Z)\{∅}) X | ∀(x, y) ∈ A V x ⊆ D u(x) ∧ V y = f u(x) [V x ] , U T := u, (V x ) x∈X ∈ ω X ×(Σ 0 1 (Z)\{∅}) X | ∀(x, y) ∈ A V x ⊆ D u(x) ∧ V y ⊆ f u(x) [V x ]
. Lemma 4.5 Let T := X, A, Z, (f n ) be a mapping tuple, and u, (V x ) x∈X ∈ U T . Then we can find a family

(W x ) x∈X of subsets of Z such that (a) u, (W x ) x∈X ∈ E T , (b) W x ⊆ V x if x ∈ X, and W x = V x if x ∈ max X .
Proof. We define W x by induction on

|p x |. If |p x | = 1, then we set W x := V x . Assume that |p x | ≥ 2, so that W y has been defined if y := p x (1). We set W x := V x ∩ f -1 u(x) (W y ).
We are done, by Lemma 4.2.

Lemma 4.6 Let T := X, A, Z, (f n ) be a mapping tuple, u, (V x ) x∈X ∈ E T , x 0 ∈ X, and W x 0 be a nonempty open subset of V x 0 . Then we can find a family

(W x ) x∈X\{x 0 } of subsets of Z such that (a) u, (W x ) x∈X ∈ E T , (b) W x ⊆ V x if x ∈ X, and W x = V x if x / ∈ C(x 0 ).
Proof. We set, for x ∈ C(x 0 ), q x := p s(A)

x,x 0 . We define W x by induction on |q x |, the case |q x | = 1 (i.e., x = x 0 ) being done. So assume that |q x | ≥ 2, so that W y has been defined if y := q x (1). We set

W x :=    f u(y) [W y ] if (y, x) ∈ A, V x ∩ f -1 u(x) (W y ) if (x, y) ∈ A.
If x ∈ X \C(x 0 ), then we set W x := V x .

Notation. Let A be an uogas on X finite, and x ∈ X. We set M x := max{|p

s(A) y,x | | y ∈ min X ∧ x ∈ p y }.
Lemma 4.7 Let T := X, A, Z, (f n ) be a mapping tuple, d ∈ ω, and u, (V x ) x∈X ∈ U T . Then we can find a family

(W x ) x∈X of subsets of Z such that (a) u, (W x ) x∈X ∈ E T , (b) W x ⊆ V x , W x ∈ ∆ 0 1 (Z) and diam(W x ) ≤ 2 -d if x ∈ X, (c) W x ∩ W y = ∅ if x = y ∈ X.
Proof. We consider the oriented graphs A m (respectively, A p m+1 ) on X m (respectively, X p m+1 ) defined before Lemma 4.3. We set, for m < L, T m := X m , A m , Z, (f n ) . Similarly, we set, when L 0 ≤ m+1 < L and p ≤ N , T p m+1 := X p m+1 , A p m+1 , Z, (f n ) . By Lemma 4.3, all these tuples are mapping tuples. We define, for m < L, u m : X m → ω by u m (x k , σ) := u(x k ). We also define, when

L 0 ≤ m+1 < L and p ≤ N , u p m+1 : X p m+1 → ω by u p m+1 (x k , σ) := u(x k ).
We first construct, by induction on m < L, a family (W m q ) q∈Xm of nonempty open subsets of Z satisfying

(1)

W m+1 x k ,σ ⊆ W m x k ,σ ⊆ V x k (2) u m , (W m q ) q∈Xm ∈ E Tm (3) diam(W m xm,σ ) ≤ 2 -d (4) ∀j = j < L W m
xm,σj ∩ W m xm,σj = ∅ We will apply Lemmas 4.5 and 4.6 to perform this construction. For m = 0, we will apply Lemma 4.5 to T 0 and u 0 . We choose a nonempty open subset V x 0 ,(0) of V x 0 with diameter at most 2 -d , and we set V x k ,(0) := V x k if 0 < k < L. Note that u 0 , (V q ) q∈X 0 ∈ U T 0 . Lemma 4.5 provides a family

(W 0 q ) q∈X 0 of subsets of Z such that (a) u 0 , (W 0 q ) q∈X 0 ∈ E T 0 , (b) W 0 x k ,(0) ⊆ V x k ,(0) ⊆ V x k .
This completes the construction for m = 0. If m + 1 < L 0 , then we proceed similarly: we choose a nonempty open subset V x m+1 ,(0) of V x m+1 (which is equal to W m x m+1 ,(0) since we only applied Lemma 4.5 to perform this construction up to this point) with diameter at most 2 -d , and we set

V x k ,(0) := W m x k ,(0) if m+1 = k < L. Note that u m+1 , (V q ) q∈X m+1 ∈ U T m+1 . Lemma 4.5 provides a family (W m+1 q ) q∈X m+1 of subsets of Z such that (a') u m+1 , (W m+1 q ) q∈X m+1 ∈ E T m+1 , (b') W m+1 q ⊆ W m q .
So we may assume that L 0 ≤ m + 1 < L. We will, starting with (Z 0 q ) q∈Xm := (W m q ) q∈Xm and inductively on p ≤ N , construct families (Z p q ) q∈X p m+1 of subsets of Z such that (a") u p m+1 , (Z p q ) q∈X p m+1 ∈ E T p m+1 , (b") Z p+1

x k ,σ ⊆ Z p x k ,σ .

At the end we will set W m+1 q := Z N q . Assume that p < N and (Z p q ) q∈X p m+1 has been constructed, which is the case for p = 0. We will apply Lemma 4.5 to T p+1 m+1 and u p+1 m+1 . Let u := u p m+1 (x m+1 , σ p ), so that Z p x m+1 ,σp ⊆ D u and f u [Z p x m+1 ,σp ] = Z p x i ,σp , by (a"). As f u |Z p x m+1 ,σp is not countable-to-one, we can find z ∈ Z p x i ,σp and (z j ) j<L ∈ (Z p x m+1 ,σp ) L injective such that f u (z j ) = z for each j < L. We choose a sequence (V x m+1 ,σpj ) j<L of pairwise disjoint clopen subsets of Z with diameter at most 2 -d such that z j ∈ V x m+1 ,σpj ⊆ Z p x m+1 ,σp for each j < L, and put

V x i ,σp := Z p x i ,σp ∩ j<L f u [V x m+1 ,σpj ],
which is an open neighborhood of z. We apply Lemma 4.6 to T p m+1 , u p m+1 , (Z p q ) q∈X p m+1 , (x i , σ p ) and V x i ,σp , which gives u p m+1 , (Y q ) q∈X p m+1 .

We then set

V x k ,τ := Y x k ,τ if x k ∈ p x i and τ ⊆ σ p . We also set V x k ,τ := Z p x k ,τ if x k / ∈ p x m+1
, or (x k ∈ p x i and τ ⊆ σ p ), or (k = m + 1 and τ is not of the form σ p j for some j < L). This defines (V q ) q∈X p+1 m+1 , and u p+1 m+1 , (V q ) q∈X p+1 m+1 ∈ U T p+1 m+1

. Lemma 4.5 provides a family (Z p+1 q

) q∈X p+1 m+1 of subsets of Z such that (a"') u p+1 m+1 , (Z p+1 q ) q∈X p+1 m+1 ∈ E T p+1 m+1 , (b"') Z p+1 q ⊆ V q if q ∈ X p+1 m+1 .
This finishes the construction of the family (W m+1 q ) q∈X m+1 as desired. It remains to get clopen sets and ensure (c). We first ensure the disjointness. In order to do this, we construct, inductively on m, a family (z m ) m<L of points of Z, and a family (σ m ) m<L of finite sequences of elements of L such that

(α) z m+1 / ∈ {z l | l ≤ m} (β) (x m , σ m ) ∈ X L-1 (γ) z m ∈ W L-1 xm,σm (δ) f u(x m+1 ) (z m+1 ) = z i if x i ∈ Succ(x m+1 )
We first set σ 0 := (0), so that (x 0 , σ 0 ) ∈ X L-1 , and choose z 0 ∈ W L-1 x 0 ,σ 0 . If m+1 < L 0 , then we set σ m+1 := (0), so that (x m+1 , σ m+1 ) ∈ X L-1 , and choose z m+1 ∈ W L-1

x m+1 ,σ m+1 \{z l | l ≤ m}, which is possible since Z is perfect.

If L 0 ≤ m + 1 < L, then let i ≤ m such that x i is the unique element of Succ(x m+1 ), so that (x m+1 , σ i j) ∈ X L-1 for each j < L. We choose j m+1 < L such that {z l | l ≤ m} ∩ W L-1
x m+1 ,σ i j m+1 = ∅, which is possible by (4). We then set σ m+1 := σ i j m+1 , so that (x m+1 , σ m+1 ) ∈ X L-1 , and choose

z m+1 ∈ W L-1 x m+1 ,σ m+1 with f u(x m+1 ) (z m+1 ) = z i . Note that u, (W L-1 xm,σm ) m<L ∈ E T . As (z m ) m<L is injective, we can find a family (O x ) x∈X of pairwise disjoint clopen subsets of Z such that z m ∈ O xm ⊆ W L-1 xm,σm .
Recall the definition of M x just before Lemma 4.7. We then define, for y ∈ X, and inductively on

M y , U y := O y ∩ x∈Pred(y) f u(x) [U x ], so that z m ∈ U xm ⊆ V xm , the U x 's are pairwise disjoint, and u, (U x ) x∈X ∈ U T .
Lemma 4.5 provides a family (W x ) x∈X of subsets of Z such that

(a"") u, (W x ) x∈X ∈ E T , (b"") W x ⊆ U x .
It remains to get clopen sets. This can be done if we apply the proof of Lemma 4.6, inductively on M y as above, using the fact that this proof uses pre-images to go towards the elements of min X .

The important properties of G 1

We first introduce the other elements of the countable antichain mentioned after Theorem 1.4.

Notation. Let (g n ) be a sequence of partial functions. We set, for s ∈ ω <ω \{∅},

g s := g s(0) • • • • • g s(|s|-1)
and s * :=< s(1), • • • , s(|s|-1) >. If L = 1 and j ≥ 1, then we set θ(j) := 2j +1. Fix L ≥ 2. We set

P L := {2 p • 3 l | p ∈ ω ∧ l < L -2} and M L := {2 31 • 3 • k | k ≥ 1 ∧ k / ∈ P L }. We define a map θ : {j ∈ ω | j ≥ 1} → {3k | k ≥ 1} as follows: θ(j) :=    3j if j / ∈ M L ∪ (M L +1) , 3j +3 if j ∈ M L , 3j -3 if j ∈ M L +1.
Recall the definition of (S n ) after Theorem 1.5. We define θ n : ω → ω by

θ n (k) := k if k / ∈ S n , 2 qn •θ(j) if k = 2 qn •j.
Lemma 5.1 Fix L ≥ 1. Then (S n ) and (θ n ) satisfy the following properties:

(1) {2 j | j ≥ q n } ⊆ ω\θ n [ω] (2) θ n is injective (3) ω\S n = {k ∈ ω | θ n (k) = k} (4) ∀s ∈ ω <ω strictly decreasing with 2 ≤ |s| ≤ L θ s * [ω] ∩ S s(0) is infinite (5) ∀s ∈ ω <ω strictly decreasing with |s| = L+1 θ s * [ω] ∩ S s(0) = ∅ (6) θ n 2 qn •(j +1) -θ n (2 qn •j) ≤ 2 qn+1 •3 Proof. (1) If k ∈ S n , then θ n (k) is a multiple of an odd number ≥ 3. It remains to note that {2 j | j ≥ q n } ⊆ S n
and θ n is the identity on ω\S n .

(2) If L = 1, then θ n is a bijection between ω\S n onto itself on one side, and from S n onto

{2 qn •(2•k+1) | k ≥ 1} ⊆ S n
on the other side. So we may assume that L ≥ 2.

The map θ : {j ∈ ω | j ≥ 1} → {3k | k ≥ 1} defined by θ (j) := 3j is a bijection. The difference between θ and θ is that θ exchanges θ (2 31 •3•k) and θ (2 31 •3•k+1) for each k ≥ 1 with k / ∈ P L . Thus θ is a bijection too. This implies that θ n is a bijection between ω\S n onto itself on one side, and from S n onto {2 qn •3•k | k ≥ 1} ⊆ S n on the other side.

(3) It is enough to check that θ is fixed point free. We may assume that L ≥ 2. In the first two cases of the definition of θ, θ(j) ≥ 3j > j. In the last case, if θ(j) = j, then 2j = 3, which is absurd.

(4) Fix r ∈ ω. Note that

θ s * (2 q s(0) +r ) = θ <s(1),••• ,s(|s|-2)> (2 q s(0) +r •3) = • • • = θ s(1) (2 q s(0) +r •3 |s|-2 ) = 2 q s(0) +r •3 |s|-1 ∈ S s(0) . (5) We may assume that L ≥ 2. Note first that if θ(3j) = 2 31 •3•m, then j ∈ P L . Indeed, we argue by contradiction. If 3j / ∈ M L ∪ (M L +1) , then θ(3j) = 3 2 •j, so that 3j = 2 31 •m.
In particular, m is a multiple of 3, which implies that m is of the form

2 p •3 l+1 with l < L-2 and j = 2 31+p •3 l . If 3j = 2 31 •3•k and k / ∈ P L , then θ(3j) = 3 2 •j +3
, so that 3j is a multiple of 2 31 and 3j +1 = 2 31 •m, which is absurd. Finally, 3j cannot be of the form

2 31 •3•k+1. If θ s * (J) ∈ S s(0) , then θ s(|s|-1) (J) ∈ S s(|s|-2) is a multiple of 3 and is of the form 2 q s(|s|-2) •3•j. Thus θ <s(|s|-2),s(|s|-1)> (J) = θ s(|s|-2) (2 q s(|s|-2) • 3 • j) = 2 q s(|s|-2) • θ(3j) ∈ S s(|s|-3) is of the form 2 q s(|s|-3) •k. Thus θ(3j) = 2 q s(|s|-3) -q s(|s|-2) •k is of the form 2 31 •3•m since q s(|s|-3) -q s(|s|-2) ≥ q s(|s|-2)+1 -q s(|s|-2) ≥ 32 q 1 -q 1 = q 2 -q 1 = 31.
The previous point implies that j ∈ P L . Thus

θ s * (J) = θ <s(1),••• ,s(|s|-2)> (2 q s(|s|-2) +p •3 l+1 ) = θ <s(1),••• ,s(N )> (2 q s(|s|-2) +p •3 |s|+l-N -1 )
as in ( 4), as long as |s|+l-N -1 ≤ L-2, i.e., l+2 ≤ N . In other words,

θ s * (J) = θ <s(1),••• ,s(l+2)> (2 q s(|s|-2) +p •3 L-2 ) = θ <s(1),••• ,s(l+1)> (2 q s(|s|-2) +p •3 L-1 ).
As θ s * (J) ∈ S s(0) , q s(|s|-2) + p ≥ q s(0) . Now θ s(l+1) (2 q s(|s|-2) +p •3 L-1 ) = 2 q s(|s|-2) +p •3 L +3 is not in S s(l) , which is the desired contradiction.

(6) We may assume that L ≥ 2. Note that θ(j +1)-θ(j) ∈ {3, 6, -3}, so that

θ n 2 qn •(j +1) -θ n (2 qn •j) ≤ 2 qn+1 •3.
This finishes the proof.

Notation. We define, for s ∈ ω <ω \{∅}, s -:=< s(0), • • • , s(|s| -2) > and s -1 :=< s(|s| -1), • • • , s(0) > .
We then set, for n ∈ ω, D 1 n := N tn0 . We extend the definition of g n : N tn0 → N tn1 after Theorem 1.5 to any L ≥ 2, writing g L n instead of g n when a confusion is possible. Fix L ≥ 2. We set, for n ∈ ω,

D L n := α ∈ N tn0 | ∀m ≤ n α(2 qn •3 m ) = α(2 qn •3 m+1 ) and G L := n∈ω Graph(g L n |D L n ), so that D L n is a nonempty clopen subset of 2 ω and G L is a Σ 0 2 digraph on 2 ω . Lemma 5.2 Fix L ≥ 1. (a) 2 ω , (g L n |D L n ) is a strongly complex situation. (b) g s (α) = g s -(α) if s ∈ ω <ω is strictly increasing, 2 ≤ |s| ≤ L, α ∈ D L s(|s|-1) and g s (α), g s -(α) are defined. (c) g s (α) = g s -(α) if s ∈ ω <ω is strictly increasing, |s| = L+1 and g s (α), g s -(α) are defined.
Proof. (a) It is known that 2 ω is a nonempty zero-dimensional perfect Polish space. Note that g n is defined, partial, and continuous since g n (α)(k) depends only on α| θ n (k)+1 . If x ∈ 2 <ω , then by Lemma 5.1.( 2

) g n [N tn0x ] = β ∈ N tn1 | ∀2 qn < i < 2 qn +1+|x| i = θ n (k) ⇒ β(k) = (t n 0x)(i) is clopen, so that g n is
= ψ(n). Pick α 0 ∈ D L n . Then α 0 , g L n (α 0 ) ∈ G L ∩ N 2 α|l . Finally, assume that U is an open subset of 2 ω and α ∈ U ∩ D L n . Then we can find x ∈ 2 <ω such that α ∈ N tn0x ⊆ U ∩ D L n . If β(k) = α(k) for k ∈ θ n [ω] ∪ 2 qn+1+|x| , then β ∈ N tn0x ⊆ U ∩ D L n and g n (β) = g n (α). As ω\θ n [ω] is infinite by Lemma 5.1.(1), ω\(θ n [ω] ∪ 2 qn+1+|x|
) is also infinite, and the set of such β's is not countable.

(b) We argue by contradiction. We set k := 2 q s(|s|-1) . As (q n ) and s are strictly increasing and |s| ≥ 2, k = 2 q s(0) , and g s(0

) (β)(k) = β θ s(0) (k) if β ∈ N t s(0) 0 . Thus g s(0) (β)(k) = β θ s(0) (2 q s(0) •2 q s(|s|-1) -q s(0) ) = β 2 q s(0) •θ(2 q s(|s|-1) -q s(0) ) = β(2 q s(|s|-1) •3) if β ∈ N t s(0) 0 . As 2 q s(|s|-1) •3 = 2 q s(1) , g <s(0),s(1)> (β)(k)= g s(1) (β)(2 q s(|s|-1) •3) = β θ s(1) (2 q s(|s|-1) •3) = β 2 q s(1) •θ(2 q s(|s|-1) -q s(1) •3) = β(2 q s(|s|-1) •3 2 ) if β ∈ N t s(1) 0 and g s(1) (β) ∈ N t s(0) 0 . Similarly, g s (α)(k) = α(2 q s(|s|-1) •3 |s| ) since 2 ≤ |s| ≤ L, which contradicts the fact that α ∈ D L s(|s|-1) since |s|-1 ≤ s(|s|-1) cause s is stricly increasing. (c) As above, g s (α)(k) = α θ s -1 (k) if k = 2 q s(0) . As θ (s -) -1 (k) is in θ (s -) -1 [ω], it is not in S s(|s|-1) by Lemma 5.1.(5). Thus θ s -1 (k) = θ (s -) -1 (k) by Lemma 5.1.
(3) and we are done.

We introduce some finitary objects used in the construction of our homomorphism. Fix L ≥ 1.

Notation. We inductively define, for each l ∈ ω, -a subset X l of 2 ≤l such that 2 ω is the disjoint union of (N x ) x∈X l , -an oriented graph B l on X l , containing finite approximations of G L and providing some control on the cycles, -a map ϕ l : B l+1 → l such that t ϕ l (y,x) 0 ⊆ y and t ϕ l (y,x) 1 ⊆ x if (y, x) ∈ B l+1 , giving the number of the function approximated by an element of B l+1 , -an uogas A l on X l contained in B l , containing finite approximations of a subset of G L with acyclic symmetrization, -a subset E l of X l , determining the future elements of X l+1 .

We first perform the construction of these objects for l = 0, sometimes more. -We set X 0 := {∅}, so that X 0 ⊆ 2 ≤0 and 2 ω is the disjoint union of (N x ) x∈X 0 .

-Generally speaking, we set

B l := (y, x) ∈ X 2 l | (N y ×N x ) ∩ G L = ∅ ∧ ∃i < |y|, |x| y(i) = x(i) ,
so that B 0 = ∅. Note that B l is an oriented graph on X l since B l ⊆< lex .

-We set A 0 := ∅.

-If x ∈ X l , then the decision of putting x in E l or not is made by induction on M x , related to A l , defined before Lemma 4.7. If M x = 1, then we put x in E l . We set, when the decision of putting y in E l is made,

l y := |y| if y / ∈ E l , |y|+1 if y ∈ E l .
Assume that the decision of putting x in E l is made if 1 ≤ M x ≤ m, which is the case for m = 1, and fix x ∈ X l with M x = m+1, so that x / ∈ min X l and Pred(x) = ∅. Fix y ∈ Pred(x), so that (y, x) ∈ A l . We put n := ϕ l-1 (y, x). We say that x is y-expandable if θ n (|x|) < l y . Generally speaking, we put x in E l exactly when x is y-expandable for each y ∈ Pred(x) and, when there is q ∈ ω with t q ∈ E l , there is no 1 ≤ i < |p tq | with x = p tq (i). In particular, E 0 = {∅}.

Assume that our objects have been constructed for p ≤ l, which is the case for l = 0.

-We set X l+1 := sε | s ∈ E l ∧ ε ∈ 2 ∪ (X l \E l ), so that X l+1 ⊆ 2 ≤l+1 and 2 ω is the disjoint union of (N x ) x∈X l+1 . -If (y, x) ∈ B l+1 , then there is a unique n ∈ ω with (N y ×N x ) ∩ Graph(g L n ) = ∅, and 2 qn = |y ∧ x|. Note that n ≤ q n < 2 qn < |y| ≤ l+1. We set ϕ l (y, x) := n, which defines ϕ l : B l+1 → l.
-We now define A l+1 . If t q ∈ max X l ∩ E l , then we put (t q 0, t q 1) in A l+1 . If y ∈ X l \max X l , then let x be the unique element of Succ(y), so that (y, x) ∈ A l . As A l ⊆ B l , we can define n := ϕ l-1 (y, x). If x / ∈ E l , then we put

   (y, x) if y / ∈ E l , (yη, x) if y ∈ E - l := E l \{t m | m ∈ ω} ∧ η ∈ 2, (y1, x), (y0, y1) if y = t q ∈ E l in A l+1 . If x ∈ E l , then y / ∈ {t m | m ∈ ω},
x is y-expandable and θ n (|x|) < l y . We put (yη, xε) in A l+1 if η ∈ 2 ≤1 , yη ∈ X l+1 and ε = (yη) θ n (|x|) . We first check the following announced facts.

Lemma 5.3 Let l ∈ ω. Then A l is an uogas on X l contained in B l .
Proof. We argue by induction on l, and the case l = 0 is clear. Note that A l+1 ⊆ B l+1 , by definition of A l+1 , so that A l+1 is an oriented graph on X l+1 . By definition, A l+1 is unambiguously oriented. We argue by contradiction to see that s(A l+1 ) is acyclic. Let (u j ) j≤N be a s(A l+1 )cycle. We choose j ≤ N such that u j is < lex -minimal, and we may assume that 0 < j < N . Then (u j , u j-1 ), (u j , u j+1 ) ∈ A l+1 , so that u j-1 = u j+1 since A l+1 is unambiguously oriented, which is absurd.

Lemma 5.4 Let l ∈ ω, and x ∈ X l+1 . Then |p x | ≤ l+1.

Proof. We argue by induction on l. For l = 0, X 1 = {(0), (1)}, p (1) = (1) and p (0) = (0) , so we are done. Let x ∈ X l+2 . Note first that if i < L := |p x |, then we can find a unique couple (x i , ε i ) in X l+1 ×2 ≤1 with p x (i) = x i ε i . Let i < L-1. By definition of A l+2 , either (x i , x i+1 ) ∈ A l+1 , or there is q ∈ ω such that t q ∈ E l+1 and p x (i), p x (i+1) = (t q 0, t q 1). In particular, (x i ) i<L is ≤ lex -increasing. By definition of E l+1 , there is at most one i < L -1 for which there is q ∈ ω such that t q ∈ E l+1 and p x (i), p x (i+1) = (t q 0, t q 1). If such a q does not exist, then (x i ) i<L = p s(A l+1 )

x 0 ,x L-1 and L ≤ l+1, by induction assumption. If now there is such a q, then (x 0 ,

• • • , x i , x i+2 , • • • , x L-1 ) = p s(A l+1 )
x 0 ,x L-1 and L-1 ≤ l+1, by induction assumption, so that L ≤ l+2.

Lemma 5.5 Fix L ≥ 1. Then there is (L n ) n∈ω ∈ (ω\{0}) ω strictly increasing satisfying the following properties:

(a) t n ∈ E Ln \( k<Ln E k ), X Ln ∩ X L n+1 = ∅, (c) 2 qn ≤ L n < L n +(6L n ) Ln-1 ≤ 2 q n+1 .
Proof. We construct L n inductively on n. We set L 0 := 1, which is correct since

t 0 = (0) is in E 1 \E 0 , p 0 = 0 and p 1 = 1. As X 1 = {(0), (1)}, |x| > 0 if x ∈ X L 0 . Assume that L n has been constructed. Claim. Let l ≥ L n +(3•2 qn+1 ) Ln-1
. Then X l does not meet X Ln . In fact, we can add m ≥ 1 coordinates at least to x ∈ X Ln in X l if l ≥ L n +m•(3•2 qn+1 ) Ln-1 and no t q appears in some E k with L n < k < l.

Indeed, fix x ∈ X Ln . We want to extend properly x in some X l with l > L n , and to give an estimate on l. We proceed by induction on M x , which was defined just before Lemma 4.7. If M x = 1, then l := L n +1 ≤ L n +(3•2 qn+1 ) Ln-1 is suitable. Assume now that M x = 2, which gives y ∈ min X Ln with x ∈ p y , and in fact x = p y (1). In particular, (y, x) ∈ A Ln ⊆ B Ln and N := ϕ Ln-1 (y, x) < L n -1 is defined. The definition of g L N and Lemma 5.1.(6) show that if α ∈ N y , then we can find l ≤ L n +3•2 q N +1 and z ⊆ α with z ∈ X l and z(|z|-1) = g L N (α)(|x|). Note that q N ≤ q n since (q n ) is increasing,

L n ≥ 2 since B 0 = B 1 = ∅, and L n < L n +3•2 qn+1 ≤ L n +6L n ≤ L n +(6L n ) Ln-1 ≤ 2 q n+1 .
Thus x is properly extended in X Ln+3•2 qn+1 , and also in X Ln+(3•2 qn+1 ) Ln-1 . This argument also shows that x can be extended by m coordinates in

X Ln+m•3•2 qn+1 if L n < L n +m•3•2 qn+1 ≤ 2 q n+1 .
More generally, this argument shows that x can be properly extended in X Ln+(3•2 qn+1 ) Ln-1 , by Lemma 5.4, which implies that

M x ≤ L n . Now note that |ψ(n+1)| ≤ n+1 ≤ 2 n ≤ 2 qn ≤ L n < L n +(3•2 qn+1 ) Ln-1 ≤ 2 q n+1
. We will extend ψ(n+1) until we reach t n+1 = ψ(n+1)0 2 q n+1 -|ψ(n+1)| in some X q with q ≥ 2 q n+1 . Note first that there is x ∈ X Ln with x ⊆ ψ(n+1)0 ∞ , and ψ(n+1) ⊆ x since |x| > n.

In order to do this, we add m := 2 p n+1 -|x| coordinates to x. By the claim, this will be possible in X q for some 2

q n+1 ≤ q ≤ L n +m•(3•2 qn+1 ) Ln-1 if no t r appears in some E k with L n < k < q. This is the case since q < L n +(m+1)•(3•2 qn+1 ) Ln-1 ≤ 2 q n+1 +2 q n+1 •(6L n ) Ln-1 ≤ (2 q n+1 ) 2 < 2 q n+2 because q n+2 = 32 q n+1 > 2q n+1 . It remains to check that L n+1 + (6L n+1 ) L n+1 -1 ≤ 2 q n+2 . As L n+1 ≤ (2 q n+1 ) 2 , L n+1 +(6L n+1 ) L n+1 -1 ≤ (6L n+1 ) L n+1 ≤ 2 (2q n+1 +3)•2 2q n+1 . It remains to note that (2q n+1 +3)•2 2q n+1 ≤ 2 5q n+1 = 32 q n+1 = q n+2 .
Corollary 5.6 For each x ∈ 2 <ω there is l ∈ ω such that x ∈ X l .

Proof. We argue by induction on |x|. For x = ∅, we can take l := 0. Assume that x ∈ X l and ε ∈ 2. If there is l > l with xε ∈ X l , then we are done. Otherwise, x ∈ X l for each l ≥ l. Using Lemma 5.5, we choose n ∈ ω such that L n ≥ l. Then x ∈ X Ln ∩ X L n+1 , which is absurd.

Lemma 5.7 We work with L = 1. Let l ∈ ω, (y, x) ∈ B l+1 and p := p s(A l+1 ) y,x C(y) . Then (a) x = p(j) for some 1 ≤ j < |p|, (b) ϕ l p(j -1), p(j) = ϕ l (y, x) = min i<j ϕ l p(i), p(i+1) , (c) ϕ l p(i), p(i+1) i<j is injective.

Proof. We argue by induction on l. We are done if l = 0 since B 1 = ∅. So assume that (y, x) ∈ B l+2 , which gives n := ϕ l+1 (y, x) ≤ l with t n 0 ⊆ y and t n 1 ⊆ x. In particular, l +1 ≥ L n . If l +1 = L n , then (y, x) = (t n 0, t n 1) and p = (t n 0)p s(A l+2 ) tn1,x C(tn0) by Lemma 4.2 and since A l+2 ⊆< lex . Thus j = 1 is convenient. So we may assume that l ≥ L n . Note that we can find (y , x ) ∈ B l+1 with t n 0 ⊆ y ⊆ y and t n 1 ⊆ x ⊆ x. By the induction assumption, p := p

s(A l+1 ) y ,x C(y )
is defined and there is 1 ≤ j < |p | with x = p (j ).

Case 1. We cannot find q ∈ ω with t q ∈ p s

(A l+1 ) y ,x ∩ E l+1 . Let ε 0 ∈ 2 ≤1 such that y = y ε 0 . Note that there is a unique ε 1 ∈ 2 ≤1 such that y, p (1)ε 1 is in A l+2 , by definition of A l+2 . Similarly, if 1 ≤ i < j , then there is a unique ε i+1 ∈ 2 ≤1 such that p (i)ε i , p (i+1)ε i+1 ∈ A l+2 . Note that p s(A l+2 ) y,p (j )ε j
is defined and equal to p (i)ε i i≤j . We will be able to set j := j if we prove that x = x ε j , by Lemma 4.2 and since A l+2 ⊆< lex again. This is the case if ε j = ∅, so we may assume that ε j ∈ 2, which implies that x ∈ E l+1 . Let ε := x(|x |), so that x = x ε and we have to see that ε j = ε. Note that p (i+1)ε i+1 is p (i)ε i -expandable if ε i+1 ∈ 2, for each i < j . More precisely, if n i := ϕ l p (i), p (i+1) , then

ε i+1 = p (i)ε i θ n i |p (i+1)| .
This implies that ε j = y θ n (|x |) since n j -1 = n = min i<j n i and (n i ) i<j is injective, by induction assumption. In particular, y is long enough to ensure that ε j = ε since (y, x) ∈ B l+2 with witness n.

Case 2. t q ∈ p s(A l+1 ) y ,x ∩ E l+1 for some q ∈ ω, which implies that l+1 = L q . Fix i 0 ≤ j with p (i 0 ) = t q . The definition of ε i is as in Case 1 if i ≤ i 0 . If ε i 0 = 0, then we set ε i := ∅ if i 0 < i ≤ j and we note that p s(A l+2 ) y,x = p (0)ε 0 , • • • , p (i 0 )0, p (i 0 )1, p (i 0 +1), • • • , x if i 0 < j , and p s(A l+2 ) y,x = p (0)ε 0 , • • • , p (i 0 )0 if i 0 = j . Apart from that, we argue as in Case 1. If ε i 0 = 1, then we set ε i := ∅ if i 0 < i ≤ j and we note that p s(A l+2 ) y,x = p (0)ε 0 , • • • , p (i 0 )1, p (i 0 +1), • • • , x if i 0 < j , and p s(A l+2 ) y,x = p (0)ε 0 , • • • , p (i 0 )1 if i 0 = j .
Apart from that, we argue as in Case 1. This is possible since, inductively on k < |q x |, V qx(k) is defined, nonempty and contained in

W (qx(k)) -, since q x (k) -, q x (k+1) -∈ A l , so that f u l ((qx(k)) -) [W (qx(k)) -] = W (qx(k+1)) -. Note that u, (V x ) x∈X l+1 ∈ U T . Indeed, let (y, x) ∈ A l+1 . If y / ∈ C(t r 1), then y -= t r , so that (y -, x -) ∈ A l . Moreover, x / ∈ C(t r 1) and V y = U l y -, V x = U l x -. Thus V y ⊆ D φ(ϕ l-1 (y -,x -)) and V x ⊆ f φ(ϕ l-1 (y -,x -)) [V y ]
, by the induction assumption. It remains to note that

u(y) = φ ϕ l (y, x) = φ ϕ l-1 (y -, x -) to see that V y ⊆ D u(y) and V x ⊆ f u(y) [V y ]. If y ∈ C(t r 1) and y ∈ q y , then x ∈ q y \{t r 1}. By definition, V x = f u l (y -) [V y ]. Note that u(y) = φ ϕ l (y, x) = φ ϕ l-1 (y -, x -) = u l (y -). If y = t r 0, then x = t r 1, V tr0 = O tr0 ⊆ D φ(r) = D u(tr0) and V tr1 = O tr1 ⊆ f u(tr0) [V tr0 ]. Otherwise, V y = U l y -and x ∈ C(t r 1). If x /
∈ q y and x -= t r , then we argue as in the case y / ∈ C(t r 1). If x ∈ q y or x -= t r , then

V x ⊆ W x -= f u l (y -) [W y -] ⊆ f u l (y -) [U l y -] = f u(y) [V y ].
Lemma 4.7 provides a sequence (U l+1 x ) x∈X l+1 of pairwise disjoint nonempty clopen subsets of Z with diameter at most 2

-l-1 such that U l+1 y ⊆ D u(y) if y / ∈ max X l+1 and U l+1 x ⊆ V x ∩ y∈Pred(x) f u(y) [U l+1 y ] if x ∈ X l+1 . Note that U l+1 x ⊆ V x ⊆ U l
x -, by definition of the W x 's, which shows that (1) is satisfied. The construction of the U l+1

x 's shows that (2)-( 4) are satisfied. For (5), let (y, x) ∈ B l+1 , and m < j with ϕ l p(j -1), p(j) = ϕ l (y, x) = min i<j ϕ l p(i), p(i+1) . If p(q) = t r 1 for each 0 < q ≤ j, then we are done, by induction assumption. If p(q) = t r 1 for some 0 < q ≤ j, then q < j or j = 1, and we may assume that q < j. It remains to note that U l+1 p(q-ε) ⊆ U l (p(q)) -⊆ D φ(ϕ l (y,x)) for each ε ∈ 2, by the induction assumption.

Proof of Theorem 1.8. We apply Lemma 3.2 to X, (f n ) , P := X and S n := D n . This is possible by Corollary 2.2. Lemma 3.2 provides a Borel subset S of X, a finer topology τ on S, and a sequence (C n ) of clopen subsets of Y := (S, τ ) such that Y, (f n|C n ) is a strongly complex situation and C n ⊆ S ∩ g -1 n (S). By Theorem 6.1,

(2 ω , G 1 ) inj c Y, n∈ω Graph(f n|C n ) . As Y, n∈ω Graph(f n|C n ) inj c (X, A f ), we are done.
Proof of Theorem 1.3. By Corollary 2.2, G 1 is a Σ 0 2 digraph of uncountable Borel chromatic number, and is in particular analytic. Theorem 1.8 shows that if S is a Borel subset of 2 ω , τ is a finer topology on S, and

(C n ) is a sequence of clopen subsets of Y := (S, τ ) such that Y, (g n|C n ) is a strongly complex situation, then (2 ω , G 1 ) inj c Y, n∈ω Graph(g n|C n )
. We apply Corollary 3.3 and the remark after it to get the minimality of G 1 . This implies the minimality of G -1 1 . We saw in the introduction that G 0 is also minimal. It remains to apply Lemma 5.2 and Corollary 2.4.

Let L < M . We argue by contradiction, which gives a Polish space Y and an analytic digraph

B on Y of uncountable Borel chromatic number such that (Y, B) inj B (2 ω , G L ), (2 ω , G M ). Theorem 1.7 gives a complex situation X, (f n ) such that (X, A f ) inj c (Y, B) or (X, A f ) inj c (Y, B -1 ).
Let us prove that (X, A f ) inj c (Y, B). We argue by contradiction, so that

(X, A f ) inj c (Y, B -1
). As G L has countable vertical sections, B too, so that B -1 and A f have countable horizontal sections. Thus A f is locally countable. By Corollary 2.2, A f is a Σ 0 2 digraph of uncountable Borel chromatic number. The discussion after Theorem 1.1 shows that (2 ω , G 0 ) inj c (X, A f ), and also

(2 ω , G 0 ) inj c (2 ω , G -1 0 ) inj c (Y, B) inj B (2 ω , G L ), (2 ω , G M ). Let H be a dense G δ subset of 2 ω such that (H, G 0 ∩ H 2 ) inj c (2 ω , G L ), (2 ω , G M ). The proof of Lemma 2.1.(b) shows that G 0 ∩ H 2 has uncountable Borel chromatic number. The discussion after Theorem 1.1 shows that (2 ω , G 0 ) inj c (H, G 0 ∩ H 2 ), and thus (2 ω , G 0 ) inj c (2 ω , G L ), (2 ω , G M ), which contradicts the claim. This shows that (X, A f ) inj B (2 ω , G L ), (2 ω , G M )
. So we may assume that Y = X and B = A f . Let P be a dense G δ subset of X such that (P,

A f ∩ P 2 ) inj c (2 ω , G L ), (2 ω , G M ). The proof of Lemma 2.1.(b) shows that A f ∩ P 2 has uncountable Borel chromatic number. The previous point shows that (2 ω , G 0 ) inj c (X, A f )
. By Lemma 3.2, we may assume that X, (f n ) is a strongly complex situation and (X, A f ) inj c (2 ω , G L ), (2 ω , G M ), which contradicts the claim.

The last assertion comes from the fact that G L ∩ (N s ∩ G) 2 has uncountable Borel chromatic number, by the proof of Lemma 2.1.(b).

Proof of Theorem 1.5. We argue by contradiction, which gives a natural number N and a basis (X i , A i ) i<N . By Theorem 7.1, we can find i < N and L = M with (X i , A i ) inj B (2 ω , G L ), (2 ω , G M ). This contradicts Theorem 7.1.

We now prove Theorem 1.4.

Notation. We set, for each n ∈ ω, Q n := ⊕ L≤n 2 ω and

H n := (L, γ), (M, δ) ∈ Q 2 n | L = M ∧ (γ, δ) ∈ G L .
Theorem 7.2 Let C ∈ {c, B}. Then (Q n , H n ) n∈ω is a inj C -strictly increasing chain made of Σ 0 2 digraphs of uncountable Borel chromatic number.

Proof. By Theorem 7.1, H n is a Σ 0 2 digraph of uncountable Borel chromatic number on Q n . The identity map shows that our sequence is increasing. We argue by contradiction, which gives n ∈ ω such that (Q n+1 , H n+1 ) inj B (Q n , G n ) with witness u. The map associating u 0 (n, γ) to γ ∈ 2 ω is Borel, which gives L < n, s ∈ 2 <ω and a dense G δ subset G of 2 ω such that u 0 (L, γ) = L if γ is in N s ∩ G.

The map v associating u 1 (n, γ) to γ ∈ N s ∩ G is injective and Borel. We can restrict G, so that we may assume that v is continuous. Thus N s ∩ G, G n ∩ (N s ∩ G) 2 inj c (2 ω , G L ) with witness v, which contradicts Theorem 7.1 since n = L.

Notation. Let (p n ) n∈ω be the sequence of prime numbers. We define, for each α ∈ 2 ω , E α ⊆ ω by E α := {p Theorem 7.3 (P α , G α ) α∈2 ω is a inj B -antichain made of Σ 0 2 digraphs of uncountable Borel chromatic number.

Proof. By Theorem 7.1, G α is a Σ 0 2 digraph of uncountable Borel chromatic number on P α . We argue by contradiction, which gives α = β such that (P α , G α ) inj B (P β , G β ) with witness u. Note that E α ∩ E β is finite, which gives L ∈ E α \E β . The map associating u 0 (L, γ) to γ ∈ 2 ω is Borel, which gives M ∈ E β , s ∈ 2 <ω and a dense G δ subset G of 2 ω such that u 0 (L, γ) = M if γ is in N s ∩ G. The map v associating u 1 (L, γ) to γ ∈ N s ∩ G is injective and Borel. We can moreover restrict G, so that we may and will assume that v is continuous. Thus v is a witness for the fact that

N s ∩ G, G L ∩ (N s ∩ G) 2 inj c (2 ω , G M )
, which contradicts Theorem 7.1 since L = M .

Our main results also hold for graphs. Proof. We first prove the following.

Claim. 2 ω , s(G L ) L∈ω is a sequence made of Σ 0 2 graphs pairwise inj B -incompatible among analytic graphs of uncountable Borel chromatic number on Polish spaces. Indeed, we argue by contradiction, which gives L = M and an analytic graph G of uncountable Borel chromatic number on a Polish space X such that (X, G) inj B 2 ω , s(G L ) , 2 ω , s(G M ) , with witnesses u, u respectively. Note that

G = G ∩ (u×u) -1 (G L ) ∩ (u ×u ) -1 (G M ) ∪ G ∩ (u×u) -1 (G L ) ∩ (u ×u ) -1 (G -1 M ) ∪ G ∩ (u×u) -1 (G -1 L ) ∩ (u ×u ) -1 (G M ) ∪ G ∩ (u×u) -1 (G -1 L ) ∩ (u ×u ) -1 (G -1 M )
. The second and the third of these subgraphs are locally countable. If one of them has uncountable Borel chromatic number, then it is above G 0 by the discussion after Theorem 1.1. By Theorem 7.1, we must have L = 0 = M , which is absurd. Thus the first or the fourth of these subgraphs has uncountable Borel chromatic number, which contradicts the incompatibility of G L and G M .

(a) By the claim, s(G 0 ) and s(G 1 ) are incompatible, and thus incomparable. Assume that we can find L ∈ 2 and an analytic graph G of uncountable Borel chromatic number on a Polish space X such that (X, G) inj C 2 ω , s(G L ) , with witness u. Note that

G = G ∩ (u×u) -1 (G L ) ∪ G ∩ (u×u) -1 (G -1 L ) .
One of these subgraphs has uncountable Borel chromatic number. Assume for example that it is the first one. Then the minimality of G L shows that (2 ω , G L ) inj Note that E α ∩ E β is finite, which gives L ∈ E α \E β . The map associating u 0 (L, γ) to γ ∈ 2 ω is Borel, which gives M ∈ E β , s ∈ 2 <ω and a dense G δ subset G of 2 ω such that u 0 (L, γ) = M if γ is in N s ∩ G. The map v associating u 1 (L, γ) to γ ∈ N s ∩ G is injective and Borel. We can moreover restrict G, so that we may and will assume that v is continuous.

Thus v is a witness for the fact that N s ∩G, s(G L )∩(N s ∩G) 2 inj c 2 ω , s(G M ) , which contradicts the claim 7.1 since L = M .

(c) We argue as in the proof of Theorem 1.5, using the claim.

  gm / / g m g n (α) = g m (α)

  a nonempty Polish space, (b) the f n 's are partial continuous and open maps whose domain and range are open in X,

  open and onto with clopen domain and range, and g L n |D L n is partial continuous open with clopen domain and range. If α ∈ 2 ω and l ∈ ω, then there is n with α|l

  ω}. Then we set P α := ⊕ L∈Eα 2 ω andG α := (L, γ), (M, δ) ∈ P 2 α | L = M ∧ (γ, δ) ∈ G L .

Theorem 7. 4

 4 Let C ∈ {c, B}.(a) There is a inj C -antichain {s(G 0 ), s(G 1 )} made of graphs inj C -minimal among analytic graphs of uncountable Borel chromatic number. (b) There is a inj C -antichain of size 2 ℵ 0 made of Σ 0 2 graphs of uncountable Borel chromatic number. (c) Any inj C -basis for the class of analytic graphs of uncountable Borel chromatic number on Polish spaces is infinite.

C 2 ω

 2 , G ∩ (u×u) -1 (G L ) , and thus2 ω , s(G L ) inj C (X, G).(b) We essentially argue as in the proof of Theorem 7.3. By the claim, s(G α ) is a Σ 0 2 graph of uncountable Borel chromatic number on P α . We argue by contradiction, which gives α = β such that P α , s(G α ) inj B P β , s(G β ) with witness u.

  locally countable Borel subset of A f with uncountable Borel chromatic number, which contradicts Lemma 2.3. A f is not inj B -below G 0 since G 0 is locally countable and A f is not, by Corollary 2.2 and Lemma 2.3. The discussion after Theorem 1.1 shows that (2 ω

The second author was supported by the grant GA ČR 15-08218S.

1

Note that (b), (c) follow from the previous discussion since ϕ l p (i), p (i+1) i<j is equal to ϕ l+1 p(i), p(i+1) i<j , except when i 0 < j in the first subcase of the Case 2 where one number bigger than the others has been added strictly before the last position.

Lemma 5.8 Fix L ≥ 1. If n ∈ ω, y |tn|+1 := t n 1 and k > |t n |+1, then for each α ∈ N tn0 we can find l k ∈ ω and y k ∈ X l k such that (α|k, y k ) ∈ B l k and y k-1 ⊆ y k ; moreover, {g n (α)} = k>|tn| N y k .

Proof. By Corollary 5.6, there is l k ∈ ω such that α|k ∈ X l k . Note that l k > L n +1 since k > |t n |+1. There is y k ∈ X l k such that g n (α) ∈ N y k since 2 ω is the disjoint union of (N x ) x∈X l k . Note that

The main construction

We now come to the construction of our homomorphism. Theorem 6.1 Let Z, (f n ) be a strongly complex situation satisfying Condition (d) in Theorem 1.8.

Proof. We construct, inductively on l,

We want these objects to satisfy the following conditions, using Lemma 5.7.

(1)

Assume that this is done. Fix α ∈ 2 ω and l ∈ ω. As 2 ω is the disjoint union of the N x 's for x ∈ X l , there is a unique k l ∈ ω for which α|k l ∈ X l . The sequence (U l α|k l ) l∈ω defines h(α) ∈ Z, using (1) and (2). Note that h : 2 ω → Z is continuous, and injective by (3) and Corollary 5.6 (which implies that k l tends to infinity as l tends to infinity).

Let us prove that

We apply Lemma 2.5 to

Let (α, β) ∈ G 1 , and n with α ∈ N tn0 and β = g n (α). By Lemma 5.8, (α|k,

So it is enough to prove that the construction is possible. We fix a compatible metric with diam(Z) ≤ 1. We first set U ∅ := Z. Assume that (U x ) x∈Xp p≤l and φ(n) Ln<l satisfying (1)-( 6) have been constructed, which is the case for l = 0. By Lemmas 5.3 and 4.2.(c), we can set, for each y ∈ X l , p l y := p s(A l ) y,x C(y) . We choose u l ∈ ω X l such that u l (y) := φ ϕ l-1 y, p l y (1) if y ∈ X l \max X l (this can be done, by the induction assumption). We define, for y ∈ X l , and inductively on |p l y |,

which defines nonempty clopen subsets of Z, by (4) of the induction assumption. Note that

by the induction assumption.

If l is of the form L r , then Lemma 2.6 applied to V := W tr and m := sup Ln<l φ(n) = sup n<r φ(n) gives φ(r) > sup n<r φ(n) and nonempty clopen subsets

We will apply, thanks to Lemma 5.3, Lemma 4.7 to T := X l+1 , A l+1 , Z, (f n ) ,

, and (V x ) x∈X l+1 defined as follows. If x ∈ X l+1 , we denote by x -the unique element X l for which there is ε ∈ 2 ≤1 with (x -)ε = x. We also set q y := p l+1 tr1,x C(y) if y ∈ C(t r 1). If x / ∈ C(t r 1), or if x / ∈ q x and x -= t r , then we set V x := U l x -. We also set V tr1 := O tr1 and V tr0 := O tr0 . If now x ∈ C(t r 1), x ∈ q x \{t r 1} and x = q x (i) with i ≥ 1, then we define V x by induction on i. We set

7 The structure of inj C Theorem 7.1 (2 ω , G L ) L∈ω is a sequence made of Σ 0 2 digraphs pairwise inj B -incompatible among analytic digraphs of uncountable Borel chromatic number on Polish spaces. In particular, the se-

Proof. By Lemma 5.2.(a), 2 ω , (g

Claim. Let L < M be natural numbers, and X, (f n ) be a complex situation satisfying the Conditions (a), (b) of a strongly complex situation. Then (X,

Indeed, we argue by contradiction, which gives witnesses u, u . We set

Note that R is closed, by continuity. If n ∈ ω, U is a nonempty clopen subset of D n and x ∈ U , then there are r, r ∈ ω such that (n, r, r , x) ∈ R. By Baire's theorem, we can find a nonempty clopen subset C of U and r, r

We inductively construct a strictly increasing sequence (n k ) k∈ω ∈ ω ω as follows. We first apply the previous point to n 0 := 0 and U := D 0 , which provides C 0 ⊆ D n 0 and r 0 , r 0 ∈ ω such that (n 0 , r 0 , r 0 , x) ∈ R if x ∈ C 0 . As X, (f n ) is a strongly complex situation, we can find n k+1 > n k such that Graph(f n k+1 ) ∩ C 2 k = ∅. We apply the previous point to n k+1 and U

As (C k ) is a decreasing sequence of nonempty closed subsets of X whose diameters tend to zero, there is x ∈ k∈ω C k . Note that (n k , r k , r k , x) ∈ R for each k. Let us prove that (r k ) is unbounded. We argue by contradiction, which gives r ∈ ω and I ⊆ ω infinite such that r k = r if k ∈ I. By continuity, we get u(x) = g L r u(x) since lim k→∞,k∈I f n k (x) = x, which contradicts the fact that g L r is fixed point free. So, extracting a subsequence if necessary, we may assume that (r k ) and (r k ) are strictly increasing.

As x ∈ C 1 and f n 1 (x) ∈ C 0 , u f n 0 f n 1 (x) = g L r 0 u f n 1 (x) = g L r 0 g L r 1 u(x) . More generally, u f ns (x) = g L rs u(x) and u f ns (x) = g M r s u (x) if s ∈ ω <ω is strictly increasing.

Assume first that L ≥ 1. We choose s ∈ ω L+1 strictly increasing. By Lemma 5.2.(c), we get g L rs u(x) = g L r s -u(x) , so that g M r s u (x) = g M M r s(|s|-1) . If L = 0, we argue simililarly, using the fact that the g 0 r 's are injective and fixed point free.