Keywords: Graphes dirigés, Coloration, Subdivisions, Compression d'entropie Directed graphs, Colouring, Subdivisions, Entropy compression

Le but principal de cette thèse est de présenter des conditions suffisantes pour garantir l'existence de subdivisions dans les graphes dirigés. Bien que ce genre de questions soit assez bien maitrisé dans le cas des graphes non orientés, très peu de résultats sont connus sur le sujet des graphes dirigés. La conjecture la plus célèbre du domaine est sans doute celle attribuée à Mader en 1985 qui dit qu'il existe une fonction f tel que tout graphe dirigé de degré sortant minimal supérieur à f (k) contient le tournoi transitif sur k sommets comme subdivision. Cette question est toujours ouverte pour k = 5. Cette thèse présente quelques résultats intermédiaires tendant vers cette conjecture. Il y est d'abords question de montrer l'existence de subdivisions de graphes dirigés autre que les tournois, en particulier les arborescences entrantes. Il y a aussi la preuve que les graphes dirigés de grand degré sortant contiennent des immersions de grand tournois transitifs, question qui avait été posée en 2011 par DeVos et al. En regardant un autre paramètre, on montre aussi qu'un grand nombre chromatique permet de forcer des subdivisions de certains cycles orientés, ainsi que d'autre structures, pour des graphes dirigés fortement connexes.

Cette thèse présente également la preuve de la conjecture de Erdős-Sands-Sauer-Woodrow qui dit que les tournois dont les arcs peuvent être partitionnés en k graphes dirigés transitifs peuvent être dominé par un ensemble de sommet dont la taille dépend uniquement de k.

Pour finir, cette thèse présente la preuve de deux résultats, un sur l'orientation des hypergraphes et l'autre sur la coloration AVD, utilisant la technique de compression d'entropie.

Chapter 1 Introduction

This chapter serves as introduction to this thesis. After giving some standard definitions and notations in Section 1.1, in Sections 1.2, 1.3, 1.4, 1.5 we motivate and present the results obtained on subdivisions and other related structures in certain classes of digraphs. In Section 1.6, we discuss domination in tournaments and the proof of the Erdős-Sands-Sauer-Woodrow conjecture. Finally, Section 1.7 introduces the method of entropy compression and presents two results obtained using this method.

Definitions

We denote by [j, k] the set of integers {j, . . . , k} and [k] the set [1, k].

A graph is a pair G = (V, E) of finite sets such that E is a set of unordered pairs of elements of V . A multigraph is a graph where we allow an edge to appear multiple times. We call these edges parallel edges, and the multiplicity of an edge is the number of times it appears in E(G). The elements of V are the vertices and the elements of E are the edges. For a graph G, we write V (G) for its vertex set and E(G) for its edge set. Let u and v be vertices of V . If {u, v} belongs to E(G), we say that u and v are adjacent, neighbours or that u sees v, and we will use uv to denote the edge. Let G = (V, E) be a graph and v a vertex of G. The neighbourhood of v, denoted by N (v) is the set of vertices adjacent to v, and the degree of v is d(v) = |N (v)|. For a subset of vertices A, we write N A (v) = N (v) ∩ A and set d A (v) = |N A (v)|. We also write N (A) = ∪ x∈A N (x). We say that G has minimum degree at least k if every vertex v is such that d(v) ≥ k. The average degree of G is the number |E| |V | . Let A ⊆ V , we call subgraph of G induced by A, the graph

G[A] = (A, E ∩ A 2 ). We denote by G -A = G[V \ A]. If B ⊆ E, then G[B] = (V, B) and G \ B = G[E \ B].
The complete graph on k vertices, denoted by K k is the graph on k vertices with every possible edge. A stable set S of G is a set of vertices such that G[S] has no edge. A clique K of G is a set of vertices such that G[K] is a complete graph. The clique number, denoted by ω(G), is the size of the largest clique in G and the stability number, denoted by α(G), is the size of its largest stable set.

A path P is a sequence of distinct vertices x 1 . . . x l such that x i x i+1 is an edge for every 1 0 < i < l. The vertices x 1 and x l are called the endvertices of P and P is referred to as an x 1 x l -path, or a path between x 1 and x l . The vertices x i for i ∈ [2, l -1] are referred to as the inner vertices of P . A set of paths P 1 , . . . , P k are said to be internally disjoint if the sets of inner vertices of these paths are pairwise disjoint. If S and T are two sets of vertices, a (S, T )-path is a st-path for some s ∈ S and t ∈ T . A cycle C is a sequence of distinct vertices x 1 . . . x l such that x i x i+1 is an edge for every 0 < i < l and x l x 1 is an edge. The length of a cycle is the number of vertices in this cycle. The girth of G is the length of its smallest cycle. The grid of size k is the graph on [k] × [k] where vertex (i, j) is adjacent to vertices (i -1, j), (i + 1, j), (i, j -1) and (i, j + 1) when these vertices exist.

In a graph G, we say that vertices x and y have connectivity k if there exists k internally disjoint paths between x and y. A graph is k-connected if every pair of vertices has connectivity k and |V | ≥ k + 1. We write connected for 1-connected. Let X and Y be sets of vertices. A set of vertices S is an (X, Y )-vertex-cut if G -S does not contain any (X \ S, Y \ S)-path. The following theorem due to Menger [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF] relates the connectivity between vertices and vertex-cuts.

Theorem 1 (Menger's theorem [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF]). Let G be a graph, and let S, T ⊆ V (G). The maximum number of vertex-disjoint (S, T )-paths is equal to the minimum size of an (S, T )-vertex-cut.

A proper k-colouring of G is a function c : V (G) → [k], such that the vertices in c -1 (i) form a stable set for every i. A graph G is said to be k-colourable if there exists a proper k-colouring of G. The chromatic number of G, denoted by χ(G) is the least k such that a proper k-colouring exists.

Let G and H be two graphs. We say that G admits a subdivision of H if there exist functions π 1 : V (H) → V (G) and π 2 mapping the edges of H to paths of G satisfying the following conditions:

• the map π 1 is an injection;

• for every edge e ∈ E(H) between u and v, π 2 (e) is a π 1 (u)π 1 (v)-path; and

• for all distinct e, e ∈ E(H), π 2 (e) and π 2 (e ) are internally disjoint.

We say that G admits an immersion of H if there exist functions π 1 : V (H) → V (G) and π 2 mapping the edges of H to paths of G satisfying the following conditions:

• the map π 1 is an injection;

• for every edge e ∈ E(H) between u and v, π 2 (e) is a π 1 (u)π 1 (v)-path; and

• for all distinct e, e ∈ E(H), π 2 (e) and π 2 (e ) have no edge in common.

In a subdivision or in an immersion, the vertices of π 1 (V (H)) are called the branching vertices of H.

Let e = xy be an edge of a graph G = (V, E). By G/e we denote the graph obtained from G by contracting the edge e into a new vertex v e , which is adjacent to all former neighbours of x and y. We say that G admits a minor of H if there exists a graph G such that, G can obtained from G by repeated contractions, and H is a subgraph of G . These notions are strongly related as minor and immersion are both weaker versions of subdivision.

A digraph is a pair D = (V, A) of finite sets such that A is a set of ordered pairs of elements of V . The elements of V are the vertices and the elements of A are the arcs. For a digraph D, we write V (D) for its vertex set and A(D) for its arc set. A multidigraph is a digraph where we allow an arc to appear multiple times. We call these arcs parallel arcs, and the multiplicity of an arc is the number of times it appears in A(D). We say that a multidigraph has multiplicity k if all its arcs have multiplicity smaller than or equal to k. Let u and v be vertices of V . If (u, v) belongs to A(D), we say that u sees v, u dominates v, v is seen by u or v is dominated by u. We also say that v is an outneighbour of u and u is an inneighbour of v. For an arc a = (u, v), u is said to be the tail of a and v its head. Let D = (V, A) be a digraph and X and Y be two subsets of V . Then A(X, Y ) represents the set of arcs of A with tail in X and head in Y . Let v be a vertex of some digraph D. The inneighbourhood of v, denoted by N -(v), is the set of inneighbours of v and the indegree of An oriented path P is a sequence of vertices together with arcs such that the underlying graph is a path on the same sequence. Let P = (x 1 , x 2 , • • • , x n ) be an oriented path. We say that P is an (x 1 , x n )-path. The vertex x 1 is the initial vertex of P and x n its terminal vertex.

The vertices x i for i ∈ [2, l -1] are referred to as the inner vertices of P . A set of oriented paths P 1 , . . . , P k is said to be internally disjoint if the sets of inner vertices of these paths are pairwise disjoint. P is a directed path or simply a dipath, if x i x i+1 ∈ A(D) for all i ∈ [n -1]. Let P be a dipath, we denote by s(P ) its initial vertex and by t(P ) its terminal vertex. For any two vertices u and v, a (u, v)-dipath or dipath from u to v is a dipath P with s(P ) = u and t(P ) = v. For two sets X, Y of vertices, an (X, Y )-dipath or dipath from X to Y is a dipath P such that s(P ) ∈ X, t(P ) ∈ Y , and no internal vertex is in X ∪ Y . Let x and y be two vertices of D, an (x, y)-walk is a non-empty sequence of vertices v 0 , . . . , v l such that, x = v 0 , y = v l and (v i , v i+1 ) ∈ A(D) for all i ∈ [l -1]. Note that the same vertex can appear multiple times. An oriented cycle C is a set of vertices such that the underlying graph is a cycle. An oriented cycle x 1 , . . . x l of a digraph D is said to be directed if (x i , x i+1 ∈ A(D) for 0 < i < l and (x l , x 1 ) ∈ A(D). For convenience, we will sometimes use path or cycle to talk about oriented path or oriented cycles. A digraph D is said to be acyclic if it doesn't contain a directed cycle as a subdigraph. In a digraph D, a directed cycle C of a dipath P is said to be Hamiltonian if it contains all vertices of D.

A block of a path P or a cycle C is a maximal directed subpath of P or of C. A path is entirely determined by the sequence (b 1 , . . . , b p ) of the lengths of its blocks and the sign + or -indicating if the first arc is forward or backward respectively. Therefore we denote by P + (b 1 , . . . , b p ) (resp. P -(b 1 , . . . , b p )) the oriented path whose first arc is forward (resp. backward) with p blocks, such that the ith block along it has length b i .

An out-arborescence is a rooted tree where all the arcs are oriented away from the root and a k-out-arborescence is an out-arborescence in which every vertex apart form the leaves has outdegree k. An in-arborescence is a tree where all the arcs are oriented towards the root and a k-in-arborescence is an in-arborescence in which every vertex apart form the leaves has indegree k. We use arborescence to talk about an in-or out-arborescence. The depth of an arborscence is the length of its longest dipath. Let x be a vertex of an arborescence T . The ancestors of x is the set of vertices on the path from the root to x and the father of x is the last vertex (towards x) on this path.

Let D and H be two digraphs, we say that D admits a subdivision of H if there exist functions π 1 : V (H) → V (G) and π 2 mapping the arcs of H to dipaths of D satisfying the following conditions:

• the map π 1 is an injection;

• for every arc e ∈ A(H) from u to v, π 2 (e) is a (π 1 (u), π 1 (v))-dipath; and

• for all distinct e, e ∈ A(H), π 2 (e) and π 2 (e ) are internally disjoint.

We say that D admits an immersion of H if there exist functions π 1 : V (H) → V (G) and π 2 mapping the arcs of H to dipaths of D satisfying the following conditions:

• the map π 1 is an injection;

• for every arc e ∈ A(H) from u to v, π 2 (e) is a π 1 (u)π 1 (v)-dipath; and

• for all distinct e, e ∈ A(H), π 2 (e) and π 2 (e ) are arc-disjoint.

In a digraph D, we say that vertices x and y have connectivity k if there exists k vertexdisjoint dipaths betweeen x and y. We say that vertices x and y have arc-connectivity k if there exists k arc-disjoint paths betweeen x and y. A digraph is k-strongly-connected if every pair of vertices has connectivity k. We write strongly connected or strong for 1-stronglyconnected. Let X and Y be sets of vertices. A set S of vertices is an (X, Y )-vertex-cut if D -S does not contain any (X \ S, Y \ S)-dipath. A set A of arcs is an (X, Y )-arc-cut if D \ A does not contain any (X, Y )-dipath.

Theorem 2 (Menger's theorem [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF]). Let D be a digraph, and let S, T ⊆ V (D). The maximum number of vertex-disjoint (S, T )-dipaths is equal to the minimum size of an (S, T )vertex-cut.

The same result holds for arc-connectivity Theorem 3 (Menger's theorem [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF]). Let D be a digraph, and let S, T ⊆ V (D). The maximum number of arc-disjoint (S, T )-dipaths is equal to the minimum size of an (S, T )arc-cut.

A hypergraph is a pair H = (S, E) of disjoint sets, where the elements of E are non-empty subsets of S. The set S is called the ground set of H. The elements of E are called the hyperedges of H. A hypergraph H is k-uniform if every hyperedge has cardinality k.

Let H be a hypergraph on a ground set S and S be a subset of S. The projection of a hyperedge E onto S is defined as E ∩ S . Let H ∩ S denotes the hypergraph defined on S where the edges are the projections of the edges of H onto S .

Let D = (V, A) be a digraph, the inneighbourhood hypergraph of D is the hypergraph H = (V, E), where E = {N -[x]; x ∈ V }.

Structures in graphs

What are the properties of a graph forbidding a certain structure? This is a very natural setting in graph theory under which many interesting conjectures and results can be rephrased. One of the classical results in Graph Theory is Kuratowski's Theorem, saying that planar graphs are precisely the graphs avoiding K 5 and K 3,3 as minors. Generalising this result, the celebrated Robertson-Seymour Theorem states: Theorem 4 (Robertson-Seymour [START_REF] Robertson | Graph minors. XX. Wagner's conjecture[END_REF]). Every class of graphs closed under the minor relation can be defined by a finite set of forbidden minors.

This theorem means that in order to understand a minor-closed class, it is sufficient to understand graphs avoiding a certain set of obstructions as minor. A very important consequence of this theorem and its proof is the development of the graph decomposition technique which led to important results in both structural and algorithmic graph theory. The main parameter in this field is the tree-width, where graphs with small tree-width behave like trees. On the other hand, if the graph has large tree-width, the following theorem allows us to understand some of its structure: Theorem 5 (Grid Minor Theorem, Robertson-Seymour [START_REF] Robertson | Graph minors. V. Excluding a planar graph[END_REF]). For every k, there exists a function f (k) such that any graph with tree-width at least f (k) contains a grid of size k as a minor.

This gives a template for solving many problems: either the graph has small tree-width and the problem can be solved easily (most of the time using a dynamic programming argument), or it contains a large grid as a minor and then we can solve the problem using this specific structure. Probably the most important example of a proof using this technique is the k-linkage problem. An instance of this problem is a graph G and a set of k pairs of vertices (s i , t i ) and the goal is to decide if there are k internally disjoint paths of G joining every possible pair (s i , t i ). In [START_REF] Robertson | Graph minors .XIII. The disjoint paths problem[END_REF], Robertson and Seymour gave a cubic-time algorithm for this problem using the above mentioned strategy, this was later improved to quadratic time.

Even outside this setting of graph decomposition, the question of what parameter can force a certain structure in a graph is natural on its own. The most famous conjecture concerning properties of graphs with a forbidden minor is Hadwiger's Conjecture, which tries to generalise the 4-Colour Theorem: Conjecture 6 (Hadwiger, 1943). For every t ≥ 1, every graph without K t+1 as a minor is t-colourable.

The case t = 5 was proved by Robertson, Seymour and Thomas [START_REF] Robertson | Hadwiger's conjecture for k 6 -free graphs[END_REF] but it remains open for t > 5. On the other hand, it was independently proved in 1984 by Kostochka and Thomason [START_REF] Kostochka | Lower bound of the hadwiger number of graphs by their average degree[END_REF][START_REF] Thomason | An extremal function for contractions of graphs[END_REF] that a graph without K t as a minor is O(t(logt) 1/2 )-colourable. In fact they showed the following stronger theorem: Theorem 7 (Kostochka [START_REF] Kostochka | Lower bound of the hadwiger number of graphs by their average degree[END_REF] and Thomason [START_REF] Thomason | An extremal function for contractions of graphs[END_REF]). For every t ≥ 1, every graph with minimum degree greater than Θ(t(logt) 1/2 ) contains K t as a minor.

Understanding graphs with a large minimum degree has also been studied beyond this link with Hadwiger's Conjecture. The following beautiful result due to Mader [START_REF] Mader | Homomorphieeigenschaften und mittlere kantendichte von graphen[END_REF] in 1967 is probably the most famous example.

Theorem 8 (Mader [START_REF] Mader | Homomorphieeigenschaften und mittlere kantendichte von graphen[END_REF]). For every k ≥ 1, there exists an integer f (k) such that every graph with minimum degree at least f (k) contains a subdivision of the complete graph on k vertices.

Mader, Erdős and Hajnal, conjectured that the right value for f (k) should be in O(k 2 ). Bollobás and Thomason [START_REF] Bollobás | Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs[END_REF] as well as Komlós and Szemerédi [START_REF] Komlós | Topological cliques in graphs ii[END_REF] proved this conjecture 30 years later.

Another related result was obtained recently by DeVos et al. [START_REF] Devos | A minimum degree condition forcing complete graph immersion[END_REF]. Studying a variant of Hadwiger's Conjecture that deals with immersions instead of minors, they showed that graphs with minimum degree greater than 200t contain an immersion of the complete graph on t vertices, proving the first linear bound for these kind of questions. Proving a linear bound for Hadwiger's Conjecture would be a major breakthrough.

Developing a decomposition theory for digraphs is a major challenge in computer science because, in many applications, the most natural model is a digraph. However, apart from a recent breakthrough due to Kawarabayashi and Kreutzer [START_REF] Kawarabayashi | The directed grid theorem[END_REF] who proved in a very technical paper the directed version of the Grid Minor Theorem, not much is known. There are many reasons for that, one being that the directed versions of the problems are inherently more difficult than their undirected version. This difficulty is particularly clear for the linkage problem. An instance of the directed k-linkage problem is a digraph D and a set of k pairs of vertices (s i , t i ) and the goal is to decide if there are k internally disjoint dipaths of D joining every possible pair (s i , t i ). While the k-linkage problem is solvable in quadratic time for every k, the directed version was proved to be NP-hard for k = 2 in [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF]. In fact, Thomassen proved in [START_REF] Thomassen | Highly connected non-2-linked digraphs[END_REF], that the problem is NP-hard for k = 2 even in the case of digraphs with arbitrarily high connectivity. When introducing the directed tree-width, Reed [START_REF] Reed | Introducing directed tree width[END_REF] and Johnson, Robertson, Seymour and Thomas [START_REF] Johnson | Directed tree-width[END_REF] chose a definition such that the k-linkage is polynomial-time solvable on digraphs with bounded directed-tree-width, but the notion is hard to handle. Another reason is our lack of understanding concerning the structural aspect of the problem. The biggest example is probably the following conjecture due to Mader [START_REF] Mader | Degree and local connectivity in digraphs[END_REF] in 1985, which is still open for k ≥ 5.

Conjecture 9 (Mader [49]). For every k ≥ 1, there exists an integer f (k) such that every digraph with minimum outdegree at least f (k) contains a subdivision of T T k , the transitive tournament on k vertices.

A large part of this thesis is dedicated to understand some structural questions related to Mader's Conjecture.

Subdivisions of cliques and local connectivity

Before discussing Conjecture 9, we will talk about the proof of the statement in the undirected case. The first thing to note, is that in any graph with average degree greater than k, there exists a subgraph with minimum degree greater than k/2. In fact Mader in [START_REF] Mader | Existenz n-fach zusammenhängender teilgraphen in graphen genügend grosser kantendichte[END_REF] proved that large average degree forces the existence of a subgraph with large connectivity.

Theorem 10 (Mader [START_REF] Mader | Existenz n-fach zusammenhängender teilgraphen in graphen genügend grosser kantendichte[END_REF]). Any graph G with average degree greater than 4k contains a k-connected subgraph.

Proof. For inductive purposes we will prove the following stronger result. Every graph G on n ≥ 2k -1 vertices and m > (2k -3)(n -k + 1) edges has a k-connected subgraph. Note that the condition m > (2k -3)(n -k + 1) implies for large value of n a average degree of roughly 4k. The proof is by induction on n. If n = 2k -1, then G must be the complete graph, so we can assume n ≥ 2k. If a vertex v satisfies d(v) < 2k -3, we can apply induction on G -v and we are done. Thus δ(G) > 2k -2. Assume G is not k-connected. By Theorem 1, there exists a vertex-cut X of less than k vertices. Call V 1 and V 2 the two components of G -X

and G i = G[V i ∪ X], for i ∈ [2]. If the G i are not k-connected, then by induction hypothesis on each G i : e(G i ) < (2k -3)(|G i | -k + 1). However, since |G 1 ∩ G 2 | = |X| < k, we get that e(G) ≤ e(G 1 ) + e(G 2 ) ≤ (2k -3)(n -k + 1), a contradiction.
For a pair of vertices with high connectivity, the following tight result was proved by Mader [START_REF] Mader | Homomorphieeigenschaften und mittlere kantendichte von graphen[END_REF].

Theorem 11 (Mader [47]). Any graph G with minimum degree k contains a pair of vertices with connectivity k.

The proofs that Mader gave of Theorem 11 and Theorem 8 both use the same idea of induction where the graph is partitioned into a clique and the rest and the induction will go on by contracting vertices onto the clique, while ensuring that the rest of the graph keeps the right properties. We now present theses proofs.

Let

K = {x 1 , . . . , x k } be a clique in a graph G. For every v ∈ N (x 1 ) \ ∩ k i=1 N (x k ), let φ(v) be the smallest integer such that x φ(v) v ∈ E(G). Let G K be the graph obtained from G by removing x 1 and adding for each vertex v ∈ N (x 1 )\∩ k i=1 N (x k ) the edge vx φ(v)
. The following lemma is the key part of the proof of Theorem 11. The idea is that, if K is a maximal clique, then doing the transformation described just above, we can remove one vertex of the clique, while preserving the connectivity between vertices outside of K.

Lemma 12 (Mader [47]).

For every k ≥ 1, if K = {x 1 , . . . , x k } is a maximal clique, then G K is such that:
• the vertices in V (G) \ K have the same degree in G and G K ;

• the connectivity between two vertices in V (G) \ K is the same in G and G K .

Proof. The first property is by construction of φ(v), since ∩ k i=1 N (x i ) is empty because K is a maximal clique.

Let u and v be vertices in V (G) \ K and suppose there exist l disjoint paths P 1 , . . . , P l in G K between u and v. Without loss of generality, we can assume that all these paths use vertices of K. This means there exist l paths Q 1 , . . . , Q l of G K from u to K intersecting only on u, and l paths S 1 , . . . S l of G K from v to K intersecting only on v. Moreover, for every i ∈ [l] and j ∈ [l] (possibly the same), the path Q i and the path S j can only intersect on K. Note that we can assume that Q i ∩ K and S i ∩ K are reduced to a single vertex for every

i ∈ [l]. So let u i = K ∩ Q i and v i = K ∩ S i
denote these vertices. Without loss of generality, we can assume that the u i and the v i are ordered on K, meaning that if i < j and u i = x l(i) and u j = x l(j) , then l(i) < l(j). Finding two sets of paths Q 1 , . . . , Q l and S 1 , . . . , S l of G with the exact same properties would prove the lemma as one can easily use edges in K to close the paths between u and v.

We will obtain each path Q i of G from u to u i by changing only the last vertex of Q i as follows: If the last edge of Q i belongs to G then u i = u i and Q i = Q i . If this edge doesn't belong to G, it means by construction of G K that this edge is an edge tx φ(t) for some t ∈ V (G) \ K. However, by definition of φ(t), it means that t is adjacent in G to all the vertices x r with r < φ(t) (including x 1 ). In particular, if there exists u j with j < i such that the last edge of Q j is not in G, then tu j ∈ E(G). So in this case u i is the biggest u j with j < i such that the last edge of Q i is not in G, if it exists and x 0 if not. By doing the same with the S i between v and K and using edges of K to connect them, we find l disjoint paths between u and v in G.

To prove Theorem 11 Mader proved the following stronger result.

Theorem 13 (Mader [47]). For every k ≥ 1, let G be a graph with a clique K such that |V (G) \ K| ≥ 2 and every vertex of V (G) \ K has degree at least k in G. Then there exists a pair of vertices of V (G) \ K with connectivity k in G.

Proof. The proof is by induction on the order of G. Note that, no matter the order of G, if |V (G) \ K| = 2, then the result is trivially true. This makes the case |G| = k + 2 trivial. Suppose now that |G| is larger than k + 2. If K is maximal, then using the previous lemma and the induction hypothesis on G K gives the result. If K is not maximal, then we can add vertices to K to make it maximal. If during this procedure, |V (G) \ K| ≤ 2, then we can conclude. If not we can apply induction on G K .

The proof of Theorem 8 is a bit different, as we will sometimes need to remove vertices of a clique which is not maximal, thus we cannot guarantee the degree of every vertex in V (G) \ K. However by doing an induction on k, we will be able to guarantee a large average degree.

The following lemma, that we do not prove here, is quite similar to Lemma 12:

Lemma 14 (Mader [START_REF] Mader | Homomorphieeigenschaften und mittlere kantendichte von graphen[END_REF]). For every l ≥ 1, let G be a graph and K a clique in G. Suppose there exists a subidvision of K l in G K with all branching vertices {x 1 , . . . , x l } in V (G) \ K and such that paths of the subdivision between vertices in {x 2 , . . . , x l } only use vertices in V (G) \ K. Then there exists a subdivision of K l in G with branching points {x 1 , . . . , x l } in V (G) \ K and such that paths of the subdivision between vertices in {x 2 , . . . , x l } only use vertices in V (G) \ K.

Proof of Theorem 8. We will prove by induction on p that a graph with average degree 3 p contains K p as a subdivision. The case p = 2 is trivial. Suppose now that the result is true for some p. We will prove it for p + 1. We will prove by induction on the size of G the following:

Let G be a graph of average degree greater than 3 p+1 and K = {x 1 , . . . , x l } a clique of size smaller than p + 2. Then G contains a subdivision of K p+1 with all the branching vertices {x 1 , . . . , x p+1 } in V (G) \ K and such that that paths of the subdivision between vertices in {x 2 , . . . , x p+1 } only use vertices in V (G) \ K.

Let n = |G|. Again, the case where n = 3 p+1 +1 is trivial. If K is maximal, then applying the induction hypothesis on the size of G to G K works as the number of edges of G K is equal to

E(G) -(p + 1) ≥ 3 p+1 2 × n -(p + 1) > 3 p+1 2 × (n -1)
and thus the average degree is greater than 3 p+1 . This allows us to conclude using Lemma 14. Suppose now that K is not maximal. By adding some vertices to it we can assume that |K| = p + 1. Consider the set of vertices X = ∩ k i=1 N (x l ). If the subgraph G[X] has minimum degree 3 p + 1, then we can apply the induction hypothesis on p to G[X] to find a subdivision of K p in X \ {x} for some vertex x ∈ X and extend it to a subdivision of K p+1 using x and edges with K. Suppose G[X] has minimum degree smaller than 3 p + 1 and let s ∈ X be a vertex of degree at most 3 p in G[X]. If we add s to K, then the difference in the number of edges between G and G K is precisely

|N X∪K (s)| ≤ p + 1 + 3 p . Since 3 p+1 2 × n -(p + 1) -3 p > 3 p+1 2 × (n -1),
G K has average degree greater than 3 p+1 and we can conclude by applying the induction hypothesis on the size of G to G K and using Lemma 14.

Subdivisions and immersions in digraphs with large minimum outdegree

When one tries to generalise Theorem 8 to digraphs, the first natural question is to ask if there exists a function f (k) such that every digraph with minimum outdegree at least f (k) contains a subdivision of the complete digraph on k vertices. However the following construction, due to DeVos et al. [START_REF] Devos | Immersing complete digraphs[END_REF](slightly adapted), shows the existence of digraphs with arbitrarily large outdegree and without two arc-disjoint directed cycles between the same pair of vertices. In particular it cannot contain ← → K 3 as a subdivision. Let D k be the digraph obtained from a k-out-arborescence of depth k + 1 by adding to each leaf the set of its ancestors as outneighbours. This is indeed a digraph with minimum outdegree at least k. Let x and y be two vertices of D k . Without loss of generality, we can assume that x is deeper than y in the arborescence. Hence every cycle containing x and y must use the arc from the father of y to y, proving the fact that there cannot exist two arc-disjoint directed cycles going through both vertices.

However, for transitive tournaments, the question remains open. In [START_REF] Mader | Degree and local connectivity in digraphs[END_REF] Mader made the following conjecture.

Conjecture 9 (Mader [START_REF] Mader | Degree and local connectivity in digraphs[END_REF]). For every k ≥ 1, there exists an integer f (k) such that every digraph with minimum outdegree at least f (k) contains a subdivision of T T k , the transitive tournament on k vertices.

The question turned out to be way more difficult than the non oriented case, as the existence of f (5) remains unknown. Weakening the statement, DeVos, McDonald, Mohar and Scheide [START_REF] Devos | Immersing complete digraphs[END_REF] made the following conjecture replacing subdivision with immersion and proved it for the case of Eulerian digraphs.

Conjecture 15 (DeVos et al. [START_REF] Devos | Immersing complete digraphs[END_REF]). For every k ≥ 1, there exists an integer h(k) such that every digraph with minimum outdegree at least h(k) contains an immersion of T T k .

Note that the construction D k given above also prove that, even in the case of immersions, ← → K 3 cannot be forced through minimum outdegree.

An important part of the proof of Mader and the one of Bollobás and Thomason about subdivision of the complete graph is the fact that one can easily find a subgraph with large connectivity inside a graph with large average degree. In digaphs however, the picture is completely different, as the complete bipartite digraph with all arcs oriented in the same direction is an example of a digraph with large average outdegree and without a subdigraph with large minimum outdegree. An interesting remark is that for Eulerian digraphs, a similar result was obtained in [START_REF] Devos | Immersing complete digraphs[END_REF], namely that every Eulerian digraph with large outdegree contains an immersion of an Eulerian digraph with large arc-connectivity.

Another useful tool for finding subdivisions of the complete graph is to find a subgraph with good linkage property. A graph or a digraph is said to be k-linked if every instance of the k-linkage problem admits a solution. Thomas and Wollan in [START_REF] Thomas | An improved linear edge bound for graph linkages[END_REF] proved the following.

Theorem 16 (Thomas and Wollan [START_REF] Thomas | An improved linear edge bound for graph linkages[END_REF]). Every 10k-connected graph is k-linked. However Thomassen in [START_REF] Thomassen | Highly connected non-2-linked digraphs[END_REF] proved the existence of digraphs with arbitrarily large connectivity which are not 2-linked.

Another example about the difficulties of understanding digraphs with large minimum degree is the following conjecture due to Alon [START_REF] Alon | Disjoint directed cycles[END_REF] and still open for k = 2.

Conjecture 17 (Alon [4]). There exists a function f (k) such that every digraph with minimum degree at least f (k) can be partitioned into two digraphs of minimum outdegree at least k.

The existence of f (1) means that one can find two disjoint directed cycles in digraphs with large minimum outdegree. This was proved by Thomassen in [START_REF] Thomassen | Disjoint cycles in digraphs[END_REF]. Even showing that large minimum outdegree digraphs can be partitioned into a directed cycles and a digraph with minimum outdegree 2 is open. Note that the existence of f (2) would imply the existence of f (k) for every k. Indeed, suppose f (2) is known and let D be a digraph with minimum outdegree f (2) k+1 . For each vertex v, we partition

N + (v) into f (2) k sets S 1 (v), . . . , S f (2) k (v), each of size f (2)
. Consider the digraph H obtained from D by replacing every vertex v by an f (2)-out-arborescence of depth k, T (v), and where the ith leaf of T (v) is linked to the roots of the arborescence associated to the vertices in S i (v). Note that contracting each f (k)-out-arborescence into one vertex yields exactly the digraph D. So H can be seen as the digraph D where every vertex is blown-up into an f (k)-out-arborescence and the outdegree of each vertex is distributed to the leaves of the out-arborescence replacing it. H is a digraph with minimum outdegree f (2), so there exists a partition of it into two digraphs of outdegree 2. It is easy to see that, by looking at the roots of the out-arborescences, this corresponds to a partition of D into two digraphs of minimum outdegree 2 k+1 .

A very nice result about digraphs with large minimum outdegree is the existence of vertices with large connectivity. Remember that in graphs with minimum degree d there exists a pair of vertices of connectivity d and the proof of this fact uses ideas similar to the one of Theorem 8. Such a tight result is not possible in digraphs, as Mader showed in [START_REF] Mader | Degree and local connectivity in digraphs[END_REF] the existence of digraphs with minimum outdegree 12m and maximum connectivity 11m. However he showed in [START_REF] Mader | Existence of vertices of local connectivity k in digraphs of large outdegree[END_REF] the existence of a function f (k) such that every digraph with minimum outdegree greater than f (k) contains a pair of vertices with connectivity k. Despite being relatively short, the proof is quite difficult to understand, in part because of the optimisation of the function f (k). We will present our understanding of the proof for arc-connectivity. First because, despite being simpler, it uses most of the very nice ideas of Mader for the verxtex-connectivity and because it served us as base to solve Conjecture 15 in [START_REF] Lochet | Immersion of transitive tournaments in digraphs with large minimum outdegree[END_REF].

Theorem 18. For every k ≥ 1, there exists an integer f (k) such that every digraph with minimum outdegree at least f (k) contains a pair of vertices with arc-connectivity at least k.

Proof. We will prove by contradiction that every digraph D where every vertex but at most k 2 has outdegree greater than k 4 contains a pair of vertices with arc-connectivity k. Let D be the smallest, in term of arcs and vertices, counterexample. By minimality of D, all the vertices have outdegree exactly k 4 except the k 2 with outdegree 0. Let T be the set of vertices with outdegree 0. Pick a vertex v with outdegree k 4 . For every vertex y ∈ D there does not exist a set of k arc-disjoint directed paths from v to y. Hence, by Theorem 3, there exists a set E y of less than k arcs such that there is no directed path from v to y in D \ E y . For every y ∈ D -v, define C y as the set of vertices which can reach y in D \ E y . Now take Y a minimal set such that ∪ y∈Y C y covers D -y. Y consists of at least k 3 elements as ∪ y∈Y E y contains all the arcs of D with tail v.

For each y ∈ Y , define S y as the set of vertices which belong to C y and no other C y for y ∈ Y , y = y. Since Y is minimal, every S y is non-empty. Note that for u ∈ S y , if there exists y ∈ Y \ y and v ∈ C y such that (u, v) ∈ A(D), then (u, v) ∈ E y . Note that T ⊆ Y as vertices in T have outdegree 0 and if y ∈ Y \ T then S y consists only of vertices of outdegree k 4 in D.

Let R be the digraph with vertex set Y and arcs the pairs (y, y ) such that there is an arc from S y to C y . As noted before,

d - R (y) ≤ |E y | ≤ k. The average outdegree of the vertices of Y \ T in R is then at most k×k 3 k 3 -k 2 < k 2 -1.
Let y be a vertex of R \ T with outdegree at most this average. Consider the digraph induced by S y ∪ v. As noted before the arcs of A(S y , Sy ) are precisely the arcs contributing to the outdegree of y in R. Therefore, D[S y ∪ v] is a digraph strictly smaller than D, without two vertices with arc-connectivity k and such that apart from k 2 vertices, every vertex has outdegree k 4 , a contradiction.

Let F (k, l) be the multidigraph consisting of k vertices x 1 , . . . , x k and l arcs from x i to x i+1 for every 1

≤ i ≤ k -1. It is clear that F (k, k
2 ) contains an immersion of T T k , so extending the previous proof to F (k, l) would prove Conjecture 15. The main difficulty to do that, if one removes the arcs of a subdivision of F (k -1, l) and tries to extend it using the same proof as above, is that there is no control on the number of vertices that lose some outdegree. The way around this problem is to remark that, using the notations of last proof, you can add new arcs in D[S y ∪ v] between vertices which belonged to same directed path of the copy of the subdivision of F (k -1, l), so that each of the (k -1)l directed paths of the subdivision of F (k -1, l) contributes to the loss of outdegree of at most one vertex. With this, we are able to control the number of vertices that lose some outdegree and proceed with the induction. The complete proof is presented in Chapter 3.

Trying to extend this technique to obtain the result for subdivisions seems hard, as it looks like the removal of the vertices on the directed paths disturbs the structure of the digraph too much.

Overall not much is known about Conjecture 9. In [START_REF] Kühn | A note on complete subdivisions in digraphs of large outdegree[END_REF], Kühn et al. proved that a digraph of order n whose minimum outdegree is at least d contains a subdivision of a complete digraph of order d 2 8n 3/2 . In [START_REF] Aboulker | Subdivisions in digraphs of large out-degree or large dichromatic number[END_REF], with several co-authors, we looked at subdivisions of digraphs different from the transitive tournament. The first thing we did was to give a tight bound for orientations of paths.

Theorem 19. Let (k 1 , k 2 , . . . , k ) be a sequence of positive integers, and let D be a digraph with δ

+ (D) ≥ i=1 k i . For every v ∈ V (D), D contains a path P + (k 1 , k 2 , . . . , k ) with initial vertex v such that k i ≥ k i if i is odd, and k i = k i otherwise.
The bound is indeed thight as the complete digraph on k vertices has minimum outdegree k -1 and contains no path on more than k vertices.

The next natural digraphs to look at are trees. It is easy to see that, by a greedy algorithm, finding a large out-arborescence in a digraph with large minimum outdegree is trivial. The question of in-arborescence is a however interesting as one needs to control the vertices with large indegree. The main result of paper [START_REF] Aboulker | Subdivisions in digraphs of large out-degree or large dichromatic number[END_REF] was to prove the existence of large in-arborescences in digraphs with sufficiently large minimum outdegree.

Theorem 20. Let F be an in-arborescence. There exists a constant C(F ) such that every digraph with minimum outdegree at least C(F ) contains a subdivision of F .

The proofs of the two previous theorems are presented in Chapter 3 together with some other results. Finding subdivisions remains however open for oriented trees in general. We believe it would be an interesting step towards Conjecture 9.

Problem 21. Let T be an oriented tree. Does there exist a constant a(T ) such that any digraph with minimum outdegree at least a(T ) contains T as a subdivision.

One interesting problem while attacking Conjecture 9 is that it is hard to find a strengthening of the conjecture which makes sense. For example, requiring that D has large in and outdegree, despite making the question trivial for trees does not add anything for the transitive tournament. Indeed suppose that there exists a function g(k) such every digraph with minimum in and outdegree greater than g(k) contains a subdivision of T T k . Let D be a digraph with outdegree greater than g(k), and D be the digraph obtained from D by reversing all the arcs. Consider H obtained by taking a disjoint copy of both D and D and adding all arcs from D to D. H is a digraph with minimum in and outdegree greater than g(k) and thus contains a subdivision of T T k . Without loss of generality, we can assume half of the branching vertices of this subdivision belong to D and thus D contains a subdivision of T T k/2 .

Subdivisions in digraphs with large (di)chromatic number

What can we say about the subgraphs of a graph with large chromatic number? Of course, one way for a graph to have large chromatic number is to contain a large complete subgraph. However, if we consider graphs with large chromatic number and small clique number, then we can ask what other subgraphs must occur. We can avoid any graph that contains a cycle because, as proved by Erdős [START_REF] Erdős | Graph theory and probability[END_REF], there are graphs with arbitrarily high girth and chromatic number. Reciprocally, one can easily show that every graph with chromatic number n contains every tree of order n as a subgraph.

The following more general question attracted lots of attention.

Problem 22. Which are the graph classes G such that every graph with sufficiently large chromatic number contains an element of G?

If such a class is finite, then it must contain a tree, by the above-mentioned result of Erdős. If it is infinite however, it does not necessary contain a tree. For example, every graph with chromatic number at least 3 contains an odd cycle. This was strengthened by Erdős and Hajnal [START_REF] Erdős | On chromatic number of graphs and set-systems[END_REF] who proved that every graph with chromatic number at least k contains an odd cycle of length at least k. A counterpart of this theorem for even length was settled by Mihók and Schiermeyer [START_REF] Mihok | Cycle lengths and chromatic number of graphs[END_REF]: every graph with chromatic number at least k contains an even cycle of length at least k. Further results on graphs with prescribed lengths of cycles have been obtained [START_REF] Gyárfás | Graphs with k odd cycle lengths[END_REF][START_REF] Mihok | Cycle lengths and chromatic number of graphs[END_REF][START_REF] Wang | Structure and coloring of graphs with only small odd cycles[END_REF][START_REF] Löwenstein | Cycle length parities and the chromatic number[END_REF].

During this thesis, we looked at similar problems for directed graphs: which are the digraph classes D such that every digraph with sufficiently large chromatic number contains an element of D? Let us denote by Forb(H) (resp. Forb(H)) the class of digraphs that do not contain H (resp. any element of H) as a subdigraph. The previous question can be reformulated as follows:

Problem 23. Which are the classes of digraphs D such that χ(Forb(D)) is finite? If D is a simple digraph, then χ(Forb(D)) < +∞ only if D is an oriented tree. Burr [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF] proved that every (k -1) 2 -chromatic digraph contains every oriented tree of order k. This was slightly improved by Addario-Berry et al. [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF] who proved the following.

Theorem 24 (Addario-Berry et al. [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF]). Every (k 2 /2 -k/2 + 1)-chromatic digraph contains every oriented tree of order k. In other words, for every oriented tree T of order k, χ(Forb(T

)) ≤ k 2 /2 -k/2.
Burr conjectured that the right bound should be linear:

Conjecture 25 (Burr [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF]). Every (2k -2)-chromatic digraph D contains a copy of any oriented tree T of order k.

This question appears to be extremely difficult, as even the case of tournaments which can be seen as the easiest case of n-chromatic digraphs, was only recently proved by Kühn et al. [START_REF] Kühn | A proof of Sumner's universal tournament conjecture for large tournaments[END_REF].

For special oriented trees T , better bounds on the chromatic number of Forb(T ) are known. The most famous one, known as the Gallai-Roy Theorem, can be seen as a variant of Dilworth's Theorem on orders:

Theorem 26 (Gallai [START_REF] Gallai | On directed paths and circuits[END_REF], Hasse [START_REF] Hasse | Zur algebraischen bergrund der graphentheorie i[END_REF], Roy [START_REF] Roy | Nombre chromatique et plus longs chemins d'un graphe[END_REF], Vitaver [START_REF] Vitaver | Determination of minimal coloring of vertices of a graph by means of boolean powers of the incidence matrix[END_REF]). χ(Forb(P + (k))) = k.

The chromatic number of the class of digraphs not containing a prescribed oriented path with two blocks (blocks are maximal directed subpaths) has been determined by Addario-Berry et al. [START_REF] Addario-Berry | Paths with two blocks in n-chromatic digraphs[END_REF].

Theorem 27 (Addario-Berry et al. [START_REF] Addario-Berry | Paths with two blocks in n-chromatic digraphs[END_REF]). Let P be an oriented path with two blocks on k vertices.

• If k = 3, then χ(Forb(P )) = 3.

• If k ≥ 4, then χ(Forb(P )) = k -1.
One interesting case is the case when D is the set of all subdvisions of a certain digraph. Let us denote by S-Forb(D) (resp. S-Forb(D)) the class of digraphs that contain no subdivision of D (resp. any element of D) as a subdigraph. Note that in the case of undirected graphs, as every graph with chromatic number greater than k contains a graph with minimum degree greater than k, Theorem 8 implies the following.

Theorem 28. For every graph H, there exists a constant C(H) such that any graph with chromatic number greater than C(H) contains a subdivison of H.

Consider the case where D is the set of all subdivisions of a fixed cycle. Let us denote by C k the directed cycle of length k. For all k, transitive tournaments provide examples of digraphs with arbitrarily large chromatic number and without C k as a subdivision. More generally, the following construction communicated to us by Nešetřil generalise this result to any oriented cycle.

Theorem 29. For any positive integers b, c, there exists an acyclic digraph D with χ(D) ≥ c in which all oriented cycles have more than b blocks. Proof. By [START_REF] Erdős | Graph theory and probability[END_REF], there exist graphs with chromatic number c and girth greater than cb. Let G be such a graph and consider a proper c-colouring φ of it. Let D be the acyclic orientation of G in which an edge uv of G is oriented from u to v if and only if φ(u) < φ(v). By construction, the length of all directed paths in D is less than c and since each oriented cycle of D has length more than cb, they all have more than b blocks. This directly implies the following theorem.

Theorem 30. For any finite family C of oriented cycles,

χ(S-Forb(C)) = ∞.
On the other hand, considering strongly connected digraphs may lead to dramatically different results. An example is provided by the following celebrated result due to Bondy [START_REF] Bondy | Disconnected orientations and a conjecture of Las Vergnas[END_REF] : every strong digraph of chromatic number at least k contains a directed cycle of length at least k. Denoting the class of strong digraphs by S, this result can be rephrased as follows.

Theorem 31 (Bondy [9]).

χ(S-Forb( C k ) ∩ S) = k -1.
The proof of this result is particularly elegant as it starts with the longest cycle where each vertex gets one different colour and extend this colouring to the rest of the digraph.

One natural question is to extend Bondy's result to other oriented cycles.

Problem 32. Let C be an oriented cycle. Is χ(S-Forb(C) ∩ S) bounded?

The first class of oriented cycles to consider is probably the case of cycles with two blocks. Addario-Berry et al. [START_REF] Addario-Berry | Paths with two blocks in n-chromatic digraphs[END_REF] posed the following problem.

Problem 33 (Addario-Berry et al. [START_REF] Addario-Berry | Paths with two blocks in n-chromatic digraphs[END_REF]). Let k and be two positive integers. Does S-Forb(C(k, )∩ S) have bounded chromatic number?

In [START_REF] Cohen | Subdivisions of oriented cycles in digraphs with large chromatic number[END_REF] we proved the following theorem: Theorem 34. S-Forb(C(k, ) ∩ S) has chromatic number O((k + l) 4 ).

The proof of this theorem, as well as other related results will be presented in Chapter 2. The function has been recently improved to O((k + l) 2 ) by Kim et al. in [START_REF] Kim | Cycles with two blocks in k-chromatic digraphs[END_REF].

A p-spindle is the union of k internally disjoint (x, y)-dipaths for some vertices x and y. Vertex x is said to be the tail of the spindle and y its head. A (k 1 + k 2 )-bispindle is the union of k 1 (x, y)-dipaths and k 2 (y, x)-dipaths, all these dipaths being internally disjoint. One possible interpretation of Theorems 34 and 31 is to view a cycle on two blocks as a 2-spindle (two internally disjoint dipaths between the same pair of vertices) and a directed cycle as a (1+1)-spindle. A natural question is to try to extend Theorems 31 and 34 to larger spindles. First, we give a construction of digraphs with arbitrarily large chromatic number that contains no 3-spindle and no (2 + 2)-bispindle. Therefore, the most we can expect in all strongly connected digraphs with large chromatic number are (2 + 1)-bispindles.

Theorem 35. For every integer k, there exists a strongly connected digraph D with χ(D) > k that contains no 3-spindle and no (2 + 2)-bispindle.

Proof. Let D k,4 be an acyclic digraph with chromatic number greater than k in which every cycle has at least four blocks. The existence of such a digraph is given by Theorem 29. Let S = {s 1 , . . . , s l } be the set of vertices of D k,4 with outdegree 0 and T = {t 1 , . . . , t m } the set of vertices with indegree 0.

Consider the digraph D obtained from D k,4 as follows. Add a dipath P = (x 1 , x 2 , . . . , x l , z, y 1 , y 2 , . . . , y m ) and the arcs (s i , x i ) for all i ∈ [l] and (y j , t j ) for all j ∈ [m]. It is easy to see that D is strong. Moreover, in D, every directed cycle uses the arc (x l , z). Therefore D does not contain a (2 + 2)-bispindle, because it contains two arc-disjoint directed cycles.

Suppose now that D has a 3-spindle with tail u and head v, and let Q 1 , Q 2 , Q 3 be its three (u, v)-dipaths. Observe that u and v are not vertices of P , because all vertices of this dipath have either indegree 2 or outdegree 2. In D, each oriented cycle with two blocks between vertices outside P must use the arc (x l , z). The union of Q 1 and Q 2 form a cycle on two blocks, which means that one of the two paths, say Q 1 , contains (x l , z). But Q 2 and Q 3 also form a cycle on two blocks, but they cannot contain (x l , z), a contradiction.

Let B(k 1 , k 2 ; k 3 ) denote the digraph formed by three internally disjoint paths between two vertices x, y, two (x, y)-directed paths, one of size k 1 , the other of size k 2 , and one (y, x)directed path of size k 3 . Note that B(k 1 , k 2 ; k 3 ) is a (2+1)-bispindle where the length of the dipaths are specified. In [START_REF] Cohen | Bispindles in strongly connected digraphs with large chromatic number[END_REF], we conjectured the following: Conjecture 36. There is a function g : N 3 → N such that every strong digraph with chromatic number at least g(k 1 , k 2 , k 3 ) contains a subdivision of B(k 1 , k 2 ; k 3 ).

As an evidence, we proved the following result:

Theorem 37. For every k ≥ 1, there is a constant γ k such that if D is a strong digraph with χ(D) > γ k , then D contains a subdivision of B(k, 1; k).
The proof is quite technical. However the main idea is to use the fact that strong digraphs with a Hamiltonian cycle and without a subdivision of B(k, 1; k) easily have bounded chromatic number. To colour a digraph without a subdivision of B(k, 1; k), we will then contract the long directed cycles one after the other until we reach a digraph without any long cycle. By Theorem 31, the resulting digraph has bounded chromatic number, and by carefully analysing how the contracted cycles can interact with one another, we deduce a colouring of the original digraph. The full proof, as well as the simpler case of B(k, 1; 1) is presented in Chapter 2.

The following conjecture, probably very hard and way stronger than the results we are looking at here, would be an interesting tool for Conjecture 36.

Conjecture 38. For every k ≥ 1, there exists an integer f (k) such that every strong digraph with chromatic number greater than f (k) contains a subdigraph H with chromatic number at least k and such that H contains a Hamiltonian cycle.

Recently, another notion of colouring for digraphs has received a lot of attention, mainly for its link to the celebrated Erdős-Hajnal conjecture (see [START_REF] Berger | Tournaments and colouring[END_REF] for more details), the directed colouring, or simply dicolouring

. A k-dicolouring is a k-partition (V 1 , . . . , V k ) of V (D) such that D[V i ] is acyclic for every i ∈ [k],
and the dichromatic number of D is the minimum k such that D admits a k-dicolouring.

To analyse digraphs with large dichromatic number, one can consider only strong digraphs, as shown by the next lemma: Lemma 39. The dichromatic number of a digraph is the maximum of the dichromatic numbers of its strong components.

Remember that Theorem 8 implies the following: Theorem 28. For every graph H, there exists a constant C(H) such that any graph with chromatic number greater than C(H) contains a subdivison of H.

In [START_REF] Aboulker | Subdivisions in digraphs of large out-degree or large dichromatic number[END_REF] we proved the following theorem, which can be seen as a generalisation of the previous theorem: The proof is presented in Chapter 2. An interesting question would be to see how much the bound 4 m (n -1) + 1 can be improved.

The Erdős-Sands-Sauer-Woodrow conjecture

We interpret a quasi-order on a set S as a digraph, where the vertices are the elements of S and the arcs are the ordered pairs (x, y) such that x ≤ y. The transitive closure of a digraph D = (V, A) is the digraph defined on V , with arc set the set of ordered pairs (x, y) such that there exists a dipath from x to y in D. The transitive closure of a digraph is a quasi-order. In a multidigraph D, a set S is dominating if for every u ∈ D -S, there exists s ∈ S such that su is an arc. Let γ(D) be the size of the smallest dominating set in D. In 1986, Sands, Sauer and Woodrow proved the following result:

Theorem 41 (Sands et al. [START_REF] Sands | On monochromatic paths in edge-coloured digraphs[END_REF]). Let D be a digraph whose arcs are coloured with two colours. Then there exists a stable set S such that for every x not in S, there is a monochromatic dipath from x to a vertex of S.

By considering the transitive closure of each colour class, the result can be stated as follows:

Theorem 42 (Sands et al. [START_REF] Sands | On monochromatic paths in edge-coloured digraphs[END_REF]). Every multidigraph D whose arc set is the union of the arc sets of two quasi-orders contains a stable set dominating D.

This statement can be seen as a generalisation of the Stable Marriage theorem. This theorem states that, given a complete bipartite graph B between n men and n women, where each person has ranked all members of the opposite gender in order of preference, there exists a perfect matching (set of marriages) such that there are no two people of opposite gender who would both rather marry each other than their current partners. To prove that there always exists such a matching, consider the following 2-arc-coloured (blue and red) digraph D: each vertex of D corresponds to an edge of B, the blue arcs correspond to the preferences of the men: if u prefers v 1 over v 2 then there is a blue arc from uv 1 to uv 2 in D. Likewise the red arcs represent the preferences of the women. Applying Theorem 42 to D gives the desired matching, as a stable set in D is precisely a matching in B and two people of opposite gender who would both rather have each other than their current partners corresponds to a non dominated vertex in D.

In the same paper, Sands et al. conjectured the following generalisation:

Conjecture 43 (Sands et al. [START_REF] Sands | On monochromatic paths in edge-coloured digraphs[END_REF]). For every k ≥ 1 there exists an integer f (k) such that, for any multidigraph D whose arc set is the union of the arc sets of k quasi-orders, there exists f (k) stable sets such that the union is dominating.

A weaker conjecture concerning tournaments was also asked in the same paper (and attributed to Erdős).

Conjecture 44 (Erdős and Sands et al. [START_REF] Sands | On monochromatic paths in edge-coloured digraphs[END_REF]). For every k ≥ 1 there exists an integer f (k) such that for any complete multidigraph D whose arc set is the union of the arc sets of k quasi-orders, γ(D) ≤ f (k). This conjecture turned out to be very difficult, as despite attracting a lot of attention, the case k = 3 remained unresolved. In fact, before our proof of Conjecture 44 that will be presented in this thesis, even the following weaker conjecture due to Gyárfás was still open for k = 3.

Conjecture 45 (Gyárfás). For every k ≥ 1 there exists an integer f (k) such that for any tournament T whose arc set is the union of the arc sets of k quasi orders, γ(T ) ≤ f (k).

We will call the tournaments whose arc set is the union of the arc sets of k quasi orders k-transitive tournaments.

A nice application of Conjecture 45 was proved in [START_REF] Pálvölgyi | Domination in transitive colorings of tournaments[END_REF]. Given two points p = (p 1 , p 2 , . . . , p d ) and q = (q 1 , q 2 , . . . , q d ) in R d , define box(p, q) as the smallest box in R d containing p and q. In other words, box(p, q) = {x ∈ R d | ∀i min(p i , q i ) ≤ x i ≤ max(p i , q i )}. In 1987, Bárány and Lehel [START_REF] Bárány | Covering with euclidean boxes[END_REF] proved that every finite subset X of R d can be covered by h(d) X-boxes (boxes between points of X). To derive this statement from Conjecture 45, we consider a coloured clique on X. Take p = (p 1 , . . . , p d ) and q = (q 1 , . . . , q d ) and assume p 1 < q 1 (we can assume that all the coordinates are different). The colour of the edge pq is given according to the 2 d-1 possible relations of the other d -1 coordinates. This gives a clique with 2 d-1 colours. Note that if pq is a red edge, then box(p, q) contains all the vertices r such that (p, r, q) is a red dipath. Now for each colour class, there are two possible orientations giving a transitive order: if p 1 < q 1 or if q 1 < p 1 . Consider all the tournaments obtained by taking any of these orientations. This gives 2 2 d-1 k-transitive tournaments. If Conjecture 45 is true, then each one has a dominating set of size depending only on d. Consider the union S of the dominating sets of all these tournaments, and take all the boxes between pairs of points of S. We claim that this is a covering of X. Suppose it is not, and let x be a point not covered by the boxes of S. This means that for any colour class, x is not in the middle of a path on three vertices between two vertices of S, so there exists an orientation of this colour class such that x is not dominated by S in this colour. By doing this for all the classes, we obtain a tournament where S is not dominating x, a contradiction.

A useful result for this problem is the following result due to Fisher [START_REF] Fisher | Squaring a tournament: A proof of Dean's conjecture[END_REF]:

Theorem 46 (Fisher [START_REF] Fisher | Squaring a tournament: A proof of Dean's conjecture[END_REF]). For every digraph D, there exists a probability distribution on the vertices w such that for every vertex x, w(N -(x)) ≥ w(N + (x)).

Fisher uses this result in [START_REF] Fisher | Squaring a tournament: A proof of Dean's conjecture[END_REF] to prove the tournament version of Seymour's second neighbourhood conjecture, which states that any oriented graph has a vertex whose outdegree is at most its second outdegree. The proof of this theorem uses Farkas's Lemma.

Lemma 47 (Farkas's Lemma). Let M ∈ R n×m and b ∈ R m . Then exactly one of the following statements is true:

1. There exists x ∈ R n such that Mx = b and x ≥ 0.

There exists y

∈ R m such that M T y ≥ 0 and b T y < 0. Let D be a digraph on vertices {v 1 , . . . , v n }. The adjacency matrix M(D) = (m ij ) of D is the n × n matrix where m ij = 1 if (v i , v j ) ∈ A(D), m ij = -1 if (v j , v i ) ∈ A(D)
and else m ij = 0. Note that a probability distribution w satisfying Theorem 46 can be seen as a vector w ∈ R n such that w ≥ 0, w1 T = 1 and M(D)w ≤ 0.

Proof of Theorem 46. Suppose that w doesn't exist. This means that the following system has no solutions (I is the identity matrix):

C = M(D) I 1 T 0 T w z = 0 1 with w z ≥ 0 0
Farkas's Lemma implies that the following system has a solution:

C = M(D) T 1 I 0 T u v ≥ 0 0 with 0 T 1 u v < 0
As M(D) T = -M(D) we get that M(D)u ≤ v1 with v < 0, so M(D)u < 0. Moreover, as Iu ≥ 0, then u ≥ 0 and by normalising u, we get the required probability distribution on the vertices.

If we apply this result to a tournament, we get that w(N -[x]) ≥ 1/2. To get the intuition, it can be useful to forget this weight function and consider that the indegree of every vertex is at least half the vertices.

A powerful tool to bound the domination on certain class of tournaments is the VCdimension of the inneighbourhood hypergraph. Let H = (V, E) be a hypergraph. We say that a subset S of V is shattered if H ∩ S contains all subsets of S . The VC-dimension of a hypergraph is the size of the biggest shattered set of H. A fundamental result concerning VC-dimension is the following lemma, due to Sauer [START_REF] Sauer | On the density of families of sets[END_REF] (see also Lemma 10.2.5 of [START_REF] Matousek | Lectures on Discrete Geometry[END_REF]).

Lemma 48 (Sauer [64]). Let H be a hypergraph of VC-dimension at most k. Then for every subset A of the ground set,

|E(H ∩ A)| < ( e|A| k ) k .
The VC-dimension of a tournament is the VC-dimension of its inneighbourhood hypergraph. It was first observed by Alon et al. [START_REF] Alon | Dominating sets in k-majority tournaments[END_REF] that any tournament T with VC-dimension bounded by t has γ(T ) ≤ O(t log(t)), because the fractional domination of a tournament is bounded by 2 and thus we can apply the -net Theorem (see chapter 10.2 of [START_REF] Matousek | Lectures on Discrete Geometry[END_REF] for a nice presentation). Rephrasing the proof of the -net Theorem in the case of tournaments with large indegree gives something along these lines:

For simplicity, we assume here that the indegree of every vertex is at least |T |/2. The probability distribution given by Theorem 46 will be the tool to deal with the general case in a similar fashion. Let c be some constant only depending in the VC-dimension t. We want to prove that there exists a dominating set of size c by contradiction. Take two random subsets of size c, S 1 and S 2 , uniformly in T and let A be the following event: "There exists a vertex v that dominates S 1 and |N -(v) ∩ S 2 | ≥ 1/4." We will compute the probability of A in two different ways and reach a contradiction. First, since we assumed that no set of size c is dominating, there exists an element v dominating S 1 , and the probability that

|N -(v) ∩ S 2 | ≥ 1/4 is
a lower bound on the probability of A. Since c is a constant, we can view roughly the random variable S 2 as picking c vertices uniformly and independently among vertices of

T . Since |N -(v)| ≥ 1/2 the random variable |N -(v) ∩ S 2 |
follows a binomial distribution with parameter c and p ≥ 1/2. Using a classical bound on the binomial distribution (see Lemma 10.2.6 of [START_REF] Matousek | Lectures on Discrete Geometry[END_REF]), we have that P r[A] ≥ 1/2. For the second way of computing P r[A], instead of taking S 1 and S 2 uniformly at random, we select a set A of size 2c uniformly at random and then partition it uniformly at random into (S 1 , S 2 ). The resulting distribution is the same as above. To bound P r[A], we fix S ⊆ A and compute the probability that a vertex v dominates S 1 and

|N -(v) ∩ S 2 | ≥ 1/4 conditioned by the fact that N -(v) ∩ A = S. If N -(v) ∩ A < c/4, then the probability is 0; if N -(v) ∩ A ≥ c/4
, then the probability is bounded by the probability that a random sample of size c in 2c elements avoids at least c/4 positions. This is at most

2c-c/4 c 2c c ≤ (1 -1/8) c ≤ exp(-c/8).
Now remark that for a vertex v, the probability that v dominates S 1 and

|N -(v) ∩ S 2 | ≥ 1/4 depends only on A ∩ N -(v)
. However, we proved that, for each possible intersection, the probability is bounded by exp(-c/8). Since the VC-dimension of the inneighbourhood of T is bounded from above by t, by Lemma 48 there are at most (ec/k) k possible intersections and we get,

1/2 ≤ P r[A] ≤ exp(-c/8)(ec/k) k
which for c big enough compared to k is a contradiction. When we tried to attack Conjecture 44, we first looked at the case k = 3 of Conjecture 45. We proved it using a sampling argument inspired by the proof of the -net Theorem presented above, despite the fact that 3-transitive tournaments do not have bounded VCdimension. Trying to extend the proof to k > 3, we found in [START_REF] Bousquet | A proof of the Erdős-Sands-Sauer-Woodrow conjecture[END_REF] a very simple proof of Conjecture 44 which does not use the VC-dimension at all. Theorem 49. For every k ≥ 1, if T is a complete multidigraph whose arc set is the union of the arc sets of k quasi-orders, then γ(T

) = O(ln(2k) • k k+2 ).
The two proofs are presented in Chapter 4.

Entropy Compression

The probabilistic method is a surprisingly powerful method in combinatorics and one of its central tool is the Lovász Local lemma (LLL in short).

Lemma 50 (LLL). Let A 1 , A 2 , . . . , A n be random events of an arbitrary probability space. Suppose that each event A i is mutually independent of all the other event A j but at most d, and that P r

[A i ] ≤ p for all i. If ep(d + 1) ≤ 1, then P r[∩ i Āi ] > 0.
One very common setting is to view the probability space as a set of independent variables X 1 , X 2 , . . . , X l and each event A i depends on a finite set D(A i ) of these variables. The LLL tells us that under the right conditions on probability and dependency, there exists an assignment of the variables such that none of the A i happens. Note that the A i are usually called the "bad events" because the goal is to avoid them. A very natural question that has attracted a lot of attention over the years was to find a way to compute these assignments. In 2009, Moser [START_REF] Moser | A constructive proof of the Lovász Local Lemma[END_REF] gave the answer to this problem by showing that the most natural algorithm works:

Algorithm 1: Moser Fix it Algorithm Pick X 1 , . . . , X n uniformly at random; while There exists i such that A i is true do Repick all the variables in D(A i ) uniformly at random; return the X i ; What is especially interesting is how he managed to prove that the algorithm terminates. Suppose for example that the X i are random bits and assume that the algorithm never finishes after k steps, where a step is one random choice. In this case, a way to see this algorithm is to see it as a deterministic algorithm which takes the random choices as a k-bits vector input and produces some assignments of the X i , which correspond to the state of the X i at the end of the algorithm run on the vector. Moser's idea was that he could modify the algorithm to produce some sequence of integers such that, given this sequence and the value of the X i at the end of the algorithm, one can deduce the value of the k-bit vector taken as input. The sequence produced is called a log. Usually the logs produced by the algorithm have very specific properties and this allow us to show that the set of possible logs after k steps is strictly smaller than 2 k . Since 2 k is the number of k-bit vectors, this gives a contradiction. The intuitive way of seeing the log is to see it being built step by step during the algorithm: each time the algorithm erases a set of random choices, it encodes it in the log using less information. For example, if A i is a bad event, and the algorithm erased the values of D(A i ), then the log need to encode two things: how to know that A i was the bad event and then the value of the variable in D(A i ). Usually, describing which A i is a bad event is the hard part, and this is where we use the local aspect of the problem. Indeed, since P r[A i ] is small, then describing the assignment of D(A i ) such that A i happens doesn't cost much compared to the set of all possible choices. Writing the proof usually requires more efforts, as one needs to define the log, show that we can deduce the random choices from it, and compute the number of possible logs (sometimes using analytic combinatorics). However the point of view of "information deleted versus information needed to recover it" is the one people use to get the intuition.

This method of showing the existence of a combinatorial object by proving that a random algorithm terminates by encoding its random choices into a set of smaller size is called "the entropy compression method". Since then, it has been used a lot, sometimes to improve on bounds obtained by the usual LLL but not always. During this thesis, we use this setting for two different results, which we shortly describe here and that one can find in Chapter 5.

Orientations of Hypergraphs

In [START_REF] Caro | Equitable hypergraph orientations[END_REF], Caro, West, and Yuster presented a generalization to hypergraphs of the notion of orientation defined for graphs. Their acknowledged purpose was to study how hypergraphs can be oriented in such a way that minimum and maximum degree are close to each other, knowing that the following theorem is true for graphs.

Theorem 51 (Folklore). If G is a graph, then there exists an orientation D of G such that |d + (u) -d -(u)| ≤ 1 for every vertex u.

Identifying an orientation of a hyperedge with a total ordering of its elements, they defined a notion of degree on oriented r-uniform hypergraphs. Caro, West, and Yuster [START_REF] Caro | Equitable hypergraph orientations[END_REF] proved that all hypergraphs admit a 1-equitable as well as a (r -1)-equitable orientation, and also proved that some hypergraphs do not admit any p-equitable orientation for all other values of p. Additionally, they parameterized the notion of maximum degree in order to focus on hypergraphs which are sparse with respect to the problem at hand:

∆ p (H) = max U ⊆V (H) |U |=p
|{S ∈ H : U ⊆ S}| Thus, they proved that for any fixed values of p and k, and for every sufficiently large integer r, every r-uniform hypergraph H with ∆ p (H) ≤ k admits a nearly p-equitable orientation. They conjectured that this setting actually ensured the existence of a p-equitable orientation, which we proved in [START_REF] Cohen | Equitable orientations of sparse uniform hypergraphs[END_REF] with Nathann Cohen.

Theorem 54. Let p, k be fixed integers. There exists r 0 such that for every r ≥ r 0 , every r-uniform hypergraph with ∆ p (H) ≤ k admits a p-equitable orientation.

Note that, as r is big compared to ∆ p (H), a p-equitable orientation means that d P (U ) is equal to 0 or 1 for every choice of set of positions P and set of vertices U .

In order to prove the existence of nearly p-equitable orientations, Caro, West, and Yuster [START_REF] Caro | Equitable hypergraph orientations[END_REF] used the Lovász Local Lemma. We use the entropy compression technique to improve their result. The algorithm we propose will orient the hyperedges of H one by one at random such that, at any time during the algorithm, the number of times a set U of p vertices is sent to a set of positions P by the hyperedges which have been oriented is 0 or 1. This means that if at some point in the algorithm all the hyperedges are oriented, then H admits a p-equitable orientation. Suppose now we have a partial orientation of H and we try to orient an hyperedge X. For any subset U of p vertices of X, the orientation we give on X cannot send U to a set of position P which it has already been sent to before. Call valid such a permutation. So for any subset of p vertices of X, there is a list of forbidden positions, and a valid orientation is one which avoids all of those. This can be seen as a generalization of derangements. Remember that a permutation σ of [n] is a derangement if σ(i) = i for all i.

The main idea of the algorithm is to ensure that, at any time, the number of valid orientations available for every hyperedge is large. To do so we need the following lemma, which can be seen as a generalization of the classical result saying that the number of derangement of size n tends to n!/e. The proof will make use of another variant of the LLL, namely the Lopsided Lovász Local lemma.

Lemma 55. Let p, k ∈ N and α < 1 be fixed. Let X be a set of cardinality r and let L S be, for every S ∈ X p , a collection of p-subsets of X with |L S | ≤ k. Then, if no p-subset occurs in more than r α of the L S , a random permutation σ of X satisfies σ(S) ∈ L S for every S with probability ≥ (1 -2k/ r p ) ( r p ) = e -2k + o(1) when r grows large.

The collection L S corresponds to the list of forbidden positions for S. What the previous lemma says is that if a position is not forbidden too many times, i.e it appears in too many different L S , then there will be a constant fraction of the permutations available as valid orientations.

So the algorithm will be the following: Chose the permutations one by one among the valid ones, and if at some point there exists an edge X of H and a set P of positions such that P is forbidden too many times for X, then erase the permutations that forbid P for X. The algorithm stops once every permutation is chosen.

The idea behind this algorithm is to make sure that at each step, the number of good permutations is high enough to make the entropy compression argument work. In this sense it is a bit different from a normal LLL argument and reminds us more of a semi-random method, where we pick part of the solution while ensuring that the rest has nice properties.

AVD-colouring

An edge colouring of a graph G is defined as a mapping c : E(G) → N associating integers (colours) to the edges of G. An edge colouring is said to be proper if no two adjacent edges receive the same colour. Vizing Theorem says that every graph has a proper edge colouring with ∆(G) + 1 colours. In 2002 Zhang, Liu, and Wang [START_REF] Zhang | Adjacent strong edge coloring of graphs[END_REF], introduced a new variant of edge colouring. Given a proper edge colouring c of G and a vertex u ∈ V (G), we let S c (u) denote the set of colours appearing on edges incident to u. A proper edge colouring c is adjacent vertex distinguishing (AVD for short) if S c (u) = S c (v) for every edge uv ∈ E(G). They conjectured:

Conjecture 56 (Zhang et al. [START_REF] Zhang | Adjacent strong edge coloring of graphs[END_REF]). Every connected graph G with maximum degree ∆ which is distinct from K 2 and C 5 has an AVD-colouring with at most ∆ + 2 colours. This conjecture captured the attention of several researchers over the years. It is known to be true e.g. if G is bipartite [START_REF] Balister | Adjacent vertex distinguishing edge-colorings[END_REF] or if ∆ = 3 [START_REF] Balister | Adjacent vertex distinguishing edge-colorings[END_REF]. It also holds asymptotically almost surely for random 4-regular graphs [START_REF] Greenhill | Neighbour-distinguishing edge colourings of random regular graphs[END_REF]. Hatami [START_REF] Hatami | ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number[END_REF] in 2005 proved that every graph with maximum degree ∆ > 10 20 and no isolated edge has an AVD-colouring with at most ∆ + 300 colours. Since then no further progress has been made on Conjecture 56.

With Gwenaël Joret in [START_REF] Joret | Progress on the adjacent vertex distinguishing edge colouring conjecture[END_REF], we improved this result to ∆ + 19 for large value of ∆.

Theorem 57. For ∆ large enough, every digraph with maximum degree ∆ and no isolated edge has an AVD-colouring with at most ∆ + 19 colours.

Algorithm

We will now describe the proof in the case of d-regular graphs. The presentation uses a simpler argument than the one presented in Chapter 5. It leads to a worse constant but contains the general ideas. The method of the proof is the following one, already present in the proof of Hatami. Start with a proper (d + 1)-edge-colouring c given by Vizing's Theorem. Let c be a partial edge colouring, then S c (u) is the set of colours incident to u in this colouring. The goal is to uncolour the edges such that the partial colouring c obtained has the following properties:

(i) The graph of uncoloured edges has maximum degree bounded by q+3 for some constant q; and (ii) c is AVD, meaning that if uv is an edge of G, then S c (u) = S c (v). Now pick c s a proper edge colouring of the uncoloured graph using a set of new colours (different from those of c): the colouring c f obtained by taking the union of c s and c is an AVD-colouring with d + q + 5 colours. Indeed, it is easy to see that this produces a proper edge colouring of the graph. Moreover if u and v are two adjacent vertices, then by definition of c , there exists a colour i adjacent to v and not to u in c . But since c s uses new colours, the colour i is still incident to v and not to u in c f .

To find c , we describe an algorithm that chooses, for every v, a set U (v) of three edges adjacent to v such that u∈V (G) U (v) will be the set of uncoloured edges. At the beginning of the algorithm, all the sets U (v) are set to empty. Now at each step, the algorithm will pick deterministically a vertex v such that U (v) = ∅ and pick U (v) among the d 3 possible choices. The goal of the algorithm is to make sure that, if it ends, then property (i) and (ii) are satisfied. We will define two types of bads events, for which the algorithm will reset some of the U (v) to empty when they occur. The first type is defined to ensure that property (i) is satisfied. Note that, the degree of a vertex v in the uncoloured graph is equal to three plus the number of times v has been chosen in U (u) for u ∈ N (v). So the first bad event will be:

Bad event of type 1. After choosing U (x), v ∈ U (x) belongs to q sets U (u).
In this case, the algorithm erases the choices of these U (u). To deal with property (ii), we define the following notion: We say that an edge uv is finished if U (w) = ∅ for each vertex w in N (u) ∪ N (v) (note that this set includes u and v). When an edge is finished, it means that all the random choices relevant to the set of colours adjacent to u and v at the end of the algorithm have been made. In particular if these sets are the same, then the algorithm triggers a bad event:

Bad event of type 2. After choosing U (x), there exists v ∈ N (x) and u ∈ N (v) such that, uv is finished and S c (u) = S c (v).

In this case, the algorithm erases the choice for U (v).

Encoding

It is clear that, if the algorithm terminates, it produces the desired partial colouring c . In order to complete the proof, we only need to show that, there exists a set of random choices such that the algorithm terminates. Using the entropy compression template, we need to show that, any time we erase a random choice, we can encode it with less information. To do this encoding, we suppose that we know the state of the U (v) for every vertex in the graph after treating the bad event. If we are able to recover the value of the variable that we just erased, it means that, by looking at the log and the state of the sets U (v) when the algorithm stops, we can recover the values of U (v) at any moment of the algorithm.

When a Bad event of type 1 is triggered, the algorithm erases q choices of U (u), so d bad event happens and thus can be encoded using an integer in [d]. To encode the q -1 neighbours of v outside of u we can use an integer in d q-1 . And finally for these vertices we need to encode the two other choices which makes U : d 2 . Overall we encode the d 3 q possibilities using an integer in d × d q-1 × d 2 q . And for q big enough (10 for example works here)

d 3 q < d × d q-1 × d 2 q
, so we managed to compress some information.

When a Bad event of type 2 happens, the algorithm erases choices for U (v), so d 3 possibilities. Note that to recover the information, we just need to know the vertices u and v. Indeed since u and v have the same set of adjacent colours, U (v) is precisely the set of colours adjacent to v and not to v. In this case encoding the d 3 possible choices only requires an integer in [d 2 ] which is needed to say which neighbour of x is v and which neighbour of v is u.

Overall this proves that, if t is big enough, then we can encode all the of t random choices such that the algorithm doesn't terminate in a set of logs of size o d 3 t . Thus there exists a set of t random choices such that the algorithm terminates, which gives the desired partial colouring.

The general proof is presented in Chapter 5.

Chapter 2

Subdivisions in digraphs with large chromatic number

In this chapter, we present some results on subdivisions in digraphs with large chromatic and dichromatic number.

After some definitions we present some proofs from [START_REF] Cohen | Subdivisions of oriented cycles in digraphs with large chromatic number[END_REF] obtained with Nathann Cohen, Frédéric Havet and Nicolas Nisse about oriented cycles in digraphs with large chromatic number. Then we present the proof obtained in [START_REF] Cohen | Bispindles in strongly connected digraphs with large chromatic number[END_REF] with Nathann Cohen, Frédéric Havet and Raul Lopes about subdivisions of spindles (so directed paths between the same pair of vertices). Finally we present a proof of a theorem obtained in [START_REF] Aboulker | Subdivisions in digraphs of large out-degree or large dichromatic number[END_REF] with Pierre Aboulker, Nathann Cohen, Frédéric Havet, Phablo Moura and Stéphan Thomassé saying that any digraph H is contained in a digraph with dichromatic number greater than a function of H.

Definitions

Let F be a digraph. An F -subdivision is a subdivision of F . A digraph D is said to be F -subdivision-free, if it contains no F -subdivision.

The union of two digraphs D 1 and D 2 is the digraph In a digraph D, the distance from a vertex x to another y, denoted by dist D (x, y) or simply dist(x, y) when D is clear from the context, is the minimum length of an (x, y)dipath or +∞ if no such dipath exists. For a set X ⊆ V (D) and vertex y ∈ V (D), we define dist(X, y) = min{dist(x, y) | x ∈ X} and dist(y, X) = min{dist(y, x) | x ∈ X}, and for two sets

D 1 ∪ D 2 defined by V (D 1 ∪ D 2 ) = V (D 1 ) ∪ V (D 2 ) and A(D 1 ∪ D 2 ) = A(D 1 ) ∪ A(D 2 ). If D is a set of digraphs,
X, Y ⊆ V (D), dist(X, Y ) = min{dist(x, y) | x ∈ X, y ∈ Y }.
An important notion in this chapter is the notion of levelling. An out-generator in D is a vertex u such that, for every x ∈ V (D), there exists an (u, x)-dipath in D. Analogously, an in-generator in D is a vertex u such that, for every x ∈ V (D), there exists an (x, u)-dipath in D. For simplicity, we call a vertex generator if it is an in-or out-generator. Observe that every vertex in a strong digraph is an in-and out-generator. Let D be a digraph. Let w, u be in-and out-generators of D, respectively. We remark that w and u are not necessarily different. For every nonnegative integer i, the ith out-level from u in D is the set

L u,+ i = {v ∈ V (D) | dist D (u, v) = i}, and the ith in-level from w in D is the set L w,- i = {v ∈ V (D) | dist D (v, w) = i}. Note that i L u,+ i = i L w,- i = V (D).
An out-Breadth-First-Search Tree or out-BFS-tree T + with root u, is a subdigraph of D spanning V (D) such that T + is an oriented tree and, for every

v ∈ V (D), dist T + (u, v) = dist D (u, v). Similarly, an in-Breadth-First-Search Tree or in-BFS-tree T -with root w, is a subdigraph of D spanning V (D) such that T -is an oriented tree and, for every v ∈ V (D), dist T -(v, w) = dist D (v, w).
It is well-known that if D has an out-generator, then there exists an out-BFS-tree rooted at this vertex. Likewise, if D has an in-generator, then there exists an in-BFS-tree rooted at this generator. Let T denote an in-or out-BFS-tree rooted at u. For any vertex x of D, there is a single (u, x)-dipath in T if T is an out-BFS-tree, and a single (x, u)-dipath in T if T is an in-BFS-tree. The ancestors or successors of x in T are naturally defined.

If y is an ancestor of x, we denote by T [y, x] the (y, x)-dipath in T . If y is a successor of x, we denote by T [x, y] the (x, y)-dipath in T . Lemma 58. Let D be a strong digraph and let T be an in-or out-BFS-tree in D. There is a level L such that χ(D[L]) ≥ χ(D)/2.

Proof. First, let us suppose, without loss of generality, that T is an out-BFS-tree in D. The proof when T is an in-BFS-tree is analogous.

Let D 1 and D 2 be the subdigraphs of D induced by the vertices of odd and even levels, respectively. Since there is no arc from L i to L j for every j ≥ i + 2, the strong components of D 1 and D 2 are contained in the levels. Hence, by Lemma 39,

χ(D 1 ) = max{ χ(D[L i ]) | i is odd} and χ(D 2 ) = max{ χ(D[L i ]) | i is even}. Moreover, note that V (D 1 ) ∪ V (D 2 ) = V (D) because D is strong. Therefore, χ(D) ≤ χ(D 1 ) + χ(D 2 ) ≤ 2 • max{ χ(D[L i ]) | i ∈ N}.
The following lemma is well-known.

Lemma 59. Let D 1 and D 2 be two digraphs. χ(D 1 ∪ D 2 ) ≤ χ(D 1 ) × χ(D 2 ). Proof. Let D = D 1 ∪D 2 . For i ∈ {1, 2}, let c i be a proper colouring of D i with {1, . . . , χ(D i )}. Extend c i to (V (D), A(D i ))

Oriented cycles

In this section we first prove that S-Forb(C(k, )) ∩ S has bounded chromatic number for every k, . We use the notion of levelling, but only for out-generators. For simplicity, we note L u i = L u,+ i . Let v be a vertex of D, we set lvl u (v) = dist D (u, v), hence v ∈ L u lvl(v) . In the following, the vertex u is always clear from the context. Therefore, for sake of clarity, we drop the superscript u.

We write BFS-tree for out-BFS-tree. For an ancestor y of x, we note y ≥ T x. For any two vertices v 1 and v 2 , the least common ancestor of v 1 and v 2 is the common ancestor x of v 1 and v 2 for which lvl(x) is maximal. (This is well-defined since u is an ancestor of all vertices.)

The following proposition directly follows from the definitions Proposition 60. Let D be a digraph having an out-generator u. If x and y are two vertices of D with lvl(y) > lvl(x), then every (x, y)-dipath has length at least lvl(y) -lvl(x).

Cycles with 2 blocks

Theorem 61. Let k and be positive integers such that k ≥ max{ , 3} and ≥ 2, and let

D be a digraph in S-Forb(C(k, )) ∩ S. Then, χ(D) ≤ (k + -2)(k + -3)(2 + 2)(k + + 1).
Proof. Since D is strongly connected, it has an out-generator u. Let T be a BFS-tree with root u. We define the following sets of arcs.

A 0 = {(x, y) ∈ A(D) | lvl(x) = lvl(y)}; A 1 = {(x, y) ∈ A(D) | 0 < | lvl(x) -lvl(y)| < k + -3}; A = {(x, y) ∈ A(D) | lvl(x) -lvl(y) ≥ k + -3}.
Since k + -3 > 0 and there is no arc (x, y) with lvl(y) > lvl(x) + 1, (A 0 , A 1 , A ) is a partition of A(D). Observe moreover that A(T ) ⊆ A 1 . We further partition A into two sets A 2 and A 3 , where

A 2 = {(x, y) ∈ A | y is an ancestor of x in T } and A 3 = A \ A 2 . Then (A 0 , A 1 , A 2 , A 3 ) is a partition of A(D). Let D j = (V (D), A j ) for all j ∈ {0, 1, 2, 3}. Claim 61.1. χ(D 0 ) ≤ k + -2. Subproof. Observe that D 0 is the disjoint union of the D[L i ] where L i = {v | dist D (u, v) = i}.
Therefore it suffices to prove that χ(D[L i ]) ≤ k + -2 for every non-negative integer i.

L 0 = {u} so the result holds trivially for i = 0.

Assume now i ≥ 1. Suppose for a contradiction χ(D[L i ]) ≥ k + -1. Since k ≥ 3, by Theorem 27, D[L i ] contains a copy Q of P + (k -1, - 1
). Let v 1 and v 2 be the initial and terminal vertices of Q, and let x be the least common ancestor of v 1 and v 2 . By definition, for j ∈ {1, 2}, there exists an (x, v j )-dipath P j in T . By definition of least common ancestor, V (P 1 ) ∩ V (P 2 ) = {x}, V (P j ) ∩ L i = {v j }, j = 1, 2, and both P 1 and P 2 have length at least 1. Consequently,

P 1 ∪ P 2 ∪ Q is a subdivision of C(k, ), a contradiction. ♦ As above |T [x i , y i-1 ]| ≥ k so lvl(y i ) -lvl(x i ) < k.
Symmetrically, let t 1 be the least common ancestor of y and z 1 and for 1 ≤ i ≤ -1, let t i+1 be the least common ancestor of t i and z i+1 . For 1 ≤ i ≤ , we have lvl(z i ) -lvl(t i ) < k. Moreover, by definition all x i and t j are ancestors of y, so they all are on T [u, y].

Let P y (resp. P z ) be a shortest dipath in D from y k (resp. z

) to T [u, y] ∪ Q 1 [y 1 , y k-1 ] ∪ Q 2 [z 1 , z -1 ]
. Note that P y and P z exist since D is strongly connected. Let y (resp. z ) be the terminal vertex of P y (resp. P z ). Let w y be the last vertex of T [x k , y k ] in P y (possibly, w y = y k .) Similarly, let w z be the last vertex of T [t , z ] in P z (possibly, w z = z .) Note that P y [w y , y ] is a shortest dipath from w y to y and P z [w z , z ] is a shortest dipath from w z to z .

If y = y j for 0

≤ j ≤ k -1, consider R = T [x k , w y ] P y [w y , y j ] as an (x k , y j )-dipath. By Proposition 60, R has length at least k because lvl(y j ) -lvl(x k ) ≥ lvl(y j ) -lvl(y k ) + 1 ≥ k. Therefore the union of R and T [x k , y] ∪ Q 1 [y, y j ] is a subdivision of C(k, k), a contradiction.
Similarly, we get a contradiction if z is in {z 1 , . . . , z -1 }. Consequently,

P y is disjoint from Q 1 [y, y k-1 ] and P z is disjoint from Q 2 [y, z -1 ].
Suppose P y and P z intersect in a vertex s. By the above statement, s / ∈ V (Q) \ {y k , z }. Therefore the union of Q 1 P y [y k , s] and Q 2 P z [z , s] is a subdivision of C(k, ), a contradiction. Henceforth P y and P z are disjoint.

Assume both y and z are in T [u, y]. By symmetry, we can assume y ≥ T z and then the union of Q 1 P y T [y , z ] and Q 2 P z form a subdivision of C(k, ). This is a contradiction.

Henceforth a vertex among y and z is not in T [u, y]. Let us assume that y is not in T [u, y] (the case z ∈ T [u, y] is similar), and so y = z i for some 1

≤ i ≤ -1. If lvl(y ) ≥ lvl(x k ) + k, then both T [x k , w y ] P y [w y , y ] and T [x k , y] Q 2 [y, z i ] have length at least k by Proposition 60, so their union is a subdivision of C(k, k), a contradiction. Hence lvl(x k ) ≥ lvl(z i ) -k + 1 ≥ lvl(z ) ≥ lvl(t ).
If z = y j for some j, then necessarily lvl(z ) ≥ lvl(x k )+k ≥ lvl(t )+k and both T [t , w z ] P z [w z , z ] and T [t , y] Q 1 [y, y j ] have length at least k, so their union is a subdivision of C(k, k), a contradiction.

Therefore

z ∈ T [u, y]. The union of T [t , z ] and T [t , w z ] P z [w z , z ] is not a subdivision of C(k, k) so by Proposition 60, lvl(z ) ≤ lvl(t ) + k -1 ≤ lvl(z ) + k -1 ≤ lvl(z -1 ).
If lvl(z ) ≤ lvl(x k ), then the union of Q 1 and

Q 2 P z T [z , y k ] is a subdivision of C(k, ), a contradiction. Hence lvl(z ) > lvl(x k ). Therefore lvl(y ) = lvl(z i ) ≤ lvl(x k ) + k -1 ≤ lvl(z ) + k -2 ≤ lvl(z ) + 2k -3, which implies that i = -1 that is y = z i = z -1 . Now the union of T [x 1 , y 1 ] Q 1 [y 1 , y k ] P y and T [x 1 , y] Q 2 [y, z -1 ] is a subdivision of C(k,

Cycles with four blocks in strong digraphs

Let Ĉ4 be the orientation of the 4-cycle with 4 blocks.

Theorem 62. Let D be a digraph in S-Forb( Ĉ4 ). If D admits an out-generator, then χ(D) ≤ 24.

Proof. The general idea is the same as in the proof of Theorem 61. Suppose that D admits an out-generator u and let T be an BFS-tree with root u We partition A(D) into three sets according to the levels of u.

A 0 = {(x, y) ∈ A(D) | lvl(x) = lvl(y)}; A 1 = {(x, y) ∈ A(D) | | lvl(x) -lvl(y)| = 1}; A 2 = {(x, y) ∈ A(D) | lvl(y) ≤ lvl(x) -2}. For i = 0, 1, 2, let D i = (V (D), A i ). Claim 62.1. χ(D 0 ) ≤ 3.
Subproof. Suppose for a contradiction that χ(D) ≥ 4. By Theorem 27, it contains a P -(1, 1) (y 1 , y, y 2 ), that is (y, y 1 ) and (y, y 2 ) are in A(D 0 ). Let x be the least common ancestor of y 1 and y 2 in T . The union of T [x, y 1 ], (y, y 1 ), (y, y 2 ), and T [x, y 2 ] is a subdivision of Ĉ4 , a contradiction.

♦ Claim 62.2. χ(D 1 ) ≤ 2.
Subproof. Since the arcs are between consecutive levels, then the colouring φ 1 defined by

φ 1 (x) = lvl(x) mod 2 is a proper 2-colouring of D 1 . ♦ Claim 62.3. χ(D 2 ) ≤ 4.
Subproof. Let x be a vertex of V (D). If y and z are distinct outneighbours of x in D 2 , then their least common ancestor w is either y or z, for otherwise the union of T [w, y], (x, y), (x, z), and T [w, z] is a subdivision of Ĉ4 . Consequently, there is an ordering y 1 , . . . , y p of N + D 2 (x) such that the y i appear in this order on T [u, x].

Let us prove that, in D 2 , N + (y i ) = ∅ for 2 ≤ i ≤ p -1. Suppose for a contradiction that y i has an outneighbour z in D 2 . Let t be the least common ancestor of y 1 and z. If t = z, then the union of (y i , z) T [z, y 1 ], (x, y 1 ), (x, y p ), and T [y i , y p ] is a subdivision of Ĉ4 ; if t = y 1 = z, then the union of (y i , z), (x, y 1 ) T [y 1 , z], (x, y p ), and

T [y i , y p ] is a subdivision of Ĉ4 . Otherwise, if t / ∈ {y 1 , z}, T [t, y 1 ], T [t, z], (x, y i ) (y i , z) and (x, y 1 ) is a subdivision of Ĉ4 .
Henceforth, in D 2 , every vertex has at most two outneighbours that are not sinks (vertices with outdegree 0). Let V 0 be the set of sinks in

D 2 . It is a stable set in D 2 . Furthermore ∆ + (D 2 -V 0 ) ≤ 2,

Spindles

Remember that B(k 1 , k 2 ; k 3 ) denotes the digraph formed by three internally disjoint paths between two vertices x, y, two (x, y)-directed paths, one of order k 1 , the other of order k 2 , and one (y, x)-directed path of order k 3 . In [START_REF] Cohen | Bispindles in strongly connected digraphs with large chromatic number[END_REF] we conjectured the following.

Conjecture 36. There is a function g : N 3 → N such that every strong digraph with chromatic number at least g(k 1 , k 2 , k 3 ) contains a subdivision of B(k 1 , k 2 ; k 3 ).

As an evidence, we proved this conjecture for k 2 = 1 and arbitrary k 1 and k 3 .

Theorem 37. For every k ≥ 1, there is a constant

γ k such that if D is a strong digraph with χ(D) > γ k , then D contains a subdivision of B(k, 1; k).
The goal of this section is to present the proof of this result.

Definitions and preliminaries

A (directed) graph G is k-degenerate if every subgraph H of G has a vertex of degree at most k.
The following statements are well-known.

Proposition 63 (Folklore). Every k-degenerate (directed) graph is (k + 1)-colourable.

Theorem 64 (Brooks [12]). Let G be a connected graph. Then χ(G) ≤ ∆(G) unless G is a complete graph or an odd cycle. The rotative tournament on 2k -1 vertices, denoted by R 2k-1 , is the tournament with vertex set {v 1 , . . . , v 2k-1 } in which v i dominates v j if and only if j -i modulo 2k -1 belongs to {1, 2, . . . , k -1}. Proposition 66. Every strong tournament of order 2k -1 contains a B(k, 1; 1)-subdivision.

Proof. Let T be a strong tournament of order 2k -1. By Camion's Theorem, it has a Hamiltonian directed cycle C = (v 1 , v 2 , . . . , v 2k-1 , v 1 ). If there exists an arc (v i , v j ) with j -i ≥ k (indices are modulo 2k -1), then the union of C[v i , v j ], (v i , v j ) and C[v j , v i ] is a B(k, 1; 1)-subdivision. Henceforth, we may assume that T = R 2k-1 . Then the union of

C[v 1 , v k-1 ] (v k-1 , v k+1 , v k+2 ), (v 1 , v k , v k+2 ), and C[v k+2 , v 1 ] is a B(k, 1; 1)-subdivision.
We will need the following lemmas: Lemma 67. Let σ = (u 1 , . . . , u p ) be a sequence of integers in [k], and let l be a positive integer. If p ≥ l k , then there exists a set L of l indices such that for any i, j ∈ L with i < j the following holds : u i = u j and u t > u i , for all i < t < j.

Proof. By induction on k. The result holds trivially when k = 1. Assume now that k > 1. Let L 1 be the elements of the sequence with value 1. If L 1 has at least l elements, we are done. If not, then there is a subsequence σ of l k -(l-1) l = l k-1 consecutive elements in {2, . . . , k -1}. Applying the induction hypothesis to σ yields the result.

Lemma 68. Let σ = (u 1 , . . . , u p ) be a sequence of integers in [k]. If p > k(m -1)
, then there exists a subsequence of m consecutive integers such that the last one is the largest.

Proof. By induction on k. The result holds trivially when k = 1. Let i be the smallest integer such that u t ≤ k -1 for all t ≥ i. If i > m, then u i-1 = k, and the subsequence of the i -1 first elements of σ is the desired sequence. If i ≤ m, apply the induction on σ = (u t ) i≤t≤p which is a sequence of more than (k -1)(m -1) integers in [k -1], to get the result.

B(k, 1; 1)

Before proving the main result for spindles, we present a proof of a weaker result in order to introduce some of the ideas. We will prove that every B(k, 1; 1)-subdivision-free strong digraph D has bounded chromatic number in the following way: We take a maximal nice collection C of directed cycles. We will prove that for every component S of C, the digraph D[S] has bounded chromatic number. Then we will prove that, since it contains no long directed cycle and it is strong, the digraph D C obtained from D by contracting each component of C into one vertex has bounded chromatic number. Those two results allow us to conclude by Lemma 65.

We will need the following lemma: Proof. By the contrapositive. We suppose that there exists such a dipath P and show that there is a B(k, 1; 1)-subdivision in D. By definition of S, there exists a dipath Q from C to C in S. By choosing C and C such that Q is as small as possible, then s(Q) = t(P ) and t(Q) = s(P ) (note that s(Q) and t(Q) can be the same vertex).

Since C has length at least 2k -2, either C[t(Q), s(P )] has length at least k -1 or C[s(P ), t(Q)] has length at least k.

• If C[t(Q), s(P )] has length at least k -1, then the union of Q C[t(Q), s(P )] P , C [s(Q), t(P )] and C [t(P ), s(Q)] is a B(k, 1 ; 1)
-subdivision between s(Q) and t(P ).

• If C[s(P ), t(Q)] has length at least k, then the union of C[s(P ), t(Q)], P C [t(P ), s(Q)] Q and C[t(Q), s(P )
] is a B(k, 1; 1)-subdivision between s(P ) and t(Q). Proof. First note that since D is strong, then so is D C . Suppose χ(D C ) ≥ 2k -2. By Bondy's Theorem [START_REF] Greenhill | Neighbour-distinguishing edge colourings of random regular graphs[END_REF], there exists a directed cycle C = (x 1 , . . . , x l , x 1 ) of length at least 2k -2 in D C . We derive a directed cycle C in D the following way: Suppose the vertex x i corresponds to a component S i of C: the arc (x i-1 , x i ) corresponds in D to an arc whose head is a vertex p i of S i , and the arc (x i , x i+1 ) corresponds to an arc whose tail is a vertex l i of S i . Let P i be a dipath from p i to l i in D[S i ]. Note that P i intersects each cycle of S i on a, possibly empty, subdipath of P i . Then C is the directed cycle obtained from C by replacing the vertices x i by the path P i .

C is a directed cycle of D of length at least 2k -2 because it is no shorter than C. Let C 1 be a cycle of C. By construction of C and D C , C and C 1 can intersect only along a subdipath of one P i . Suppose this dipath is more than just one vertex. Let x and y be the initial and terminal vertex, respectively, of this dipath. Then the union of C [x, y], C 1 [x, y] and C 1 [y, x] is a B(k, 1; 1)-subdivision, a contradiction.

So C is a directed cycle of length at least 2k -2, intersecting each cycle of C on at most one vertex, and which does not belong to C, for otherwise it would be reduced to one vertex in D C . This contradicts the fact that C is maximal.

We can finally prove Theorem 69.

Proof of Theorem 69. Let C be a maximal nice collection of directed cycles in D. Lemmas 71, 72 and 65 give the result.

B(k, 1; k)

We will now present a proof of Theorem 37.

We prove the result by the contrapositive. We consider a B(k, 1; k)-subdivision-free digraph D. We shall prove that χ(D)

≤ γ k = 8k 2 (4k 2 + 2)(2 • (4k) 4k + 1)(2 • (6k 2 ) 3k + 14k).
Our proof heavily uses the notion of k-suitable collection of directed cycles, which can be seen as a generalization of the notion of nice collection of directed cycles used to prove Theorem 69.

A collection C = {C 1 , C 2 , . . . , C N } of directed cycles is k-suitable if all cycles of C have length at least 8k, and for any two distinct directed cycles C i , C j ∈ C, the intersection C i ∩C j is either empty or a dipath of order at most k, denoted by P i,j . We denote by s i,j (resp. t i,j ) the initial (resp. terminal) vertex of P i,j .

The proof of Theorem 37 uses the same general idea as Theorem 69: take a maximal k-suitable collection of directed cycles C; show that the digraph D C obtained by contracting the components of C has bounded chromatic number, and that each component also has bounded chromatic number; conclude using Lemma 65. However, because the intersection of cycles in this collection are more complicated and because there might be arcs between directed cycles of the same component, bounding the chromatic number of the components is way more challenging. The next part is devoted to this.

k-suitable collections of directed cycles

Let φ be a colouring of a graph G. A subset of vertices or a subgraph S of G is rainbowcoloured by φ if all vertices of S have distinct colours.

Set α k = 2 • (6k 2 ) 3k + 14k. The first step of the proof is the following lemma.

Lemma 73. Let C be a k-suitable collection of directed cycles in a B(k, 1; k)-subdivision-free digraph. There exists a proper colouring φ of C with α k colours, such that, each subdipath of length 7k of each directed cycle of C is rainbow-coloured.

In order to prove this lemma, we need some definitions and preliminary results.

Lemma 74. Let C be a k-suitable collection of directed cycles in a B(k, 1; k)-subdivision-free digraph. Let C 1 , C 2 , C 3 be three pairwise-intersecting directed cycles of C, and let v be a vertex in

V (C 2 ) ∩ V (C 3 ) \ V (C 1 )
. Then exactly one of the following holds:

(i) C 2 [t 1,2 , v] and C 3 [t 1,3
, v] both have length less than 3k; Suppose for a contradiction that none of (i) and (ii) holds. By symmetry and the above inequalities, we may assume that both

(ii) C 2 [v,
C 2 [t 1,2 , v] and C 3 [v, s 1,3 ] have length more than 3k. But v / ∈ V (C 1 ), so v / ∈ V (P 1,3 ). Thus C 3 [v, t 1,3 ] has also length at least 3k as well. If there is a vertex in V (C 1 ) ∩ V (C 2 ) ∩ V (C 3 ), then C 3 [v, t 1,3
] would have length less than 2k (since it would be contained in P 2,3 ∪ P 1,3 and each of those paths has length less than k), a contradiction. Hence

V (C 1 ) ∩ V (C 2 ) ∩ V (C 3 ) = ∅.
C 3 [t 2,3 , s 1,3 ] C 1 [s 1,3 , s 1,2 ] is a B(k, 1; k)- subdivision, a contradiction.
Let C be a k-suitable collection of directed cycles. For every set of vertices or digraph S, we denote by C ∩ S the set of directed cycles of C that intersect S.

Let C 1 ∈ C. For each C j ∈ C ∩ C 1 such that C j = C 1 , let Q j be the subdipath of C j containing all the vertices that are at distance at most 3k from P 1,j in the cycle underlying C j . Then the dipaths C j [s(Q j ), s 1,j ] and

C j [t 1,j , t(Q j )] have length 3k. Set Q - j = C[s(Q j ), s 1,j [ and Q + j = C]t 1,j , t(Q j )]. Set I(C 1 ) = C 1 ∪ C j ∈C∩C 1 Q j , I + (C 1 ) = C j ∈C∩C 1 Q + j and I -(C 1 ) = C j ∈C∩C 1 Q - j .
Observe that Lemma 74 implies directly the following. (ii)

I -(C 1 ) ∩ C j = Q - j and I + (C 1 ) ∩ C j = Q + j , for all C j ∈ C ∩ C 1 .
Lemma 76. Let C be a k-suitable collection of directed cycles in a B(k, 1; k)-subdivision-free digraph D. Let C 1 ∈ C and let A be a connected component of C -I(C 1 ). Then all vertices of (C ∩ A) -A belong to a unique directed cycle C A in C.

Proof. Suppose it is not the case. Then there are two distinct directed cycles C 2 , C 3 of C ∩ A that intersect with C 1 . Observe that there is a sequence of distinct directed cycles

C 2 = C * 1 , C * 2 , . . . , C * q = C 3 of C ∩ A such that C * j ∩ C * j+1 = ∅ because A is a connected component of C -I(C 1 )
. Free to consider the first C * j = C 2 in this sequence such that V (C * j ) ⊆ A in place of C 3 , we may assume that all C * j , 2 ≤ j ≤ q -1, have all their vertices in A. In particular, there exists a (

C 3 , C 2 )-dipath Q A in D[A]. Let R 3 = C 1 [t 1,2 , t 1,3 ] Q + 3 .
Clearly, R 3 has length at least 3k. Let v be the last vertex in

Q 2 ∩ R 3 along Q 2 . (This vertex exists since t 1,2 ∈ Q 2 ∩ R 3 .) Since there is a (C 3 , C 2 )-dipath in D[A], by Corollary 75, C 3 [t(Q 3 ), s(Q A )] is in D[A]. Thus there exists a (t(Q 3 ), C 2 )-dipath R A in D[A]. Let w be its terminal vertex. By definition of A, w is in C 2 [t(Q 2 ), s(Q 2 )], therefore C 2 [w, v] has length at least 3k since it contains C 2 [s(Q 2 ), s 1,2 ]. Consequently, both C 2 [v, t(Q 2 )] and R 3 [v, t(Q 3 )] have length less than k for otherwise the union of C 2 [w, v], C 2 [v, w] and R 3 [v, t(Q 3 )] R A would be a B(k, 1; k)-subdivision. In particular, v = t(Q 2 ). This implies that s 2,3 ∈ V (Q 2 ∩R 3 ). Moreover, Q 2 [s 2,3 , t(Q 2 )] has length less than 2k because Q 2 [s 2,3 , v] is a subdipath of P 2,3 and so has length less than k. Therefore C 2 [t 1,2 , s 2,3 ] = Q 2 [t 1,2 , s 2,3 ] has length at least k because Q 2 has length at least 3k. It follows that the union of C 2 [s 2,3 , t 1,2 ], C 2 [t 1,2 , s 2,3 ] and R 3 [t 1,2 , s 2,3 ] is a B(k, 1; k)-subdivision, a contradiction.
Lemma 77. Let C be a k-suitable collection of directed cycles in a B(k, 1; k)-subdivision-free digraph. For any directed cycle C 1 ∈ C, the digraph I + (C 1 ) has no directed cycle.

Proof. Suppose for a contradiction that I + (C 1 ) contains a directed cycle C . Clearly, it must contain arcs from at least two Q + j . Assume that C contains several vertices of Q + j . Necessarily, there must be two vertices x, y of Q

+ j ∩ C such that no vertex of C ]x, y[ is in C j and y is before x in Q + j . Therefore C [x, y] Q + [y, x]
is also a directed cycle in I + (C 1 ). Free to consider this cycle, we may assume that C ∩ Q + j is a dipath. Doing so, for all j, we may assume that C ∩ Q + j is a dipath for every C j ∈ C ∩ C 1 . Without loss of generality, we may assume that there are directed cycles C 2 , . . . , C p such that

• C is in Q + 2 ∪ • • • ∪ Q + p ;
• for all 2 ≤ j ≤ p, C ∩ Q + j is a dipath P + j with initial vertex a j and terminal vertex b j ;

• the a j and the b j appear according to the following order around C : (a 2 , b p , a 3 , b 2 , . . . , a p , b p-1 , a 2 ) with possibly a j+1 = b j for some 1 ≤ j ≤ p where a p+1 = a 2 .

For 2 ≤ j ≤ p, set B j = C j [b j , a j ]. Note that B j has length at least 4k, because Q + 2 has length less than 3k.

Consider the closed directed walk

W = C p [a 2 , b p ] B p C p-1 [a p , b p-1 ] • • • B 3 C 2 [a 3 , b 2 ] B 2 .
W contains a directed cycle C W . Wihtout loss of generality, we may assume that this cycle is of the form

C W = B q [v, a q ] C q-1 [a q , b q-1 ] • • • B 3 C 2 [a 3 , b 2 ] B 2 [b 2 , v]
for some vertex v ∈ B 2 ∩ B q . (The case when W is a directed cycle corresponds to q = p + 1 and B 2 = B p+1 .)

Note that necessarily, q ≥ 4, for

B 3 does not intersect B 2 , for otherwise b 3 = b 2 since the intersection of C 2 and C 3 is a dipath. Observe that C W [b 2 , v] = C 2 [b 2 , v] or C W [v, a 4
] has length at least k. Indeed, if q = p + 1, then it follows from the fact that B 2 has length as least 4k; if 5 ≤ q ≤ p, then it comes from the fact that B 4 is a subdipath of C W [v, a r ]; if q = 4, then it follows from Lemma 74 applied to

C 3 , C 2 , C 4 in the role of C 1 , C 2 , C 3 respectively. In both cases, C W [b 2 , a 4 ] has length at least k. Furthermore, C W [a 4 , b 2 ] has length at least k because it contains B 3 . Therefore the union of C W [b 2 , a 4 ], C W [a 4 , b 2 ] and C [b 2 , a 4 ] = C 3 [b 3 , a 4 ] is a B(k, 1; k)-subdivision, a contradiction. Lemma 78. Let C be a k-suitable collection of directed cycles in a B(k, 1; k)-subdivision-free digraph.
Let φ be a partial colouring of a directed cycle C 1 ∈ C such that only a path of length at most 7k is coloured and this path is rainbow-coloured. Then φ can be extended into a colouring of I(C 1 ) using α k colours, such that every subdipath of length at most 7k of C 1 is rainbow-coloured and Q j is rainbow-coloured, for every C j ∈ C ∩ C 1 .

Proof. We can easily extend φ to C 1 using 14k colours (including the at most 7k already used colours) so that every subdipath of C 1 of length 7k is rainbow-coloured.

We shall now prove that there exists a colouring φ + of I + (C 1 ) with (6k 2 ) 3k (new) colours so that Q + j is rainbow-coloured for every C j ∈ C ∩ C 1 , and a colouring φ -of I -(C 1 ) with (6k 2 ) 3k (other new) colours so that Q - j is rainbow-coloured for every C j ∈ C ∩ C 1 . The union of the three colourings φ, φ + , and φ -is clearly the desired colouring of I(C 1 ). (Observe that a vertex of I(C 1 ) is coloured only once because C 1 , I + (C 1 ) and I -(C 1 ) are disjoint by Corollary 75.)

It remains to prove the existence of φ + and φ -. By symmetry, it suffices to prove the existence of φ + . To do so, we consider an auxiliary digraph D + 1 . For each C j ∈ C ∩ C 1 , let T + j be the transitive tournament whose Hamiltonian dipath is Suppose for a contradiction that χ(D + 1 ) ≤ (6k 2 ) 3k . By Theorem 26, D + 1 admits a dipath of length (6k 2 ) 3k . Replacing all fake arcs (u, v) in some A(T + j ), by Q + j [u, v] we obtain a directed walk P in I + (C 1 ) of length at least (6k 2 ) 3k . By Lemma 77, P is necessarily a dipath. Set P = (v 1 , . . . , v p ). We have p ≥ (6k 2 ) 3k .

Q + j . Let D + 1 = C j ∈C∩C 1 T + j . The arcs of A(T + j ) \ A(Q + j )
For 1 ≤ i ≤ p, let m i = min Dis(v i ). Lemma 67 applied to (m i ) 1≤i≤p yields a set L of 6k 2 indices such that for any i < j ∈ L, m i = m j and m k > m i , for all i < k < j. Let

l 1 < l 2 < • • • < l 6k 2 be the elements of L and let m = m l 1 = • • • = m l 6k 2 .
For 1 ≤ j ≤ 6k 2 -1, let M j = max l j ≤i<l j+1 Dis(v i ). By definition M j ≤ 3k. Applying Lemma 68 to (M j ) 1≤j≤6k 2 , we get a sequence of size 2k M j 0 +1 , . . . , M j 0 +2k such that M j 0 +2k is the greatest. For sake of simplicity, we set i = j 0 + i for 1 ≤ i ≤ 2k. Let f be the smallest index not smaller than 2k for which M 2k ∈ Dis(v f ).

Let j 1 be an index such that C j 1 [t 1,j 1 , v 1 ] has length m and set

P 1 = C j 1 [t 1,j 1 , v 1 ]. Let j 2 be an index such that C j 2 [t 1,j 2 , v k ] has length m and set P 2 = C j 2 [t 1,j 2 , v k ]. Let j 3 be an index such that C j 3 [t 1,j 3 , v f ] has length M 2k and set P 3 = C j 3 [v f , s 1,j 3 ] (some vertices of P 3 are not in I + (C 1 )).
Note that any internal vertex x of P 1 or P 2 has an integer in Dis(x) which is smaller than m and every internal vertex y of P 3 has an integer in Dis(y) which is greater than M 2k , or does not belong to I + (C 1 ). Hence, P 1 , P 2 and P 3 are internally disjoint from

P [v 1 , v f ].
We distinguish between the intersections of P 1 , P 2 and P 3 :

• Suppose P 3 does not intersect P 1 ∪ P 2 .

-Assume first that P 1 and P 2 are disjoint. If s(P 1 ) is in C 1 [t(P 3 ), s(P 2 )], then the union of

P 1 P [v 1 , v k ], P [v k , v f ] P 3 C 1 [
P 1 P [v 1 , v k ], P [v k , v f ] P 3 C 1 [t(P 3
), s(P 2 )], and P 2 is a B(k, 1; k)-subdivision, a contradiction.

-Assume now P 1 and P 2 intersect. Let u be the last vertex along P 2 on which they intersect. The union of

P 1 [u, v 1 ] P [v 1 , v k ], P [v k , v f ] P 3 C[t(P 3 ), s(P 1 )] P 1 [s(P 1 ), u], and P 2 [u, v k ] is a B(k, 1; k)-subdivision, a contradiction.
• Assume P 3 intersects P 1 ∩ P 2 . Let v be the first vertex along P 3 in P 1 ∩ P 2 and let u be the last vertex of P 1 ∩ P 2 along P 2 . The union of

P 1 [u, v 1 ] P [v 1 , v k ], P [v k , v f ] P 3 [v f , v] P 1 [v, u], and P 2 [u, v k ] is a B(k, 1; k)-subdivision, a contradiction.
• Assume now that P 3 intersects P 1 ∪ P 2 but not P 1 ∩ P 2 . Let v be the first vertex along P 3 in P 1 ∪ P 2 .

-If v ∈ P 2 , let u be the last vertex on P 2 ∩ P 3 along P 3 . Observe that P 3 [v, u] is also a subdipath of P 2 and therefore contains no vertex of P 1 . Furthermore, there is a dipath Q from u to v 1 in P 3 [u, t(P 3 )] ∪ C 1 ∪ P 1 . Hence, the union of

P [v k , v f ] P 3 [v f , v], Q P [v 1 , v k ], and P 2 [u, v k ] is a B(k, 1; k)-subdivision, a contradiction.
-If v ∈ P 1 , let u be the last vertex on P 1 ∩ P 3 along P 3 . Observe that P 3 [v, u] is also a subdipath of P 1 and therefore contains no vertex of P 2 . Furthermore, there is a dipath

Q from u to v k in P 3 [u, t(P 3 )] ∪ C 1 ∪ P 2 . The union of P [v k , v f ] P 3 [v f , u], P 1 [u, v 1 ] P [v 1 , v k ] and Q is a B(k, 1; k)-subdivision, a contradiction.

♦

Claim 78.1 shows the existence of φ + and completes the proof of Lemma 78.

We are now ready to prove Lemma 73. In fact, we prove the following stronger statement.

Lemma 79. If there exists a partial colouring φ such that one of the directed cycle C 1 has a path of length less than 7k which is rainbow-coloured, then we can extend this colouring to all D[C] using less than α k colours such that, on each directed cycle, every subdipath of length 7k is rainbow-coloured. Proof. We define a sort of Breadth-First-Search for S. Let C 0 be a directed cycle of S and set L 0 = {C 0 }. For every directed cycle C s of S ∩ C 0 , we put C s in level L 1 and say that C 0 is the father of C s . We build the levels L i inductively until all directed cycles of S are put in a level : L i+1 consists of every directed cycle C l not in j≤i L j such that there exists a directed cycle in L i intersecting C l . For every C l ∈ L i+1 , we choose one of the directed cycles in L i intersecting it to be its father. Henceforth every directed cycle in L i+1 has a unique father even though it might intersect many directed cycles of

L i . A directed cycle C is an ancestor of C if there is a sequence C = C 1 , . . . , C q = C such that C i is the father of C i+1 for all i ∈ [q -1].
For a vertex x in S, we say that x belongs to level L i if i is the smallest integer such that there exists a directed cycle in L i containing x. Observe that the vertices of each directed cycle C l of S belong to consecutive levels, that is there exists i such that

V (C l ) ⊆ L i ∪ L i+1 .
To bound the chromatic number of D[S], we partition its arc set in (A 0 , A 1 , A 2 ), where

• A 0 is the set of arcs of D[S] whose ends belong to the same level, and

• A 1 is the set of arcs of D[S]
whose ends belong to different levels i and j with |i-j| < k.

• A 2 is the set of arcs of D[S] whose ends belong to different levels i and j with |i-j| ≥ k.

For i ∈ {0, 1, 2}, let D i be the spanning subdigraph of D[S] with arc set A i . We shall now bound the chromatic numbers of D 0 , D 1 and D 2 .

Claim 80.1. χ(D 1 ) ≤ k.

Subproof. Let φ 1 be the colouring that assigns to all vertices of level L i the colour i modulo k, it is easy to see that φ 1 is a proper colouring of D 1 .

♦

Let C l be a directed cycle of L i , i ≥ 1 and C l its father. Let p + l and r + l be the vertices such that C l [t l,l , p + l ] and C l [p + l , r + l ] have length k. Let p - l and r - l be the vertices such that

C l [p - l , s l,l ] and C l [r - l , p - l ] have length k. Let R - l be the set of vertices of C l ]r - l , s l,l [, P - l the set of vertices of C l ]p - l , s l,l [, R + l the set of vertices of C l ]t l,l , r l [, P + l the set of vertices of C l ]t l,l , p +
l [, and finally let R l be the set of vertices belonging to

L i in C l \ {R + l ∪ R - l }. Claim 80.2. Let x be a vertex in L i with i ≥ 1.
Let C l and C m be two directed cycles of L i containing x. Then either x ∈ P + l and x ∈ P + m , or x ∈ P - l and x ∈ P - m . Subproof. Suppose for a contradiction that x ∈ P + l and x ∈ P + m . Let C l and C m be the fathers of C l and C m respectively (they can be the same directed cycle). By definition of the L j 's, there exists a dipath P from t l,l to s m,m only going through C l , C s and their ancestors. In particular P is disjoint from C l -C l and C s -C s . Observe that C l [s l,l , t l,m ] has length at most 3k because it is contained in the union of P l,l , P l,m , and C l [t l,l , x] which has length at most k because x ∈ P + l . Hence C l [t l,m , s l,l ] has length at least k. Moreover C m [s m,m , t l,m ] contains C m [t m,m , x] which has length at least k because x / ∈ P + m . Thus the union of C l [t l,m , s l,l ] P , C m [t l,m , s m,m ], and C m [s m,m , t l,m ] is a B(k, 1; k)-subdivision, a contradiction. The case where x ∈ P - l and x ∈ P - m is symmetrical and the case where x does not belong to P - l ∪ P + l ∪ P - m ∪ P + m is identical. ♦ Claim 80.2 implies that each level L i may be partitioned into sets X + i , X - i and X i , where

X + i (resp. X - i ) is the set of vertices x of L i such that every x ∈ R + l (resp. x ∈ R - l ) for every directed cycle C l of L i containing x and X i is set of vertices in L i but not in X + i ∪ X - i . Set X + = V (C 0 ) ∪ i≥1 X + i , X -= i≥1 X - i and X = i≥1 X i . Clearly (X + , X -, X ) is a partition of V (D[S]). Claim 80.3. χ(D 2 ) ≤ 4k 2 + 2. Subproof. Since X + ∪X -∪X = V (D 2 ), we have χ(D 2 ) ≤ χ(D 2 [X + ∪X ])+χ(D 2 [X -∪X ]). We shall prove that χ(D 2 [X + ∪ X ]) ≤ 2k 2 + 1 and χ(D 2 [X -∪ X ]) ≤ 2k 2 + 1, which imply the result.
Let x and y be two adjacent vertices of D 2 [X + ∪ X ]. Let L i be the level of x and L j be the level of y. Without loss of generality, we may assume that j ≥ i + k. Let C x be the directed cycle of L i such that x ∈ C x and C y the directed cycle of L j such that y ∈ C y . By considering ancestors of C x and C y , there is a shortest sequence of directed cycles C 1 , . . . , C p such that C 1 = C x and C p = C y and for all l ∈ [p -1], either C l is the father of C l+1 or C l+1 is the father of C l . In particular C p-1 is the father of C p . Since y ∈ X + ∪ X , then C[y, t p-1,p ] has length at least k.

Assume that (x, y) is an arc. In p-1 l=1 C l , there is a dipath P from t p-1,p to x. This dipath has length at least k -1 because it must go through all levels L i , i ≤ i ≤ j -1 because the vertices of any directed cycle of S are in two consecutive levels. Hence the union of P (x, y), C p [t p-1,p , y], and C p [y, t p-1,p ] is a B(k, 1; k)-subdivision, a contradiction. Hence (y, x) is an arc.

Suppose that C x is not an ancestor of C y . In particular, C 2 is the father of C 1 and there exists a path P from t 1,2 to y in p-1 l=2 C l of length at least k -1 and internally disjoint from

C 1 . Hence the union of P yx, C 1 [x, t 1,2 ] and C 1 [t 1,2 , x] is a subdivsion of B(k, 1; k). Hence C x is an ancestor of C y .
In particular, C l is the father of C l+1 for all l ∈ [p -1]. Let P be the dipath from t 1,2 to y in p l=2 C l . It has length at least k -1 because it must go through all levels L i , 1

≤ i ≤ p -1. C 1 [x, t 1,2
] has length less than k, for otherwise the union of P yx, C 1 [x, t 1,2 ] and C 1 [t 1,2 , x] would be a subdivision of B(k, 1; k).

To summarize, the only arcs of

D 2 [X + ∪ X ] are arcs (y, x) such that C x is an ancestor of C y and C 1 [x, t 1,2 ] has length less than k with C 1 . . . C p the sequence of directed cycles such that C 1 = C x to C p = C y and C l is the father of C l+1 for all l ∈ [p -1]. In particular, D 2 [X + ∪ X ] is acyclic.
Let y be a vertex of D 2 [X + ∪ X ]. Let L p be the level of y and let C 0 , . . . , C p be the sequence of directed cycles such that C l-1 is the father of C l for all l ∈ [p]. For 0 ≤ l ≤ p -1, let R l be the subdipath of C l of length k -1 terminating at t l,l+1 . By the above property, the outneighbbours of y are in p-1 l=0 R l . Suppose for a contradiction that y has outdegree at least 2k 2 + 1. Then there are 2k + 1 distinct indices l 1 < • • • < l 2k+1 such that for all i ∈ [2k + 1], C l i contains an outneighbour X i of y. Let P be the shortest dipath from x 1 to y in p l=l 1 C l . This dipath intersects all directed cycles C l l 1 ≤ l ≤ p. Let z be the first vertex of P along C l k+1 [x k+1 , t l k+1 ,l k+2 ]. Vertex z belongs to either L l k+1 -1 or L l k+1 . Thus P [x 1 , z] and P [z, y] have length at least k -1 and k respectively since P goes through all levels from L l 1 to L p . Hence the union of (y, x 1 ) P [x 1 , z], (y, x k+1 ) C l k+1 [x k+1 , z], and

P [z, y] is a B(k, 1; k)-subdivision, a contradiction. Therefore D 2 [X + ∪ X ] has maximum outdegree at most 2k 2 . D 2 [X + ∪ X ]
is acyclic and has maximum outdegree at most 2k 2 . Therefore it is 2k 2degenerate, and so χ(

D 2 [X + ∪ X ]) ≤ 2k 2 + 1. By symmetry, we have χ(D 2 [X -∪ X ]) ≤ 2k 2 + 1. ♦
To bound χ(D 0 ) we partition the vertex set according to a colouring φ of S given by Lemma 73. For every colour c ∈ [α k ], let X + (c) be the set X + ∩ φ -1 (c) of vertices of X + coloured c, and X -(c) the set X -∩ φ -1 (c) of vertices of X -coloured c. Similarly, let

X + i (c) = X + i ∩ φ -1 (c) and X - i (c) = X - i ∩ φ -1 (c).
We denote by D + 0 (c) (resp. D - 0 (c), D 0 (c)) the subdigraph of D 0 induced by the vertices of X + (c), (resp. X -(c), X (c)). vertex y of P 3 either has an integer in Len(y) which is greater than M 2k , or does not belong to X + (c). Hence, P 1 , P 2 and P 3 are disjoint from

P [v 1 , v f ].
We distinguish cases according to the intersection between P 1 , P 2 and P 3 : Let P 4 be a shortest dipath in ∪ i<i 0 L i from t j 1 ,j 1 to t j 2 ,j 2 and P 5 be a shortest dipath in ∪ i<i 0 L i from s j 3 ,j 3 to t j 2 ,j 2

• Suppose P 3 does not intersect P 1 ∪ P 2 .

-Suppose P 1 and P 2 are disjoint. Let v be the last vertex of P 4 in P 4 ∩P 5 . The union of

P 5 [v, t j 1 ,j 1 ] P 1 P [v 1 , v k ], P 4 [v, t j 2 ,j 2 ] P 2 , and P [v k , v f ] P 3 P 5 [s j 3 ,j 3 , v] is a B(k, 1; k)-subdivision, a contradiction.
-Assume now P 1 and P 2 intersect. Let u be the last vertex along P 2 on which they intersect. The union of

P 1 [u, v 1 ] P [v 1 , v k ], P 2 [u, v k ],
and

P [v k , v f ] P 3 P 5 P 1 [t j 1 ,j 1 , u] is a B(k, 1; k)-subdivision, a contradiction.
• Assume P 3 intersects P 1 ∩ P 2 . Let v be the first vertex along P 3 in P 1 ∩ P 2 and let u be the last vertex of P 1 ∩ P 2 along P 2 . The union of

P 1 [u, v 1 ] P [v 1 , v k ], P 2 [u, v k ],
and

P [v k , v f ] P 3 [v f , v] P 1 [v, u] is a B(k, 1; k)-subdivision, a contradiction.
• Assume now that P 3 intersects P 1 ∪ P 2 but not P 1 ∩ P 2 . Let v be the first vertex along

P 3 in P 1 ∪ P 2 .
-If v ∈ P 2 , let u be the last vertex of P 2 ∩ P 3 along P 3 . Observe that P 3 [v, u] is also a subdipath of P 2 and therefore contains no vertex of P 1 . Hence, the union of P 3 [u, s j 3 ,j 3 ]

P 5 P 1 P [v 1 , v k ], P 2 [u, v k ],
and

P [v k , v f ] P 3 [v f , v] is a B(k, 1; k)-subdivision, a contradiction.
-If v ∈ P 1 , let u be the last vertex of P 1 ∩ P 3 along P 3 . Observe that P 3 [v, u] is also a subdipath of P 1 and therefore contains no vertex of P 2 . Hence the union of

P 1 [u, v 1 ] P [v 1 , v k ], P 3 [u, s j 3 ,j 3 ] P 6 P 2 , and P [v k , v f ] P 3 [v f , u], is a B(k, 1; k)-subdivision, a contradiction.

♦

Similarly to Claim 80.5, one proves that

χ(D - 0 (c)) ≤ (4k) 4k for every c ∈ [α k ]. Hence, χ(D 0 (c)) ≤ χ(D + 0 (c)) + χ(D - 0 (c)) + χ(D 0 (c)) ≤ 2 • (4k) 4k + 1. Thus χ(D 0 ) ≤ (2 • (4k) 4k + 1)α k .
Via Lemma 59, this equation and Claims 80.1 and 80.3 yield

χ(D) ≤ χ(D 0 ) × χ(D 1 ) × χ(D 2 ) ≤ k(4k 2 + 2)(2 • (4k) 4k + 1)α k = β k .
By Lemma 39, we may assume that D is strong. Let u be a vertex in D and T u an out-BFS-tree with root u. By Lemma 58, there is a level

L u such that χ(D[L u ]) ≥ 2c -1. By Lemma 39, there is a strong component C of D[L u ] such that χ(C) = χ(D[L u ]) ≥ 2c -1. Since D is strong, there is a shortest (v, u)-dipath P in D such that V (P ) ∩ V (C) = {v}.
Let T v be an in-BFS-tree in C rooted at v. By Lemma 58, there is a level

L v of T v such that χ(D[L v ]) ≥ c. By definition of c, D[L v ]
contains a subdivision S of F -a. Let x and y be the vertices in S corresponding to the vertices x and y of F . Now T v [x , v] ∪ P ∪ T u [u, y ] is a directed (x , y )-walk with no internal vertex in L v . Hence it contains an (x , y )-dipath Q whose internal vertices are not in S. Therefore, S ∪ Q is a subdivision of F in D.

We can now prove Theorem 40

Proof of Theorem 40. We prove the result by induction on m. If m = 0, then F is an empty digraph and the result is trivial. If m > 0, then consider an arc a ∈ A(F ). By the induction hypothesis on F -a, we obtain that any digraph D with χ(D) ≥ 4 m-1 (n -1) + 1 contains a subdivision of F -a. By Lemma 81, we obtain that any digraph with χ(D) ≥ 4(4 m-1 (n -1) + 1) -3 contains a subdivision of F , which proves the result.

Chapter 3

Digraphs with large minimum outdegree

In 1985, Mader made the following beautiful conjecture: Conjecture 9 (Mader [START_REF] Mader | Degree and local connectivity in digraphs[END_REF]). For every k ≥ 1, there exists an integer f (k) such that every digraph with minimum outdegree at least f (k) contains a subdivision of T T k , the transitive tournament on k vertices.

The conjecture remains open for k ≥ 5 which shows our lack of understanding of what it means for a digraph to have large minimum degree. In this chapter we present some work on weakenings of the conjecture. First we present some results obtained in [START_REF] Aboulker | Subdivisions in digraphs of large out-degree or large dichromatic number[END_REF] with Pierre Aboulker, Nathann Cohen, Frédéric Havet, Phablo Moura and Stéphan Thomassé concerning subdivisions of digraphs which are simpler than the transitive tournaments. Then we present the proof of Conjecture 15 concerning immersions of transitive tournaments obtained in [START_REF] Lochet | Immersion of transitive tournaments in digraphs with large minimum outdegree[END_REF].

Subdivisions in digraphs with large minimum outdegree 3.1.1 Subdivisions of oriented paths

The first case to consider when one tries to weaken Mader's conjecture is probably the case of oriented paths.

Theorem 19. Let (k 1 , k 2 , . . . , k ) be a sequence of positive integers, and let D be a digraph with δ

+ (D) ≥ i=1 k i . For every v ∈ V (D), D contains a path P + (k 1 , k 2 , . . . , k ) with initial vertex v such that k i ≥ k i if i is odd, and k i = k i otherwise.
Proof. By induction on . If = 1, then the result holds trivially. Assume now ≥ 2, and suppose that, for every path P + (x 1 , x 2 , . . . , x t ) with t < and every digraph G with δ + (G) ≥

Let v be a vertex of D. Since δ + (D) ≥ i=1 k i , there exists a (v, u)-dipath P v,u in D of length exactly k 1 , for some vertex u ∈ V (D). Let D = D -(P v,u -u), let C be the connected component of D containing u, and let H be a sink strong component of C (i.e. a strong component without arcs leaving it) that is reachable by a directed path in C starting at u. We denote by P u,x a (u, x)-dipath in C such that V (P u,x ) ∩ V (H) = {x}.

Note that no vertex of H dominates a vertex in V (P u,x ) \ {x} since H is a sink strong component. Thus, δ + (H) ≥ δ + (D)-k 1 ≥ k 2 . As a consequence, H contains a directed cycle of length at least k 2 . Using this and the fact that H is strongly connected, we conclude that there exists a dipath P y,x in H from a vertex y ∈ V (H) \ {x} to x of length exactly k 2 . Let G = H -(P y,x -y). One may easily verify that δ

+ (G) is at least δ + (D) -k 1 -k 2 ≥ i=3 k i . Let Q v,y = P v,u P u,x P y,x . Note that Q v,y is a path P + (k 1 , k 2 ) starting at v with k 1 ≥ k 1 .
Therefore, the result follows immediately if = 2. Suppose now that ≥ 3. By the induction hypothesis, G contains a path W y := P + (k 3 , . . . , k ) with initial vertex y such that k i ≥ k i if i is odd, and

k i = k i otherwise. Therefore, Q v,y W y is the desired path P + (k 1 , k 2 , . . . , k ) with initial vertex v.
The result is tight, as i=1 k i = |V (P + (k 1 , k 2 , . . . , k ))| -1, and the complete digraph K k on k vertices has minimum outdegree k -1 and contains no path on more than k vertices.

Subdivisions of in-arborescences

The aim of this subsection is to prove that in-arborescences are contained in digraphs with large minimum outdegree as subdivision. We need the following result about flows. Proof. Suppose to the contrary that there do not exist |S| vertex-disjoint (S, T )-dipaths in D. By Theorem 2, there exists a set of vertices X ⊆ V (D) with cardinality |X| < |S| which is an (S, T )-vertex-cut. Let C be the set of vertices in D -X that are reachable in D by a dipath with initial vertex in S \ X. Set k = |X ∩ S|. Observe that k < |S|.

Let us count the number a(C, X) of arcs with tail in C and head in X. Since the vertices in S have indegree 0 and every vertex in C has outdegree at least ∆ -(D),

a(C, X) ≥ |C| • ∆ -(D) -[|C| -(|S| -k)] • ∆ -(D) = (|S| -k) • ∆ -(D).
Moreover, a(C, X) is at most the number of arcs with head in X which is at most

(|X| -k) • ∆ -(D), because the vertices in S ∩ X have indegree 0. Hence (|S| -k) • ∆ -(D) ≤ a(C, X) ≤ (|X| -k) • ∆ -(D). This is a contradiction to |X| < |S|.
Let k and be positive integers. The -in-arborescence of depth k is denoted by B(k, ). The number of vertices of B(k, ) is denoted by b(k, ); so b(k,

) = k i=0 i = k+1 -1 -1 .
Observe that every in-arborescence T is a subdigraph of B(k, ) with = ∆ -(T ) and k the maximum length of a dipath in T . Therefore proving the result for B(k, ) for all k and implies the result for in-arborescences. We define a recursive function f : N → N as follows. For all positive integers k and such that ≥ 2, f (1, ) = and, for k ≥ 2, we define

f (k, ) = t(k, ) • ( -1) • k + t(k, ), where t(k, ) := f (k -1, b(k -1, ) • ( -1) + 1) • b(k -1, ).
If D is a family of digraphs, a packing of elements of D is the disjoint union of copies of elements of D.

Theorem 83. Let k ≥ 1 and ≥ 2 be integers, and let D be a digraph with δ + (D) ≥ f (k, ). Then D contains a subdivision of B(k, ), the -in-arborescence of depth k.

Proof. We prove the result by induction on k and .

If k = 1, then δ + (D) ≥ . Thus, ∆ -(D) • |V (D)| ≥ v∈V (D) d -(v) = v∈V (D) d + (v) ≥ • |V (D)|.
Hence there is a vertex with indegree at least in D and, consequently, the result follows when k = 1. Assume now k ≥ 2, and suppose that, for every positive integers k < k and , and every digraph H with δ + (H) ≥ f (k , ), H contains a subdivision of the -branching in-arborescence of depth k .

Let F be a packing of -branching in-arborescences subdigraphs of any non-zero depth in D that covers the maximum number of vertices.

We denote by U ⊆ V (D) the set of vertices not covered by F, that is, U = V (D) \ A∈F V (A). Let r A denote the root of the in-arborescence A, for each A ∈ F, and let R = {r A ∈ V (D) : A ∈ F} be the set of the roots of the arborescences in F.

We now construct the digraph H with vertex set R such that there exists an arc (r A , r B ) in H if and only if r A dominates some vertex of V (B) in D. Subproof. Let p = b(k -1, ) • ( -1) + 1. By the induction hypothesis, H contains a subdivision T of B(k -1, p). Let R be the set of branching vertices of T , that is, R = {r ∈ T : d - T (r) = p}. We assume that each in-arborescence of F has at most b(k -1, ) vertices, as any larger arborescence would yield the theorem. Thus, for each r ∈ R , there exists a vertex h r in the in-arborescence rooted at r such that h r is dominated in D by vertices of V (T ). Similarly, for each r ∈ V (T ) with indegree 1, there exists a vertex h r in the in-arborescence rooted at r such that h r is dominated in D by a vertex of V (T ). Using these remarks, we next define a procedure to obtain a subdigraph of T that is a subdivision of B(k -1, ).

For each r ∈ R , we remove from T all arcs with head r but exactly arcs from vertices in V (T ) that dominate h r in D. We denote by T the component of the subdigraph of T obtained by applying the above-described procedure and that contains the root of T . One may easily verify that T is a subdivision of B(k -1, ). Let P r be the path from h r to r in the in-arborescence corresponding to r, for every r ∈ V (T ) such that either r ∈ R or r has indegree 1.

Let Q be the in-arborescence obtained from T in the following way. For each r ∈ V (T ) such that either r ∈ R or r has indegree 1, we add h r to T , and we add an arc from every inneighbour of r in T to h r . Additionally, we remove all arcs with head r in T , and link h r to r by using the dipath P r . Finally, for each r ∈ V (T ) that is a leaf, we replace r by its corresponding in-arborescence belonging to F.

By this construction, we have that Q is a subdigraph of D such that every internal vertex has either indegree or 1. Furthermore, it has depth at least k. Therefore, by possibly pruning some levels of Q, we obtain a subdivision of B(k, ).

♦

Suppose now δ + (H) < t(k, )/b(k-1, ). Observe that, for every v ∈ R such that d + H (v) < t(k, )/b(k -1, ), we have, in the digraph D, that d + U (v) ≥ t(k, ) • ( -1) • k since δ + (D) ≥ t(k, ) • ( -1) • k + t(k, ). We define X = {v ∈ R : d + U (v) ≥ t(k, ) • ( -1) • k}. Let D be the digraph obtained from D[U ∪ X]
by removing all arcs with head in X. From D , we construct a digraph G by replacing every vertex v ∈ X by t(k, ) new vertices v 1 , . . . , v t(k, ) , and adding, for each i ∈ [t(k, )], at least ( -1)

• k arcs from v i to N + D (v) in such a way that d - D (u) = d - G (u), for all u ∈ N + D (v).
In other words, we "redistribute" the outneighbours of v in D among its t(k, ) copies in G so that every copy has outdegree at least ( -1) • k, and the indegrees of vertices belonging to U are not changed. Let S ⊆ V (G) be the set of vertices that replaced those of X, that is, S = v∈X {v 1 , . . . , v t(k, ) }. Let T be the set of vertices in U that have large outdegree outside U in the digraph D, more formally,

T = {v ∈ U : d + V (D)\U (v) ≥ t(k, ) + 1}. For every i ∈ [k -1], let F i = {A ∈ F : A has depth exactly i}. Note that {F i } i∈[k-1]
forms a partition of the packing F. Additionally, observe that, due to the maximality of F, every vertex in U is dominated by at most -1 vertices belonging to U , and by at most -1 roots of in-arborescences in F i , for each i ∈ [k -1]. Thus, the indegree in G of every vertex belonging to U is at most ( -1) + ( -1)

• (k -1) = ( -1) • k. Therefore, we have ∆ -(G) ≤ ( -1) • k. Moreover, since δ + (D) ≥ t(k, ) • ( -1) • k + t(k, ), we have d + G (v) ≥ t(k, ) • ( -1) • k for every v ∈ U \ T . Hence, d + G (v) ≥ ( -1)
• k, for every v ∈ V (G) \ T . By Lemma 82, there exists a set P of |S| vertex-disjoint paths from S to T in G.

Note that, in D, every vertex belonging to T has at least t(k, ) + 1 outneighbours in V (D) \ U . Therefore one can greedily extend each path of P with an outneighbour of its terminal vertex in V (D) \ U in order to obtain a set P of |S| vertex-disjoint paths from S to V (D) \ U such that for any v ∈ X all the paths in P with initial vertex v have distinct terminal vertices (and different from v).

We now construct the digraph M on the vertex set R where there exists an arc from v = r A to r B in M whenever either r A dominates some vertex of V (B) in D, or there is a dipath from some v i to V (B) in P .

Since, for each v ∈ X, all vertices in {v i } i∈[t(k, )] are the initial vertices of vertex-disjoint dipaths in P , we obtain δ + (M ) ≥ t(k, )/b(k-1, ). Therefore, the result follows by Claim 83.1 with M playing the role of H. initial vertex c 3 1 and c 4 1 , respectively, and length i 3 and i 4 = min{k 2 , i 3 }. By the maximality of , if

i 4 ≥ k 2 then i 3 < k 1 -1 since otherwise the union of A ∪ B 2 , C 3 , C 3 , (b 2 k 2 -1 , c 3 1 ) and (b 2 k 2 -1 , c 4 1
) would contain an ( + k 1 -1, k 1 , k 2 )-fork, contradicting the maximality of . For sake of contradiction, assume that both c 3 i 3 and

c 4 i 4 have no outneighbour in (A\{a })∪ C 1 ∪C 2 . Because |V (B 1 )∪V (B 2 )∪V (C 3 )∪V (C 4 )∪{a }| = k 1 +k 2 +i 3 +i 4 -1 < 2(k 1 +k 2 )-2 (since i 3 + i 4 < k 1 + k 2 -1) and δ + (D) ≥ 2(k 1 + k 2 -1) + 1, then there exist distinct vertices c 3 i 3 +1 , c 4 i 4 +1 ∈ V (D -(F ∪ C 1 ∪ C 2 ∪ C 3 ∪ C 4 )) (if i 3 ≥ k 2 , we only define c i 3 +1 ) such that (c 3 i 3 , c 3 i 3 +1 ), (c 4 i 4 , c 4 i 4 +1
) ∈ A(D). This contradicts the maximality of i 3 . So one of

c 3 i 3 , c 4 i 4 has an outneighbour in (A \ {a }) ∪ C 1 ∪ C 2 .
We assume that it is c 3 i 3 ; the case when it is c 4 i 4 is similar. If c 3 i 3 has an outneighbour a q ∈ A \ {a } (for some q < ), then the union of either the dipaths (a , B 1 , C 1 , a j , . . . , a q ) and (a , B 2 , C 3 , a q ) (if q ≥ j), or the dipaths (a

, B 1 , C 1 , a j ) and (a , B 2 , C 3 , a q , • • • , a j ) (if q < j), is a subdivision of C(k 1 , k 2 ). If c 3 i 3 has an outneighbour c 1 h ∈ V (C 1 ) for some 1 ≤ h ≤ i 1 , then the union of the dipaths (a , B 1 , c 1 1 , • • • , c 1 h ) and (a , B 2 , C 3 , c 1 h ) is a subdivision of C(k 1 , k 2 ). Similarly, we find a subdivision of C(k 1 , k 2 ) if c 3 i 3 has an outneighbour in C 2 .

Three dipaths between two vertices

A slight adaptation of the proof of Theorem 84 leads to a stronger result. Let k 1 , k 2 , k 3 be positive integers. Remember that B(k 1 , k 2 ; k 3 ) is the digraph formed by three internally disjoint paths between two vertices x, y, two (x, y)-dipaths, one of size k 1 , the other of size k 2 , and one (y, x)-dipath of size k 3 . We denote by B uv (k 1 , k 2 ; k 3 ) a subdivision of B(k 1 , k 2 ; k 3 ) where the vertex u plays the role of x and the vertex v plays the role of y.

Theorem 85. Let k 1 , k 2 , k 3 be positive integers with k 1 ≥ k 2 . Let D be a digraph with δ + (D) ≥ 3k 1 + 2k 2 + k 3 -5. Then D contains B(k 1 , k 2 ; k 3 ) as a subdivision.

Proof. Let be an integer. An ( , k 3 ; k 1 , k 2 )-fork is a digraph obtained from the union of four disjoint directed paths P = (p 1 , . . . , p

), A = (a 1 , • • • , a k 3 -1 ), B 1 = (b 1 1 , • • • , b 1 k 1 -1 ) and B 2 = (b 2 1 , • • • , b 2 k 2 -1
) by adding the arcs (p , a 1 ), (a

k 3 -1 , b 1 1 ) and (a k 3 -1 , b 2 1 ). Since a (1, k 3 ; k 1 , k 2 )-fork has k 1 + k 2 + k 3 -2 vertices and δ + (D) ≥ k 1 + k 2 + k 3 -2, then D contains a (1, k 3 ; k 1 , k 2 )
-fork as a subdigraph. So, let ≥ 1 be the largest integer such that D contains an ( , k 3 ; k 1 , k 2 )-fork as a subdigraph. Let F be such a fork. For convenience, we denote its subpaths and vertices by their labels in the above definition.

If there exist i, j ∈ [ ], with i ≤ j, such that

p i ∈ N + (b 1 k 1 -1 ) and p j ∈ N + (b 2 k 2 -1 ) or p i ∈ N + (b 2 k 2 -1 ) and p j ∈ N + (b 1 k 1 -1 ), then F contains a B a k 3 -1 p j (k 1 , k 2 ; k 3 ). So, let us assume that b 1 k 1 -1 has no outneighbour in P (the case where b 2 k 2 -1 has no outneighbour in P is similar). Since |A∪B 1 ∪B 2 | = k 1 +k 2 +k 3 -3 and δ + (D) ≥ k 1 +k 2 +k 3 -1, b 1 k 1 -1 has two distinct outneighbours, say c 1 1 and c 2 1
, not in F . Let i 1 ≥ 1 be the largest integer such that there exist two disjoint directed paths C 1 = (c 1 1 , . . . c 1 i 1 ) and C 2 = (c 2 1 , . . . , c 2 i 2 ) in D-F with initial vertex c 1 1 and c 2 1 respectively and length i 1 and

i 2 = min{k 2 -1, i 1 }. If i 1 ≥ k 1 -1, then i 2 ≥ k 2 -1,
and thus P ∪A∪B 1 ∪C 1 ∪C 2 would 56 contain a fork that contradicts the maximality of . Hence we may assume that i

1 ≤ k 1 -2 (and in particular |V (C 1 ) ∪ V (C 2 )| ≤ k 1 + k 2 -3).
For sake of contradiction, assume that both c 1 i 1 and c 2 i 2 have no outneighbour in P . Since

|V (A) ∪ V (B 1 ) ∪ V (B 2 ) ∪ V (C 1 ) ∪ V (C 2 )| ≤ 2k 1 + 2k 2 + k 3 -6 < δ + (D) -2, then there exist c 1 i 1 +1 , c 2 i 2 +1 ∈ V (D -(F ∪ C 1 ∪ C 2 )) such that (c 1 i 1 , c 1 i 1 +1 ), (c 2 i 2 , c 2 i 2 +1 ) ∈ A(D) and c 1 i 1 +1 = c 2 i 2 +1
. This contradicts the maximality of i 1 . Henceforth, we assume that c 1 i 1 has an outneighbour p i ∈ P (the case in which c 2 i 2 has an outneighbour in P is similar). If b 2 k 2 -1 has also an outneighbour p j ∈ P , then

F ∪ C 1 contains a B a k 3 p j (k 1 , k 2 ; k 3 ) if i ≤ j, and a B a k 3 p i (k 1 , k 2 ; k 3 ) if j ≤ i.
So, we may assume that b 2 k 2 -1 has no outneighbour in P . Hence, b 2 k 2 -1 has two distinct outneighbours, say c 3 1 and c 4 1 , not in F ∪ C 1 . Let i 3 ≥ 1 be the largest integer such that there exist two disjoint dipaths C 3 and C 4 in D -(F ∪ C 1 ) with initial vertex c 3 1 and c 4 1 respectively and length i 3 and

i 4 = min{k 2 -1, i 3 }. If i 3 ≥ k 1 , then i 4 ≥ k 2 -1 and thus P ∪ A ∪ B 2 ∪ C 3 ∪ C 4 contains
a fork that contradicts the maximality of F . Thus, we may assume that

i 3 ≤ k 1 -2. In particular |V (C 3 ) ∪ V (C 4 )| ≤ k 1 + k 2 -3.
Suppose to the contrary that both c 3 i 3 and c 4 i 4 have no outneighbour in P , where c 3 i 3 and c 4 i 4 are the last vertices of C 3 and C 4 . Note that

|V (A) ∪ V (B 1 ) ∪ V (B 2 ) ∪ V (C 1 ) ∪ V (C 3 ) ∪ V (C 4 )| ≤ 3k 1 + 2k 2 + k 3 -7 ≤ δ + (D) -2. Hence, there exist distinct vertices c 3 i 3 +1 , c 4 i 4 +1 ∈ V (D -(F ∪ C 1 ∪ C 3 ∪ C 4 )) such that (c 3 i 3 , c 3 i 3 +1 ), (c 4 i 4 , c 4 i 4 +1 ) ∈ A(D)
. This contradicts the maximality of i 3 .

Therefore, one of c 3 i 3 , c 4 i 4 has an outneighbour in p j in P . We assume that it is

c 3 i 3 ; the case when it is c 4 i 4 is similar. We conclude that F ∪ C 1 ∪ C 3 contains a B a k 3 p j (k 1 , k 2 ; k 3 ) if i < j, and a B a k 3 p i (k 1 , k 2 ; k 3 ) if j < i.

Immersions of transitive tournaments

An interesting weakening of Mader's conjecture has been made by DeVos et al. [START_REF] Devos | Immersing complete digraphs[END_REF]:

Conjecture 15 (DeVos et al. [START_REF] Devos | Immersing complete digraphs[END_REF]). For every k ≥ 1, there exists an integer h(k) such that every digraph with minimum outdegree at least h(k) contains an immersion of T T k .

In the same paper, they proved the result for Eulerian digraphs. In fact they showed that, in the case of Eulerian digraphs, large minimum outdegree is enough to force immersions of large complete digraphs.

Remember that F (k, l) is the multidigraph consisting of k vertices x 1 , . . . , x k and l arcs from x i to x i+1 for every 1

≤ i ≤ k -1. It is clear that F (k, k
2 ) contains an immersion of T T k , so the following theorem proved in [START_REF] Lochet | Immersion of transitive tournaments in digraphs with large minimum outdegree[END_REF] implies Conjecture 15.

Theorem 86. For every k ≥ 1 and l ≥ 1, there exists a function h(k, l) such that every multidigraph with minimum outdegree at least h(k, l) and multiplicity at most kl contains an immersion of F (k, l).

Proof. Note that F (k, 1) is a dipath on k vertices and thus h(k, 1) = k. We prove the result for h(k, l) = 2k 3 l 2 and l ≥ 2. We proceed by induction on k. For k = 1 this is then no matter the orientations of the arcs between the red chains, the resulting tournament will be a 3-transitive tournament. In particular, a random orientation will give arbitrarily large VC-dimension.

Let T be a tournament and S a set of vertices of T . The VC-dimension of S is the VCdimension of S in the inneighbourhood hypergraph. S is said to be shattered if it is shattered in the inneighbourhood hypergraph. In a tournament, the VC-dimension argument tells us that the vertices which are difficult to dominate are the vertices with large in and outdegree inside some shattered set. However, in the example we just provided, the structure of a shattered set makes the domination of these vertices very easy.

The goal of our approach was to understand the structure of shattered sets in order to deal with them during the sampling part of the proof of the -net Theorem. In the first part of the proof, we analyse shattered sets in a 3-transitive tournament and prove that they have a long monochromatic chain, meaning that we only have to consider shattered chains.

Structure of shattered sets

Let C = x 0 , . . . , x k be a chain of order k + 1, we denote by I(C) the set of vertices x i for 0 < i < k.

Lemma 88. Let C = x 0 , . . . , x k be a chain of a 3-transitive tournament T . If v is a vertex of T such that (v, x 0 ) and (x k , v) belong to A(T ), then none of the arcs between v and I(C) have the same colour as C.

Proof. Suppose C is a red chain and let x i be a vertex of I(C). If (x i , v) belongs to T and is coloured red, then by transitivity (x 0 , v) belongs to T and is coloured red. Likewise, if (v i , x) is coloured red then (v, x k ) belongs to T .

Let C = x 0 , . . . , x k be a chain of a 3-transitive tournament T and let G(C) be the set of vertices v of T such that (v, x 0 ) and (x k , v) belong to A(T ). The previous lemma implies that, for a vertex v of G(C), it is not possible to have one arc from I(C) to v and one arc from v to I(C) of the same colour. Indeed since this colour cannot be the colour of C by the previous lemma, it would force an arc of another colour between vertices in C. Thus, the vertices of G(C) divide in two types, depending on the colour of A(v, I(C)) and A(I(C), v). For example, if C is a red chain, then the two types are the following:

• The vertices v such that the arcs in A(v, I(C)) are green and the arcs in A(I(C), v) are blue.

• The vertices v such that the arcs in A(v, I(C)) are blue and the arcs in A(I(C), v) are green.

Lemma 89. Let C = x 0 , . . . , x k be a chain of a 3-transitive tournament T . Let u and v be two vertices of G(C) with the same type such that there exist two indices 0 < i < k and 0 < j < k where ux i vx j is a directed cycle, then the arc between u and v is of the same colour as C. ) And when t is big enough, this is smaller than 1/2, so we reach a contradiction. Now we show how to prove the general case, using the probability distribution given by Lemma 46 (actually we use a slightly more precise version found in [START_REF] Fisher | Probabilities within optimal strategies for tournament games[END_REF]).

Proof of Proposition 87. Let C be as Proposition 94. If T has a dominating vertex we are done so we can assume it does not. By Thereom 1.5 of [START_REF] Fisher | Probabilities within optimal strategies for tournament games[END_REF], there exists a rational number p(v) for every vertex v such that p is a probability distribution on the vertices, p(v) ≤ 1/3 for all v and p(N -[v]) ≥ 1/2. This implies that p(N -(v)) ≥ 1/6. By blowing each vertex v of T with a red transitive tournament of size M f (v) for some integer M , we get a tournament T satisfying the conditions of Proposition 94, so with a dominating set of size C. Finally, by taking for each vertex in the dominating set of T , its original vertex in T we obtain a dominating set of T of cardinality at most C.

General proof

In this section we prove Theorem 49.

The important part in the last proof is that, if A is a shattered set and B is the set of vertices with large in and outdegree in A, then the structure of B is simple. The question we had was to know if this was still true if T is the union of more than three quasi-orders. One way for B to be simple is to have bounded VC-dimension and a natural question was to ask what happens when B doesn't have bounded VC-dimension? Suppose there exists a set C in B such that C has large in and outdegree in B, what can we say about that set? The answer to this question, when all the arcs involved belong to the same transitive digraph is the following lemma which is the essential part of the proof of Theorem 49.

Let P be a quasi-order on S. We say that A ⊆ P is -dense in P if there exists a probability distribution w on the vertices of P such that w(N -[x]) ≥ for every element x of A. Let T be a complete multidigraph whose arcs are the union of the arcs of k quasi orders P 1 , . . . , P k , we define

N - i [x] (resp N + i [x]
) as the closed inneighbourhood (resp. outneighbourhood) of the digraph induced by P i .

Lemma 95. Let be a real in [0, 1]. There exists an integer g( ) such that for every quasiorder P on a set A and two subsets C ⊆ B of A such that B is -dense in P and C is -dense in B, there exists a set of g( ) elements in A dominating C.

x 1 ≤ r p ; x 2 ≤ k; x 3 ≤ ( r p ) r 1 -1 ; x 4 ≤ k r 1 -1 ; x 5 ≤ p! r 1 -1 ; x 6 ≤ (r -p)! r 1 -1 ; x 7 ≤ r!;
• F is an integer smaller than (r! + 1) |H| representing a partial orientation of H.

The log of order M (or just log) is actually a trace of the deterministic algorithm's execution after M steps. Its objective is to encode which orientations get canceled during the algorithm's execution. We will show later that Algorithm 3 cannot produce the same log from two different input vectors v, v ∈ [cr!] M , and that, for M big enough, that the set of possible logs is smaller than (cr!) M . We now describe the log and how Algorithm 3 produces it.

• R is initialized to the empty word. We append 1 to R whenever Algorithm 3 adds a new orientation; we append 0 whenever it cancels one.

• Consider the following bad event: after orienting S 1 , a hyperedge S ∈ H is pressured by a family {S 1 , . . . , S r 1 } of cardinality r 1 . We note s i the set of vertices that S i maps to P . We associate the following 7-tuple which identifies the sets S i as well as their orientations:

x 1 < r p represents the set s 1 among the r p possible subsets of size p of S 1 . x 2 < k identifies S as one of the (at most k) hyperedges containing s 1 .

x 3 < ( r p ) r 1 -1 is an integer representing the set of subsets s 2 , . . . s r 1 amongst the r p subsets of size p of S.

x 4 < k r 1 -1 is an integer representing the sequence (y 2 , . . . , y r 1 ) ∈ [k] r 1 -1 such that the y l -th edge containing s l is S l .

x 5 < p! r 1 -1 is an integer representing the sequence (p 1 , . . . , p r 1 ), where p i ∈ [p!] represents the subpermutation of S i onto s i (we know it's a permutation of P ).

x 6 < (r -p)! r 1 -1 is the integer representing the sequence [p 2 , . . . , p r 1 ], where

p i ∈ [(r -p)!] represent the subpermutation of S i onto [r] \ s i .
x 7 < r! is the integer representing the permutation chosen for S 1 .

X is the list of the 7-tuples describing the bad events, in the order in which they happen.

• F is the integer representing the partial orientation of H (i.e. a choice among r! + 1 per hyperedge of H) after M steps.

Lemma 102. Let A, B be two sets of size r, and let σ : A → B be a random bijection. For every A 1 , . . . , A k ⊆ A ⊆ A and B 1 , . . . , B k ⊆ B ⊆ B, the following function increases with t.

P r i [σ(A i ) = B i ] σ(A )\B has cardinality t (5.2)
Proof. We implicitly assume in this proof that the conditionning event has a nonzero probability for t and t + 1. Let S 1 , S 2 be two sets of cardinality |A | with symmetric difference S 1 ∆S 2 = {x, y} where x ∈ S 2 is an element of B\B . Let σ xy be the permutation transposing x and y. Then,

P r i [σ(A i ) = B i ] σ(A ) = S 1 ≤ P r i [σ xy σ(A i ) = B i ] σ(A ) = S 1 = P r i [σ(A i ) = B i ] σ(A ) = S 2
We are now ready to derive the result:

(5.2) = 1 |B\B | t |B | |A |-t S⊆B |S|=|A | |S\B |=t P r i [σ(A i ) = B i ] σ(A ) = S
Using our previous remark, we find an upper bound on the last term of the equation by averaging it over sets S obtained from S by the exchange of two elements:

(5.2) ≤ 1 |B\B | t |B | |A |-t S⊆B |S|=|A | |S\B |=t 1 (|B\B | -t)(|A | -t) S ⊆B |S |=|A | |S \B |=t+1 |S∆S |=2 P r i [σ(A i ) = B i ] σ(A ) = S = 1 |B\B | t |B | |A |-t (t + 1)(|B | -|A | + t + 1) (|B\B | -t)(|A | -t) S ⊆B |S |=|A | |S \B |=t+1 P r i [σ(A i ) = B i ] σ(A ) = S = |B\B | t+1 |B | |A |-t-1 |B\B | t |B | |A |-t (t + 1)(|B | -|A | + t + 1) (|B\B | -t)(|A | -t) P r i [σ(A i ) = B i ] σ(A )\B has cardinality t + 1 = P r i [σ(A i ) = B i ] σ(A )\B has cardinality t + 1

AVD-colouring

In this section, we present the proof of Theorem 57 obtained in [START_REF] Joret | Progress on the adjacent vertex distinguishing edge colouring conjecture[END_REF] with Gwenaël Joret. In Subsection 5.2.1 we set up the plan for the proof of Theorem 57. In particular, vertices with big degrees (at least ∆/2, roughly) and those with small degrees are treated independently, and differently. Then, Subsection 5.2.2 and Subsection 5.2.3 are devoted to handling big and small degree vertices, respectively.

Initial colouring

Fix some with 0 < < 1/2, which will be assumed small enough later in the proof. Let G be a graph with maximum degree ∆ and no isolated edge. We assume ∆ is large enough for various inequalities appearing in the proof to hold.

The beginning of our proof of Theorem 57 follows closely that of Hatami [START_REF] Hatami | ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number[END_REF]. In particular, we reuse his approach of treating differently vertices with 'small' degrees and those with 'big' degrees, except we use (1/2 -)∆ as the threshold instead of ∆/3 in [START_REF] Hatami | ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number[END_REF]. This larger threshold helps a little bit in reducing the additive constant in the main theorem; however, the bulk of the reduction from 300 to 19 comes from treating big degree vertices differently.

Let d := (1/2 -)∆ . Taking ∆ large enough, we may assume that d < ∆/2. We begin as in [START_REF] Hatami | ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number[END_REF] In [START_REF] Hatami | ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number[END_REF], the author points out that if moreover c is an AVD-colouring of G then c is an AVD-colouring of G. Using this observation, the proof in [START_REF] Hatami | ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number[END_REF] then focuses on finding an AVD-colouring of G . This is done by starting with a proper edge colouring c with ∆ + 2 colours, which exists by Vizing's theorem, and then recolouring some edges of G with new colours to obtain an AVD-colouring of G . The advantage of working in G instead of G is that the subgraph of G induced by the vertices with degree strictly less than d has no isolated edge, which is important in that proof.

In our proof, we follow a similar approach but we keep the focus on G: We start with a proper edge colouring c of G with ∆ + 2 colours obtained from Vizing's theorem and extend it to an edge colouring c of G as in the above remark. Thus, the edge colouring c uses ∆ + 2 colours and satisfies the following property:

S c (u) ∩ S c (v) = {c(uv)} ∀uv ∈ E(G) s.t.{w ∈ N (u) ∪ N (v) : d G (w) < d} = {u, v}. (5.3)
Then, we modify c to obtain an AVD-colouring of G. Thus G is only used to produce the initial edge colouring c of G. One advantage of working in G is that we avoid having to deal with parallel edges, which would introduce (trivial but annoying) technicalities in our approach. On the other hand, a small price to pay compared to [START_REF] Hatami | ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number[END_REF] is that we will have to watch out for these edges uv such that {w ∈ N (u) ∪ N (v) : d G (w) < d} = {u, v} in our proof.

Say that a vertex u ∈ V (G) is small if d G (u) < d, and big otherwise. Let A and B be the sets of small and big vertices of G, respectively. Our goal is to transform the edge colouring c into an AVD-colouring of G. The plan for doing so is roughly as follows. First we show that we can uncolour a bounded number of edges per big vertex in such a way that edges uv with S c (u) = S c (v) and u, v ∈ B that remain form a matching satisfying some specific properties. Then we show how we can recolour these uncoloured edges, plus a few other edges of G, to obtain an edge colouring where every edge uv with u, v ∈ B satisfies S c (u) = S c (v). Finally, we recolour edges with both endpoints in A in such a way that the resulting edge colouring is an AVD-colouring of G.

Big vertices

For each vertex u ∈ B, choose an arbitrary subset N + (u) of N (u) of size d. We use a randomised algorithm, Algorithm 4, to select a subset U + (u) ⊆ N + (u) of size 2 for each vertex u ∈ B. For each vertex v ∈ V (G), we let U -(v) := {u ∈ B : v ∈ U + (u)}. Algorithm 4 chooses the subsets U + (u) iteratively, one big vertex u at a time. Hence, we see the sets U + (u) as variables, and the sets U -(v) (v ∈ V (G)) as being determined by these variables. (For definiteness, we set U + (u) := ∅ for every small vertex u.) Just after choosing the subset U + (u) of a big vertex u, the algorithm checks whether this choice triggered any 'bad event'. If so, the bad event is handled, which involves resetting the variable U + (u), which means setting U + (u) := ∅, and possibly resetting other variables U + (v) for some well-chosen big vertices v close to u in G.

Thanks to these bad events, the selected subsets satisfy a number of properties. A key property is that |U -(v)| ≤ q for every v ∈ V (G), with q := 13 being the constant that is optimised in this proof.

At any time during the execution of the algorithm, we say that an edge uv ∈ E(G) is selected if v ∈ U + (u) or u ∈ U + (v). In the algorithm, we will make sure that if v ∈ U + (u) then u / ∈ U + (v) (that is, an edge can be selected 'at most once'). After the algorithm terminates, selected edges will be used to fix locally the edge colouring c for big vertices: The plan is to recolour them using q + 3 new colours, and then recolour a well-chosen matching of G with yet another new colour, in such a way that at the end S c (u) = S c (v) holds for all edges uv ∈ E(G) with u, v ∈ B. The resulting edge colouring of G will use ∆ + q + 6 colours in total.

Let us explain the conventions and terminology used in Algorithm 4. First, we assume that the vertices of G are ordered according to some fixed arbitrary ordering. This naturally induces an ordering of each subset of V (G) as well, of each set of pairs of vertices (say using lexicographic ordering), and more generally of any set of structures built using vertices of G. This is used implicitly in what follows.

We say that an edge uv linking two big vertices is finished if U + (w) = ∅ for each big vertex w in N (u) ∪ N (v) (note that this set includes u and v). For u ∈ V (G), define S (u) as the set S c (u) minus colours of edges incident to u that are selected. That is,

S (u) := {c(uv) : v ∈ N (u), v / ∈ U + (u) ∪ U -(u)}.
In the algorithm, we check whether S (u) = S (v) for two big vertices u, v with d G (u) = d G (v) only when uv is finished, the idea being that if there are still big vertices adjacent to u or v waiting to be treated then this could potentially impact the sets S (u) and S (v). We say that an edge

uv ∈ E(G) is bad if u, v ∈ B, uv is finished, d G (u) = d G (v)
, and S (u) = S (v).

As mentioned earlier, we need to watch out for edges uv such that d G (u) = d G (v) < d and d G (w) ≥ d for all w ∈ (N (u) ∪ N (v)) -{u, v}. This is because every edge incident to u or v distinct from uv is incident to a big vertex, and all these edges will have a fixed colour when we are done dealing with big vertices. Indeed, in the next section we only recolour edges in the subgraph induced by small vertices. Thus, if u and v were to see the same set of colours at the end of this step, we would have no way to fix this later. Note that at the beginning u and v see disjoint sets of colours in the edge colouring c except for colour c(uv).

Once the algorithm terminates, we will recolour at most q + 2 edges incident to each big vertex w (with new colours). Thus, if d G (u) = d G (v) ≥ q + 4, we know that there will be at least one edge e incident to u distinct from uv that kept its original colour c(e). Since v does not see the colour c(e), we are then assured that u and v see different sets of colours after the recolouring step. Therefore, it is only when d G (u) = d G (v) ≤ q + 3 that we need to be careful when selecting edges incident to u or v to recolour. Let us call such edges fragile edges, i.e. uv is fragile if d G (u) = d G (v) ≤ q + 3 and d G (w) ≥ d for all w ∈ (N (u) ∪ N (v)) -{u, v}. Fragile edges will be carefully handled in the algorithm.

As mentioned, the algorithm considers remaining big vertices u with U + (u) = ∅ one by one, selects the subset U + (u) randomly each time, and deals with any bad event that may occur. Let us explain how the random choices are made. Given a big vertex u with U + (u) = ∅, an unordered pair {v, w} ⊆ N + (u) is admissible for u if the following three conditions are satisfied:

• v, w / ∈ U -(u);
• if vw ∈ E(G) then vw is not fragile, and

• setting U + (u) := {v, w} does not create any bad edge incident to u.

At the beginning of the while loop, the algorithm chooses an admissible pair for the vertex u ∈ B under consideration uniformly at random among the first s := d-q 2 -3d admissible pairs. Lemma 103 below shows that there are always at least s such pairs, thus this random choice can always be made.

Five types of bad events are considered in the algorithm. They correspond to the five conditions tested by the if / else if statements; we refer to them as Bad Event 1, Bad Event 2, etc. in order. These events state the existence of certain structures in the graph. We remark that there could be more than one instance of the structure under consideration ) In this case, we assume that the algorithm chooses one according to some deterministic rule. For the convenience of the reader, the five types of bad events considered are illustrated in Figure 5.1. Let us emphasise that if any bad event is triggered, then the current vertex u is always reset (i.e. the algorithm sets U + (u) := ∅). This will ensures that no other bad event remains in the graph after dealing with the bad event under consideration.

The following lemma establishes some key properties of Algorithm 4. Note that by an invariant of the while loop, we mean a property that is true every time the condition of the loop is being tested. Thus, such a property holds when a new iteration of the loop starts, and also when the loop (and thus the algorithm) stops.

Lemma 103. The following properties are invariants of the while loop in Algorithm 4: Proof. Let us start with property (1). Clearly, |U -(v)| ≤ q for every v ∈ V (G) the first time the condition of the while loop is being tested. This remains true for every subsequent test Event 4 would have been triggered. But this shows that Bad Event 5 occurs. We deduce that property (4) is maintained.

1. |U -(v)| ≤ q for every v ∈ V (G).
Finally, it remains to show that property ( 5) is an invariant of the loop. Consider thus any vertex u ∈ B with U + (u) = ∅ when the condition of the loop is being tested. (Thus, a new iteration of the loop is about to start.) From invariant (1), we know that there are at least d-q 2 unordered pairs of distinct vertices in N + (u) -U -(u). Next, a key observation is that for every x ∈ N (u), if there exists {v, w} ⊆ N + (u) -U -(u) s.t. setting U + (u) := {v, w} makes the edge ux bad, then the set {v, w} is uniquely determined. Hence, potential bad edges forbid at most |N (u)| ≤ ∆ pairs of vertices in N + (u) -U -(u). Finally, among the remaining pairs {v, w}, at most d/2 of them are s.t. vw is a fragile edge. Therefore, we conclude that there are at least d-q

2 -∆ -d/2 ≥ d-q 2 -3d = s admissible pairs for u.
The properties listed in Lemma 103 hold in particular when Algorithm 4 stops. However, it is not clear at first sight that the algorithm should ever stop. Our next result shows that it does so with high probability. For simplicity, we sometimes call one iteration of the while loop a step.

Theorem 104. The probability that Algorithm 4 stops in at most t steps tends to 1 as t → ∞.

We use an 'entropy compression' argument to prove this theorem, a proof method introduced by Moser and Tardos [START_REF] Moser | A constructive proof of the general Lovász Local Lemma[END_REF] in their celebrated algorithmic proof of the Lovász Local Lemma. In a nutshell, the main idea of the proof is to look at sequences of t random choices such that the algorithm does not stop in at most t steps. Exploiting the fact that the algorithm did not stop, we show how one can get an implicit lossless encoding of these sequences, by writing down a concise log of the execution of the algorithm. Then, looking at the structure of the algorithm, we prove that there are only o (s t ) such logs. Since in total there are s t random sequences of length t, we deduce that only a o(1)-fraction of these make the algorithm run for at least t steps. Theorem 104 follows.

To describe the log of an execution of the algorithm, we need the following definitions. First, recall that a Dyck word of semilength k is a binary word w 1 w 2 . . . w 2k with exactly k 0s and k 1s such that the number of 0s is at least the number of 1s in every prefix of the word. A descent in a Dyck word is a maximal sequence of consecutive 1s, its length is the number of 1s.

For our purposes, it will be more convenient to drop the requirement that a Dyck word has the same number of 0s and 1s. Let us define a partial Dyck word of semilength k as a binary word w 1 w 2 . . . w p with exactly k 0s and at most k 1s such that the number of 0s is at least the number of 1s in every prefix of the word. Descents are defined in the same way as for normal Dyck words.

Let us consider a sequence (r 1 , . . . , r t ) of t random choices such that Algorithm 4 does not stop in at most t steps when run with these random choices. In other words, the algorithm is about to start its (t+1)-th iteration of the while loop, at which point we freeze its execution. γ i := -1 and δ i := -1. Otherwise, say that a bad event β of type j was handled. The definition of γ i assumes that B i is known, while that of δ i assumes that B i and U + i+1 are both known. In particular, we know the vertex u treated at the beginning of the iteration, since it is the first vertex in B i . With these remarks in mind, γ i and δ i are defined as follows: j = 1 The bad event β was triggered because the admissible pair chosen for u contained a vertex v with |U - i (v)| = q. Vertex u and the q vertices in U - i (v) were subsequently reset. There are at most d choices for vertex v and at most ∆ q choices for U - i (v). We may thus encode v and U

- i (v) with a number γ i ∈ d ∆ q . Observe that B i+1 = B i ∪ U - i (v).
Now that v and U - i (v) are identified, we want to encode the admissible pair {v, x} that was chosen for u at the beginning of the iteration, and the sets U + i (w) for each vertex w ∈ U - i (v). There are at most d choices for x, and similarly for each w ∈ U - i (v) there are at most d choices for the vertex in U + i (w) which is distinct from v. We let δ i ∈ [d q+1 ] encode these choices. Since U + i only differs from U + i+1 on vertices w ∈ U - i (v), with the encoded information we can deduce U + i from U + i+1 . Note also that r i is determined by the admissible pair {v, x} that was chosen for u. j = 2 The bad event β was triggered because the admissible pair chosen for u contained a vertex v incident to a fragile edge vw with U - i (w) = ∅. Then two vertices were reset, namely u and some vertex x in U - i (w). There are at most d choices for vertex v. Once v is identified, we know vertex w since fragile edges form a matching. Finally, there are at most q + 2 choices for x, since d G (w) ≤ q + 3 and x = v. We let γ i ∈ [(q + 2)d] encode v, w, and x. Observe that B i+1 = B i ∪ {x}.

Next, to encode r i we only need to specify the vertex in the admissible pair chosen for u that is distinct from v (d choices). Similarly, there are at most d possibilities for the set U + i (x) since we know that it includes w. Hence, we can encode this information with a number δ i ∈ [d 2 ]. Note that, knowing x and U + i (x), we can directly infer

U + i from U + i+1 , since U + i (y) = U + i+1 (
y) for all y ∈ B -{x}. j = 3 After selecting the admissible pair for u, we had S (v) = S (w) = S (x) for three distinct vertices v, w, x ∈ B -{u} with vw, wx ∈ E(G) and u ∈ N (v) ∪ N (w). Then u, v, x were reset. There are at most 2∆ 3 choices for the triple v, w, x (the factor 2 is due to the fact that u can be adjacent to v or w). We let

γ i ∈ [2∆ 3 ] encode v, w, x. Observe that B i+1 = B i ∪ {v, x}.
Knowing v, w, x and U + i+1 , our next aim is to encode U + i and r i using δ i . First, we simply encode the admissible pair {u 1 , u 2 } that was chosen for u during the i-th iteration explicitly, thus there are d 2 possibilities. Next, we observe that

U + i (y) = U + i+1 (y)
for every y ∈ B -{u, v, x}, and U + i (u) = ∅. Thus it only remains to encode U + i (v) and U + i (x). Here the idea is that, since at this point we know the set U + i (w) and the admissible pair {u 1 , u 2 } chosen for u, there are only O(1) possibilities for the sets U + i (v) and U + i (x) in order to have that S (v) = S (w) = S (x) just before u, v, x were reset.

Let us focus on the set U + i (v), the argument for U + i (x) will be symmetric. First, let us write down the following local information: (1) Is w ∈ U + i (v)? (2) Is w ∈ U + i (x)? (3) Is v ∈ U + i (x)? Thus there are 8 possibilities. ( 1)-( 2) gives enough information to reconstruct the set S (w) just before the resets, since we already know U + i (w) and whether w ∈ {u 1 , u 2 } or not. From (3) we also know the set S (v) := S (v) -{c(vv ) : v ∈ U + i (v)} just before the resets, since we know whether v ∈ {u 1 , u 2 } or not, and whether v ∈ U + i (z) or not for every z ∈ N (v) -{u}. Now, it only remains to observe that U + i (v) is determined by the two sets S (v) and S (w), namely

U + i (v) = {v ∈ N (v) : c(vv ) ∈ S (v) -S (w)}.
Proceeding similary for the set U + i (x) (8 possibilities again), this fully determines U + i . Now, given U + i we know exactly the set of admissible pairs for u at the beginning of the i-th iteration. Since we know that the pair {u 1 , u 2 } was chosen, we can deduce the value of r i . Hence, this shows that U + i and r i can be encoded using a number δ i ∈ [64 d 2 ]. (The constant 64 could be reduced with a more careful analysis but this would not make a difference later on.) j = 4 Here we let γ i ∈ [4∆ 4 ] encode the four vertices v, w, x, y as seen from u (the factor 4 comes from the fact that u is adjacent to at least one of them but we do not know which one). Since u, v, w, y are reset during this iteration, we have B i+1 = B i ∪{v, w, y}.

Next, we set up δ i to encode U + i and r i knowing U + i+1 . As in the previous case, we encode the admissible pair {u 1 , u 2 } that was chosen for u during the i-th iteration explicitly ( d 2 choices). Once we know U + i , we know which are the admissible pairs for u at the beginning of the i-th iteration, and thus we can determine r i , exactly as before. Thus, it only remains to encode U + i (v), U + i (w), and U + i (y).

Let us start with U + i (w). We already know that x ∈ U + i (w), and we encode the other vertex in U + i (w) explicitly (d choices).

Next, consider U + i (v). Here, the idea is the same as for Bad Event 3, namely once U + i (w) is known there are only O(1) possibilities for U + i (v) to have that S (v) = S (w) just before the resets. To be precise, we write down the following local information: (1) Is w ∈ U + i (v)? (2) Is w ∈ U + i (x)? (3) Is w ∈ U + i (y)? (4) Is v ∈ U + i (x)?

(5) Is v ∈ U + i (y)? Thus there are 32 possibilities. ( 1)-( 3) gives us enough information to reconstruct the set S (w) just before the resets, since we already know U + i (w) and whether w ∈ {u 1 , u 2 } or not. Similarly, (4)-( 5) allow us to determine the set S (v) := S (v) -{c(vv ) : v ∈ U + i (v)} just before the resets, which in turn determines

U + i (v) since U + i (v) = {v ∈ N (v) : c(vv ) ∈ S (v) -S (w)}.
For U + i (y), we proceed exactly as for U + i (v), exchanging v with y and w with x. The only difference here is that x is not reset, thus U + i (x) = U + i+1 (x). We similarly conclude that there are at most 32 possibilities for the set U + i (y). In summary, we may encode all the necessary information with a number δ i ∈ 2

+ i (v), U + i (w), U + i (x), U + i (y).
Similarly as for Bad Event 4, there are most d possibilities for the set U + i (w), since we already know that z ∈ U + i (w). The same is true U + i (x).

For U + i (v) we proceed exactly as in the previous case, exploiting the fact that U + i (w) is already encoded: Writing down which sets among U + i (v), U + i (x), U + i (y) include vertex w, and similarly which of U + i (x), U + i (y) include v, is enough to determine U + i (v). Thus there are 32 choices. This is also true for U + i (y) since the situation is completely symmetric (swapping v, w with y, x, respectively). Hence, we can record the desired information with a number δ i ∈ 2 10 d 2 d 2 .

Let R t denote the set of sequences (r 1 , . . . , r t ) with each r i ∈ [s] such that Algorithm 4 does not stop in at most t steps when using r 1 , . . . , r t for the random choices. Also, let L t denote the set of logs defined by the algorithm on these sequences. The following lemma follows from the discussion above.

Lemma 105. For each t ≥ 1, there is a bijection between the two sets R t and L t .

Next, we bound |L t | from above when t is large. To do so we need to count some specific Dyck words where each descent is weighted with some integer: Given a set E = {(l 1 , w 1 ), . . . , (l k , w k )} of couples of positive integers with all l j 's distinct, we let C t,E be the number of Dyck words of semilength t where each descent has length in the set {l 1 , . . . , l k }, and each descent of length l j is weighted with an integer in [w j ].

For our purposes, we take E := {(l 1 , w 1 ), . . . , (l 5 , w 5 )}, where (l j , w j ) is determined by the characteristics of Bad Event j: l j is the number of vertices that are reset, and w j is an upper bound on the number of values the corresponding pair (γ i , δ i ) can take in the log during the corresponding i-th iteration of the algorithm. Thus, following the discussion of bad events above, we take:

• l 1 = q + 1 and w 1 = ∆ q d q+2
• l 2 = 2 and w 2 = (q + 2)d 3 In our logs we deal with partial Dyck words that are weighted as above. The difference between the number of 0s and 1s in the partial Dyck word corresponds to the number of big vertices u ∈ B for which U + (u) is currently not set; we call this quantity its defect. Observe that partial weighted Dyck words of semilength t and defect k can be mapped injectively to weighted Dyck words of semilength t + k by adding k occurrences of 011 at the end, where each of the k new descents of length 2 are weighted with, say, the number 1. Since k ≤ n = |V (G)|, we obtain the following lemma.

Lemma 106. |L t | ≤ n k=0 C t+k,E .
In our setting, n and s are fixed while t varies; thus, to prove that |L t | ∈ o (s t ), it is enough by the above lemma to show that C t,E ∈ o (s t ). In order to bound C t,E from above, we follow [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF] and use a bijection between Dyck words and rooted plane trees.

Lemma 107. The number C t,E is equal to the number of weighted rooted plane trees on t + 1 vertices, where each vertex has a number of children in E ∪ {0}, and for each i ∈ [5] each vertex with l i children is weighted with an integer in [w i ] (leaves are not weighted).

The proof of this lemma is essentially that of Lemma 7 in [START_REF] Esperet | Acyclic edge-coloring using entropy compression[END_REF]. Now we use generating functions and the analytic method described e.g. in [ Then y(x) satisfies y(x) = xφ(y(x)). As noted in [21, Theorem 5] (see also [28, p.278, Proposition IV.5]), the following asymptotic bound holds for C t,E .

Theorem 108. Let R denote the radius of convergence of φ and suppose that lim x→R -xφ (x) φ(x) > 1. Then there exists a unique solution τ ∈ (0, R) of the equation τ φ (τ ) = φ(τ ), and C t,E = O(γ t ), where γ := φ(τ )/τ .

The radius of convergence of our function φ is R = ∞, and lim x→∞ xφ (x) φ(x) > 1, thus the theorem applies. For our purposes, it is not necessary to compute exactly τ , a good upper bound on γ = φ(τ )/τ will be enough. To obtain such an upper bound we use the following lemma.

Lemma 109. For every x ∈ (0, R), if xφ (x)/φ(x) < 1 then φ(τ )/τ < φ(x)/x.

Proof. As noted in [START_REF] Flajolet | Analytic Combinatorics[END_REF]Note IV.46] the function xφ (x)/φ(x) is increasing on (0, R). Thus, xφ (x)/φ(x) < 1 if and only if x < τ . Consider the function xφ (x)/φ(x) on (0, τ ). Since xφ (x)/φ(x) < 1, we have xφ (x) -φ(x) < 0. Moreover, since ∂ ∂x ( φ(x) x ) = xφ (x)-φ(x)

x 2

, we see that φ(x) x is decreasing on (0, τ ). Hence, φ(x) x > φ(τ ) τ .

Using these tools we can bound γ from above.

Lemma 110. γ < s when d is large enough.

Proof. We will use Lemma 109. Let 1 > 0 be fixed (at the end of the proof 1 will be taken small enough as a function of q = 13). Let

x := 1 q(1 + 1 )w 1 1/(q+1) .

We claim that xφ (x)/φ(x) < 1 when d is large enough. First, let us give some intuition: If we counted only the subset of weighted Dyck words where each descent is of length l 1 = q + 1 and is weighted with an integer in [w 1 ], then the corresponding function φ would be φ(x) = 1 + w 1 x q+1 , and one would get τ = 1 qw 1

1/(q+1)

. As it turns out, the value of τ for our function of φ tends to that one (from below) as d → ∞, hence our choice of 1 qw 1 1/(q+1) , slightly scaled down, for x.

To show xφ (x)/φ(x) < 1, we make the following observations, each of which is self evident:

• xφ (x) = 5 i=1 l i w i x l i • φ(x) ≥ 1 + w 1 x q+1 • x = O 1 d 2
• l i w i = O(d 2l i -1 ) for each i ∈ [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF][START_REF] Alon | Dominating sets in k-majority tournaments[END_REF].

i=2 l i w i x l i φ(x) = O 1 d
and xφ (x) φ(x) ≤ (q + 1)w 1 x q+1 1 + w 1 x q+1 + O

1 d = 1 1+ 1 • q+1 q 1 + 1 (1+ 1 )q + O 1 d = 1 1+ 1 • q+1 q 1 1+ 1 • q+1 q + 1 1+ 1 + O 1 d .
Thus xφ (x)/φ(x) < 1 when d is large enough, as claimed. Hence, to prove the lemma it is enough to show that φ(x)/x < s for d large enough, by Lemma 109.

Observe that φ(x) x = 1 x + w 1 x q + O(d).

Since s = d-q 2 -3d = Θ(d 2 ), to prove that φ(x)/x < s for d large enough it is enough to show that 1/x + w 1 x q < (1 -δ)s for some fixed δ > 0. Let c q, 1 := (q(1 + 1 )) 1/(q+1) + 1 q(1 + 1 ) q/(q+1)

.

Using that a b ≤ a b b! and d ≤ ∆/2, we obtain the following bound:

1 x + w 1 x q = c q, 1 ∆ q d q+2 1/(q+1) ≤ c q, 1 ∆ 2q+2 2 q+2 q! 1/(q+1) = c q, 1 1 2 q+2 q! 1/(q+1) ∆ 2 .
Since s = d-q 2 -3d, for any fixed > 0 we have s ≥ 1- 2 d 2 ≥ (1-)(1/2-) 2

2

∆ 2 if d is large enough. Hence, to conclude the proof it suffices to show that the following inequality holds if , and 1 are chosen small enough:

c q, 1 1 2 q+2 q! 1/(q+1) < (1 -)(1/2 -) 2 2 .
(5.4) This is true, since c q,0 1 2 q+2 q! 1/(q+1) 0.12292 < 1/8 for q = 13.

It follows from Theorem 108 and the above lemma that C t,E ∈ o (s t ), and hence |L t | ∈ o (s t ), when d is large enough. (To avoid any confusion, let us emphasise that here the o(•) notation is w.r.t. the variable t, that is, we first assume that d is large enough for Lemma 110 to hold, and then when the graph is fixed we let t vary.) Since there are s t random sequences of length t, Theorem 104 follows from Lemma 105 and Lemma 110.

It follows from Theorem 104 that Algorithm 4 stops on some random sequence, and thus a function U + satisfying the properties of Lemma 103 exists. Consider such a function U + and the corresponding set of selected edges. Recall that each vertex of G is incident to at most q + 2 selected edges, as follows from property (1) of Lemma 103. Using Vizing's theorem we recolour the set of selected edges properly using q + 3 new colours, say from the set [∆ + 3, ∆ + q + 5]. Let c denote the resulting edge colouring of G. That is, c (e) := c(e) if e was not selected, and c (e) denotes the new colour of e if e was selected.

For each bad edge uv ∈ M , choose one of its two endpoints, say u, and mark one edge uw for some vertex w ∈ U + (u), with w = v in case v ∈ U + (u). It follows from property (4) of Lemma 103 that marked edges form a matching, and that each bad edge is incident to exactly one marked edge. Recolouring all marked edges with a new colour, say colour ∆ + q + 6, we obtain a proper edge colouring c of G with ∆ + q + 6 colours such that S c (u) = S c (v) for all edges uv ∈ E(G) with u, v ∈ B and d G (u) = d G (v). Indeed, if uv is a bad edge this holds because there is exactly one marked edge incident to uv, and it is distinct from uv itself. If uv is not a bad edge, then by definition u and v see distinct sets of colours in the edge colouring c when considering only non-selected edges. Since marked edges form a subset of selected edges, we see that S c (u) = S c (v) as desired.

Finally, consider edges uv ∈ E(G) with u, v ∈ A that are isolated in G[A] (i.e. such that all neighbours of u, v outside {u, v} are big) with d G (u) = d G (v). Recall that d G (u) = d G (v) ≥ 2, since uv is not isolated in G. Recall also that in the initial colouring c of G we had S c (u) ∩ S c (v) = {c(uv)}, that is, u and v saw no common colour except for that of uv. If uv is fragile, then at least one of u, v is such that no incident edge was selected, by property 2 of Lemma 103, and hence S c (u) = S c (v) (since marked edges form a subset of selected edges). If uv is not fragile, then d G (u) = d G (v) ≥ q + 4 by definition. Since at most q + 2 edges incident to u were selected, and same for v, we see that u and v are each incident to a non-selected edge distinct from uv. It follows that S c (u) = S c (v).

Small vertices

At this point, we know that S c (u) = S c (v) for every edge uv ∈ E(G) with u, v ∈ B, and for every edge uv ∈ E(G) with u, v ∈ A which is isolated in G[A]. However, we could have S c (u) = S c (v) for some non-isolated edges uv of G[A]. Let A be the subset of vertices of A that are not incident to an isolated edge of G[A]. In this section we modify the colouring c on the graph G[A ] only, and make sure that S c (u) = S c (v) for every uv ∈ E(G) with u, v ∈ A . Since this has no effect on the sets S c (u) for u ∈ B ∪ (A -A ), the resulting colouring will be an AVD-colouring of G.

First, uncolour every edge of G[A ] and fix an arbitrary ordering of these edges. We colour these edges one by one using the following iterative algorithm; at all times, we let c denote the current partial edge colouring of G. Consider the first uncoloured edge uv in the ordering. Let s := 2 ∆ . Since (d G (u) -1) + (d G (v) -1) ≤ 2(d -1) ≤ ∆ -2 ∆, there are at least s + q + 6 available choices for the edge uv in order to maintain a proper (partial) edge colouring. In case all other edges around u are already coloured, we possibly remove one colour from the set of available choices as follows: Say that a neighbour w of u in A -{v} is dangerous for u if d G (u) = d G (w), all edges incident to w are already coloured, and S c (w) = S c (u)∪{i} for some colour i ∈ [∆+q +6]; the colour i is a dangerous colour for u. Dangerous neighbours and colours for v are defined similarly. If u has exactly one dangerous neighbour, remove the corresponding dangerous colour from the set of available choices. Do the same for v. Thus, there are at least s + q + 4 ≥ s available choices remaining for the • c is the current edge colouring at the end of the t-th iteration.

For each i ∈ [t], we let γ i := -1 and δ i := -1 in case no bad event was triggered during the i-th iteration. Otherwise, if a bad event occurred, say involving a vertex w that was dangerous for one of the two endpoints of the edge uv coloured during the iteration, we let γ i ∈ [2d] identify vertex w knowing uv (recall that u and v have degree at most d). Observe that this identifies also the extra edge that is uncoloured (besides the edge uv).

Then, we let δ i ∈ [START_REF] Addario-Berry | Oriented trees in digraphs[END_REF] identify the colours of the two edges that got uncoloured, assuming we know these two edges and the edge colouring c at the end of iteration i. Observe that we already know the set of colours that was used for these two edges, these are the two colours appearing around w but not around the vertex (u or v) that triggered the bad event. Thus it only remains to specify the mapping of these two colours to the two edges (2 possibilities).

Reading W and γ from the beginning, one can deduce which subset of the edges of G[A ] was coloured at any time during the execution. Then using the edge colouring c at the end of the t-th iteration and working backwards, we can reconstruct the edge colouring c at any time during the execution using γ and δ, and deduce in particular which random choice was made for the edge under consideration during the i-th iteration. Hence, the log (W, γ, δ, c ) uniquely determines the t random choices that were made.

As before, we see a random choice as a number in [s]. Let R t denote the set of random vectors (r 1 , . . . , r t ) of length t, where each entry is a number in [s]. Let L t denote the set of logs after t steps resulting from executions of the algorithm that last for at least t steps. By the discussion above, there is an injective mapping from L t to R t . Since |R t | = s t , to prove Theorem 112 it only remains to show that |L t | = o(s t ).

Here, a rather crude counting will do. First, we count the partial Dyck words W of semilength t that can appear in our logs. Each such word has only descents of length 2. They can be mapped to Dyck words of semilength t simply by adding the missing 1s at the end. Notice that each Dyck word of semilength t is the image of at most two such partial Dyck words. (Two of our partial Dyck words have the same image iff they are the same except one ends with 0 and the other ends with 011.) Hence, the number of our partial Dyck words of semilength t is at most twice the number of Dyck words of semilength t, and thus is at most 2 • 4 t .

Next, given a log (W, γ, δ, c ), the indices i ∈ [t] such that γ i = -1 and δ i = -1 correspond to descents of W . Thus there are at most t/2 such indices, and we see that the number of possible pairs (γ, δ) for a given W is at most (2d) t/2 • 2 t/2 = (4d) t/2 ≤ (2∆) t/2 .

Finally, the number of partial edge colourings c of G is at most |E(G)| ∆+q+7 , and is in particular independent of t.

Assuming that ∆ is large enough so that s = 2 ∆ > (32∆) 1/2 , we conclude that

|L t | ≤ 2 • 4 t • (2∆) t/2 • |E(G)| ∆+q+7 = O (32∆) t/2 = o(s t ),
as desired.

93

Conjecture 9 (Mader [START_REF] Mader | Degree and local connectivity in digraphs[END_REF]). For every k ≥ 1, there exists an integer f (k) such that every digraph with minimum outdegree at least f (k) contains a subdivision of T T k , the transitive tournament on k vertices.

A major part of this thesis was devoted to the study of this question, which remains widely open and deserves further research. In Theorem 19 and Theorem 20 we proved the existence of large oriented paths and in-arborescences in digraphs with large minimum outdegree. It might be interesting to generalise these results to other acyclic digraphs, in particular to oriented trees: Problem 21. Let T be an oriented tree. Does there exist a constant a(T ) such that any digraph with minimum outdegree at least a(T ) contains T as a subdivision.

Another interesting case is the one for oriented cycles: Problem 114. Let C be a oriented cycle. Does there exist a constant f (C) such that any digraph with minimum outdegree at least f (C) contains a subdivision of C.

Mader in [START_REF] Mader | Existence of vertices of local connectivity k in digraphs of large outdegree[END_REF] proved the existence of a pair of vertices with connectivity k in digraphs with large minimum outdegree. This means finding k vertex-disjoint dipaths between some pair of vertice x and y. However, forcing the length of these paths seems difficult. We proved in Theorem 84 that digraph with large minimum outdegree contains subdivisions of C(k, k) (the cycle with two blocks of length k). A natural generalisation is the following problem: Problem 115. Let k 1 , k 2 , . . . , k l be positive integers. Does there exist an integer f (k 1 , k 2 , . . . , k l ) such that in any digraph with minimum outdegree at least f (k 1 , k 2 , . . . , k l ) there exist two vertices x and y and a collection of l internally disjoint (x, y)-dipaths P 1 , . . . , P l , such that |P i | ≥ k i for every i ∈ [l].

We do not know about the existence of f (2, 2, 3). One of the difficulties in solving Mader's conjecture is the effect of removing directed paths for connectivity. In the case of undirected graphs, the famous Lovász' path removal conjecture (see [START_REF] Kawarabayashi | A weaker version of Lovász' path removal conjecture[END_REF]) states the following:

Conjecture 116 (Lovász' path removal conjecture). There is an integer-valued function f (k) such that if G is any f (k)-connected graph and x and y are any two vertices of G, then there exists a path P with ends x and y such that G -V (P ) is k-connected.

A weaker version of the conjecture which removes the edges of the path instead of the vertices has been proved by Kawarabayashi et al. in [39]. A similar statement for digraphs has been proved false by Thomassen in [START_REF] Thomassen | Highly connected non-2-linked digraphs[END_REF]. This probably indicates why strengthening the requirement from large minimum outdegree to large connectivity doesn't seem to be helpful for finding a subdivision of T T k . Understanding, which parameters stronger than the minimum outdegree condition can help us in finding transitive tournaments, is an interesting question. Remember that proving the result for large out and indegree would imply Mader's conjecture. On the other hands, it makes the version of the conjecture for oriented trees trivial. It is likely that the key parameter isn't something as symmetrical as k-connectivity. In this regard, Mader's proof of the existence of vertices with high connectivity in digraphs with large minimum outdegree, is interesting to analyse. In the undirected case, by considering the dense part of an (x, y) k-vertex-cut, we can progress towards a k-connected subgraph. In the directed case however, we obtain a digraph with some vertices of degree 0 and for every vertex x with d + (x) > 0, there exists a vertex y such that the connectivity between x and y is greater than k. Another interesting observation is that, despite the fact that we mainly focused on acyclic digraphs, they are not the only possible candidates to be found in all digraphs with large minimum outdegree. For example, by considering a miximal dipath, one can easily show that every digraph with minimum degree at least k contains a directed cycle of length at least k. With constructions given in [START_REF] Devos | Immersing complete digraphs[END_REF] and in [START_REF] Thomassen | Even cycles in directed graphs[END_REF], we have a pretty rough idea of the probable candidates. However the fact that we are not able to give a precise and simple characterisation shows, once again, our lack of understanding. Investigating this question might help us find a key notion for Mader's conjecture.

Another obstacle for Mader's conjecture, and also part of the reason why we believe it is a crucial one, is that the class of digraphs with large minimum outdegree remains a mystery. Let us remind the following conjecture due to Alon in [START_REF] Alon | Disjoint directed cycles[END_REF] and whose difficulty is particularly intriguing:

Conjecture 17 (Alon [START_REF] Alon | Disjoint directed cycles[END_REF]). There exists a function f (k) such that every digraph with minimum degree at least f (k) can be partitioned into two digraphs of minimum outdegree at least k.

We can also cite the following infamous conjecture on the class of digraphs with large minimum degree:

Conjecture 117 (Cacceta-Häggkvist [START_REF] Caccetta | On minimal digraphs with given girth[END_REF]). Every simple digraph of order n with minimum outdegree at least r has a directed cycle with length at most n/r . The case r = n 3 of the conjecture is still open, and is probably the most studied question in structural digraph theory (see [START_REF] Sullivan | A summary of problems and results related to the Caccetta-Häggkvist conjecture[END_REF] for a survey on this conjecture). Thus finding any structure for this class of digraphs is interesting.

In Theorem 86, we proved a weakening of Mader's conjecture, due to DeVos et al., about immersions instead of subdivisions. Proving the conjecture for butterfly-minors (see [START_REF] Kawarabayashi | The directed grid theorem[END_REF] for more details on butterfly-minors), which is another weakening of subdivisions, seems to be an interesting middle step towards Mader's conjecture. Especially since finding a complete graph (or just a dense one) as a minor is an important part of both the proof of Thomas and Wollan of Theorem 16 and the proof of Bollobás and Thomason in [START_REF] Bollobás | Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs[END_REF] that a minimum degree of O(k 2 ) is enough to force a subdivision of the complete graph on k vertices.

Conjecture 118. There exists a function f such that every digraph with minimum outdegree at least f (k) contains a T T k as a butterfly-minor.

  v, d -(v) = |N -(v)| is its size. For a subset of vertices A, let N - A (v) = N -(v) ∩ A and denote by d - A (v) = |N - A (v)|. We also write N -(A) = ∪ x∈A N -(x). The minimum indegree (resp. maximum indegree) of a digraph D, denoted by δ -(D) (resp. ∆ -(D)), is the minimum (resp. maximum) value of d -(v) over all vertices of D. The closed inneighbourhood of v, denoted by N -[v] is defined as N -[v] = N -(v) ∪ {v}. The outneighbourhood of v, denoted by N + (v), is the set of outneighbours of v and the outdegree of v, d + (v) = |N (v)| is its size. For a subset of vertices A, let N + A (v) = N + (v) ∩ A and d + A (v) = |N + A (v)|. We also write N + (A) = ∪ x∈A N + (x). The minimum outdegree (resp. maximum outdegree) of a digraph D, denoted by δ + (D) (resp. ∆ + (D)), is the minimum (resp. maximum) value of d + (v) over all vertices of D. The closed outneighbourhood of a v, denoted by N + [v], is defined as N + [v] = N + (v) ∪ {v}. The underlying graph of a digraph D is the graph obtained from D by forgetting the orientation. The degree of a vertex v in a digraph D is the degree of v in the underlying graph of D. The chromatic number χ(D) of a digraph D is the chromatic number of its underlying graph. The chromatic number of a class of digraphs D, denoted by χ(D), is the smallest k such that χ(D) ≤ k for all D ∈ D. A digraph D is said to be Eulerian if d + (v) = d -(v) for every vertex v. A tournament on k vertices is an orientation of the complete graph on k vertices. The transitive tournament on k vertices, denoted by T T k , is the acyclic tournament on k vertices. The complete digraph on k vertices, denoted by ← → K k is the digraph on k vertices with all possible arcs. A multidigraph is complete if the underlying graph is complete. Let S ⊆ V , we call subdigraph of G induced by S, the digraph D[S] = (S, A ∩ S 2 ). We denote by D -S = D[V \ S]. If B ⊆ A, then D[B] = (V, B) and D \ B = D[A \ B].

Theorem 40 .

 40 Let F be a digraph on n vertices and m arcs. Every digraph D with χ(D) > 4 m (n -1) + 1 contains a subdivision of F .

Definition 52 .

 52 Let H be an r-uniform hypergraph, and let every S ∈ E(H) define a total order on its elements as a bijection σ S : S → [r]. The degree d P (U ) of a set of vertices U ⊆ V (H) with respect to a set of positions P ⊆ [r] (where |P | = |U |) is equal to: d P (U ) = |{S ∈ H : U ⊆ S and σ S (U ) = P }| From there they defined equitable orientations: Definition 53. The orientation of a r-uniform hypergraph H is said to be p-equitable if |d P (U ) -d P (U )| ≤ 1 for any choice of U ⊆ V (H) and P, P ⊆ [r] of cardinality p. It is said to be nearly p-equitable if the looser requirement |d P (U ) -d P (U )| ≤ 2 holds.

  we denote by D the union of the digraphs in D, i.e. V ( D) = D∈D V (D) and A( D) = D∈D A(D). If D is a dipath or a directed cycle, then we denote by D[a, b] the subdipath of D with initial vertex a and terminal vertex b. We denote by D[a, b[ the dipath D[a, b] -b, by D]a, b] the dipath D[a, b] -a, and by D]a, b[ the dipath D[a, b] -{a, b}. If P and Q are two dipaths such that V (P ) ∩ V (Q) = {t(P )} = {s(Q)}, the concatenation of P and Q, denoted by P Q, is the dipath P ∪ Q.

  by assigning the colour 1 to all vertices in V 3-i . Now the function c defined by c(v) = (c 1 (v), c 2 (v)) for all v ∈ V (D) is a proper colouring of D with colour set {1, . . . , χ(D 1 )} × {1, . . . , χ(D 2 )}.

Lemma 65 .

 65 Let D be a digraph, D 1 , . . . , D l be disjoint subdigraphs of D and D the digraph obtained by contracting each D i into one vertex d i . Then χ(D) ≤ χ(D )•max{χ(D i ) | i ∈ [l]}. Proof. Set k 1 = max{χ(D i ) | i ∈ [l]} and k 2 = χ(D ).For each i, let φ i be a proper colouring of D i using colours in [k 1 ] and let φ be a proper colouring of D using colours in[k 2 ]. Define φ : V (D) → [k 1 ] × [k 2 ]as follows. If x is a vertex belonging to some D i , then φ(x) = (φ i (x), φ (d i )), else φ(x) = (1, φ (x)). Let x and y be adjacent vertices of D. If they belong to the same subdigraph D i , then φ i (x) = φ i (y) and so φ(x) = φ(y). If they do not belong to the same component, then the vertices corresponding to these vertices in D are adjacent and so φ(x) = φ(y). Thus φ is a proper colouring of D using k 1 • k 2 colours.

Theorem 69 .

 69 Let k ≥ 3 be an integer and let D be a strong digraph. If χ(D) > (2k -2)(2k -3), then D contains a subdivision of B(k, 1; 1). Let C be a collection of directed cycles. It is nice if all cycles of C have length at least 2k -2, and any two distinct cycles of C intersect on at most one vertex. A component of C is a connected component in the adjacency graph of C, where vertices correspond to cycles in C and two vertices are adjacent if the corresponding cycles intersect. Note that if S is a component of C, then S is both a connected component and a strong component of C. For sake of simplicity, we denote by D[S] the digraph D[ S]. Observe that this digraph contains S but has more arcs.

Lemma 70 .

 70 Let C be a nice collection of directed cycles in a B(k, 1; 1)-subdivision-free digraph D and let C, C be two cycles of the same component S of C. There is no dipath P from C to C whose arcs are not in A( S).

Lemma 71 .

 71 Let k ≥ 3 be an integer, and let C be a nice collection of directed cycles in a B(k, 1; 1)-subdivision-free digraph D and S a component of C. Then χ(D[S]) ≤ 2k -2.Proof. By induction on the number of directed cycles in S. Let C be a cycle of S. There is no chord (x, y) of C such that C[x, y] has length at least k, for otherwise there would be a B(k, 1; 1)-subdivision. Hence D[C] has maximum degree at most 2k -2. Moreover, by Proposition 66, D[C] is not a tournament of order 2k -1. Thus, by Brooks' Theorem[START_REF] Sauer | On the density of families of sets[END_REF],χ(D[C]) ≤ 2k -2.Let c be a proper colouring of C with 2k -2 colours. Let S 1 , S 2 , . . . , S r be the components of S \ {C}. Since S is the union of the S l for l ∈ [r], and {C}, each S l has less cycles than S. By the induction hypothesis, there exists a proper colouring c l using 2k -2 colours for each D[S l ]. Now, we claim that each D[S l ] intersects C in exactly one vertex. It is easy to see that C must intersect at least one cycle of each S l . Now suppose there exist two vertices of C, x and y, in D[S l ]. By definition of a nice collection, they cannot belong to the same cycle of S l , so there exist two cycles C i and C j of S l such that x ∈ C i and y ∈ C j . Now C[x, y] is a dipath from C i to C j whose arcs are not in A( S l ). This contradicts Lemma 70.Consequently, free to permute the colours of c l , we may assume that each vertex of C receives the same colour in c and in c l . In addition, byLemma 70, there is no arc between different D[S l ] nor between D[S l ] and C. Hence the union of c l and c is a proper colouring of D[S] using 2k -2 colours. Lemma 72. Let C be a maximal nice collection of directed cycles in a B(k, 1; 1)-subdivisionfree strong digraph D and D C the digraph obtained from D by contracting each component of C into one vertex. Then χ(D C ) ≤ 2k -3.

Corollary 75 .

 75 Let C be a k-suitable collection of directed cycles and let C 1 ∈ C.

  (i) I + (C 1 ) and I -(C 1 ) are vertex-disjoint digraphs.

Proof.

  By induction on the number of directed cycles in C. Consider a rainbow-colouring of a subdipath of length less than 7k of a directed cycle C 1 ∈ C. By Lemma 78, we can extend this colouring to a colouring φ 1 of I(C 1 ) at most α k colours. Note that the non-coloured vertices of C are in one of the connected components of C -I(C 1 ). Let A be a connected component of C -I(C 1 ). The coloured (by φ 1 ) vertices of C ∩ A are those of (C ∩ A) -A. Hence, by Lemma 76, they all belong to some directed cycle C j and so to the dipath Q j which has length at most 7k. Hence, by the induction hypothesis, we can extend φ 1 to A. Doing this for each component, we extend φ 1 to the whole C.Set β k = k(4k 2 + 2)(2 • (4k) 4k + 1)α k .The second step of the proof is the following lemma. Lemma 80. Let C be a k-suitable collection of directed cycles in a B(k, 1; k)-subdivision-free digraph D. For every component S of C, we have χ(D[S]) ≤ β k .

Lemma 82 .

 82 Let D be a digraph with |A(D)| ≥ 1, let S ⊆ V (D) be a nonempty subset of vertices of indegree 0 in D, and let T ⊆ V (D) such that T ∩ S = ∅. If d + (v) ≥ ∆ -(D) for all v ∈ V (D) \ T , then there exist |S| vertex-disjoint (S, T )-dipaths in D.

Claim 83. 1 .

 1 If δ + (H) ≥ t(k, )/b(k -1, ), then D contains a subdivision of B(k, ).

  by modifying the graph G as follows. Let G be the multigraph obtained from G by contracting each edge uv ∈ E(G) such that d G (u) < d and d G (v) < d but neither u nor v has any other neighbour w with d G (w) < d. Then G has maximum degree ∆ and maximum edge multiplicity at most 2. Every proper edge colouring c of G can be extended to a proper edge colouring c of G with the same set of colours as follows: For each edge e ∈ E(G) appearing in G , set c(e) := c (e). For each edge uv ∈ E(G) that was contracted, we know that d G (u) + d G (v) < ∆. Thus some colour α of c is not used on any of the edges incident to u and v, set then c(uv) := α.

Figure 5 . 1 :

 51 Figure 5.1: The five types of bad events in Algorithm 4. Bad edges are drawn in bold. (Note that possibly z = u in Bad Event 5.)

2 .

 2 At least one of U -(v), U -(w) is empty for each fragile edge vw.

3 .

 3 Bad edges form a matching. 4. If w, x ∈ B belong to distinct bad edges, then ({w} ∪ U + (w)) ∩ ({x} ∪ U + (x)) = ∅. 5. Every u ∈ B with U + (u) = ∅ has at least s admissible pairs.

• l 3 = 3 and w 3 = 2 7 ∆ 3 d 2 • l 4 = 4 and w 4 = 2 12 ∆ 4 d d 2 • l 5 = 5 and w 5 = 2 11 ∆ 4 d 2 d 2

 332244225522

5 i=1w

 5 21, Section 1.2]. Let y(x) := t≥1 C t,E x t denote the generating function associated to our objects, and let φ(x) := 1 + i x l i .

  Claims 61.1, 61.2, 61.3, and 61.4, together with Lemma 59 yield the result.

		),
	a contradiction.	♦

  and since D 2 -V 0 is acyclic, it is 2-degenerate and thus 3-colourable. Therefore χ(D 2 ) ≤ 4.

♦ Claims 62.1, 62.2, 62.3, and Lemma 59 implies χ(D) ≤ 24.

  s 1,2 ] and C 3 [v, s 1,3 ] both have length less than 3k.Proof. Observe first that since C 2 has length at least 8k and P 1,2 has length at most k -1, the sum of the lengths of C

2 [t 1,2 , v] and C[v, s 1,2 ] is at least 7k + 1.

Similarly, the sum of the lengths of C 2 [t 1,3 , v] and C[v, s 1,3 ] is at least 7k + 1. In particular, if (i) holds, then (ii) does not hold and vice-versa.

  In particular, P 1,2 , P 1,3 , and P 2,3 are disjoint. The dipath C 2 [s 1,2 , t 2,3 ] has length at least 3k because it contains C 2 [t 1,2 , v]. Moreover, the dipath C 3 [t 2,3 , s 1,3 ] has length at least 2k because C 3 [v, s 1,3 ] has length at least 3k and C 3 [v, t 2,3 ] has length less than k. Thus C 3 [t 2,3 , s 1,3 ] C 1 [s 1,3 , s 1,2 ] has length at least 2k. Consequently, the union of C 2 [s 1,2 , t 2,3 ], C 2 [t 2,3 , s 1,2 ], and

  are called fake arcs. Clearly, φ + exists if and only if D + 1 admits a proper (6k 2 ) 3k -colouring. Henceforth it remains to prove the following claim. To each vertex v in I + (C 1 ) we associate the set Dis(v) of the lengths of the C j [t 1,j , v] for all directed cycles C j ∈ C ∩ C 1 containing v such that C j [t 1,j , v] has length at most 3k.

	Subproof.
	Claim 78.1. χ(D + 1 ) ≤ (6k 2 ) 3k .

  Lemma 93. Let S be a set of size 2s and S = (A, B) a random bipartition such that |A| = |B| = s and G a subset of S of size t. Then P r[|G ∩ A| < t/4 or |G ∩ B| < t/4] < t 4 (2/3) t/4 . Proof. By considering the set between A and B with the smallest intersection with G, we get the following bound: Because the VC-dimension of R is bounded by 25t, by Lemma 48 there are at most ( er 25t ) 25t possible inneighbourhoods S and by the union bound, P r[C] ≤ (276/t 2 ) t 2 /276 ( et 575 ) 25t +

	t 2 100 (2/3) t 2 /100 .	♦
	Finally, because l ≤ 2t, we have
	t/4 i=0 t/2 i=0 P r[E 0 ] ≤ (276/t 2 ) t 2 /276 ( t i 2s-t s-i t i 2s-t s-i ≤ t/4 i=0 t/2 i=t/4 et 575	t i ) 25t + 2s-t s-i t i 2s-t s-i t 2 100 ≤ (2/3) t 2 /100 + 2t(2(3/4) t/100 t 3 + t/4 i=0 t i t/2 i=t/4 t i ≤ t 4 t t/4 t t/2 ≤ t 4 t/4 . . . t/2 t/2 . . . 3t/4 t 4 (2/3) t/4 .

  10 d d 2 . j = 5: We let γ i ∈ [2∆ 5 ] encode the vertices v, w, x, y, z. (Recall that possibly z = u.) Since u, v, w, x, y are reset during this iteration, we have B i+1 = B i ∪ {v, w, x, y}.Next, we encode U + i and r i based on U + i+1 . Again, we encode the admissible pair {u 1 , u 2 } chosen for u explicitly ( d 2 choices), which will determine r i once we know U + i . It only remains to encode U

q possibilities. To encode this we need to give two information: the vertex v and neighbours of v for which we deleted the choices of U . Because the bad event occurs when a vertex x of N (v) chooses v in U (x), describing v is just describing for which neighbour of x the

t i=1 x i , G contains a path P + (x 1 , x 2 , . . . , x t ) starting at any vertex of G such that x i ≥ x i if i is odd, and x i = x i otherwise.

Acknowledgements

Firstly, I would like to express my sincere gratitude to András and Bojan for their careful reading and comments that helped improve the presentation of this thesis. I would also like to thank Daniel, Ioan and Victor for accepting to be part of my committee.

Je voudrais ensuite remercier Fred et Stéphan pour ces trois années à travailler a vos côtés. Que ce soit humainement, ou scientifiquement, j'ai apprecié chaque discussion que j'ai pu avoir avec vous deux. Par vos questions, vous m'avez donné l'occasion de réfléchir à de superbes problèmes, et c'est la, à mon sens, le but principal d'une thèse.

Because a thesis consists mostly of hours spent on the board discussing maths with other people, I would like to thank all the people I was lucky enough to work with since I entered this wonderful world of graph theory: Anders, Cyril, Gwen, Marthe, Nicolas B., Nicolas N., Peter, Pierre A., Pierre C., Phablo, Raul, Stéphane B., Stéphane P. and Tash. A ce sujet, je remercie tout particulierement Nathann pour ces heures passées à réfléchir et me raconter des théorèmes.

Je remercie toute l'equipe COATI pour sa bonne humeur, sa gentillesse, ses discussions foot, ses discussions vélo, le tout enrobé en permanence d'un leger ésprit taquin. Une mention particulière pour l'équipe du 230 de m'avoir supporté tous ces trajets.

Je remercie aussi l'equipe MC2 pour sa passion de l'informatique, sa convivialité, ses potins arrachés à Nicolas, les bières partagées au foyer avec Michael et ses petits, ainsi que les nombreux restos ou Rosi, Tash et Nam ont bien voulu m'accompagner.

I would also like to say thank you to all the PhD students who had to live with my grumpiness for these three years: Alex, Andrea, Fionn, Guillaume, Nicolas, Phablo, Sebastian, Tim. Thank you Matthieu, Nam and Romain for being such great friends.

Finalement je tiens à remercier mes parents, mon frère, ainsi que toute ma famille pour m'avoir soutenu depuis toutes ces années.

Claim 61.2. χ(D 1 ) ≤ k + -3.

Subproof. Let φ 1 be the colouring of D 1 defined by φ 1 (x) = lvl(x) (mod k + -3). By definition of D 1 , this is clearly a proper colouring of D 1 . ♦ Claim 61.3. χ(D 2 ) ≤ 2 + 2.

Subproof. Suppose for a contradiction that χ(D 2 ) ≥ 2 + 3. By Theorem 27, D 2 contains a copy Q of P -( + 1, + 1), which is the union of two dipaths which are disjoint except in there initial vertex y, say Q 1 = (y 0 , y 1 , y 2 , . . . , y +1 ) and Q 2 = (z 0 , z 1 , z 2 , . . . , z +1 ) with y 0 = z 0 = y. Since Q is in D 2 , all vertices of Q belong to T [u, y]. Without loss of generality, we can assume z 1 ≥ T y 1 .

If z +1 ≥ T y +1 , then let j be the smallest integer such that z j ≥ T y +1 . Then the union of T [y 1 , y] Q 2 [y, z j ] T [z j , y +1 ] and Q 1 [y 1 , y +1 ] is a subdivision of C(k, ), because T [y 1 , y] has length at least k -2 as lvl(y) ≥ lvl(y 1 ) + k + -3. This is a contradiction.

Henceforth y +1 ≥ T z +1 . Observe that all the z j , 1 ≤ j ≤ + 1 are in T [y +1 , y 1 ]. Thus, by the Pigeonhole principle, there exists i, j ≥ 1 such that y i+1 ≥ T z j+1 ≥ T z j ≥ T y i ≥ T z j-1 .

If lvl(z j-1 ) ≥ lvl(y i ) + -1, then T [y i , z j-1 ] (z j-1 , z j ) has length at least . Hence its union with (y i , y i+1 ) T [y i+1 , z j ], which has length greater than k, is a subdivision of C(k, ), a contradiction.

Thus lvl(z j-1 ) < lvl(y i ) + -1 (in particular, in this case, j > 1 and i > 2). Therefore, by definition of A , lvl(y i ) ≥ lvl(z j ) + k -1 and lvl(y i-1 ) ≥ lvl(z j-1 ) + k -1. Hence both T [z j-1 , y i-1 ] and T [z j , y i ] have length at least k -1. So the union of T [z j-1 , y i-1 ] (y i-1 , y i ) and (z j-1 , z j ) T [z j , y i ] is a subdivision of C(k, k) (and thus of C(k, )), a contradiction. ♦ Claim 61.4. χ(D 3 ) ≤ k + + 1.

Subproof. In this claim, it is important to note that k + -3 ≥ k -1 because ≥ 2. We use the fact that lvl(x) -lvl(y) ≥ k -1 if (x, y) is an arc in A 3 .

Suppose for a contradiction that χ(D 3 ) ≥ k + + 1. By Theorem 27, D 3 contains a copy Q of P -(k, ) which is the union of two dipaths which are disjoint except in there initial vertex y, say Q 1 = (y 0 , y 1 , y 2 , . . . , y k ) and Q 2 = (z 0 , z 1 , z 2 , . . . , z ) with y 0 = z 0 = y.

Assume that a vertex of Q 1 -y is an ancestor of y. Let i be the smallest index such that y i is an ancestor of y. If it exists, by definition of A 3 , i ≥ 2. Let x be the common ancestor of y i and y i-1 in T . By definition of A 3 , y i is not an ancestor of y i-1 , so x is different from y i and y i-1 . Moreover by definition of A , lvl(y) -k ≥ lvl(y i-1 ) -k ≥ lvl(y i ) -1 ≥ lvl(x). Hence T [x, y i-1 ] and T [x, y] have length at least k. Moreover these two dipaths are disjoint except in x. Therefore, the union of T [x, y i-1 ] and T [x, y] Q 1 [y, y i-1 ] is a subdivision of C(k, k) (and thus of C(k, )), a contradiction.

Similarly, we get a contradiction if a vertex of Q 2 -y is an ancestor of y. Henceforth, no vertex of V (Q 1 ) ∪ V (Q 2 ) \ {y} is an ancestor of y.

Let x 1 be the least common ancestor of y and y 1 . Note that |T [x 1 , y]| ≥ k so |T [x 1 , y 1 ]| < k, for otherwise G would contain a subdivision of C(k, k). Therefore lvl(y 1 ) -lvl(x 1 ) < k. We define inductively x 2 , . . . , x k as follows: x i+1 is the least common ancestor of x i and y i+1 . Subproof. We need to prove that D 0 (c) has no arc. Suppose for a contradiction that (x, y) is an arc of D 0 (c). By definition of D 0 , the vertices x and y are in a same level L i . Let C l and C m be two directed cycles of L i such that x ∈ C l and y ∈ C m .

If C l = C m , then both C l [x, y] and C l [y, x] have length at least 7k because the subdipaths of length 7k of C l are rainbow-coloured by φ. Hence the union of those paths and (x, y) is a B(k, 1; k)-subdivision, a contradiction. Henceforth, C l and C m are distinct directed cycles.

Suppose first that C l and C m intersect. By Claim 80.2, s l,m belongs to P - l , P + l or L i-1 , and by construction of R l , C l [x, s l,m ] and C l [s l,m , x] are both longer than k. Therefore they form with (x, y) C m [y, s l,m ] a B(k, 1; k)-subdivision, a contradiction.

Suppose now that C l and C m do not intersect. Let C l and C m be the fathers of C l and C m respectively. Let P be the dipath from s m,m to s l,l in j<i L j . Then the union of C l [s l,l , x], (x, y) C m [y, s m,m ] P , and C l [x, s l,l ] is a B(k, 1; k)-subdivision, a contradiction. ♦ Claim 80.5. χ(D + 0 (c)) ≤ (4k) 4k for every c ∈ [α k ].

Subproof. Set p = (4k) 4k . Suppose for a contradiction that there exists c such that χ(D + 0 (c)) > p. Observe that D + 0 (c) is the disjoint union of the D[X + i (c)]. Thus there exists a level L i 0 such that χ(D[X + i (c)]) > p. Moreover i 0 > 0, because the vertices of C 0 coloured c form a stable set. By Theorem 26, there exists a dipath P = (v 0 , . . . , v p ) of length p in D[X + i (c)]. Suppose that P contains two vertices x and y of a same directed cycle C of S. Without loss of generality, we may assume that P ]x, y[ contains no vertices of C. Now both C[x, y] and C[y, x] have length at least 7k because the subdipaths of length 7k of C are rainbowcoloured by φ. Thus the union of C[x, y], P [x, y] and C[y, x] is a B(k, 1; k)-subdivision, a contradiction. Hence P intersects every directed cycle of S at most once.

For every v ∈ V (P ), let Len(v) be the set of lengths of C l [t l,l , v] for all directed cycles C l ∈ L i 0 containing v and whose father is C l .

For

. By definition M j ≤ 2k. Applying Lemma 68 to (M j ) 1≤j≤4k 2 , we get a sequence of size 2k M j 0 +1 , . . . , M j 0 +2k such that M j 0 +2k is the greatest. For sake of simplicity, we set i = j 0 + i for 1 ≤ i ≤ 2k. Let f be the smallest index not smaller than 2k for which M 2k ∈ Len(v f ).

Let j 1 and j 1 be indices such that

. Note that any internal vertex x of P 1 or P 2 has an integer in Len(x) which is smaller than m and every internal

Proof of Theorem 37

Consider a maximal k-suitable collection C of directed cycles in D. Recall that D C is the digraph obtained by contracting every component of C into one vertex. For each connected component S i of C, we denote by s i the new vertex created.

Claim 80.6. χ(D C ) ≤ 8k.

Proof. First note that since D is strong so is D C .

Suppose for a contradiction that χ(D C ) > 8k. By Theorem 31, there exists a directed cycle C = (x 1 , x 2 , . . . , x l , x 1 ) of length at least 8k. For each vertex x j that corresponds to an s i in D, the arc (x j-1 , x j ) corresponds in D to an arc whose head is a vertex p i of S i and the arc (x j , x j+1 ) corresponds to an arc whose tail is a vertex l i of S i . Let P j be the dipath from p i to l i in C. Note that this dipath intersects the elements of S i only along a subdipath. Let C be the directed cycle obtained from C where we replace all contracted vertices x j by the dipath P j . First note that C has length at least 8k. Moreover, a directed cycle of C can intersect C only along one P j , because they all correspond to different strong components of C. Thus C intersects each directed cycle of C on a subdipath. Moreover this subdipath has length less than k for otherwise D would contain a B(k, 1; k)-subdivision. So C is a directed cycle of length at least 8k which intersects every directed cycle of C along a subdipath of length less than k. This contradicts the maximality of C.

Using Lemma 65 with Claim 80.6 and Lemma 80, we get that χ(D) ≤ 8k • β k . This proves Theorem 37 for

Subdivisions in digraphs with large dichromatic number

and that the dichromatic number of D, noted χ(D), is the minimum k such that D admits a k-dicolouring.

We present here a proof of the following Theorem, obtained in [START_REF] Aboulker | Subdivisions in digraphs of large out-degree or large dichromatic number[END_REF].

Theorem 40. Let F be a digraph on n vertices and m arcs. Every digraph D with χ(D) > 4 m (n -1) + 1 contains a subdivision of F .

The proof uses induction on m with the following lemma providing the induction step.

Lemma 81. Let F be a digraph and let a = (x, y) be an arc in A(F ). Suppose there exists a constant c such that any digraph D with χ(D) ≥ c contains a subdivision of F -a. Then any digraph D with χ(D) ≥ 4c -3 contains a subdivision of F .

Proof. Let D be a digraph with χ(D) ≥ 4c-3. We shall prove that D contains a subdivision of F .

Cycles with two blocks

Recall that C(k 1 , k 2 ) is the oriented cycle with two blocks, one of length k 1 and one of length k 2 . It can also be seen as the union of two internally disjoint dipaths, one of length k 1 and one of length k 2 with the same initial vertex and same terminal vertex.

Theorem 84. Let D be a digraph with

Proof. Let us assume, without loss of generality, that k 1 ≥ k 2 . Let be a positive integer. An ( , k 1 , k 2 )-fork is a digraph obtained from the union of three disjoint dipaths

) by adding the arcs (a , b 1 1 ) and (a , b 2 1 ). Since a (1,

-fork as a subdigraph by a greedy argument. Let ≥ 1 be the largest integer such that D contains an ( , k 1 , k 2 )-fork as a subdigraph. Let F be such a fork. For convenience, we denote its subpaths and vertices by their labels in the above definition.

If there exist i, j ∈ [ -1] ∪ {0}, where i ≤ j (resp. j ≤ i), such that

Let i 1 ≥ 1 be the largest integer such that there exist two disjoint dipaths C 1 and C 2 in D -F with initial vertex c 1 1 and c 2 1 , respectively, and length i 1 and i 2 = min{k 2 , i 1 }.

) would contain an ( + k 1 -1, k 1 , k 2 )-fork, contradicting the maximality of .

Suppose to the contrary that none of c 1 i 1 and

. This contradicts the maximality of i 1 . Henceforth, we assume that c 1 i 1 has an outneighbour a j ∈ A \ {a } for some 0 ≤ j < . The case in which c 2 i 2 has an outneighbour in A \ {a } is similar. If also b 2 k 2 -1 has an outneighbour a m ∈ A\{a }, then the union of the dipaths (a , B 1 , C 1 , a j , . . . , a m ) and (a

So, we may assume that b

has two distinct outneighbours, say c 3 1 and c 4 1 , not in F ∪ C 1 ∪ C 2 . Let i 3 ≥ 1 be the largest integer such that there exist two disjoint dipaths C 3 and C 4 in D -(F ∪ C 1 ∪ C 2 ) with trivial because F (1, l) is one vertex. Suppose now that the result holds for k and assume for a contradiction that it does not hold for k + 1. Let D be the multidigraph with the smallest number of arcs and vertices such that D has multiplicity at most (k + 1)l, all but at most c 1 = k + (k + 1)l vertices have outdegree at least h(k + 1, l) and without an immersion of F (k + 1, l). By minimality of D, every vertex has outdegree exactly h(k + 1, l), except c 1 of them with outdegree 0. Call T the set of vertices of outdegree 0. Suppose we want to remove arcs from D such that the multiplicity of the remaining digraph is at most kl, while keeping the minimum outdegree as large as possible. For a vertex v, the worst case is when, for every vertex y ∈ N + (v), the multiplicity of (v, y) is equal to (k + 1)l. In this case we have to remove at most l arcs for each of the h(k+1,l) (k+1)l vertices of N + (v). Therefore, by removing T and these parallel arcs, we obtain a multidigraph of outdegree greater than

, we get that d ≥ h(k, l) and by induction there exists an immersion of

the set of vertices of the immersion and P i,j the jth directed path of this immersion from x i to x i+1 . We can assume this immersion is of minimum size, so that every vertex in P i,j has exactly one outgoing arc in P i,j . Let D be the multidigraph obtained from D by removing all the arcs of the P i,j and the vertices x 1 , . . . , x k-1 . By the previous remark, the outdegree of each vertex in D is either 0 if this vertex belongs to T or at least h(k

For every vertex y ∈ D -x k , there do not exist l arc-disjoint directed paths from x k to y in D , for otherwise there would be an immersion of F (k + 1, l) in D. Hence, by Menger's Theorem there exists a set E y of less than l arcs such that there is no directed path from x k to y in D \ E y . Define C y for every vertex y ∈ D -x k as the set of vertices which can reach y in D \ E y . Now take Y a minimal set such that ∪ y∈Y C y covers D -x k . We claim that Y consists of at least c 2 ≥ h(k+1,l)-(k-1)l-(k-1)(k+1)l l ≥ 2c 1 elements, as ∪ y∈Y E y must contain all the arcs of D with x k as tail.

For each y ∈ Y , define S y as the set of vertices which belong to C y and no other C y for y ∈ Y . Since Y is minimal, every S y is non-empty. Note that for u ∈ S y , if there exists y ∈ Y \ y and v ∈ C y such that uv ∈ A(D), then uv ∈ E y . Note that T ⊂ Y as vertices in T have outdegree 0 and if y ∈ Y \ T then S y consists only of vertices of outdegree h(k + 1, l) in D.

Let R be the digraph with vertex set Y and arcs from y to y if there is an arc from S y to C y . As noted before,

Let y be a vertex of R \ T with outdegree at most this average. Let H be the digraph induced on D by the vertices in S y to which we add X, all the arcs that existed in D (with multiplicity) from vertices of S y to vertices of X and the following arcs: For each P i,j , let z 1 , z 2 , . . . , z l = P i,j ∩ S y , where z i appears before z i+1 on P i,j and add all the arcs (z i , z i+1 ) to H. Note that, if (x, y) is an arc of D , then by minimality of the immersion of F (k, l), every time x appears before y on some P i,j , then P i,j uses one of the arcs (x, y). Thus for each pair of vertices x and y in H, either (x, y) ∈ A(D) and the number of (x, y) arcs in H is equal to the one in D, or (x, y) ∈ A(D) and the number of (x, y) arcs in H is bounded by (k -1)l. This implies that H has multiplicity at most (k + 1)l.

Claim 86.1. H is a multidigraph with multiplicity at most (k + 1)l, such that all but at most c 1 vertices have outdegree greater than h(k + 1, l) and H does not contain an immersion of

Proof of the claim. Suppose H contains an immersion of F (k + 1, l), then by replacing the new arcs by the corresponding directed paths along the P i,j we get an immersion of F (k + 1, l) in D. Moreover, we claim that the number of vertices in H with outdegree smaller than h(k + 1, l) is at most k + 2l + (k -1)l = c 1 . Indeed, the vertices of H that can have outdegree smaller in H than in D are the x i , or the vertices with outgoing arcs in E y for some y ∈ Y \ y, or the vertices along the P i,j . But with the additions of the new arcs, we know that there is at most one vertex per path P i,j that loses some outdegree in H.

However, since H is strictly smaller than D, we reach a contradiction.

Chapter 4

The Erdős-Sands-Sauer-Woodrow conjecture All the proofs in this chapter are joint work with Nicolas Bousquet and Stéphan Thomassé.

In this chapter we will present a proof of conjecture 44:

The first part of this chapter is dedicated to the proof of the case k = 3 of Conjecture 45:

Proposition 87. There exists an integer C such that every 3-transitive tournament T has γ(T ) ≤ C.

While Proposition 87 is much weaker than Theorem 49, we decided to present it for two reasons. First it uses a new variation of the VC-dimension technique that we find interesting and could be applied to prove other results, and second it provides a context onto how we arrived to the short and simple proof of Theorem 49.

Domination in 3-transitive tournaments

In this section, T is a 3-transitive tournament. We will prove that T has bounded domination number.

By definition, A(T ) decomposes into three sets, R, G and B such that T [R], T [G] and T [B] are quasi-orders. We will use the colours red, blue and green to speak about the sets R, G and B, respectively. A chain is a monochromatic subtournament of T . As a chain is a transitive tournament, we will refer to a chain as its directed Hamiltonian path x 1 , . . . , x k .

Remember that the VC-dimension of a tournament is the VC-dimension of the inneighbourhood hypergraph. It is not very difficult to see that a 3-transitive tournament does not necessarily have bounded VC-dimension. For example, if you take two red chains such that all the arcs from one chain to the other are blue and the arcs in the other direction are green, Proof. Suppose C is a red chain. Without loss of generality, we can assume that (u, x i ) and (v, x j ) are blue and (x i , v) and (x j , u) are green and moreover that (u, v) belongs to T . If (u, v) is blue, then by transitivity (u, x j ) belongs to T . Likewise, if (u, v) is green then (x j , v) belongs to T . This means that (u, v) is red.

Lemma 90. Let T be a 3-transitive tournament and S a set of vertices of T such that S is a shattered set of the inneighbourhood hypergraph of T . Then T [S] cannot have two chains of length 6 of different colours.

Proof. Suppose it does and let C 1 = (c 1 0 , . . . , c 1 5 ) and C 2 = (c 2 0 , . . . , c 2 5 ) be those two chains. For each i ∈ [2], we define 5 sets of vertices of G(C i ):

The purpose of these sets is that, if there exist two vertices, say a and b, such that a ∈ A 1 ∩ A 2 and b ∈ B 1 ∩ B 2 and these vertices have the same type towards C 1 and C 2 , then we reach a contradiction. Indeed ac 1 2 bc 1 3 and ac 2 2 bc 2 3 are directed cycles, but since C 1 and C 2 are two chains of different colours, then Lemma 89 implies that the arc between a and b has two different colours, which is impossible.

To find two vertices like this, we use the fact that the set is shattered. Because the set is shattered, it means that for every possible subset S of S, there exists a vertex x in T such that the inneighbourhood of x in S is precisely S (and thus the outneighbourhood is precisely S \ S ). This means that we can find five vertices: a (resp. b, l, d, e) that belongs to

. Now each of these vertices has one of two specific types regarding C 1 and C 2 , this means there are 4 combinations of types. By the Pigeonhole Principle, we can find two vertices, say a and b such that they both have the same type towards C 1 and the same type towards C 2 . This ends the proof.

Dominating shattered sets

Let u and v be two vertices of a 3-transitive tournament T , define S(u, v) as the set of vertices x such that there exist two disjoint vertices u 1 = u 1 (x), u 2 = u 2 (x), such that u, u 1 , v, u 2 is a monochromatic chain (in that order), x dominates u and v and x is dominated by the u i .

Lemma 92. Let T be a 3-transitive tournament. For every pair of vertices u and v of T , there exists a set φ(u, v) of four vertices which dominates S(u, v).

Proof. Without loss of generality we can assume that (u, v) is a blue arc. Let x be a vertex of S(u, v) and u 1 , u 2 the vertices completing the blue chain, then one of the following is true:

(i) The arcs (u i , x) are green and the arcs (x, u) and (x, v) are red; or (ii) the arcs (u i , x) are red and the arcs (x, u) and (x, v) are green.

To prove this, first note that none of the arcs (u i , x), (x, u) or (x, v) can be blue. Indeed, if (x, u) or (x, v) is blue, then (x, u 2 ) must be an arc, and if (u 1 , x) or (u 2 , x) is blue, then (u, x) must be an arc. Finally, since uu 1 vu 2 is a blue chain, (x, u) and (x, v) must have different colour than (u 2 , x) and (u 1 , x).

Consider S 1 the set of vertices of S(u, v) such that (i) is true and let

) is a blue arc by transitivity with v. Now let x ∈ S 1 , we claim that for every y in U 1 , either the arc (y, x) exists and is green or the arc (x, y) exists and is red. Indeed if (y, x) is blue, then (u, x) must be blue, if (x, y) is blue then (x, v) must be blue, if (x, y) is green then (u 2 (x), y) must be green and if (y, x) is red then (y, u) must be red. In all cases, this is a contradiction. The same can be said with U 2 , so we have the following property: For every vertex x ∈ S 1 , the set of arcs A(x, U 1 ∪ U 2 ) is red and the set of arcs A(U 1 ∪ U 2 , x) is green. This means that for any x 1 and x 2 two different vertices of S 1 , if the arc (x 1 , x 2 ) is red then by transitivity

and (x, y) is a blue arc of T if it is a blue arc of T . T satisfies the hypothesis of Theorem 42 and therefore has a dominating vertex x, and thus, in T , {x} ∪ u 1 (x) dominates S 1 .

By doing the same thing with the set of vertices such that (ii) is true, we obtain a set of four vertices dominating S(u, v).

For a set X, let φ(X) be the union of all the φ(x, y) for x and y in X.

Sampling argument

We are now ready to prove Proposition 87. Basically we will show that, if we take a set of vertices S of a certain size at random, then with positive probability S ∪φ(S) is a dominating set of T .

We need the following (not tight) lemma:

We first show the case where every vertex has large indegree.

Proposition 94. There exists a constant C such that any 3-transitive tournament T with minimum indegree greater than |T |/6 has domination number bounded by C.

Proof. Let t be an integer and let A be a random set of vertices picked by t 2 independent random draws, where each element is drawn from V (T ) uniformly. The goal is to show that A ∪ φ(A) is a dominating set with positive probability when t is big enough (but still a constant). Suppose A ∪ φ(A) is not a dominating set and let B be another random set obtained by picking t 2 vertices randomly. Formally, we regard A and B as sequences of elements of T , with possible repetitions. So A = (a 1 , . . . , a t 2 ) and B = (b 1 , . . . , b t 2 ). For a sequence S = (s 1 , . . . , s l ), |S| will denote the number of elements in the sequence. Abusing the notation slightly, d - S (u) will denote the number of indices i ∈ [l] such that s i ∈ N -(u), so one vertex could count multiple times. Let E 0 be the event "there exists a vertex u such that u dominates A∪φ(A) and d - B (u) ≥ t 2 /12". Since we assumed that A∪φ(A) is not a dominating set, there exists a vertex u dominating this set. Hence P r[E 0 ] ≥ P r[d - B (u) ≥ t 2 /12]. Since d -(u) ≥ n/6, the following claim can be proved with Chebyshev's inequality (see Lemma 10.2.6 of [START_REF] Matousek | Lectures on Discrete Geometry[END_REF] for the complete proof) Claim 94.1. P r[E 0 ] ≥ 1/2. Now we are going to bound P r[E 0 ] differently. First let N = (z 1 , . . . , z 2t 2 ) be a random sequence of 2t 2 elements chosen uniformly. In a second stage, we randomly chose t 2 positions in N and put the elements at these positions in A, and the remaining elements in B. The resulting distribution of A and B is the same as the one described before. We now prove that the probability of E 0 is small. To do so, consider the set N corresponding to the elements of N (so removing repetitions). If this set has VC-dimension bounded by 25t, it means we can do the same proof as the -net Theorem and prove that P r[E 0 ] is smaller that 1/2. If the VC-dimension is not bounded by 25t, then by Lemma 91, there exists a shattered chain of length t. Let T 1 , . . . , T l be a maximal collection of disjoint subsequences of N , such that the elements of each T i forms a shattered chain of length t in N , without repetition. This means that one element can belong to different chains if it appeared multiple times in N . Note that l ≤ 2t. Let R = N \ ∪ i T i be the remaining subsequence of N . Note that, if we note R the set of elements contained in R, then R has VC-dimension bounded by 25t.

For each i ∈ [l], let L i be the event: "there exists a vertex x with d - T i (x) ≥ t/48 and the random partition of N is such that x is not dominated by A ∩ T i ∪ φ(A ∩ T i )". Let C be the event:"|R| > t 2 23 , there exists a vertex x with N - R (x) > |R|/12 and the random cut is such that x is not dominated by A ∩ R". Remember that E 0 is the event that there exists a vertex u such that u dominates A ∪ φ(A) and d We can suppose that t is big enough so that this value is bounded by (3/4) t/100 , and the probability that one of the two sets is avoided is then smaller than 2(3/4) t/100 . Overall, since there are at most t 3 choices for the positions of the first, middle and last inneighbour on T i , we get that (2/3) t 2 /100 . If we look at the trace of the inneighbourhood hypergraph on R, it has VCdimension bounded by 25t by Lemma 91. Fix the inneighbourhood S of x in R, then the probability P S = P r[S ∩ A = 0|R 1 ] is at most the probability that a random sample of r/4 elements avoids the r/12 elements of S so:

Proof. Let w A : A → [0, 1] and w B : B → [0, 1] be the probability distributions such that w A (N -[x]) ≥ for every x ∈ B and w B (N -[x]) ≥ for every x ∈ C. Let g( ) = ln( ) ln(1-) + 1 and pick independently at random according to the distribution w A a (multi)set S of g( ) elements of A. For every vertex x ∈ B, P r(x ∈ N + [S]) ≥ 1 -(1 -) g( ) > 1 -. Thus, by linearity of w B and the expectation, E(w B (N + [S])) > 1 -. Therefore, there exists a choice of S such that w B (N + [S]) > 1 -. Since w B (N -[y]) ≥ for every y ∈ C, the set N -[y] intersects N + [S]. In particular, by transitivity, S dominates y.

The next lemma is a direct consequence of Theorem 46.

Lemma 96. Let T be a complete multidigraph whose arc set is the union of the arc sets of k quasi-orders. There exists a probability distribution w on V (T ) and a partition of V (T ) into sets T 1 , T 2 , . . . , T k such that for every i and x ∈ T i , w(N - i [x]) ≥ 1/2k. Proof. By Theorem 46 there exists a weight function w : V (T ) → [0, 1] such that w(N -[x]) ≥ 1/2 for all x ∈ T . For every i in [k], let T i be the subset of vertices such that w(N - i [x]) ≥ 1/2k. The sets T i cover the vertices, so we can extract a partition with the required properties.

We are now ready to prove the main theorem:

Proof of Theorem 49. Consider P 1 = T 1 , T 2 , . . . , T k together with w the partition given by Lemma 96 applied to T . Each of the T i is a complete multidigraph whose arc set is the union of the arc sets of k quasi-orders, this means we can apply Lemma 96 and obtain T i,1 , T i,2 . . . , T i,k together with a probability distribution w i on T i such that w i (N - j [x]) ≥ 1/2k for every x ∈ T i,j . By repeating this process k times, we obtain a sequence of k + 1 partitions P 1 , . . . , P k+1 with P i = ∪ j 1 ,j 2 ,...,j i ≤k T j 1 ,j 2 ,...,j i such that for every l ≤ k + 1 and each j 1 , . . . , j l in [k] l , T j 1 ,j 2 ,...,j l is a subset of T j 1 ,j 2 ,...,j l-1 and the probability distribution w j 1 ...,j l-1 is such that w j 1 ...,j l-1 (N - j l [x]) ≥ 1/2k for every x in T j 1 ,...,j l . Fix j 1 , . . . , j k+1 , in [k] k+1 , by the Pigeonhole Principle there exist two indices, i < l such that j i = j l , then by applying Lemma 95 where T j 1 ,...,j i-1 , T j 1 ,...,j i and T j 1 ,...,j l play the roles of, respectively, A, B and C there exists a set of size g(1/2k) that dominates T j 1 ,...,j l and thus T j 1 ,...,j k+1 . This means that γ(T

The Sands-Sauer-Woodrow conjecture

In a recent paper, Harutyunyan et al. [START_REF] Harutyunyan | Domination and fractional domination in digraphs[END_REF] proved that the fractional domination of a digraph D is bounded by 2α(D). This means that there exists a probability distribution on the vertices, where every vertex x has d -[x] > 1 2α(D) . With this result, we can adapt the previous proof to show that there exists a function f (α, k) such that any multidigraph whose arcs are the union of k quasi-orders and with stability number smaller than α is dominated by f (α, k) vertices. However Conjecture 43 remains open.

Chapter 5 Entropy compression 5.1 Orientations of Hypergraphs

We present here the proof of the following theorem, obtained with Nathann Cohen in [START_REF] Cohen | Equitable orientations of sparse uniform hypergraphs[END_REF]. Theorem 54. Let p, k be fixed integers. There exists r 0 such that for every r ≥ r 0 , every r-uniform hypergraph with ∆ p (H) ≤ k admits a p-equitable orientation.

We first describe a random algorithm that produces such orientation. To analyse the behaviour of this algorithm we will need the following lemma on permutations, which we will prove in the last subsection.

Lemma 55. Let p, k ∈ N and α < 1 be fixed. Let X be a set of cardinality r and let L S be, for every S ∈ X p , a collection of p-subsets of X with |L S | ≤ k. Then, if no p-subset occurs in more than r α of the L S , a random permutation σ of X satisfies σ(S) ∈ L S for every S with probability ≥ (1 -2k/ r p ) ( r p ) = e -2k + o(1) when r grows large.

Algorithm

In what follows, we assume that every finite set S has an implicit enumeration on its elements, and in particular that the hyperedges of a hypergraph H are implicitly ordered. We will say that i represents an element s ∈ S when s is the i-th element of S in this implicit ordering. We will orient the hyperedges of H one by one as a (partial) equitable orientation of H, i.e. in such a way that no p-subset of V (H) appears more than once at the same position among the oriented hyperedges. To do so, we require the partial orientation to enforce an additional property.

Definition 97. Let H be a partially oriented r-uniform hypergraph. We say that an hyperedge S ∈ H is pressured by a family {S 1 , . . . , S l } of hyperedges (oriented by σ S 1 , . . . , σ S l ) if there exists P ∈ [r] p such that σ -1 S i (P ) ⊆ S for every i.

Note that Lemma 55 ensures that a partial orientation of H can be extended to an unoriented hyperedge S, provided that no family of more than r α oriented hyperedges pressures S. It asserts, for c < e -2k and r sufficiently large, that at least cr! orientations of S are admissible for this extension: we name them good permutations of S. Algorithm 2 selects an ordering randomly among them, while ensuring that no other hyperedge is pressured by a family of hyperedges larger than r 1 = r α . Algorithm 2 starts with every hyperedge being unoriented. At each step it orients the unoriented hyperedge of smallest index by choosing a random permutation amongst the cr! first good permutations. We call bad event the event that a hyperedge S ∈ H is pressured by a family {S 1 , . . . , S r 1 } of cardinality r 1 . If a bad event occurs after orienting S 1 , then the algorithm erases the orientation of the S 1 , . . . , S r 1 .

It is trivial to see that Algorithm 2 only returns p-equitable orientations of H. Moreover, every time the algorithm chooses a random permutation, it does so among at least cr! good ones by Lemma 55. Note that we need to consider large families pressuring already oriented hyperedges: indeed, we might have to cancel the orientation of such a hyperedge to redefine it again later.

Theorem 98. Let p, k ∈ N, α, c ∈ R >0 with α < 1 and c < e -2k . For every sufficiently large r, there is a set of random choices for which Algorithm 2 terminates.

In order to prove this result we will analyse the possible executions of the M first steps of Algorithm 2. To this end we make it deterministic by defining a log (following the idea of [START_REF] Moser | A constructive proof of the Lovász Local Lemma[END_REF]) and obtain Algorithm 3, in the following way:

• Take as input a vector v ∈ [cr!] M which simulates the random choices.

• Output a log when it is not able to orient all hyperedges.

We define a log of order M to be a triple (R, X, F ) where:

• R is a binary word whose length lies between M and 2M .

• X is a sequence of h 7-tuples of integers (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ) where:

This gives the following algorithm: Algorithm 3: A deterministic algorithm Data: Append 0 to the end of R F ← the integer representing the partial orientation of H. Return (R, X, F )

We will show the following claim.

Claim 98.1. Let e be a vector in [cr!] M from which Algorithm 3 cannot produce a p-equitable orientation of H and outputs a log (R, X, F ). We can reconstruct e from (R, X, F ).

Proof of the claim. First we show that we can find, for every z ≤ M , the set C(z) of hyperedges which are oriented after z steps. We proceed by induction on z, starting from C(0) = ∅. At step z + 1, Algorithm 3 chooses an orientation for the smallest index i not in C(z). If, in R, the (z + 1)-th 1 is not followed by a 0, then there is no bad event triggered by this step. In this case the set C(z + 1) is the set C(z) ∪ i. Suppose now that the (z + 1)-th 1 is followed by a sequence of 0: this means that the algorithm encountered a bad event. By looking at the number of sequences of 0 in R before the z + 1-th 1 we can deduce the number of bad events before this one. This mean we can find, in X, the 7-tuple (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ) associated to this bad event. We take the following notations for the bad event : After orienting S 1 , a hyperedge S of H is pressured by a family {S 1 , . . . , S r 1 } of cardinality r 1 . We note s i the subset of S i that is sent to P . S 1 is the last hyperedge we oriented (known by induction), We can now deduce the set S(z) of all chosen orientations after z steps. We also proceed by induction, this time starting from step M . By construction, F is exactly the integer representing the partial orientation of H at step M . If the last letter of R is a 1, this means the last step of the algorithm consisted only of choice of an orientation. We just showed that we know which orientation was chosen after M -1 steps, so we can deduce the state of all orientations after M -1 steps. If the last letter is a 0, Algorithm 3 encountered a bad event. Keeping the notation of the bad event, let (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ) be the 7-tuple associated to this bad event. Like before x 1 , x 2 , x 3 , x 4 and the knowledge of C(M -1) allow us to know which permutations Algorithm 3 erased at this step. Moreover x 7 tells us the random choice made by Algorithm 3 and from x 7 and x 1 we can deduce P . For each s i we know the orientation chosen for S i at the step M -1 sends P onto s i , from x 5 we deduce exactly in which order and from x 6 we get the rest of the orientation. Therefore we can deduce the set of chosen orientations before the bad event occurred. With the sets S(z) and C(z) known for all z ≤ M we can easily deduce e.

The previous claim has the following corollary:

Corollary 99. If H admits no p-equitable orientation, then Algorithm 3 defines an injection from the set of vectors

Let L M be the set of all possible logs after M steps of Algorithm 3. To show Theorem 98 it suffices to show that, for M big enough,

Proof. We will compute a bound for |L M |. R is a binary word of size ≤ 2M , and there are at most 4 M such words. X is a list of 7-tuples. As Algorithm 3 made M choices and each bad event removes r 1 of those, there exist at most M r 1 bad events. Moreover, for each 7-tuple, (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ) we have

We can assume r > 2p, and so r r-p+1 < 2:

Derangements

This subsection is devoted to the proof of Lemma 55. The main ingredient is the following lemma from Erdős and Spencer [START_REF] Erdős | Lopsided Lovász Local lemma and latin transversals[END_REF]:

Lemma 101 (Lopsided Lovász Local Lemma). Let A 1 , . . . , A m be events in a probability space, each with probability at most p. Let G be a graph defined on those events such that for every A i , and for every set S avoiding both A i and its neighbours, the following relation holds:

Then if 4dp ≤ 1, all the events can be avoided simultaneously:

Thanks to this result we can prove the following, which can be seen as a generalization of the fact that a random permutation of n points is a derangement with asymptotic probability 1/e. Lemma 55. Let p, k ∈ N and α < 1 be fixed. Let X be a set of cardinality r and let L S be, for every S ∈ X p , a collection of p-subsets of X with |L S | ≤ k. Then, if no p-subset occurs in more than r α of the L S , a random permutation σ of X satisfies σ(S) ∈ L S for every S with probability ≥ (1 -2k/ r p ) ( r p ) = e -2k + o(1) when r grows large.

Proof. For every S ∈ X p , we define the bad event B S with:

Each B S has a probability P r[B S ] ≤ k/ r p . On these bad events we define a lopsidependency graph (see [START_REF] Erdős | Lopsided Lovász Local lemma and latin transversals[END_REF]) G B with the following adjacencies:

As a p-subset of X intersects at most O(r p-1 ) others, and noting that every p-subset can occur at most r α times, we have that:

In order to apply the Lopsided Lovász Local Lemma to the events B S and graph G B , we must ensure for every S ∈ X p and

Indeed, if we denote by T (for trace) the number of elements of B S ∈S B S sent by the random permutation σ into L S :

As L S is disjoint from the L S , ∀B S ∈ S B , we have:

And thus:

In order to prove (5.1), we will first need the following observation:

Additionally, we will prove a relationship on the members of t P r[T = t] and on those of t P r[T = t | B S ∈S B BS ], which both sum to 1. We thus only need to ensure the following, which is a consequence of Lemma 102:

P r[

We are now ready to prove (5.1), and we define d t for every t where P r[T = t] is nonzero:

Because d t is a difference of probability distributions the sum t d t is null, and we can rewrite (5.1) using d t :

We will thus prove that the sum t d t P r[B S | T = t] is nonnegative. It is a consequence of Claim 101.2 that all nonnegative values of d t appear before all nonpositive ones, and so that there is a t 0 such that d t ≥ 0 if and only if t ≤ t 0 . As a result,

and we can write:

The second hypothesis of Lemma 101 is that 4pd ≤ 1, which translates in our case to 4 k ( r p ) o(r p ) = o(1) and is thus satisfied when r grows large. Hence, we have that: Similarly, it is clear that property (2) is an invariant of the while loop, thanks to Bad Event 2.

Let us consider property (3). The property is true at the beginning of the algorithm, since there are no bad edges. Next, suppose that property (3) held true at the beginning of the loop but that there are two incident bad edges e, f just after selecting the admissible pair U + (u) for a big vertex u. Then at least one of e, f , say e, became bad just after treating u.

Note that e cannot be incident to u, by definition of admissible pairs. Thus e is at distance 1 from u. It suffices to show that some bad event is triggered, since then u is reset and e is no longer bad (since e is not finished). This is clearly true, since either Bad Event 1 or Bad Event 2 is triggered, and if not then Bad Event 3 is triggered for sure (because of the existence of the pair e, f ). Thus we see that property (3) is an invariant of the loop.

The proof for property (4) is similar. The property clearly holds at the beginning of the algorithm. Next, suppose that it held true at the beginning of the loop but that just after selecting the subset U + (u) for a big vertex u, there are two independent bad edges vw, xy s.t. {w} ∪ U + (w) and {x} ∪ U + (x) intersect. Then at least one of the two edges, say vw, is at distance exactly 1 from u. (Recall that u cannot be incident to either of the two edges, by definition of admissible pairs.) As before, it suffices to show that some bad event occurs, since then u is reset and vw is no longer bad. Let z ∈ ({w} ∪ U + (w)) ∩ ({x} ∪ U + (x)) and say none of the first four bad events happens. Then z / ∈ {v, w, x, y}, since otherwise Bad Each random choice r i consisted in choosing an admissible pair for some big vertex u among its first s admissible pairs, thus we see r i as a number in [s].

For each i ∈ [t + 1], let U + i and U - i denote the functions U + and U -, respectively, at the beginning of the i-th iteration, and let B i denote the subset of vertices u ∈ B with U + i (u) = ∅. We associate to the sequence (r 1 , . . . , r t ) a corresponding log (W, γ, δ, U + t+1 ), where W is a partial Dyck word of semilength t such that the length of each descent is in the set {2, 3, 4, 5, q + 1}, and γ = (γ 1 , . . . , γ t ) and δ = (δ 1 , . . . , δ t ) are two sequences of integers.

The partial Dyck word W is built as follows during the execution of the algorithm: Starting with the empty word, we add a 0 at the end of the word each time a big vertex is treated. If the corresponding random choice triggers a bad event, we moreover add 1s at the end of the word, where is the number of big vertices that are reset (so = q +1, 2, 3, 4, 5 for bad events of types 1, 2, 3, 4, 5, respectively). Thus descents in W are in bijection with bad events treated during the execution, and the length of a descent tells us the type of the corresponding bad event.

The two sequences γ and δ are defined as follows. For i ∈ [t], the integers γ i and δ i encode information about the bad event handled during iteration i. If there was none, we simply set γ i := δ i := -1. Otherwise, γ i is a nonnegative integer encoding the set of big vertices that are reset when the bad event is handled, and δ i is a nonnegative integer encoding extra information which will help us recover the random choice r i from the log. The precise definitions of γ i and δ i depend on the type of the bad event (see the list below); however, before giving these definitions we must explain the assumptions we make.

The definition of γ i assumes that the set B i is known. In turn, γ i will encode enough information to determine completely B i+1 from B i . Since B 1 = B, it then follows that we can read off all the sets B 1 , B 2 , . . . , B t+1 from the sequence γ: For i = 1, . . . , t, either γ i ≥ 0, in which case B i+1 is determined by B i and γ i . Or γ i = -1, in which case no bad event occurred during iteration i, and thus B i+1 := B i -{u} where u is the first vertex in B i .

As already mentioned, the purpose of the log is to encode all t random choices r 1 , . . . , r t that have been made during the execution. To encode r i (i ∈ [t]), we work backwards: We assume that the function U + i+1 is known, and we show that one can then deduce r i and U + i using the log. Since U + t+1 is part of the log, this implies that the log uniquely determines r t , r t-1 , . . . , r 1 , as desired. Let us remark that if no bad event occurred during the i-th iteration, then we can already deduce r i and U + i from U + i+1 using the sets B i and B i+1 . Indeed, in this case B i = B i+1 ∪ {u} where u is the vertex treated during the i-th iteration. Thus, for v ∈ B,

tells us what was the random choice r i that was made for u during iteration i. Indeed, using U + i we can deduce what was the set of admissible pairs for u at the beginning of iteration i. Then, r i is the position of the pair U + i+1 (u) in the ordering of these admissible pairs. Therefore, it is only when a bad event happens that we need extra information to determine r i and U + i . This is precisely the role of δ i . Definitions of γ and δ. Let i ∈ [t]. If no bad event occurred during iteration i, set edge uv. Colour uv with a colour chosen at random among the first s colours available.

As with the algorithm from the previous section we define some bad events that could happen after colouring the edge uv. Here, we only need to consider one type of bad event:

The edge uv received a colour that was dangerous for u or v.

If such an event happens, consider a corresponding dangerous neighbour w, say it was dangerous for u. Let F denote the set of edges incident to u in G[A ] that are distinct from uv. Observe that |F | ≥ 2, since otherwise we would have removed the dangerous colour for u from the available choices. Our ordering of the edges of G[A ] induces an ordering of the edges in F ; it will be convenient to see this ordering as a cyclic ordering. With these notations, the bad event is handled as follows:

Uncolour uv and the edge just after uw in the cyclic ordering of F .

After possibly handling one such bad event, the algorithm proceeds with the next uncoloured edge in this fashion, until every edge is coloured.

Lemma 111. If the algorithm terminates, then the resulting edge colouring c is an AVDcolouring of G.

Proof. Consider an edge uv ∈ E(G) with d G (u) = d G (v). We already know that S c (u) = S c (v) if u, v ∈ B, so let us assume that u, v ∈ A. Arguing by contradiction, suppose that S c (u) = S c (v). Recall that G[A ] has no isolated edges, thus there is at least one edge incident to u or v which is distinct from uv in G[A ]. Let e be the last edge coloured by the algorithm among all such edges. Suppose w.l.o.g. that e is incident to v, say e = vw. Then, just before the edge vw was coloured for the last time, vertex u was dangerous for v, with dangerous colour c (vw). Hence, a bad event has been triggered after colouring vw. The bad event that was handled by the algorithm could have been the one with edge uv, or another one corresponding to another edge incident to v or w. In any case, the edge vw got uncoloured, a contradiction. Thanks to the above lemma, to conclude the proof it only remains to show that the algorithm terminates with nonzero probability, which we do now.

Theorem 112. The algorithm terminates with high probability.

Proof. The proof is very similar to the corresponding proof in the previous section (but simpler). Let us encode the first t steps (iterations) of an execution of the algorithm with a corresponding log (W, γ, δ, c ), where

• W is a partial Dyck word of semilength t, obtained by adding a 0 (a 1) each time an edge is coloured (uncoloured, respectively);

• γ = (γ 1 , . . . , γ t );

• δ = (δ 1 , . . . , δ t );

Chapter 6

Conclusions and further work

In this thesis, we investigated different problems regarding structures in digraphs, in particular subdivisions.

The first topic was to study the relation between subdivisions and chromatic number of digraphs. In Theorem 61, we generalised Bondy's Theorem (Theorem 31), by showing that large cycles with two blocks can be found in strong digraphs with large chromatic number. An interesting result would be to generalise this result to any oriented cycle. Let us remind our conjecture, which would be an interesting tool towards this question. Conjecture 38. For every k ≥ 1, there exists an integer f (k) such that every strong digraph with chromatic number greater than f (k) contains a subdigraph H with chromatic number at least k and such that H contains a Hamiltonian cycle.

Another interesting generalisation would be the following.

Conjecture 36. There is a function g : N 3 → N such that every strong digraph with chromatic number at least g(k 1 , k 2 , k 3 ) contains a subdivision of B(k 1 , k 2 ; k 3 ).

In Theorem 37, we proved a weaker result for B(k, 1; k). The proof is quite technical, and we believe some new ideas are necessary to prove the general statement. In this case as well, being able to prove Conjecture 38 would be an interesting step.

A famous open question concerning the chromatic number of digraphs is Burr's conjecture, which states that digraphs with chromatic number greater than 2k -2 contain all the oriented trees on k vertices as subdigraphs. The current best upper bound is in k 2 2 + o(k 2 ) and getting it down to linear seems to be very challenging. An interesting weaker problem is the following, where we replace subdigraph with subdivision.

Conjecture 113. There exists a constant a such that for every k, every digraph D with χ(D) ≥ ak contains every oriented tree of size k as a subdivision.

The most important question concerning subdivisions in digraphs is probably Mader's conjecture about subdivisions of transitive tournaments. Proving Alon's conjecture (Conjecture 17) would also be a major step in our understanding of digraphs with large minimum outdegree. A tempting approach is to use the entropy compression technique. The major obstacle for this approach are the vertices of large indegree as they are the ones creating large dependencies in a random partition. It could be interesting to look at the case of undirected graphs. In [START_REF] Stiebitz | Decomposing graphs under degree constraints[END_REF] Stiebitz proved that graphs with minimum degree s + t + 1 can be partitioned into two graphs, one of minimum degree s and one of minimum degree t, which is optimal. However, as far as we know, no probabilistic proof of the existence of a partition (even not the optimal one) exists, and once again dealing with the vertices of large degree seems to be the main difficulty.

In Theorem 49, we provided a proof that the domination of k-transitive tournaments is bounded by a function of k. The generalisation of this theorem to digraphs remains open:

Conjecture 43 (Sands et al. [START_REF] Sands | On monochromatic paths in edge-coloured digraphs[END_REF]). For every k ≥ 1 there exists an integer f (k) such that, for any multidigraph D whose arc set is the union of the arc sets of k quasi-orders, there exists f (k) stable sets such that the union is dominating.

Our proof can be extended to the class of digraphs with bounded stability number. An interesting result would be to find classes of digraphs with unbounded stability number and where the conjecture holds.