Dans la première partie, nous aborderons la question (a) -G peut-il être partitionné en copies du motif H ? -en présentant d'abord les conjectures des flots de Tutte et en montrant la connexion intime entre les flot dans les graphes et les décompositions de motifs. Nous allons prouver la conjecture de Barat-Thommasen sur les décompositions de motifs du chapitre 2 et la dépasser dans le cas où le motif est une trajectoire des chapitres 3 et 4, incluant la preuve d'une conjecture de Haggkvist et Kriesell. Nous revenons ensuite pour démontrer certaines propriétés des flot dans les graphes et un cas particulier de la conjecture de Jaeger-Linial-Payan-Tarsi au chapitre 5.

La deuxième partie est consacrée à la question (b) -Si G ne contient aucune copie du motif H, quelles sont les propriétés de G ? -où nous commençons avec la conjecture d'Erdos-Hajnal sur la non-existence de motifs dans les grands graphes et sa «dualité» dans les tournois -des graphes où chaque paire de sommets a un bord orienté. Nous montrons ensuite au chapitre 6 que la complexité locale d'un tournoi en dicte la complexité globale, ce qui résout une conjecture de Berger et al. Nous présentons un résultat majeur de Berger et al, caractérisant tous les tournois satisfaisant la conjecture d'Erdos-Hajnal dans un cas extrême, et étendons ce résultat aux graphes orientés denses du chapitre 7. Ce résultat supporter une conjecture de Harutyunian et McDiarmid que la propriété d'Erdos-Hajnal est même véritable pour les graphes dirigés en général. Enfin, au chapitre 8, nous présenterons des propriétés plus raffinées dans un cas particulier, lorsque le motif H est le triangle orienté.

1.2 SOME NOTIONS IN GRAPH THEORY | 5 edges is called the underlying graph of G. Conversely, a directed graph obtain from an undirected graph G by adding orientations to all edges is called an orientation of G Degree of vertices Given an undirected graph G, the set of edges incident with a vertex v is denoted by E G (v), and the cardinality of E G (v) is called the degree of v, denoted by d G (v). A vertex with degree 0 is called an isolated vertex. The minimum degree and maximum degree of G are δ(G) := min v∈V(G) d G (v) and ∆(G) := max v∈V(G) d G (v), respectively.

Given a directed graph G, the set of edges going in (resp. going out) a vertex v is denoted by

, respectively. A vertex with indegre (resp. outdegree) 0 is called a source (resp. sink). We similarly have the definition of minimum/maximum in/out-degree of a vertex in a directed graph. When it is clear from the context, the subscript G can be omitted.

Subgraphs, walks and connectivity in graphs

In other words, H is a subgraph of G if H can be obtained from G by repeatedly removing vertices (together with incident edges) and edges. We also say that G is a supergraph of H or G contains H. If V(H) = V(G), we say that H is a spanning subgraph of G. Given a graph G and A ⊆ V(G), the subgraph obtained from G by removing all vertices in V \ A (and their incident edges) is called the induced subgraph of G on A, denoted by G[A].

A walk in a graph G is a sequence of vertices and edges v 0 , e 1 , v 2 , e 2 , ..., e , v such that e i = v i-1 v i for every i. The length of the walk is . If v i = v j for every i = j, the walk is called a path. If v 0 = v and e i = e j for every i = j, the walk is called a tour. A tour with v i = v j for every i = j ≤ -1 is called a cycle. A tour containing every edge of G exactly once is called an Eulerian tour.

Two vertices u, v of an undirected graph G are k-edge-connected if there are k edgedisjoint paths connecting u and v in G. We say that G is k-edge-connected if every pair of vertices of G is k-edge-connected. If G is 1-edge-connected, we say that G is connected for short.

Some special graphs

The following are some special graphs; many of them will serve as patterns in the following chapters.

• A singleton is a graph with one vertex and no edge.

Résumé

Un graphe est un ensemble de sommets (également appelés noeuds), ainsi qu'un ensemble d'arêtes (également appelé liens ou arcs) reliant des paires de sommets, les arêtes pouvant être orientées ou non. Les graphes ont de nombreuses applications dans les domaines des réseaux sociaux, de l'organisation des données, du traitement automatique du langage naturel, etc. Avec la quantité croissante de données collectées, il est de plus en plus important de comprendre les structures et les comportements de très grands graphes [CXWW14, JLM17, HYL17, AHKT18]. Néanmoins, l'augmentation rapide de la taille des grands graphes rend l'étude de tous les graphes de moins en moins efficace. Ainsi, il existe une demande impérieuse pour des méthodes plus efficaces pour étudier de grands graphes sans nécessiter la connaissance des graphes dans leur ensemble. Une méthode prometteuse pour comprendre les comportements de grands graphes -en particulier dans les cas liés à le flot d'informations au sein du réseau, telle que la diffusion d'informations virales ou l'adoption de nouveaux produits -consiste à exploiter les propriétés spécifiques des structures locales, telles que la taille des grappes ou la présence locale d'un motif spécifique -c'est-à-dire un graphe donné (généralement petit) [HJJ + 18, NP12, LLDM09, Fau07]. Un exemple classique tiré de la théorie des graphes (cas avérés de la conjecture d'Erdos-Hajnal [START_REF] Erdös | Ramsey-type theorems[END_REF]) est que, si un graphe de grande taille ne contient pas de motif spécifique, il doit alors avoir un ensemble de sommets liés par paires ou non liés, de taille exponentiellement plus grande que prévue.

Dans cette thèse, nous aborderons certains aspects de deux questions fondamentales de la théorie des graphes concernant la présence, en abondance ou à peine, d'un motif donné H dans un grand graphe G:

(a) G peut-il être partitionné en copies de H ? (b) Si G ne contient aucune copie de H, quelles sont les propriétés de G ? Ces questions sont étroitement liées à certaines des conjectures les plus importantes de la théorie des graphes: les conjectures de Tutte sur les écoulements dans les graphes et la conjecture d'Erdos-Hajnal susmentionnée.

Graphs and patterns

A graph is a set of vertices (also called nodes), together with a set of edges (also called links or arcs) connecting pairs of vertices, where the edges can be either oriented or non-oriented. Graphs have numerous applications in the fields of Social Networks, Data Organization, Natural Language Processing, etc. With the accumulating amount of data collected, there is a growing interest in understanding the structures and behaviors of very large graphs [CXWW14, JLM17, HYL17, AHKT18]. Nevertheless, the rapid increasing in size of large graphs makes studying the entire graphs becomes less and less efficient. Thus, there is a compelling demand for more effective methods to study large graphs without requiring the knowledge of the graphs in whole. One promising method to understand the behaviors of large graphs -especially in cases related to the flow of information among the network such as the spread of viral news or the adoption of new products -is via exploiting specific properties of local structures, such as the size of clusters or the presence locally of a specific pattern -i.e. a given (usually small) graph [HJJ + 18, NP12, LLDM09, Fau07]. A classical example from Graph Theory (proven cases of the Erdős-Hajnal conjecture [START_REF] Erdös | Ramsey-type theorems[END_REF]) is that if a large graph does not contain some specific pattern, then it must have a set of vertices pairwise linked or not linked of size exponentially larger than expected.

In this thesis, we will address some aspects of two fundamental questions in Graph Theory about the presence, abundantly or scarcely, of a given pattern H in a large graph G: In Part I, we will address Question (a) -Can G be partitioned into copies of pattern H? -by first presenting the Tutte's flows conjecture and showing the intimate connection between flows in graphs and pattern-decompositions. We will prove the Barát-Thommasen conjecture on pattern-decompositions in Chapter 2, and going beyond it in the case the pattern is a path in Chapters 3 and 4, including the proof of a conjecture of Häggkvist and Kriesell. We then return to prove some properties of flows in graphs and a special case of Jaeger-Linial-Payan-Tarsi's conjecture in Chapter 5.

Part II is devoted to Question (b) -If G does not contain any copy of pattern H, which properties does G have? -where we start with the Erdős-Hajnal conjecture about the non-existence of patterns in large graphs, and its "dual version" in tournaments -a graph where every pair of vertices has an oriented edge. We then show in Chapter 6 that the local complexity of a tournament dictates its global complexity, solving a conjecture of Berger et al. We then present a major result by Berger et al, characterizing all tournaments satisfying the Erdős-Hajnal conjecture in an extremal case, and extend that result to dense directed graphs in Chapter 7. This result supports a conjecture of Harutyunian and McDiarmid that the Erdős-Hajnal property even holds for general directed graphs. Finally, in Chapter 8, we will present some more refined properties in a specific case, when the pattern is the oriented triangle.

Some notions in Graph Theory

Graphs

A graph G is an ordered pair (V (G), E(G)) where V(G) = {v 1 , ..., v n } is the set of vertices of G, and E(G) ⊆ {v i v j : 1 ≤ i, j ≤ n} is the set of edges of G. The cardinality of V (G) and E(G) are called the order and size of G, respectively. If the edges of G are unordered, i.e. v i v j = v j v i for every i, j, then G is an undirected graph. If the edges of G are ordered, i.e. v i v j = v j v i , then G is called a directed graph (or digraph for short). Edges in directed graphs are usually called directed edges or arcs to distinguish with edges in undirected graphs. Given an edge e = v i v j in a graph G, v i and v j are called endpoints of e. We also say that v i and v j are adjacent, and e is incident with each v i and v j . If e is a directed edge, then v i and v j are the source and target of e, respectively. We also say that two edges are incident if they are incident to some common vertex.

A graph is finite if the cardinality of V(G) is finite and is infinite otherwise. A loop is an edge with identical endpoints. A graph is loopless if it does not contain any loop. A graph G is called simple if it is loopless and every edge does not appear more than once in E (G). In a multigraph G, edges and loops may appear more than once in E (G). Given a directed graph G, the graph obtained from G by removing the direction of all 6| INTRODUCTION

• A path of length , denoted by P , is a graph with vertex set {v 0 , ..., v } and edge set {v 0 v 1 , v 1 v 2 , ..., v -1 v }.

• A star with leaves, denoted by S , is a graph with vertex set {v 0 , v 1 , ..., v } and edge set {v 0 v 1 , v 0 v 2 , ..., v 0 v }.

• A cycle (or directed cycle in the case the graph is directed) of length is a graph with vertex set {v 1 , ..., v } and edge set {v 1 v 2 , v 2 v 3 , ..., v v 1 }.

• A tree is a connected undirected graph not containing any cycle. Paths and stars are trees. The vertices of a tree with degree 1 are called leaves.

• The complete graph on vertices, denoted by K is the undirected simple graph with an edge between every pair of distinct vertices.

• A graph G is bipartite if V(G) is the union of two disjoint sets A, B such that there is no edge between vertices of A and no edge between vertices of B. Trees are bipartite graphs.

• A tournament is a directed graph such that its underlying graph is a complete graph. A tournament is transitive if it contains no directed cycle. The transitive tournament of vertices is denoted by T 1 . More generally, a digraph is acyclic if it contains no directed cycle.

(a) (b) (c) (e) (d) (f) (h) (i) (f) FIGURE 1.
1 -List of special graphs: (a) the singleton, (b) the path of length 4 P 4 , (c) the star with 5 leaves S 5 , (d) the cycle of length 5 C 5 , (e) a tree, (f) the complete graph of 5 vertices K 5 , (g) a bipartite graph, (h) a tournament on 5 vertices, and (i) the transitive tournament on 5 vertices T 5 . 1 The usual notation in literature for the transitive tournament on vertices is TT .

SOME NOTIONS IN GRAPH THEORY | 7

Some other notions

Two graphs G and H are isomorphic if there is a bijective map ϕ from V(G) to V(H) such that uv ∈ E(G) if and only if ϕ(u)ϕ(v) ∈ E(H). If G and H are isomorphic, we can say that H is a copy of G and vice versa. With the definition of isomorphic graphs, we can extend other notions, such as H is an (induced) subgraph of G if there is an (induced) subgraph of G which is a copy of H. If G does not contain H as an induced subgraph, we say that G is H-free. Given a graph G, a set of vertices A ⊆ V(G) is called a clique if there is an edge between every pair of vertices in A, and is called an independent set (or stable set) if there is no edge between any pair of vertices in A.

A vertex-coloring (resp. edge-coloring) of a graph G is an assignment a color to each vertex (resp. edge) of G. If there are two adjacent vertices (resp. incident edges) with the same color in a vertex-coloring (resp. edge-coloring) of an undirected graph, the coloring is called improper. It is called proper otherwise.

Part I

Pattern-Decompositions of Large Graphs

Chapter 2

The Barát-Thomassen Conjecture

The Tutte's flow conjectures

In Optimization Theory or Operations Research, a flow network is often defined as a directed graph satisfying the balance property, i.e. for every vertex v (except sources and sinks) the total flows entering and leaving v are equal. Tutte's flow conjectures, however, are concerned with a more general notion of flow, where the balance property still holds but is measured on Abelian groups. Since the scope of this thesis is confined to flows on Z p for some integer p, we will provide a more narrow definition of flows as follows.

DEFINITION 2.1

Given an integer p, a nowhere-zero p-flow (or p-flow for short) on a directed graph G is an assignment f of values {1, 2, . . . , p -1} to the edges of G such that for each vertex v,

∑ e∈E + (v) f (e) ≡ ∑ e∈E -(v)
f (e) mod p.

An undirected graph G admits a p-flow if there is an orientation G of G admitting a p-flow.

Tutte proposed several conjectures about flows in undirected graphs, most notably the 3-flow Conjecture in 1949 and the 5-flow Conjecture in 1954 (see [START_REF] Thomas | A contribution to the theory of chromatic polynomials[END_REF], [START_REF] Steinberg | Grötzsch's theorem dualized[END_REF] The content of this chapter is covered in paper A proof of the barát-thomassen conjecture, Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, Martin Merker, and Stéphan Thomassé, Journal of Combinatorial Theory, Series B, 124:39-55, 2017.

12| THE BARÁT-THOMASSEN CONJECTURE and [BM + 76]). In the rest of Part I, the term graphs is used to mention simple, finite, and undirected graphs. The most well-known theorems on p-flows are the following: Seymour [START_REF] Paul | Nowhere-zero 6-flows[END_REF] proved that that every 2-edge-connected graph has a 6-flow and Jaeger [START_REF] Jaeger | Flows and generalized coloring theorems in graphs[END_REF] that every 4-edge-connected graph has 4-flow. We may easily notice that in all these conjectures and theorems, there is a strong correlation between edge-connectivity and the existence of a p-flow. One reason is that edge-connectivity requires a global connection among vertices of the graph, and so the more edge-connectivity a graph has, the easier its flow distributes among regions of the graph in order to achieve the balance property. One simple example is that a graph G made of two cliques A and B connected by a single edge e. Then G is not 2-edge-connected. No matter the assignment of value and orientation of edges, the total flow between A and B must be 0 to achieve the balance property. This implies that the value assigned to e must be 0, violating the definition of p-flow. Hence, G does not admits a p-flow.

The 3-flow conjecture is known to be notoriously hard. The weak version of it [START_REF] Jaeger | Flows and generalized coloring theorems in graphs[END_REF], where 4-edge-connectivity is replaced by any arbitrarily large edgeconnectivity, stood for more than 30 years.

CONJECTURE 2.4 The weak 3-flow conjecture

There exists a fixed integer k such that every k-edge-connected graph has a 3-flow.

The Barát-Thomassen conjecture

The weak 3-flow conjecture was solved by Thomassen in 2012 [START_REF] Thomassen | The weak 3-flow conjecture and the weak circular flow conjecture[END_REF] who showed that every 8-edge-connected graph has a 3-flow. His proof revealed a close link between flows in graph and pattern-decompositions. A decomposition of a graph G is a set of subgraphs H 1 , . . . , H k that partition the edges of G. That is, k i=1 E(H k ) = E(G) and E(H i ) ∩ E(H j ) = ∅ for every i, j. When every H i is an isomorphic copy of a given pattern H, we call the decomposition an H-decomposition. In his proof, Thomassen [START_REF] Thomassen | The weak 3-flow conjecture and the weak circular flow conjecture[END_REF] showed that the following are equivalent: (1) Every 8-edge-connected graph G has a 3-flow;

(2) Every 8-edge-connected graph G of size divisible by 3 has an orientation such that d + (v) is divisible by 3 for every v.

On the other hands, it is not hard to see that ( 2) is equivalent to the following statement,

(3) Every 8-edge-connected graph G of size divisible by 3 admits a decomposition into copies of S 3 , the star of 3 leaves (note that the condition the size of G divisible by |E(S 3 )| is obvious and inevitable).

Indeed, suppose that (3) holds. Then for any 8-edge-connected graph G of size divisible by 3, consider an S 3 -decomposition of G, and for every copy of S 3 in that decomposition, orient its edges out from the center of the star. This implies that G satisfies (2). The reverse direction is similar. Hence, (1) and (3) are equivalent, i.e., every 8-edgeconnected graph has a 3-flow is equivalent to every 8-edge-connected graph has a S 3 -decomposition. Said differently, Thomassen [START_REF] Thomassen | The weak 3-flow conjecture and the weak circular flow conjecture[END_REF] showed that every highly edgeconnected graph G with size divisible by |E(S 3 )| admits an S 3 -decomposition. This property was indeed observed several years before by Barát and Thomassen [START_REF] Barát | Claw-decompositions and tutteorientations[END_REF] in another paper about flows in graphs. They conjectured that the property does not only hold for S 3 but for every pattern which is a tree.

DEFINITION 2.5 The Barát-Thomassen property

We say that a pattern H has the Barát-Thomassen Property if there exists an integer k H such that every k H -edge-connected graph with size divisible by |E(H)| has an H-decomposition.

CONJECTURE 2.6

The Barát-Thomassen conjecture, [START_REF] Barát | Claw-decompositions and tutteorientations[END_REF] Every tree has the Barát-Thomassen Property.

When the conjecture was made in 2006, it was only known to hold when the pattern has less than 3 edges. The first non-trivial case was the 3-star S 3 [START_REF] Thomassen | The weak 3-flow conjecture and the weak circular flow conjecture[END_REF] that we mentioned above. In the same paper, Thomassen proved the conjecture for all stars.

Since then, the Barát-Thomassen conjecture has attracted growing attention, and it was verified for different families of trees such as bistars1 [START_REF] Barát | Edge-decomposition of graphs into copies of a tree with four edges[END_REF][START_REF] Thomassen | Decomposing a graph into bistars[END_REF], and paths of a certain length [START_REF] Botler | Decomposing highly connected graphs into paths of length five[END_REF][START_REF] Thomassen | Decompositions of highly connected graphs into paths of length 3[END_REF][START_REF] Thomassen | Edge-decompositions of highly connected graphs into paths[END_REF][START_REF] Thomassen | Decomposing graphs into paths of fixed length[END_REF]. Recently, breakthrough results were obtained by Botler et al. [START_REF] Botler | Decomposing highly edge-connected graphs into paths of any given length[END_REF], who proved the conjecture for all paths, and by Merker [START_REF] Merker | Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree[END_REF], who proved the conjecture for all trees of diameter2 at most 4, hence covering some of the results above.

The rest of this chapter is dedicated to provide a proof of the Barát-Thomassen conjecture.

THEOREM 2.7

Every tree has the Barát-Thomassen Property.

Proof overview

Fix a tree T with m edges as our pattern. The proof contains three steps.

(i) Given a graph G with high edge-connectivity, we first use previous results to reduce to the case where G is bipartite and one side has all degrees divisible by m. This is obtained by repeatedly removing a small number of copies of T in G.

(ii) Then we find a decomposition of G into homomorphic copies of T, i.e., overlapping between vertices in each copy is allowed. However we will find a way to ensure a low percentage of such bad copies.

(iii) Finally, we swap edges between homomorphic copies to convert them to isomorphic copies and complete the proof.

Simplifying G

First, it was shown by Thomassen in [START_REF] Thomassen | Decomposing a graph into bistars[END_REF], and independently by Barát and Gerbner in [START_REF] Barát | Edge-decomposition of graphs into copies of a tree with four edges[END_REF], that it is sufficient to verify the Barát-Thomassen conjecture in the case G is bipartite.

THEOREM 2.8 [BG14, Tho13a]

Let T be a tree on m edges. The following two statements are equivalent:

(1) There exists a natural number k T such that every k T -edge-connected graph with size divisible by m has a T-decomposition.

(2) There exists a natural number k T such that every k T -edge-connected bipartite graph with size divisible by m has a T-decomposition.

A corollary of the Barát-Thomassen conjecture for stars [START_REF] Thomassen | The weak 3-flow conjecture and the weak circular flow conjecture[END_REF] is the following decomposition theorem, which was shown by Thomassen in [START_REF] Thomassen | Decomposing a graph into bistars[END_REF] and also applied in [START_REF] Botler | Decomposing highly connected graphs into paths of length five[END_REF] and [START_REF] Merker | Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree[END_REF]. THEOREM 2.9 [START_REF] Thomassen | Decomposing a graph into bistars[END_REF] Let G be a bipartite graph with partition classes A 1 and A 2 , and size divisible by m. If G is (4λ + 6m)-edge-connected, then G can be decomposed into two λedge-connected graphs G 1 and G 2 such that d G i (v) is divisible by m for every v in A i .

By Theorems 2.8 and 2.9, it is sufficient to prove the Barát-Thomassen conjecture for bipartite graphs G on vertex classes A and B, where all vertices in A have degree divisible by m, the size of the pattern T.

Equitable coloring

Since every tree is bipartite, let us call T A and T B the vertex classes of the bipartition of T, and we may assume that T B contains a leaf. The T-decompositions we are going to construct will respect the bipartitions of G and T in the sense that the vertices corresponding to T A will lie in A for each copy of T. We say that vertices v ∈ V(G) and t ∈ V(T) are compatible if v ∈ A and t ∈ T A , or v ∈ B and t ∈ T B .

We consider a specific kind of edge-coloring of G, that was introduced in [START_REF] Merker | Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree[END_REF]. Assuming G is (improperly) edge-colored, we denote by d i (v) the degree of vertex v in color i. For t ∈ V(T), let E T (t) denote the set of edges incident with t.

DEFINITION 2.10

An edge-coloring φ :

E(G) → E(T) is called T-equitable, if for any compatible vertices v ∈ V(G), t ∈ V(T) and j, k ∈ E T (t), we have d j (v) = d k (v).
It was shown by Merker [Mer17] that highly edge-connected graphs admit Tequitable edge-colorings.

THEOREM 2.11 Theorem 3.4 in [Mer17]

For all natural numbers m and L there exists a natural number f (m, L) such that the following holds: If G is an f (m, L)-edge-connected bipartite graph with bipartite classes A and B where all vertices in A have degree divisible by m, and T 16| THE BARÁT-THOMASSEN CONJECTURE is a tree on m edges with bipartite classes T A and T B where T B contains a leaf, then G admits a T-equitable coloring where the minimum degree in each color is at least L.

Notice that since we put no constraints on the degrees in B, it is necessary that the greatest common divisor of the degrees in T B is 1 if we want to construct a T-equitable coloring. For this reason we chose the bipartition of T so that T B contains a leaf.

If there exists a T-decomposition of a bipartite graph G where all copies of T are oriented the same way (with respect to the bipartite classes), then this gives rise to a T-equitable coloring of G. Vice versa, a T-equitable coloring can also be used to construct a T-decomposition. This was done in [START_REF] Merker | Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree[END_REF] for the case that the girth of G is at least the diameter of T, and also in general for trees of diameter at most 4.

We then use probabilistic methods to show that a T-equitable coloring can be turned into a T-decomposition whenever the minimum degree in each color is large enough.

THEOREM 2.12

Let T be a tree on m edges and let G be a bipartite graph admitting a T-equitable coloring. If the minimum degree in each color is at least 10 50m , then G has a Tdecomposition.

Combined with the previous theorems, Theorem 2.12 completes the proof of the Barát-Thomassen conjecture as follows.

Proof of Theorem 2.7: By Theorem 2.8, we may assume that G is bipartite. We show that every (4 f (m, 10 50m ) + 6m)-edge-connected bipartite graph has a T-decomposition, where f is the function given by Theorem 2.11. By Theorem 2.9 we can decompose G into two spanning f (m, 10 50m )-edge-connected graphs G 1 and G 2 , such that in one side of the bipartition of each G i all vertices have degree divisible by m. By Theorem 2.11, we can find a T-equitable coloring of G i in which the minimum degree in each color is at least 10 50m . This coloring can be turned into a T-decomposition by Theorem 2.12.

Pseudo-decompositions and the proof of Theorem 2.12

In our proof of Theorem 2.12, a T-decomposition of a graph G is obtained in two steps, which we describe more formally below.

• In the first step we construct a decomposition of G into so-called pseudo-copies of T, which are subgraphs that are in some sense homomorphic to T. Such a decomposition, which we call a T-pseudo-decomposition, can easily be obtained from a T-equitable coloring, see also [START_REF] Merker | Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree[END_REF]. Instead of choosing any such decomposition, we use probabilistic methods to find one in which the vast majority of pseudo-copies at every vertex are isomorphic to T. The details of this step can be found in Section 2.4.

• In the second step, we use these isomorphic copies to repair the non-isomorphic copies of T by making subgraph switches. While the switching itself is a deterministic operation, we again use probabilistic methods to find a suitable set of isomorphic copies. This part of the proof is detailed in Section 2.5.

Step 1: Finding a good T-pseudo-decomposition

Let G be a graph with a T-equitable coloring. Recall that E T (t) denotes the set of edges incident with a vertex t ∈ V(T). Let us denote by N i (v) the set of edges colored i incident with v ∈ V(G). Furthermore, we set

N E T (t) (v) := i∈E T (t) N i (v) for every t ∈ V(T) compatible with v. Since the edge-coloring of G is T-equitable, we have that |N E T (t) (v)| is divisible by |E T (t)| for every compatible v ∈ V(G), t ∈ V(T).
Thus, we partition N E T (t) (v) into stars of size |E T (t)| that contain each of the colors in E T (t) exactly once. Let S be the collection of stars we get after having done this for every v ∈ V(G) and compatible t ∈ V(T). Consider an auxiliary graph G S whose vertices are the stars in S, and where two vertices are joined by an edge whenever the corresponding stars have an edge in common. By construction, each connected component of G S is a tree isomorphic to T. For every connected component in G S , we take the union of all the stars corresponding to it in G. It is easy to see that this decomposes G into parts of the same size as T. In fact even more is true: Each part is isomorphic to a graph obtained from T by identifying vertices. This motivates the following definition.

DEFINITION 2.13

A graph H is a pseudo-copy of T, if there exists a surjective graph homomorphism h : V(T) → V(H) that induces a bijection between E(T) and E(H).

In other words, a graph H is a pseudo-copy of T, if it is isomorphic to a multigraph obtained from T by identifying vertices and keeping all edges. We also refer to pseudo-copies of T as pseudo-trees. The term T-pseudo-decomposition denotes a decomposition where each part is a pseudo-copy of T. Given a T-equitable coloring of G, the construction above results in a T-pseudo-decomposition of G.

Notice that it might be the case that a graph H can be considered as a pseudocopy of T in different ways if there exists more than one homomorphism from T to H with the required properties. However, we will only consider homomorphisms that induce the same edge-coloring of H as the given T-equitable coloring. Furthermore, we only consider pseudo-copies of T in G that respect the bipartition in the sense that vertices corresponding to T A always lie in A.

18| THE BARÁT-THOMASSEN CONJECTURE

Let P be a T-pseudo-decomposition of G. For every compatible v ∈ V(G) and t ∈ V(T), we denote by N P (v|t) the set of pseudo-trees in P in which v is the image of t. Let d P (v|t) = |N P (v|t)|. Clearly, for any two different vertices u and v of G, we have N P (u|t) ∩ N P (v|t) = ∅. Notice also that v∈G N P (v|t) = P for every t ∈ V(T).

So far we have explained how T-pseudo-decompositions can be obtained from a T-equitable coloring. We denote such a resulting T-pseudo-decomposition P of G by H ∪ I, where I denotes the collection of pseudo-copies that are isomorphic to T and H denotes the collection of the remaining pseudo-copies.

If the minimum degree in each color is large in the T-equitable coloring, then there are many possibilities at every vertex to decompose its incident edges into stars. Using probabilistic methods, we find a T-pseudo-decomposition where d H (v|t) εd I (v|t) for some given ε > 0 and every compatible v ∈ V(G), t ∈ V(T). Now for every non-isomorphic copy H ∈ N H (v|t), there are many copies isomorphic to T in N I (v|t). We will use one of these isomorphic copies to improve the T-pseudodecomposition by repairing H. This is done by a subgraph switch operation which is explained in more detail in Step 2. However, if the trees in N I (v|t) overlap too much, then we might not be able to make any switch that improves the T-pseudodecomposition. To avoid this, we need to find a large set of isomorphic copies in N I (v|t) that pairwise intersect only in v. To measure how much the pseudo-trees in a T-pseudo-decomposition overlap, we use the following concept called conflict ratio.

DEFINITION 2.14

Let P be a collection of pseudo-copies of T in G, and v ∈ V(G) and t ∈ V(T) be compatible vertices. The conflict ratio of v with respect to t, denoted by conf P (v|t), is defined by

conf P (v|t) := max u =v {T ∈ N P (v|t) : u ∈ V(T)} d P (v|t) .
Intuitively, conf P (v|t) measures the maximum proportion of pseudo-copies in N P (v|t) in which some fixed vertex u appears. Clearly, we always have 0 conf P (v|t) 1. If v and t are not compatible, then we set conf P (v|t) = 0. Globally, we define conf(P |t) := max v conf P (v|t) and conf(P ) := max t conf(P |t).

To ensure that the isomorphic copies in the T-pseudo-decomposition H ∪ I are sufficiently spread out, we also require conf(I ) δ for some given δ > 0. In Section 2.4, we prove that such a T-pseudo-decomposition can always be obtained provided the minimum degree in each color is large enough.

LEMMA 2.15

Let T be a tree on m edges and ε, δ real numbers with 0 < ε, δ < 1. Let G be a T-equitably colored bipartite graph where the minimum degree in each color is at least (10m) 18 (εδ) -6 . Then G admits a T-pseudo-decomposition H ∪ I, where I denotes the collection of isomorphic copies of T, such that:

(1) for every compatible v ∈ V(G) and t ∈ V(T), we have d H (v|t) εd I (v|t);

(2) conf(I ) δ.

Step 2: Repairing non-isomorphic copies For this part of the proof we label the vertices t 0 , . . . , t m of T so that, for every i ∈ {1, . . . m}, the subgraph induced by t 0 , . . . , t i is connected. Such an ordering can for example be obtained by applying a breadth-first search algorithm from some vertex t 0 of T. We also label the edges of T so that e i denotes the edge joining t i with T[t 0 , . . . , t i-1 ] for every i ∈ {1, . . . m}. To indicate at which place a pseudo-copy H fails to be isomorphic to T, we introduce the following definitions.

DEFINITION 2.16

Let H be a pseudo-copy of T, and let v i denote the image of t i in H for every i ∈ {0, . . . , m}. For i ∈ {1, . . . , m}, we say that H is i-good if the vertices v 0 , . . . , v i are pairwise distinct. If H is not i-good, then we say that H is i-bad.

Note that since G does not have multiple edges, every pseudo-copy of T in G is 2-good. Moreover, since G is bipartite, every pseudo-copy of T in G is even 3-good.

The idea is to use isomorphic copies to repair the pseudo-trees that are not isomorphic to T. We start by considering all pseudo-trees in H that are 4-bad. For each such H, we will find an isomorphic copy f (H) in I such that H ∪ f (H) can be written as the union of two 5-good pseudo-copies of T, say H 1 ∪ H 2 . We then remove H from H and f (H) from I, and add {H 1 , H 2 } to H. The technical definition of this so-called switch is given below. We use this operation for all 4-bad pseudo-copies of T in H. Let H ∪ I denote the resulting T-pseudo-decomposition, where I again contains only isomorphic copies of T and all pseudo-copies in H are 4-good. We repeat this step, this time repairing all 5-bad pseudo-copies in H by using isomorphic copies in I . We continue like this until we get a T-pseudo-decomposition in which all pseudo-copies are m-good and thus isomorphic to T.

To make sure that we can perform a switch between H and f (H), we need f (H) to satisfy certain properties. Let v j denote the image of t j in H for j ∈ {0, . . . , m} and suppose i is chosen minimal such that H is i-bad. By the choice of our labelling, there exists i ∈ {0, . . . , i -1} with t i t i ∈ E(T). To ensure that v i is distinct from the previous vertices v 0 , . . . , v i-1 , we want to choose a different edge corresponding to e i at v i . Since we take this edge from f (H), we want f (H) to also use the vertex v i as image of t i . However, this should be the only point of intersection with H to ensure that both copies will be i-good after the switch.

More precisely, for every edge e i ∈ E(T), let T i-denote the connected component of Te i containing t 0 . Let T i+ be the subgraph of T induced by E(T) \ E(T i-). If H is a pseudo-copy of T, then we denote the images of T i-and T i+ under the homomorphism by H i-and H i+ . Now we are ready to define the switching operation.

DEFINITION 2.17

Let H be a collection of pseudo-copies of T in G and i ∈ {1, . . . , m}. Let t i be the endpoint of the edge e i that is different from t

i . Suppose H 1 , H 2 ∈ N H (v|t i ) for some v ∈ V(G). The i-switch of {H 1 , H 2 } is defined by sw i ({H 1 , H 2 }) = {H i+ 1 ∪ H i- 2 , H i- 1 ∪ H i+ 2 }.
By making an i-switch between two pseudo-copies H and f (H), their vertices corresponding to v 0 , . . . , v i-1 remain unchanged. In particular, if both H and f (H) are (i -1)-good, then also both copies in sw i ({H, f (H)}) will be (i -1)-good. Moreover, if H ∩ f (H) = {v i }, then after the switch both pseudo-trees will be i-good. Notice that neither of the two new pseudo-trees is necessarily still isomorphic to T. In particular, the collection of isomorphic copies might shrink with every step of the repairing process.

If the pseudo-trees in I overlap too much, we might not be able to find a single pseudo-tree f (H) in I with H ∩ f (H) = {v i }. A sufficiently low conflict ratio of I ensures that we can find such a function f : H → I. However, to continue this process we also need that the remaining collection of isomorphic copies I \ f (H) has a low conflict ratio. To this end we use the Local Lemma to prove the following lemma in Section 2.5.

LEMMA 2.18

Let T be a tree on m edges and ε, δ positive real numbers with ε + δm < 1 2 and εm < 1. Let H and H be collections of pseudo-copies of T in G with conf(H ) δ and d

H (v|t) > max{22/ε 7 , d H (v|t)/ε} for each compatible v ∈ V(G), t ∈ V(T).
For every t ∈ V(T), there exists an injective function f t : H → H such that

• f t (N H (v|t)) ⊂ N H (v|t) for every v ∈ V(G) compatible with t, • H ∩ f t (H) = {v} for every H ∈ N H (v|t), and • d f t (H) (v|t ) 3εd H (v|t ) for every compatible v ∈ V(G), t ∈ V(T).

FIND A GOOD PSEUDO-DECOMPOSITION | 21

By using Lemma 2.18 with H = I, we find a collection f (H) in which the degrees are low compared to the degrees in I. Thus, the conflict ratio of the collection of isomorphic copies only increases by a constant factor after each step of the repairing process. By choosing ε and δ sufficiently small, the proof of Theorem 2.12 will follow from Lemma 2.15 and repeated applications of Lemma 2.18. The details can be found at the end of Section 2.5.

Find a good pseudo-decomposition

Given a graph with a T-equitable coloring and large minimum degree in each color, we construct a T-pseudo-decomposition satisfying the conditions in Lemma 2.15. As described in Step 1 of Section 2.3, every T-equitable coloring gives rise to several T-pseudo-decompositions. We form the pseudo-copies of T by grouping the edges at every vertex randomly into rainbow stars. If the degrees in each color are large enough, we can ensure that most of the resulting pseudo-trees are isomorphic to T and also the conflict ratio of the resulting T-pseudo-decomposition is small. The proof of this is essentially an application of the Local Lemma.

PROPOSITION 2.19 Symmetric Local Lemma

Let A 1 , ..., A n be events in some probability space Ω with P[A i ] p for all i ∈ {1, . . . , n}. Suppose that each A i is mutually independent of all but at most d other events A j . If 4pd < 1, then P[∩ n i=1 A i ] > 0.

The bad events in this case are of the form that many copies in N H (v|t) are either not isomorphic to T or have a vertex different from v in common. To show that each event occurs with low probability, we make use of an inequality due to McDiarmid [START_REF] Mcdiarmid | Concentration for independent permutations. Combinatorics[END_REF] (see also [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]).

PROPOSITION 2.20 McDiarmid's Inequality (simplified version)

Let X be a non-negative random variable, not identically 0, which is determined by m independent permutations Π 1 , ..., Π m . A choice is the position that a particular element gets mapped to in a permutation. If there exist d, r > 0 such that • interchanging two elements in any one permutation can affect X by at most d, and

• for any s > 0, if X s then there is a set of at most rs choices whose outcomes certify that X s,

22| THE BARÁT-THOMASSEN CONJECTURE then for any 0 λ E[X], P |X -E[X]| > λ + 60d rE[X] 4e - λ 2 8d 2 rE[X] .
A necessary condition to apply the Local Lemma is that each event is mutually independent of most other events. To make sure that this is the case, we start the proof by partitioning the edges at each vertex into so-called fans of roughly the same size. Recall that for v ∈ V(G) and t ∈ V(T), we denote by N i (v) the edges colored i incident with v in G, and by E T (t) the set of edges incident with t in T.

Proof of Lemma 2.15: Set c = (10m) 9 (εδ) -3 . For every v ∈ V(G) and color i, we choose r v,i ∈ {0, . . . , c -2} such that d i (v) ≡ r v,i (mod c -1). Since the minimum degree in each color in G is greater than c 2 , we can partition every set N i (v) into subsets of size c and c -1 so that precisely r v,i of them have size c. We call these subsets i-blades. Note that an edge uv of color i in G appears both in an i-blade of N i (u) as well as in an i-blade of N i (v), but we do not require these two i-blades to have the same size.

For every compatible t ∈ V(T), v ∈ V(G), and i, j ∈ E T (t), we have

d i (v) = d j (v)
since the coloring is T-equitable. Thus, the number of i-blades of size c (respectively, of size c -1) in the partition of N i (v) is equal to the number of j-blades of size c (respectively, of size c -1) in the partition of N j (v). We can therefore partition the edges of N E T (t) (v) into fans, which are unions of blades of the same size, such that every fan contains precisely one i-blade for every i ∈ E T (t). In other words, a fan ϕ at a vertex v (with relation to t) is a subset of N E T (t) (v) of size c|E T (t)| or (c -1)|E T (t)| such that all colors in E T (t) appear c times or c -1 times in ϕ. We also call ϕ a t-fan to indicate the colors appearing in ϕ.

For every compatible t ∈ V(T), v ∈ V(G), and every t-fan ϕ at v, we uniformly at random partition the edges in ϕ into rainbow stars of size |E T (t)|. More precisely, for every i ∈ E T (t) we choose a permutation Π ϕ,i independently and uniformly at random from all permutations on c elements (respectively, on c -1 elements if the blades of ϕ have size c -1). By labelling the edges of each blade, each permutation Π ϕ,i corresponds to an ordering of the edges of the i-blade of ϕ. Now we partition the edges of ϕ into stars of size |E T (t)| by grouping the edges of different blades that were mapped to the same position. In other words, for every s ∈ {1, . . . , c} (respectively, s ∈ {1, . . . , c -1}) we form a star by choosing for every i ∈ E T (t) the edge labeled Π ϕ,i (s) in the i-blade of ϕ. These stars are centered at v and each color in E T (t) appears precisely once. Note that every edge uv ∈ E(G) belongs to exactly two stars, one centered at u and one centered at v. As described in Step 1 in Section 2.3, these stars correspond to a T-pseudo-decomposition of G in a canonical way. All that remains to show is that there exists an outcome of the random permutations such that the resulting T-pseudo-decomposition satisfy the conditions (1) and (2) of Lemma 2.15.

We denote the set of pseudo-trees using edges of a fan ϕ by T ϕ . Note that |T ϕ | is either equal to c -1 or c. Now we formally define what the bad events at a t-fan ϕ at a vertex v are. Let A ϕ be the event that more than 2m 2 c 2/3 of the pseudo-copies in T ϕ are not isomorphic to T. Let B ϕ be the event that there exists a vertex u ∈ V(G) with u = v such that more than 2mc 2/3 pseudo-copies in T ϕ contain u. Finally, let C ϕ = A ϕ ∪ B ϕ . We will prove the following two statements.

Claim 1: Each C ϕ is mutually independent of all but at most 4(cm) 2m other events C ψ .

Claim 2: P[C ϕ ] < 9(cm) m me -c 2/3 /32 .
Before we proceed to prove these claims, let us note that they allow us to use the Local Lemma to get our desired T-pseudo-decomposition H ∪ I. Indeed, since e -x < (9m)!

x 9m for x > 0, we have

4 • 4(cm) 2m • P[C ϕ ] < 2 8 • (cm) 3m • m • e -c 2/3 /32 < 2 45m+8 • m c 3m • m • (9m)! < 2 18 • m c • (9m) 3 3m < 10 9 m 4 c 3m < 1 ,
where the last inequality follows from c (10m) 9 . Thus, the symmetric version of the Local Lemma yields a T-pseudo-decomposition H ∪ I for which none of the events C ϕ holds. Now H ∪ I has the desired properties:

• Since A ϕ does not hold for any ϕ, at most 2m 2 c 2/3 of the pseudo-copies in T ϕ are not isomorphic to T. Since c (10m) 9 ε -3 , we have 2m 2 c 2/3 < ε 1+ε c. Thus, less than ε 1+ε c of the pseudo-copies in T ϕ are in H, while at least 1 1+ε c of them are in I. This holds for every t-fan at v, so we have d H (v|t) < εd I (v|t).

• Since B ϕ does not hold for any ϕ, there are at most 2mc 2/3 trees in T ϕ containing a given vertex u different from v. As argued above, at least c 1+ε of the pseudocopies in T ϕ are in I. Since c (10m) 9 (εδ) -3 , we have 2mc 2/3 < δ c 1+ε . Thus, the proportion of trees in T ϕ ∩ I containing u is less than δ. This is true for every t-fan at v, so we have

{H ∈ N I (v|t) : u ∈ V(H)} d I (v|t) δ
and thus conf(I ) δ.

24| THE BARÁT-THOMASSEN CONJECTURE

It remains to verify Claims 1 and 2. We begin by proving Claim 1.

Proof of Claim 1: The structure of T ϕ depends on permutations in different fans. Let J(ϕ) denote the set of fans ψ for which there exists an outcome of the random permutations such that T ϕ ∩ T ψ is non-empty. Since each fan consists of at most cm edges, there are at most cm + (cm) 2 + . . . + (cm) m fans we can reach from ϕ via a path of length at most m. Thus,

|J(ϕ)| cm + (cm) 2 + . . . + (cm) m < 2(cm) m .
This shows that there are at most 2(cm) m fans where the outcome of the permutation affects the structure of T ϕ . The same calculation shows that each permutation affects the structure of at most 2(cm) m sets T ψ . Hence, the event C ϕ is mutually independent of all but at most 4(cm) 2m other events C ψ .

Before we prove Claim 2, let us introduce more terminology. Let t i and t j be two distinct vertices of T. Notice that t i or t j could be equal to t. We say that a pseudocopy H of T is (t i , t j )-bad if the images of t i and t j in H are identical. For a t-fan ϕ at a vertex v, let A ϕ (t i , t j ) be the event that the number of (t i , t j )-bad pseudo-trees in T ϕ is greater than 2c 2/3 . For a vertex u ∈ V(G) with u = v, let B ϕ (u|t i ) be the event that the number of pseudo-trees in T ϕ in which u is the image of t i is greater than 2c 2/3 . The proof of Claim 2 consists of two parts: Claim 2A: P[A ϕ (t i , t j )] < 4e -c 2/3 /32 for every t i , t j ∈ V(T) with t i = t j .

Claim 2B: P[B ϕ (u|t i )] < 4e -c 2/3 /8 for every u ∈ V(G), t i ∈ V(T) and u = v.

The proofs of Claims 2A and 2B use McDiarmid's inequality and have a very similar structure. We will therefore present all the details in the proof of Claim 2A, and only point out the differences in the proof of Claim 2B.

Proof of Claim 2A:. Fix t i and t j as different vertices of T. Let P i and P j denote the paths in T from t to t i and t j . In the case that one is a subpath of the other, we may assume that P i is contained in P j . Let t j denote the second last vertex of P j and let j denote the edge joining t j and t j . Now Tj consists of two components, one of which contains t j while the other one contains t, t i , and t j .

Let π be a fixed outcome of all permutations apart from those at the j-blades of t j -fans. In other words, given π, we only need to know the outcome of the permutations Π ψ,j for every t j -fan ψ to construct the T-pseudo-decomposition. For any such outcome π, we will show that the conditional probability P[A ϕ (t i , t j )|π] is at most 4e -c 2/3 /32 . Clearly, since we condition on an arbitrary but fixed event, this uniform bound implies Claim 2A.

Let T denote the component of Tj containing t, t i and t j , and let T denote the subgraph of T induced by E(T) \ E(T ). Let T ϕ denote the images of T in the pseudo- trees of T ϕ . By fixing π, the set T ϕ is also fixed. The permutations of the j-blades at the t j -fans only decide how the images of T and T get matched at the t j -fans.

Let Ψ denote the set of t j -fans which contain edges of pseudo-copies in T ϕ . Note that also the set Ψ is completely determined by π. Let X ϕ denote the random variable counting the number of (t i , t j )-bad pseudo-trees in T ϕ conditional on π. Notice that X ϕ only depends on the random permutations Π ψ,j with ψ ∈ Ψ.

For each pseudo-tree H ∈ T ϕ at a t j -fan ψ ∈ Ψ, we already know what the image of t i in H is. There are c -1 or c different images of T that could get matched to H at ψ, each having a distinct vertex as image of t j . Thus, there are at least c -1 different vertices that could be the image of t j in H. Since the permutation Π ψ,j is chosen uniformly at random, the probability that H will be part of a (t i , t j )-bad pseudo-tree is at most 1 c-1 . Now, by linearity of expectation,

E[X ϕ ] |T ϕ | • 1 c -1 c c -1 .
We will apply McDiarmid's inequality to the random variable Y ϕ defined by Y ϕ :=

X ϕ + c 2/3 . Clearly E[Y ϕ ] = E[X ϕ ] + c 2/3 .
Only the permutations Π ψ,j with ψ ∈ Ψ affect X ϕ and thus Y ϕ . If two elements in one of these permutations are interchanged, then the structure of two pseudo-trees in T ϕ changes. In particular, the number of (t i , t j )-bad trees in T ϕ changes by at most 2. Thus, we can choose d = 2 in McDiarmid's inequality.

If Y ϕ s, then X ϕ sc 2/3 , and thus at least sc 2/3 of the pseudo-trees in T ϕ are (t i , t j )-bad. Let H ∈ T ϕ be a part of a pseudo-tree H that is counted by X ϕ . Let v i and v j denote the images of t i and t j in H. To verify that H is (t i , t j )-bad, we only need to know which edge in the j-blade of ψ gets mapped to the same position as the edges in H in other blades of ψ. In other words, the vertex v j is determined by the position of one element in the permutation Π ψ,j , and thus v i = v j can be certified by a single outcome. Thus, X ϕ sc 2/3 can be certified by the outcomes of sc 2/3 < s choices and we can choose r = 1 in McDiarmid's inequality.

By applying McDiarmid's inequality to

Y ϕ with λ = E[Y ϕ ], d = 2, r = 1, we get P |Y ϕ -E[Y ϕ ]| > E[Y ϕ ] + 120 E[Y ϕ ] 4e - E[Y ϕ ] 32 4e -c 2/3 32 .
Since c 10 9 and

E[Y ϕ ] c 2/3 + c c-1 , we have 120 E[Y ϕ ] < 1 2 E[Y ϕ ] which implies P X ϕ > 2c 2/3 = P Y ϕ > 3c 2/3 < P |Y ϕ -E[Y ϕ ]| > 3 2 E[Y ϕ ] 4e -c 2/3 32 .
Now P[A ϕ (t i , t j )|π] < 4e -c 2/3 /32 and Claim 2A follows.

26| THE BARÁT-THOMASSEN CONJECTURE

Proof of Claim 2B:. Let t i ∈ V(T) be a fixed vertex different from t. Let P denote the path from t to t i in T. Let t j denote the second last vertex of P and let i denote the edge joining t j and t i . Now Ti consists of two components, one of which contains t and t j while the other one contains t i . Let π be any fixed outcome of all permutations apart from those at the i-blades of t j -fans. We show that the conditional probability P[B ϕ (u|t i )|π] is at most 4e -c 2/3 /8 . As π is arbitrary, this implies the general bound

P[B ϕ (u|t i )] < 4e -c 2/3 /8 .
Let X ϕ denote the random variable conditional on π which counts the number of pseudo-trees in T ϕ where u is the image of t i . The vertex u appears at most once in each t j -fan, so by linearity of expectation we have

E[X ϕ ] |T ϕ | • 1 c -1 c c -1 .
We apply McDiarmid's inequality to the random variable X ϕ + c 2/3 . Swapping two positions in a permutation Π ψ,i can affect X ϕ by at most 1 since u is incident to at most one edge of the i-blade of ψ. If X ϕ + c 2/3 s, then this can be certified by revealing at most s positions in the random permutations. Thus, applying McDiarmid's inequality to the random variable

X ϕ + c 2/3 with λ = E[X ϕ ] + c 2/3 , r = 1, d = 1 yields P X ϕ > 2c 2/3
4e -c 2/3 /8 . Now P[B ϕ (u|t i )|π] < 4e -c 2/3 /8 and Claim 2B follows.

Now the proof of Claim 2 follows easily from Claims 2A and 2B.

Proof of Claim 2: By Claim 2A, we have

P[A ϕ ] P   ∀i<j A ϕ (t i , t j )   ∑ ∀i<j P A ϕ (t i , t j ) < 4m 2 e -c 2/3 /32 .
Let B ϕ (u) be the event that the number of pseudo-trees in T ϕ containing u is greater than 2mc 2/3 . Since u cannot be the image of t, we have, by Claim 2B,

P[B ϕ (u)] P ∀i B ϕ (u|t i ) ∑ ∀i P[B ϕ (u|t i )] < 4me -c 2/3 /8 .
Since each fan consists of at most cm edges, there are at most cm + (cm) 2 + . . . + (cm) m vertices we can reach from ϕ via a path of length at most m. Thus, there are less than 2(cm) m vertices u for which P[B ϕ (u)] could be positive. In particular, we have

P[B ϕ ] = P ∀u,u =v B ϕ (u) ∑ ∀u,u =v P[B ϕ (u)] < 8(cm) m me -c 2/3 /

REPAIRING NON-ISOMORPHIC COPIES | 27

This concludes the proof of Lemma 2.15.

Repairing non-isomorphic copies

Let H ∪ I be the T-pseudo-decomposition given by Lemma 2.15. As described in

Step 2 in Section 2, we use copies in I to repair the pseudo-trees in H that are not isomorphic to T. We apply Lemma 2.18 to show the existence of a suitable subset of I to perform the switches. The proof of Lemma 2.18 relies on the following probabilistic tools, see also [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]. The first one is a generalization of the Symmetric Local Lemma (Proposition 2.19).

PROPOSITION 2.21 Lovász Local Lemma

Let A 1 , ..., A n be a finite set of events in some probability space Ω, and suppose that for some J i ⊂ [n], A i is mutually independent of {A j : j / ∈ J i ∪ {i}}. If there exist real numbers x 1 , ..., x n in (0, 1) such that

P[A i ] x i ∏ j∈J i (1 -x j ) for every i ∈ {1, ..., n}, then P[∩ n i=1 A i ] > 0.

PROPOSITION 2.22 Simple Concentration Bound

Let X be a random variable determined by n independent trials T 1 , ..., T n such that changing the outcome of any one trial T i can affect X by at most c. Then

P[|X -E[X]| > λ] 2e -λ 2 /(2c
∈ V(G), t ∈ V(T).
The value of d f t (H) (v|t ) only depends on the set of pseudo-trees in N H (v|t ) that are contained in some S(H). Let H be the collection of pseudo-copies of H that are contained in some S(H). Clearly, each tree in N H (v|t ) can be matched with exactly one tree in H and this occurs with probability 1-δm ε -1 . By linearity of expectation,

E[d f t (H) (v|t )] = 1 -δm ε -1 d H (v|t ) < 2εd H (v|t
P[A v,t ] < 2e -ε 2 d H (v|t )/2 .
We claim that A v,t is mutually independent of all but at most m 1-δm ε d H (v|t ) other events A v ,t . Indeed, A v,t depends on at most d H (v|t ) random trials, and in each trial we have a choice of 1-δm ε trees to match. Each tree affects precisely m events other than A v,t . Now we apply Proposition 2.21 to show that with positive probability none of the events A v,t occur. Set x = ε 4 8 . It is sufficient to show that

x (1 -x) m 1-δm ε d H (v|t ) P[A v,t ] holds for all compatible v ∈ V(G), t ∈ V(T). If d H (v|t ) < 2 ε 6 , then d f t (H) (v|t ) < 2 ε 6 < 3εd H (v|t ), so P[A v,t ] = 0. If d H (v|t ) 2 ε
6 , then we have

x (1 -x) m 1-δm ε d H (v|t ) x (1 -x) d H (v|t )/ε 2 xe -2xd H (v|t )/ε 2 P[A v,t ] • x 2 • e ε 2 4 d H (v|t ) P[A v,t ] • ε 2 6 d H (v|t ) P[A v,t ] .
By the Local Lemma, there is a positive probability that none of the bad events occur. Thus, there exists a function f t with the desired properties.

We now have all ingredients for the proof of Theorem 2.12.

Proof of Theorem 2.12: As described in Step 2 of Section 2, let t 0 , . . . , t m be a labelling of the vertices of T such that T[t 0 , . . . , t i ] is connected for every i ∈ {1, . . . m}. We also label the edges of T so that e i denotes the edge joining t i with T[t 0 , . . . , t i-1 ] for every i ∈ {1, . . . m}. Set ε i = 5 i-m /15m for i ∈ {1, . . . , m}. We are going to construct a sequence (H i ∪ I i ) m i=1 of T-pseudo-decompositions of G such that the following holds:

• I i is a collection of isomorphic copies of T for every i ∈ {1, . . . m};

• H i is i-good for every i ∈ {1, . . . m};

• d I i (v|t) > max{22/ε 7 i , d H i (v|t)/ε i } for every compatible v ∈ V(G), t ∈ V(T);
• conf(I i ) ε i for every i ∈ {1, . . . , m}.

Since the minimum degree in each color in G is at least 10 50m , we can apply Lemma 2.15 with parameters ε = δ = 10 -2m . Let H ∪ I denote the resulting Tpseudo-decomposition. Clearly H ∪ I satisfies the conditions for H 1 ∪ I 1 . Let i ∈ {2, . . . , m} and suppose we have constructed H i-1 ∪ I i-1 such that the conditions above are satisfied. We need to repair the pseudo-trees in H i-1 that are not i-good. Since the pseudo-trees in H i-1 are all (i -1)-good, we can achieve this by making i-switches. Let t j be the endpoint of e i that is different from t i . Let f j : H i-1 → I i-1 be the function we get by applying Lemma 2.18 with H = H i-1 , H = I i-1 , ε = δ = ε i-1 , and t = t j . Now f j (H i-1 ) is the set of trees we use to repair the pseudo-trees in H i-1 that are not i-good. Set

H i = H∈H i-1 sw i (H, f j (H)) and I i = I i-1 \ f j (H i-1 ) ,
where sw i (H, f j (H)) denotes the i-switch of H and f j (H) as defined in Section 2. Since H ∩ f j (H) = {v} for every H ∈ N H i-1 (v|t j ), the two pseudo-copies in sw i (H, f j (H)) are both i-good.

Notice that the degree d H i (v|t) of a vertex is invariant under i-switches between pseudo-trees in H i . Since d f j (H i-1 ) (v|t) 3ε i-1 d I i-1 (v|t) holds for compatible v ∈ V(G) and t ∈ V(T), we have

d I i (v|t) (1 -3ε i-1 )d I i-1 (v|t) and d H i (v|t) 4ε i-1 d I i-1 (v|t) . Thus, d H i (v|t) 4ε i-1 (1 -3ε i-1 ) d I i (v|t) 5ε i-1 d I i (v|t) = ε i d I i (v|t) , d I i (v|t) (1 -3ε i-1 )d I i-1 (v|t) 22 1 -3ε i-1 ε 7 i-1 22
ε 7 i and conf(I i ) conf(I i-1 ) 1 -3ε i-1 5 4 ε i-1 < ε i .
Hence, the T-pseudo-decomposition H i ∪ I i has the desired properties. In particular, H m is m-good and H m ∪ I m is a T-decomposition of G.

Chapter 3

Beyond the Barát-Thomassen Conjecture

Finding a weaker hypothesis

While the Tutte's 3-flow conjecture states that the required amount of edgeconnectivity is 4, Thomassen [START_REF] Thomassen | The weak 3-flow conjecture and the weak circular flow conjecture[END_REF] could only achieve 8. One year later, Lovász et al [START_REF] Miklós | Nowhere-zero 3-flows and modulo k-orientations[END_REF] showed that 6-edge-connectivity is sufficient, and so cut half the distance between the state-of-the-art and the 3-Flow Conjecture. The difference between 4-edge-connectivity and 6-edge-connectivity is indeed not as narrow as it may sound. The edge-connectivity is an expensive condition since increasing the amount of edge-connectivity on a graph by 1 means another layer of global connection needs to be added, while global connections are hard to achieve in large graphs.

Unfortunately, our proof of the Barát-Thomassen conjecture in Chapter 2 provides a terrible exponential bound, 10 O(|E(T)|) , for the amount of edge-connectivity of G due to the probabilistic approach. To reduce this amount to a reasonable bound, one may need a completely new approach, which is left for future work. On the other hand, given the high cost of edge-connectivity, it would be reasonable to some cheaper conditions for the Barát-Thomassen conjecture rather than the edge-connectivity.

QUESTION 3.1

Is it possible to replace the high edge-connectivity hypothesis in the Barát-Thomassen conjecture by some weaker ones which do not require such strong global connections?

One prominent candidate is high minimum degree, a much less costly requirement, since roughly speaking it only requires that every vertex has enough arbitrary connections to the rest of the large graph rather than every vertex must have high global connections. However, similar to the Tutte's flow conjectures, it is easy to see that in order to the Barát-Thomassen conjecture holds, the graph G must have some minimum amount of edge-connectivity. One simple example is where G is the disjoint union of two cliques of size 4n + 2 for an arbitrarily large n. Then G has very high minimum degree but cannot be decomposed into copies of P 2 , the path of length 2. The reason is that each clique of G has odd number of edges, so there is always one edge left out in each clique which could not be joint to become a copy of P 2 . A more complex example in Proposition 3.8 and Figure 3.1 gives a counterexample of a 2-edge-connected graph G with very large minimum degree, which could not have a P 9 -decomposition.

The main result of this chapter is the following theorem, which states that if G is 24-edge-connected, then high minimum degree is a sufficient condition so that the Barát-Thomassen conjecture holds when the pattern is a path.

THEOREM 3.2

For every integer 2, there exists d such that every 24-edge-connected graph G with minimum degree at least d has a decomposition into paths of length and a path of length at most .

Let us again emphasize that the main point in the statement of Theorem 3.2 is that the required edge-connectivity, namely 24, is constant and not dependent on the path length as in the statement of the Barát-Thomassen conjecture. Nevertheless, this theorem still leaves a gap to the lower bound the amount of edge-connectivity. Very recently, Klimošová and Thomassé drastically improved the bound from 24 to 3 [START_REF] Klimošová | Decomposing graphs into paths and trees[END_REF], and so by combining with Proposition 3.8 to provide a tight bound for path patterns in general. Nonetheless, the true bound for specific patterns has not yet been reached. For example, one may ask what is the minimum amount of edgeconnectivity required when the pattern is P 3 or P 5 , which is still an open question.

It is natural to expect that we can similarly replace high edge-connectivity by high minimum degree when the pattern is a tree. However, it was proved, also in [START_REF] Klimošová | Decomposing graphs into paths and trees[END_REF], that this does not hold, and so Question 3.1 is still open when the pattern is a tree.

FINDING A WEAKER HYPOTHESIS | 33

Some notations and preliminary results

In Chapter 2, we used "collection" as a set of copies of the pattern. In this chapter we will develop a system of notions around the term collection. The proof contains two main parts. We will show in Section 3.2 that the graph G contains a large collection with low conflict and covering almost entire G, and then then in Section 3.3 that G contains another sparse collection, which has a tree-shape and spanning all over G. These two collections will complement each other to return a path-decomposition of G without any conflict, and so proves Theorems 3.2.

Given a graph G and a subset X of V(G), we denote by d X (v) the degree of v in the subgraph of G induced by X ∪ {v}. Given two graphs G = (V, E) and H = (V, F) with F ⊆ E, we denote by G\H the graph (V, E\F).

We now introduce some notions about the density of a subgraph with respect to the original graph. Let H = (V, F) be a spanning subgraph of a graph G = (V, E). Let α be some real number in [0, 1]. We say that

H is α-sparse in G if d H (v) αd G (v) for all vertices v of G. Conversely, we say that H is α-dense in G if d H (v) αd G (v) for all vertices v of G.
We will also heavily depend on subgraphs of G which are both (roughly) α-sparse and α-dense. This definition depends on the length of the path . We say that

H is an α-fraction of G if αd G (v) -10 d H (v) αd G (v) + 10 .
Given an (improper) edge-coloring φ of some graph G and a color i, for every vertex v of G we denote by d i (v) the number of i-colored edges incident to v. We call φ nearly equitable if, for every vertex v and every pair of colors i = j, we have

|d i (v) -d j (v)| 2.
We can now recall a result of de Werra (cf. [START_REF] Stiebitz | Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture[END_REF], Theorem 8.7), and its corollary concerning 1/k-fractions.

PROPOSITION 3.3

Let k 1. Every graph has a nearly equitable improper k-edge-coloring.

PROPOSITION 3.4 Let k 1. Every graph G = (V, E) has a spanning subgraph H = (V, F) such that |d H (v) -d G (v)/k| 2 for every vertex v.
We now recall three results on oriented graphs. The first of these is a folklore result on balanced orientations of graphs.

PROPOSITION 3.5

Every multigraph G has an orientation D such that |d -

D (v) -d + D (v)| 1 for every vertex v.
The proof is straightforward. We first arbitrarily pair vertices of odd degree of G, then add a dummy edge between every pair to obtain a multigraph G in which every vertex has even degree. Orienting the edges of G as they are encountered when going along an Eulerian tour, we then deduce an orientation

D of G such that d - D (v) = d + D (v) for every vertex v. Removing the dummy edges results in a desired orientation D of G.
The second result is a result of Nash-Williams (see [START_REF] St | On orientations, connectivity and odd vertex pairings in finite graphs[END_REF]) implying that any graph with large edge-connectivity admits a balanced orientation with large arc-connectivity. In the following, a digraph D is k-arc-strong if the removal of any set of at most k -1 arcs leaves D strongly-connected.

PROPOSITION 3.6

Every 2k-edge-connected multigraph has an orientation D such that D is k-arcstrong and such that |d -(v)

-d + (v)| 1 for every vertex v.
The third result we recall is due to Edmonds (see [START_REF] Edmonds | Edge-disjoint branchings[END_REF]) and expresses a condition for a digraph to admit many arc-disjoint rooted arborescences. In the statement, an out-arborescence of a digraph D refers to a rooted spanning tree T of D whose arcs are oriented in such a way that the root has in-degree 0, and every other vertex has in-degree 1.

PROPOSITION 3.7

A directed multigraph with a special vertex z has k arc-disjoint out-arborescences rooted at z if and only if the number of arc-disjoint paths between z and any vertex is at least k.

For the sake of completeness, we end this section by proving the claim that 3-edgeconnectivity is necessary when the pattern is P 9 .

PROPOSITION 3.8

There exist 2-edge-connected graphs with arbitrarily large minimum degree admitting no P 9 -decomposition.

Proof. We start from the 2-edge-connected graph G depicted in Figure 3.1, which admits no P 9 -decomposition. To obtain a 2-edge-connected graph with arbitrarily large minimum degree d from it, just consider any 2-edge-connected graph G with sufficiently large minimum degree (i.e., at least d) and verifying |E(G )| ≡ 7 (mod 9). Then consider any vertex v of G with small degree, and add two edges from v to a new copy of G . Repeating this transformation as long as necessary, we get a new graph which is still 2-edge-connected, with minimum degree at least d and whose size is a multiple of 9 (due to the size of G and G ), but with no P 9 -decomposition -otherwise, it can be easily checked that G would admit a P 9 -decomposition, a contradiction.

Path-collections

Fix P as our pattern and let G = (V, E) be a graph. A path-collection P on G is a set of edge-disjoint paths of G. We denote by U P = (V, E ) the graph where E is the set of edges of paths in P. If U P = G then P is said to be a path-decomposition of G. For convenience, from now on, we say collection for path-collection and decomposition for path-decomposition.

Let us denote by H P = (V, E ) the multigraph where each edge uv ∈ E corresponds to a path between u and v in P (if P contains several paths from u to v, we have as many edges uv ∈ E ). The degree of a vertex v in P, denoted d P (v), is the degree (with multiplicity) of v in H P , which is also the number of paths in P with endpoint v.

We need also to speak of the lengths of the paths in P. Let us say that P is ancollection if all paths in P have length , a ( )-collection if all paths in P have length at least , an ( 1 , 2 , ...)-collection if all paths in P have length among { 1 , 2 , ...}, and an

[ , + i]-collection if all paths in P have length in the interval [ , + i].
Similar to Chapter 2, we also use notions of conflict and conflict ratio in this proof. Two edge-disjoint paths of G sharing an endpoint v are conflicting if they also intersect at some vertex different from v. Equivalently, we say that two paths of P issued from the same vertex are conflicting if the corresponding paths in U P are conflicting. In general, the paths of a collection can pairwise intersect, and hence we would like to measure how much. For every vertex v, let P (v) be the set of paths in P incident with v, i.e., starting or ending at v. The conflict ratio of v is

conf P (v) := max w =v {P ∈ P (v) : w ∈ P} d P (v) .
We denote the conflict ratio of P by conf(P ) := max v conf P (v). We always have conf(P )

1 since |P (v)| = d P (v).
We now prove that every graph with large enough minimum degree contains a ( )-collection meeting particular properties: low conflict, well-balanced, and covers almost entire G. Note that in this section, the edge-connectivity of G will not be utilized.

THEOREM 3.9

Let be a positive integer, and ε be an arbitrarily small positive real number. There exists L such that if G = (V, E) is a graph with minimum degree at least L, then there is an -collection P on G with

• conf(P ) ε,

• d P (v)/d G (v) ∈ 1-ε , 1+ε
for every vertex v, and

• d G\U P (v) εd P (v) for every vertex v. Proof. Let c := [ √ L] and b := [c 2/3
], and pick L so that b . According to Proposition 3.3, we can nearly equitably color the edges of G with colors. For every color i, applying Proposition 3.5 we can orient the i-colored edges so that the numbers of inedges and out-edges of color i incident to every vertex v differ by at most 1. Let E - i (v) and E + i (v) be the sets of i-colored in-edges and out-edges, respectively, incident to v. Then, for every color i ∈ {1, ..., -1}, we have

|E - i (v)| -|E + i+1 (v)| 2.
For the sake of convenience, we would like to have that

|E - i (v)| = |E + i+1 (v)| for all i and v. To this end, we add a dummy vertex v 0 to G. Now, if |E - i (v)| -|E + i+1 (v)| = k > 0, then we add k dummy edges of color i + 1 from v to v 0 to equalize |E - i (v)| and |E + i+1 (v)|. Similarly, if |E + i+1 (v)| -|E - i (v)| = k > 0, then we add k dummy edges of color i from v 0 to v. Now, for every v ∈ V(G) and color i ∈ {1, ..., }, we choose r v,i ∈ {0, . . . , c -2} such that E - i (v) ≡ r v,i (mod c -1)
. Since the minimum degree in each color in G is greater than c(c -2), we can partition every set E - i (v) into subsets of size c and c -1 so that precisely r v,i of them have size c.

As E + i+1 (v) = E - i (v)
, we can similarly partition every set E + i+1 (v) into subsets of size c and c -1 so that precisely r v,i of them have size c.

We call these subsets of edges i-half-cones and (i + 1)-half-cones, respectively. Now, for each vertex v and color i,

1 i -1, we arbitrarily pair i-half-cones of E - i (v) with (i + 1)-half-cones E + i+1 (v)
in a way such that in each pair the size of the two halfcones are equal. We call such a pair an i-cone at vertex v. Thus, an i-cone ϕ at some vertex v consists of an i-half-cone ϕ -and an (i + 1)-half-cone ϕ + with |ϕ -| = |ϕ + |. Note that an edge e of color i directed from a vertex u to a vertex v in G appears both in an i-half-cone of E + i (u) as well as in an i-half-cone of E - i (v), but we do not require these two i-half-cones to have the same size. By convention, we do not create a cone at the dummy vertex v 0 . However, each edge uv 0 will still be inside a cone at vertex u. We also remark that the 1-half-cones of E + 1 (v) and the -half-cones of E -(v) do not get paired with other half-cones. Nevertheless, we will adopt the convention that whenever we talk of a general cone ϕ, we will assume that ϕ might also consist of a single 1-half-cone or -half-cone of the aforementioned type.

We now have a fixed set of cones on G. To obtain our desired collection, we will use the cone structure to construct rainbow paths of length , i.e., paths where for all i the i th edge of every path is of color i. One way to obtain this is to randomly match edges of the two half-cones of every cone. Indeed, this is what we do. For each cone ϕ we carry out random permutations π - ϕ of the edges of ϕ -and π + ϕ of the edges of ϕ + . We then pair the edges π - ϕ (k) and π + ϕ (k) for each 1 k c. If ϕ is actually a special 1-half-cone or -half-cone, then there is only one random permutation performed at ϕ, which will have no effect on the decomposition as will be apparent shortly. Note that each edge e = uv of G, with the exception of some edges of 1-cones, some edges of -cones and the dummy edges, is in exactly two cones -one centered at u and the second centered at v. Thus, e is involved in two random permutations corresponding to the two permutations of the two half-cones containing it. Therefore, given the random matchings, each non-dummy edge e = uv of color i, 1 < i < , is paired exactly with one edge of color i -1 (which enters u) and one edge of color i + 1 (which exits v). From an arbitrary edge, we can thus go forward and backward by edges paired with it until we reach edges of color or 1 (unless we reach dummy edges). Thus, the random matchings yield a natural decomposition of all edges of G into edge-disjoint walks. Unfortunately, some of the walks will not be paths. We will divide the walks into three types. Of the first type are those walks which are paths, and thus by construction they are necessarily isomorphic to P . A walk that is not a path and which does not use the dummy vertex v 0 is called a bad walk; note that every bad walk is of length . A walk that uses the dummy vertex v 0 is called a short walk. Note that a short walk is no longer extended from v 0 as there is no cone centered at v 0 .

For each cone ϕ, there are c -1 or c walks via ϕ, depending on |ϕ|. We will show that, with high probability, the number of bad or short walks via ϕ is negligible compared to c. We then will argue that proving this statement for all the cones is sufficient for us to extract a dense collection from G.

Denote P := x 0 x 1 ...x . We first focus on bad walks. Suppose that ϕ is a k-cone at some vertex v, and i, j are two colors. We say that a bad walk P = u 0 u 1 ...u going through ϕ is (i, j)-bad if its i th vertex and j th vertex are the same, that is, u j = u i . Let A ϕ (i, j) be the event that the number of (i, j)-bad walks going through the cone ϕ is greater than b. We will show that P[A ϕ (i, j)] < 4e -c 2/3 /64 . Denote by P i,k and P j,k the subpaths from x i to x k , and x j to x k in P , respectively. In case one of these paths is contained in another, we may assume that P i,k is contained in P j,k . Let x j be the neighbor of x j in P j,k . Note that j ∈ {j -1, j + 1}. Let P ϕ be the set of walks that go through ϕ which are not short. Clearly, |P ϕ | c.

We define Ω j to be the set of all j -cones in G if j = j -1, and the set of all jcones if j = j + 1. Let Π be an arbitrary but fixed outcome of all permutations at all cones except the set of permutations on Ω j . In other words, given Π, we only need to know the outcomes of the set of permutations {π + ϕ , π - ϕ | ϕ ∈ Ω j } to know the decomposition of the walks in G. We will condition on Π; that is, we will show that P[A ϕ (i, j)] | Π] < 4e -c 2/3 /64 for any Π. Clearly, since Π is arbitrary, this is sufficient to give us the uniform bound P[A ϕ (i, j)] < 4e -c 2/3 /64 . Let P ϕ denote the set of walks P ϕ conditional on Π. Let X ϕ be the number of (i, j)bad walks going through the cone ϕ conditional on Π. By fixing Π, the set P ϕ is also fixed. Indeed, each P ∈ P ϕ is a partial subwalk, where we know the vertex of P that lies in some half-cone of a cone ψ ∈ Ω j . Note that the vertex u i of P corresponding to x i is already known. Moreover, the vertex u j corresponding to the vertex x j is known as well.

Note that whether P is (i, j)-bad depends only on the permutations π - ψ and π + ψ . Note that there are c -1 or c different images possible to match u j when the random permutations π - ψ and π + ψ are carried out, and only one of which could possibly be u i . Thus, the probability that P is (i, j)-bad is at most 1 c-1 . Now, by linearity of expectation,

E[X ϕ ] |P ϕ | • 1 c -1 c c -1 .
We will apply McDiarmid's inequality to the random variable Y ϕ defined by

Y ϕ := X ϕ + c 2/3 . Clearly E[Y ϕ ] = E[X ϕ ] + c 2/3 ∈ [c 2/3 , c 2/3 + 2]. Only the permutations π - ψ , π + ψ with ψ ∈ Ω j affect X ϕ and thus Y ϕ .
If two elements in one of these permutations are interchanged, then the structure of two walks in P ϕ changes. However, clearly the number of (i, j)-bad walks in P ϕ cannot change by more than 2. Thus, we

can choose d = 2 in McDiarmid's inequality. If Y ϕ s, then X ϕ s -c 2/3
, and thus at least sc 2/3 of the walks in P ϕ are (i, j)bad. Let P ∈ P ϕ be a subwalk of a walk P that is counted by X ϕ . As before, let u i = u j denote the images of x i and x j in P, and ψ ∈ Ω j the cone through which P passes. To verify that P is (i, j)-bad, we only need to reveal the two elements π + ψ (s), π - ψ (s), where 1 s c is the value such that the edge u j u j ∈ {π + ψ (s), π - ψ (s)}.

Thus, X ϕ sc 2/3 can be certified by the outcomes of 2(sc 2/3 ) < 2s choices and we can choose r = 2 in McDiarmid's inequality. By applying McDiarmid's inequality to

Y ϕ with λ = E[Y ϕ ], d = 2, r = 2, we get P |Y ϕ -E[Y ϕ ]| > E[Y ϕ ] + 120 2E[Y ϕ ] 4e - E[Y ϕ ] 64 4e -c 2/3 64
and thus P X ϕ > 2c 2/3 4e -c 2/3 /64 . So we have P[A ϕ (i, j)|Π] < 4e -c 2/3 /64 . Since Π is arbitrary it follows that P[A ϕ (i, j)] < 4e -c 2/3 /64 . Let A ϕ be the event that there are more than 2 b bad walks via ϕ. Then

P[A ϕ ] P ∀i,j A ϕ (i, j) ∑ ∀i,j P[A ϕ (i, j)] < 4 2 e -c 2/3 /64 .
We still consider the same cone ϕ. For an integer j = k and vertex u, let B ϕ (j, u) be the event that the number of walks via ϕ, which maps x j to u, is greater than b, and let B ϕ (u) be the event that the number of walks of ϕ containing u is greater than b.

We show that P[B ϕ (j, u)] < 4e -c 2/3 /64 . As the computation is virtually identical to the case of P[A ϕ (i, j)], we only highlight the differences. As before, let x j be the vertex adjacent to x j on P j,k , and let Π be an arbitrary but fixed outcome of all permutations at all cones except the set of permutations on Ω j . It suffices to show that

P[B ϕ (j, u) | Π] < 4e -c 2/3 /64 .
Let X ϕ denote the random variable conditional on Π which counts the number of walks in P ϕ where u is the image of x j . The vertex u appears at most once in each cone of Ω j , so by linearity of expectation we have

E[X ϕ ] |P ϕ | • 1 c -1 c c -1 .
We again apply McDiarmid's inequality to the random variable Y ϕ defined by

Y ϕ := X ϕ + c 2/3 . As before, E[Y ϕ ] = E[X ϕ ] + c 2/3 .
Since the vertex u appears at most once in each cone of Ω j , swapping two positions in any permutation of a half-cone in Ω j can affect X ϕ by at most 1. Thus, we can

choose d = 1 in McDiarmid's inequality. If Y ϕ s, then X ϕ s -c 2/3
. Let P be a subwalk that is counted by X ϕ . As before, we can certify that P is counted by X ϕ by considering only ψ ∈ Ω j , the cone through which P passes.

To certify that P is counted by X ϕ we only need to reveal the two elements π + ψ (s), π - ψ (s), where s is the value such that one of the edges π + ψ (s), π - ψ (s) contains the endpoint u. Thus, X ϕ sc 2/3 can be certified by the outcomes of 2(sc 2/3 ) < 2s choices and we can choose r = 2 in McDiarmid's inequality. Thus, by a similar argument as above we obtain that P[B ϕ (j, u)] < 4e -c 2/3 /64 . Now,

P B ϕ (u) P ∀i B ϕ (i, u) ∑ ∀i P B ϕ (i, u) < 4 e -c 2/3 /64 .
Let B ϕ be the event that there exists a vertex u such that more than b walks of ϕ contain u. The number of vertices u that could possibly appear in the walks P ϕ is at most c + c 2 + ... + c < c +1 . Hence,

P[B ϕ ] = P ∀u B ϕ (u) ∑ ∀u P[B ϕ (u)] < 4c +1 e -c 2/3 /64 .
Let B ϕ (j) be the event that the number of walks via ϕ such that they enter v 0 at exactly their j th -vertex is greater than b, and let B ϕ be the event that the number of walks of ϕ containing v 0 is greater than b. We upper bound P[B ϕ (j)].

The argument is virtually identical to that of the estimate above. We apply Mc-Diarmid's inequality to the random variable Y ϕ := X ϕ + c 2/3 , where X ϕ is the number of walks via ϕ that enter v 0 at the j th edge conditional on Π. As before, we ob-

tain that E[X ϕ ] c/(c -1), d = 1, r = 2, yielding P[B ϕ (j)]
4e -c 2/3 /64 . Thus,

P[B ϕ ] < 4 e -c 2/3 /64 . Let J ϕ = A ϕ ∪ B ϕ ∪ B ϕ . Then P[J ϕ ] P[A ϕ ] + P[B ϕ ] + P[B ϕ ] < ( 2 + c +1 + )4e -c 2/3 /64 < e -b/100 .
Let J ϕ be the set of events J ψ that are not mutually independent of J ϕ . Note that the number of permutations determining J ϕ is at most (2c) + (2c) 2 + ... + (2c) < c +1 . Indeed, c +1 is an upper bound on the number of walks of length that could contain an edge of ϕ. Each such permutation itself could affect at most c + ...

+ c < c +1 events J ψ . Thus, |J ϕ | (c +1 ) 2 .
We now apply the symmetric version of the Local Lemma. To that aim, we need to have that (c +1 ) 2 e -b/100 < 1/4, which clearly holds since is fixed and c is sufficiently large. Thus, by Lovász Local Lemma, P ∀ϕ J ϕ > 0. Thus, there exists pairings of the edges of the cones Γ such that no event J ϕ occurs for every cone ϕ.

Let P be the -collection obtained from Γ by removing all bad walks and short walks. Let R := G\U P . We can assume that L is sufficiently large so that 4 b < ε(1ε)c/2. Then:

(i) In every cone ϕ, there are no more than εc bad and short walks via it, so there are at least (1ε)c paths in P via it. Hence, using the fact that G is nearly equitably colored and by considering the special 1-half and -half-cones, we obtain that for every vertex v, there are at least 1-ε 2 d G (v) paths in P starting at v, and at least 1-

ε 2 d G (v) paths in P ending at v. Hence, d P (v) 1-ε d G (v).
The nearly equitable -edge-coloring implies immediately that d P (v) 1+ε d G (v).

(ii) For every pair of vertices u, v, u = v, among all walks via a cone of u, the ratio of walks going through v is less than 2 b/c < ε/2 . Hence, among all walks via u, the ratio of walks going through v is less than ε/2 . Thus

|{P ∈ P : u, v ∈ P}| d G (u) ε/2 ,
and, hence, conf(u) ε.

(iii) In every cone, there are no more than 3 b bad and short walks via it, so the proportion of bad walks is at most 3

b/c < ε(1 -ε)/2 .
Hence, among all walks via a vertex v, the ratio of bad and short walks is less than

ε(1 -ε)/2 . Thus d R (v) < ε(1 -ε)d G (v)/2 , implying d R (v) εd P (v).
This completes the proof of Theorem 3.9.

In the sequel, given two collections P 1 and P 2 over the same graph, we will need to grow paths of, say, P 1 using the paths from P 2 . This will essentially be achieved by considering every path P of P 1 , incident to, say, a vertex v, then considering a path P incident to v in P 2 , and just concatenating P and P . So that the concatenation can be performed this way for every path of P 1 , we just need P 2 to have enough paths, and to make sure to evenly use these paths. The latter requirement can be ensured by just orienting P 2 in a balanced way, that is so that |d

+ (v) -d -(v)|
1 for every vertex v, and choosing, as P , a path out-going from v. All such out-going paths are called private paths of v throughout the upcoming proofs.

The collection P we get from G after applying Theorem 3.9 hence satisfies 1-ε

d G (v) d P (v) 1+ε d G (v)
for every vertex v. If we preserve the orientation of the edges of H as in the proof, and denote by d + P (v) the number of paths starting from v in P, we get

1 -ε 2 d G (v) d + P (v) 1 + ε 2 d G (v)
for every vertex v. These d + P (v) paths out-going from v will hence be regarded as its private paths in what follows.

THEOREM 3.10

Let be a positive integer, and ε be a sufficiently small positive real number depending on . There exists L such that, for every graph G with minimum degree at least L, there is an ( , + 1)-collection P decomposing G with

• conf(P ) 1/4( + 10), and

• 1-ε d G (v) d P (v) 1+ε d G (v) for every vertex v.

42| BEYOND THE BARÁT-THOMASSEN CONJECTURE

Proof. Let ε > 0 be sufficiently small, and set ε := ε /10 . Let G 1 be a 1/9 -fraction of G obtained by Proposition 3.4, and G 2 := G\G 1 . By applying Theorem 3.9 on G 1 and G 2 with ε, we get two -collections P 1 and P 2 and two remainders R 1 and R 2 satisfying all properties from the statement of Theorem 3.9. For convenience, we will keep the orientation of the edges of P 1 and P 2 given by Theorem 3.9. Note that

1-ε • d G (v) 9 -2 d P 1 (v) 1+ε • d G (v) 9 + 2 and 1-ε • (9 -1)d G (v) 9 -2 d P 2 (v) 1+ε • (9 -1)d G (v) 9 + 2 . Now, we have 1-ε (1+ε)(9 -1) d P 2 (v) -10 d P 1 (v) 1+ε (1-ε)(9 -1) d P 2 (v) + 10 for all vertices v. Let R := R 1 ∪ R 2 . Then for every vertex v, we have d R (v) = d R 1 (v) + d R 2 (v) εd P 1 (v) + εd P 2 (v) 10 εd P 1 (v).
Arbitrarily orient the edges of R. In our construction, every step consists in extending an arc vu of R using a private (i.e., out-going) -path starting at v in P 1 that does not contain u -thus forming an ( + 1)-path. Since the conflict ratio of P 1 satisfies conf(P 1 ) ε, at most εd P 1 (v) paths in P 1 with v as endpoint contain u. Note that the number of directed -paths in P 1 starting at v is v) . Thus,

d + P 1 (v) 1 2 • (1-ε)d G 1 (
d + P 1 (v) -d R (v) > εd P 1 (v)
since L can be chosen sufficiently large. Hence, all the d R (v) edges can be used to form ( + 1)-paths.

We call P 1 the resulting ( , + 1)-collection obtained by concatenating paths from P 1 and paths from R. Since d R (v) 10 εd P 1 (v) for every v, the degree of v in P 1 is as

d P 1 (v) -10 εd P 1 (v) d P 1 (v) d P 1 (v) + 10 εd P 1 (v).
Let P := P 1 ∪ P 2 . Then P is an ( , + 1)-collection decomposing G, in which we have d P (v) = d P 1 (v) + d P 2 (v) for all vertices v. Thus,

d P 1 (v) -10 εd P 1 (v) + d P 2 (v) d P (v) d P 1 (v) + 10 εd P 1 (v) + d P 2 (v). Thus, 1-ε d G (v) -10 εd P 1 (v) + 1 d P (v) 1+ε d G (v) + 10 εd P 1 (v) + 1. Since ε = 10 ε, we obtain that 1-ε d G (v) d P (v) 1+ε d G (v).
Observe also that d P 1 (v)/d P 2 (v) 1/6 . Thus, conf(P ) conf(P 2 ) + conf(P 1 )/6 ε + 1/6 < 1/4( + 10), as required.

TREE-LIKE COLLECTIONS | 43

Tree-like collections

This part is the combinatorial core behind the proof of Theorem 3.2. We call P a tree-like collection if H P is a tree (even if the paths of P pairwise intersect). We also say that P spans G if H P spans G. We need here to show the existence of particular tree-like collections, namely ( , 2 )-tree-like collections, under mild connectivity and minimum degree requirements. These ( , 2 )-tree-like collections will play a crucial role to insure that some collection has all of its vertices being of even degree. However, directly getting an ( , 2 )-tree-like collection seems a bit challenging, and we will follow a long way for this, starting with a (1, 2)-tree-like collection and making its paths grow.

We start with the following lemma which is the key for the drop of the large edgeconnectivity requirement.

LEMMA 3.11

Every 2-edge-connected multigraph G has a spanning (1, 2)-tree-like collection T such that H T is subcubic.

In this proof and the proof of following lemmas, we use a notion called structuredtree, which is a special digraph satisfying some specific properties. At first, a structured-tree is not a collection but will ultimately evolves to a tree-like collection.

Proof. Let G be connected and bridgeless. Let us call a structured-tree T a stronglyconnected digraph whose vertices are subsets X i of V(G) satisfying the following properties:

• The X i 's form a partition of V(G).

• The arcs of T are of two types: the forward arcs forming a rooted outarborescence A, and the backward arcs, always directed from a vertex to one of its ancestors in A.

• Every arc X i X j corresponds to some edge x i x j ∈ E(G) such that x i ∈ X i and x j ∈ X j .

• There is at most one backward arc leaving each vertex X i (unless T is rooted at X i ).

• Internal vertices of A are singletons.

• Every leaf X i of A is spanned by a (1, 2)-tree-like collection T i on G with maximum degree 3.

• The (unique) forward and backward arcs incident to a leaf X i have endpoints in T i with degree at most 2, and if these endpoints coincide, the degree is at most 1 in T i . In other words, adding the arcs as edges of T i preserves maximum degree 3.

• Every edge of G is involved in at most one arc of T and one path of T i . In other words, the edges of G involved in T and the T i 's are distinct.

Let G be connected and bridgeless. Let us call T a strongly-connected digraph whose vertices are subsets X i of V(G) satisfying the following properties:

• The X i 's form a partition of V(G).

• The arcs of T are of two types: the forward arcs forming a rooted outarborescence A, and the backward arcs, always directed from a vertex to one of its ancestors in A.

• Every arc X i X j corresponds to some edge x i x j ∈ E(G) such that x i ∈ X i and x j ∈ X j .

• There is at most one backward arc leaving each vertex X i (unless T is rooted at X i ).

• Internal vertices of A are singletons.

• Every leaf X i of A is spanned by a (1, 2)-tree-like collection T i on G with maximum degree 3.

• The (unique) forward and backward arcs incident to a leaf X i have endpoints in T i with degree at most 2, and if these endpoints coincide, the degree is at most 1 in T i . In other words, adding the arcs as edges of T i preserves maximum degree 3.

• Every edge of G is involved in at most one arc of T and one path of T i . In other words, the edges of G involved in T and the T i 's are distinct.

We first show that G has such a structured-tree T , using a classical algorithm to find a strongly-connected orientation of a bridgeless graph. Fix a vertex x and compute a Depth-First-Search tree A from x. Orient the edges of A from x to form the forward arcs. By the DFS property, every edge of G not in A joins vertices which are parents. Orient these edges from the descendent to the ancestor: these are our backward arcs. Since we need to keep at most one backward arc issued from every vertex, we only keep the arc going to the lowest ancestor. Note that we obtain a structured-tree T , where each X i is a singleton vertex in G and every leaf T i is a trivial (1, 2)-tree-like collection on one vertex.

TREE-LIKE COLLECTIONS | 45

We now prove that every structured-tree T with at least two vertices on G can be reduced to one with less vertices. This will imply that T can be reduced to a single vertex X i = V(G), hence providing the subcubic spanning (1, 2)-tree-like collection T i .

We start by deleting the backward arcs of T which are not needed for strong connectivity. Then we consider an internal vertex X j = {x j } of A with maximal height. Let X 1 , X 2 , ..., X r be the (leaf) children of X j . Each forward arc X j X i corresponds to an edge x j x i , where x j ∈ X j and x i ∈ X i . Each of these leaves X i is the origin of a backward arc X i X i which we write y i x i , where y i ∈ X i and x i ∈ X i . We assume that our enumeration satisfies that X i+1 is always an ancestor of X i (possibly equal to X i ). We now discuss the different reductions, in which the conditions of structured-trees are easily checked to be preserved.

• If X j has only one child X 1 and is not the origin of a backward arc, we merge X 1 and X j into a unique leaf X 1j spanned by the (1, 2)-tree-like collection T 1 ∪ {x 1 x j }. If X j is the root, we are done, otherwise we let the forward arc entering X 1j be the one entering X j , and the backward arc leaving X 1j be X 1j X 1 (thus corresponding to the edge y 1 x 1 ).

• If X j has only one child and is the origin of a backward arc X j X j , we merge X 1 and X j into a unique leaf X 1j spanned by the (1, 2)-tree-like collection T 1 ∪ {x 1 x j }. The forward arc entering X 1j is the one entering X j , and the backward arc leaving X 1j is the one of X j X j .

• If X j has at least three children, or X j has two children and is the origin of a backward arc, observe that deleting X 1 and X 2 from T preserves strong connectivity. Hence we merge X 1 and X 2 into a unique leaf X 12 spanned by the (1, 2)-tree-like collection T 1 ∪ T 2 ∪ {x 1 x j x 2 }. The forward arc entering X 12 is x 1 y 1 (hence reversing the backward arc X 1 X 1 ), and the backward arc leaving X 12 is X 12 X 2 corresponding to y 2 x 2 .

• The last case is when X j has two children X 1 and X 2 and is not the origin of a backward arc. Here we merge X 1 , X 2 , X j into a unique leaf X 12j spanned by the (1, 2)-tree-like collection T 1 ∪ T 2 ∪ {x 1 x j } ∪ {x 2 x j }. If X j is the root, we are done, otherwise we let the forward arc entering X 12j be the one entering X j , and the backward arc leaving X 12j be X 12j X 2 (thus corresponding to y 2 x 2 ).

This completes the proof of Lemma 3.11.

We now turn our (1, 2)-tree-like collection into a (1, k)-tree-like collection. For this we need to feed our original 2-edge-connected graph G (in which we find the (1, 2)tree-like collection) with some additional graph H, edge-disjoint from G, and with large enough degree.

LEMMA 3.12

Let G = (V, E) be a graph. Let T be a spanning (1, k)-tree-like collection of G, where k

2. Let H be a graph on V, edge-disjoint from G, with the property that d H (v) 2(d T (v) + 2k) for every vertex v of G. Then there is a (1, k + 1)-tree-like collection T spanning G ∪ H.

Proof. Start by arbitrarily orienting the edges of H in a balanced way so that every vertex v of H has outdegree at least d T (v) + 2k. Every vertex is hence provided with a set of private edges in H, namely, its out-going arcs. We will use these private edges to transform k-paths of T into (k + 1)-paths.

In this proof, a structured-tree T on G is a rooted (1, k)-tree-like collection whose vertices are subsets X i partitioning V(G) and satisfying the following properties:

• If X i X j is an edge in T , then there exists a corresponding 1-path or k-path x i x j ∈ E(T), where x i ∈ X i and x j ∈ X j .

• If X j has children X 1 , ..., X r in T then there is a unique x j ∈ X j such that x 1 x j , ..., x r x j are the corresponding paths in E(T). We call x j the center of X j .

• Every vertex X i of T is spanned by a (1, k + 1)-tree-like collection T i .

Initially, let T be the structured-tree T , where each X i is a singleton element {x i } in V(T). Note that all the vertices of T are trivial (1, k + 1)-tree-like collections. Our goal is to iteratively reduce T to a structured-tree consisting of one single vertex X i , hence providing a spanning (1, k + 1)-tree-like collection T i . We will always make sure that at any iteration every center x j has at least r + 2k private edges, where r is the number of children of X j , hence guaranteeing the repetition of the process. Let us now show that T can be reduced to a structured-tree with less vertices (unless T is a single vertex).

We consider an internal vertex X j of T with maximal height. Let X 1 , ..., X r be the (leaf) children of X j corresponding to paths x 1 x j , ..., x r x j , where x j is the center of X j . If one of these paths, say x 1 x j , is an edge, we simply create a new vertex X 1j by concatenating X 1 and X j and letting T 1j = T 1 ∪ T j ∪ {x 1 x j }. So we can assume that every x i x j -path has length k.

Consider X j and one of its children, say X 1 . Let y be a private neighbor of x j which is not a vertex of the path x j x 1 . Such a y exists since x j has at least 2k + r private neighbors. We distinguish two cases, in which the conditions of structured-trees are easily checked to be preserved:

• We first consider the case where y is in some X i , X i = X 1 . Call P the (k + 1)-path obtained by concatenating the k-path x 1 x j with the edge x j y. We here add X 1 to the set X i to form the set X 1i which is spanned by T 1i = T 1 ∪ T i ∪ {P}. Here x j loses one private edge, but X j has one less child.

• The second case is when y ∈ X 1 . We here add X 1 to the set X j to form the set X 1j which is spanned by the (1, k + 1)-tree-like collection T 1j = T 1 ∪ T j ∪ {x j y}.

Here x j loses one private edge, but X j has one less child.

This completes the proof of Lemma 3.12.

The next result follows from Lemma 3.11 and repeated applications of Lemma 3.12:

COROLLARY 3.13
For every , there exists L such that if G = (V, E) is a 2-edge-connected graph and H is another graph on V, edge-disjoint from G, with minimum degree at least L, then one can form a spanning (1, + 1)-tree-like collection T where d T (v) d H (v) for every vertex v.

Proof. We first apply Lemma 3.11 to get a subcubic (1, 2)-tree-like collection T 0 from G. Fix a sufficiently small ε 1 > 0. We choose a sequence of edge-disjoint subgraphs H 1 , ..., H -1 of H, where each H i is an ε i -fraction of H, where ε i+1 = 4ε i for all i. Free to choose L large enough as a function of ε 1 , we can clearly obtain the desired subgraphs H 1 , ..., H -1 by repeatedly applying Proposition 3.4. Since L is sufficiently large, for each vertex v, we have that d H 1 (v) ε 1 L -10 > 2d T 0 (v) + 4 . Thus, by Lemma 3.12, we can use H 1 to extend T 0 into a (1, 3)-tree-like collection T 1 . Note that

d T 1 (v) d T 0 (v) + d H 1 (v). Now we have that d H 2 (v) 3.5d H 1 (v) > 2d T 1 (v) + 4 ,
and thus, we can again use H 2 as an additional graph to extend T 1 into a (1, 4)-tree-like collection T 2 with

d T 2 (v) d T 0 (v) + d H 1 (v) + d H 2 (v).
We iterate this process to form our (1, + 1)-tree-like collection T . Note that

d T (v) d T 0 (v) + -1 ∑ i=1 d H i (v) < L d H (v),
where the second to last inequality follows from the fact that we can choose ε 1 to be arbitrarily small.

Our ultimate goal now is to find tree-like collections where the lengths of the paths are a multiple of some fixed value . One way to do so is to transform some (1, + 1)tree-like collections into ( , 2 )-tree-like collections. Note that if is even, and our graphs G and H are bipartite with the same bipartition, then there is no spanning ( , 2 )-tree-like collection since an even path always connects a partite set with itself. The next result asserts that we can nevertheless connect each partite set separately.

LEMMA 3.14

For every even integer , there exists L such that if G = (V, E) is a 2-edgeconnected bipartite graph with vertex partition (A, B) and H is another bipartite graph on V with vertex partition (A, B), edge-disjoint from G, and with minimum degree at least L, then one can form an ( , 2 )-tree-like collection T spanning A where d T (v) d H (v) for every vertex v.

Proof. We first use a small ε-fraction of H (and still call H the graph minus this fraction for convenience) in order to apply Corollary 3.13. We can then obtain a spanning (1, + 1)-tree-like collection T where d T (v)

εd H (v) for all vertices v. Note that ε > 0 can be taken arbitrarily small since we can take L so that εL is sufficiently large to apply Corollary 3.13. We now apply Theorem 3.9 on H to find an ( -1)collection H (while preserving the balanced orientation given by the proof) on H with conf(H ) ε and

1 -ε -1 d H (v) d H (v) 1 + ε -1 d H (v)
for all vertices v.

In our construction, every step consists in extending a path P of T starting at some vertex v using a private (i.e., out-going) ( -1)-path from H . This will form either an -path or a 2 -path. According to the conflict ratio assumption and the fact that ε can be chosen to be sufficiently small, every such P is conflicting with at most |P|εd H (v) < d H (v)/8 private paths of v, which is 1/4 total number of private paths of v. In our upcoming process, the total number of private paths of v we will use is at most d T (v) εd H (v), thus at most 1/4 of the total number of private paths of v since

d + H (v) 1-ε 2 d H (v).
Hence, even if we have already used 1/4 of the private paths of v, and we need a private path of v which is non-conflicting with two paths of T incident to v, we can still find one. Thus, in the upcoming arguments, we always assume that a private path is available whenever we need one.

We now turn to the construction of the ( , 2 )-tree-like collection T spanning A.

A structured-tree T on G is a rooted tree in which the vertices are disjoint subsets X i whose union covers a subset of V(G) containing A with the following properties:

• If X i X j is an edge in T , then there exists a corresponding 1-path or ( + 1)-path

x i x j ∈ E(T), where x i ∈ X i and x j ∈ X j .

• If X j has children X 1 , ..., X r then there is a unique x j ∈ X j such that x 1 x j , ..., x r x j are the corresponding paths in T . We call x j the center of X j .

• Every vertex X i containing an element of B is a singleton, i.e., X i = {x i }.

• Every vertex X i of T is spanned by an ( , 2 )-tree-like collection T i .

TREE-LIKE COLLECTIONS | 49

We again start with T equal to T in the sense that all X i 's are singletons, and all T i 's are trivial ( , 2 )-tree-like collections. We root T at some arbitrary vertex of A. Again our goal is to show that we can reduce T until it is reduced to its root, which will therefore be equal to the set A, covered by an ( , 2 )-tree-like collection. Note that since is even, we always have that an edge X i X j of T connects a vertex of B and a subset of A.

Observe first that if T has a leaf in B, we can simply delete it and keep our properties. We can then assume that all leaves are subsets of A. We consider an internal vertex X j of T with maximal height. Let X 1 , X 2 , ..., X r be the (leaf) children of X j corresponding to the paths x 1 x j , ..., x r x j . Note that all X i 's are subsets of A, and that X j = {x j } is in B. We now discuss the different reductions, in which the conditions of structured-trees are easily checked to be preserved.

Consider X j and one of its children, say X 1 . Let X k be the parent of X j in T . Note that X k is a subset of A. We denote by x j x k the path of T joining X j and X k . Let y be a private neighbor of x j which is not a vertex of the path x j x k and x j x 1 . We again consider two cases:

• First assume that y is in some X i , with X i = X 1 . We denote by P the path obtained by concatenating the path x 1 x j with x j y. Note that P is an -path or a 2 -path. We add X 1 to the set X i to form the set X 1i which is spanned by T 1i = T 1 ∪ T i ∪ {P }. Note that x j loses a private path, but X j has one less child.

• Otherwise, y ∈ X 1 . We add X 1 to the set X k to form the set X 1k which is spanned by the ( , 2 )-tree-like collection T 1k = T 1 ∪ T k ∪ {P }, where P is the concatenation of x k x j and x j y (note that P is an -path or a 2 -path). Note that x j loses a private path, but X j has one less child.

This completes the proof of Lemma 3.14

We will also need the following lemma.

LEMMA 3.15

Let be a positive integer. There exists L such that if

G 1 = (V, E) is a 2-edge- connected graph and G 2 = (V, F) is a graph of minimum degree at least L edge- disjoint from G 1 , then there is a connected [ , + 3]-collection P decomposing G 1 ∪ G 2 with conf(P ) < 1 2( +10) .
Proof. Start by applying Lemma 3.11 to get a spanning (1, 2)-tree-like collection T of G 1 such that H T is subcubic, and put the non-used edges of G 1 in G 2 . Still calling this graph G 2 , we decompose G 2 into a 1/(5 )-fraction R 1 and a 1 -1/(5 )-fraction R 2 , by Proposition 3.3. Thus, by Theorem 3.10, G 2 can then be decomposed into two ( , + 1)-collections P 1 and P 2 , respectively, both having conflict ratio at most 1 4( +10) , and verifying

1 -ε (5 -1)(1 + ε) d P 2 (v) d P 1 (v) 1 + ε (5 -1)(1 -ε) d P 2 (v)
for all vertices v, and any ε.

In our construction, every step consists in extending a path P of T starting at v using a private ( )-path starting at v in P 1 (where we recall that the private paths at any vertex are its out-going paths in a balanced orientation of P 1 ). This will form a ( )-path. By the assumption on the conflict ratio, every P is conflicting with at most, say, half of the private paths of v. Because H T is subcubic, the total number of private paths of v we will need is at most 6. Since L can be chosen so that

L 5 • 1 2 • 1 -1 4( +10)
is arbitrarily large, we can hence assume we have enough private paths for the whole process.

We now turn to the construction of the spanning ( )-tree-like collection T from T and P 1 . We start with a structured-tree T , which is a rooted tree in which the vertices are disjoint subsets X i partitioning V with the following properties:

• If X i X j is an edge in T , then there exists a corresponding 1-path or 2-path x i x j ∈ E(T), where x i ∈ X i and x j ∈ X j .

• Every vertex X i of T is spanned by a ( )-tree-like collection T i .

We again start with T being equal to T in the sense that all X i 's are singletons, and all T i 's are trivial ( )-tree-like collections. We root T at some arbitrary vertex. Again our goal is to show that we can reduce T until it is reduced to its root, which will therefore be a spanning ( )-tree-like collection.

We consider a leaf X 1 of T with direct ancestor X j . Then there exists a path x 1 x j of T having length 1 or 2. We pick a private path x j y ∈ H 1 not conflicting with the path x 1 x j . Assume y ∈ X k . If X k = X 1 , then we denote by P the path obtained by concatenating x 1 x j and x j y. Then we add X 1 to X k to form the set X 1k being spanned by

T 1k = T 1 ∪ T k ∪ {P}. If X k = X 1 ,
then we add X 1 to X j to form the set X 1j being spanned by T 1j = T 1 ∪ T j ∪ {x j y}. We choose a private path x j z in P 1 not conflicting with x 1 x j , and concatenate these two paths to get a path x 1 z that we put back into P 1 .

Once the procedure above is finished, we end up with a spanning ( )-tree-like collection T and an ( , + 1)-collection P 1 , where P 1 is the collection remaining from P 1 after we have used some of its paths to obtain T . Let P := T ∪ P 1 ∪ P 2 . Then P covers all edges of G. Note also that P is an [ , + 3]-collection. Since d T ∪P 1 (v) d P 1 (v) + 3 for every vertex v and we can choose to be sufficiently small, we have d T ∪P 1 (v) d P 2 (v)/4( + 10) for every vertex v. Thus, conf(P ) conf(P 2 ) + conf(T ∪ P 1 ) 4( + 10) < 1 4( + 10) + 1 4( + 10) 1 2( + 10) ,

PATH-DECOMPOSITIONS | 51

which concludes the proof.

Path-decompositions

Before completing the proof of Theorem 3. The original result of Jackson is as follows. For a vertex v, let E v be the set of edges incident to v. A generalised transition system S for a graph G is a set of functions {S v } v∈V (G) such that S v : E v → 2 E v and whenever e 1 ∈ S v (e 2 ), we have that e 2 ∈ S v (e 1 ). We say that an Eulerian tour E is compatible with S if for all v ∈ V(G), whenever e 1 ∈ S v (e 2 ) it follows that e 1 and e 2 are not consecutive edges in E .

THEOREM 3.16 Jackson [Jac93]

Let S be a generalised transition system for an Eulerian graph G. Suppose that for each vertex v ∈ V(G) and e ∈ E v , we have Then G has an Eulerian tour compatible with S.

From Theorem 3.16, the following result is immediate.

THEOREM 3.17

Every Eulerian collection P with conf(P ) 1/2( + 10) and d P (v) + 10 for every v has a non-conflicting Eulerian tour.

Proof. Let P ∈ P (v). The number of paths of P (v) conflicting with P is at most 1 2( +10) ( + 3)d P (v), and so at most 1 2 d P (v) -2 since d P (v) + 10. The result now follows from Theorem 3.16.

We now have all ingredients to prove Theorems 3.2.

Proof of Theorem 3.2. Without loss of generality, we assume that is even (as the statement for paths of length 2k implies the statement for paths of length k). First of all, 52| BEYOND THE BARÁT-THOMASSEN CONJECTURE we consider a maximum cut (V 1 , V 2 ) of G, and just keep the set of edges F across the cut. We call G the graph (V, F). Observe that G is at least 12-edge-connected and has minimum degree at least d /2. By Proposition 3.6, there is an orientation D of G such that D is 6-arc-strong and with d + (v) and d -(v) differing by at most 1 for every vertex v. By applying Proposition 3.7 to D with some vertex z, we obtain 6 arc-disjoint out-arborescences, T 1 , ..., T 6 , rooted at z. Since each vertex v has in-degree at most 1 in T i (z has in-degree 0), and

d + D (v) and d - D (v) differ by at most 1, the graph T 1 ∪ ... ∪ T 6 is 1/2-sparse in G . Call now G 1 := T 1 ∪ T 2 , G 2 := T 3 ∪ T 4 , G 3 := T 5 ∪ T 6
, and let R be the graph consisting of all the edges of F which are not in G 1 , G 2 , G 3 . Observe that G 1 , G 2 , G 3 are connected and bridgeless. Furthermore, the graph

G 1 ∪ G 2 ∪ G 3 is 1/2-sparse in G , and hence R is 1/2-dense in G .
In the sequel, several fractions of edges will be removed from R, but, for the sake of legibility, we will still call R the set remaining after the transfers.

We turn G 1 into an ( , 2 )-tree-like collection as follows: we consider a small εfraction R 1 of R, and apply Lemma 3.14 (with G 1 for G and R 1 for H) to form an

( , 2 )-tree-like collection T spanning V 1 in which d T (v) d R 1 (v) for all vertices v ∈ V 1 .
In other words, T is ε -sparse in R for some negligible ε > 0 depending on ε. Similarly, we can obtain, from G 2 , a ε -sparse ( , 2 )-tree-like collection T spanning V 2 . We still consider (neglecting the two ε-fractions

) that R is 1/2-dense in G . Add all edges of E(G)\F to R. Now, G = G 3 ∪ U T ∪ U T ∪ R.
We claim that we can remove a collection ofpaths or 2 -paths from the tree-like collection T spanning V 1 in a way so that we can obtain that at most one vertex of V 1 has odd degree in G. Indeed, note that the following claim is straightforward.

Given a tree T and an even subset X of V(T), then there exists a set of edges F ⊆ E(T) such that for each vertex x, d F (x) is odd if and only if x ∈ X (one way to see this is to note that the characteristic vector of X is in the span of the incidence matrix of T). In particular, denoting by X 1 the set of all odd-degree vertices of G 3 ∪ U T ∪ R inside V 1 (and possibly removing one vertex of X 1 to make X 1 of even size) we can find a sub-collection F of T such that d F (v) is odd if and only if v ∈ X 1 . In other words, removing the -or 2 -paths of T corresponding to F leaves G with every vertex of V 1 (except possibly one) having even degree. Similarly, we remove paths of the tree-like collection T spanning V 2 so that at most one vertex of V 2 has odd degree.

We still call G the remaining graph after the procedure, and we add the remaining edges of U T ∪ U T to R. Then G = G 3 ∪ R. Note that G 3 is 2-edge-connected, and R is 1/4-dense in G. By applying Lemma 3.15 (with G 3 for G 1 and R for G 2 ), G contains a connected [ , + 3]-collection P with conf(P ) < 1/2( + 10). Note that d G (v)d P (v) is even for every vertex v -so the degree of every vertex in P is even, except (possibly) for two vertices v 1 ∈ V 1 and v 2 ∈ V 2 . In this case, we add a dummy -path from v 1 out that Häggkvist ([Hag89], Problem 3.3) and Kriesell [START_REF] Kriesell | Fourth international conference on combinatorics, graph theory, and applications[END_REF] conjectured a more general statement regarding self-avoiding Eulerian tours.

Given an Eulerian tour E of a multigraph G, for every positive integer , a walk e 1 e 2 ...e where any e i , e i+1 are consecutive edges of E is called a segment of length of E . We say that E is -step self-avoiding if every segment of length at most of E is a path, which is equivalent to that E "contains" no cycle of length at most .

Häggkvist ([Hag89], Problem 3.3) and Kriesell [START_REF] Kriesell | Fourth international conference on combinatorics, graph theory, and applications[END_REF] independently conjectured that high minimum degree is a sufficient condition for the existence of an -step selfavoiding Eulerian tour.

CONJECTURE 4.2 [Hag89, Kri11]

For every positive integer , there is an integer d such that every Eulerian graph G with minimum degree at least d admits an -step self-avoiding Eulerian tour.

Häggkvist also asked to identify the minimum of d if it exists. There is in fact very little is known about self-avoiding Eulerian tour, except for the case = 3, a.k.a. triangle-free Eulerian tours. Adelgren [START_REF] Adelgren | Triangle-free eulerian tours in graphs with maximum degree at most 4[END_REF] characterized all graphs with maximum degree at most 4 which admit a triangle-free Eulerian tour before Oksimets [START_REF] Oksimets | Triangle-free eulerian tours in graphs with minimum degree at least 6[END_REF] proved Conjecture 4.2 for = 3 with a sharp bound d 3 = 6. The main part of this chapter is devoted to verify Conjecture 4.2.

THEOREM 4.3

For every positive integer , there is an integer d such that every Eulerian graph G with minimum degree at least d admits an -step self-avoiding Eulerian tour.

By just cutting the tour found by Theorem 4.3 into paths of length , we immediately obtain a P -decomposition of G, answering the question at the beginning of this chapter.

COROLLARY 4.4

For every integer 2, there is an integer d such that every Eulerian graph with size divisible by and minimum degree at least d can be decomposed into paths of length .

Outline the proof of Theorem 4.3

The following theorem is the self-avoiding tour version of Theorem 4.1.

THEOREM 4.5

For every positive integer , there is an integer d such that every 4-edge-connected Eulerian graph G with minimum degree at least d admits an -step self-avoiding Eulerian tour.

Clearly, Theorem 4.5 cannot be extended to multigraphs: a multigraph consisting of two vertices linked by many edges is a counterexample. However, the main tool to prove Theorem 4.3 is indeed the following weak extension of Theorem 4.5 to multigraphs. Roughly speaking, we only require the Eulerian tour to behave well on a given simple subgraph, not necessary on the whole multigraph. Please note that multigraphs in this chapter may contain multiple edges and loops, where each loop contributes two to the degree of the incident vertex.

THEOREM 4.6

For every integer , there is an integer d such that for every 4-edge-connected Eulerian multigraph G with minimum degree at least d and every simple subgraph G of G, the multigraph G admits an Eulerian tour in which every segment of length at most and consisting of only edges of G is a path.

Merging multiple Eulerian tours

In this section, we use Theorem 4.6 as a black box to prove Theorem 4.3. Then we prove Theorem 4.6 in the next section. We start by recalling the definition of cactus graphs.

DEFINITION 4.7

A connected loopless multigraph is a cactus if every edge belongs to at most one cycle.

The singleton graph is a cactus by convention. Clearly, if a cactus is Eulerian then every edge belongs to exactly one cycle. The following is a well-known property of cactus graphs.

PROPOSITION 4.8

There are at most two edge-disjoint paths between any two distinct vertices of a cactus.

The main idea of the proof of Theorem 4.3 is as follows. We first partition the original graph G into 4-edge-connected Eulerian "induced subgraphs"; these subgraphs are structurally linked by a big cactus. We then apply Theorem 4.6 to obtain a wellbehaved Eulerian tour of each subgraph, and finally connect these tours by the cactus to get an Eulerian tour of G.

Given a multigraph G = (V, E), to contract a set of vertices X ⊂ V, we remove all edges inside X, and then merge the vertices of X to a new vertex x, and each edge incident to x corresponds to an edge incident with some v ∈ X. Note that if the sum of degrees of vertices of X is even, then the degree of x is even.

Let G = (V, E) be an Eulerian multigraph and X be a partition of V into nonempty sets X 1 , X 2 , ..., X k for some positive integer k. Let M X be the loopless multigraph obtained from G by contracting each X i to a new vertex x i . Clearly, the degree of each x i of M X is even. If k 2, we have that M X is connected since G is connected, and hence M X is Eulerian.

Let us suppose for the moment that M X is a cactus. Thus an edge e of M X belongs to exactly one cycle in M X . Let e be an edge of the same cycle and incident with e. We say that {e, e } is a pair at x i , where x i is some endpoint shared by e and e . Note that every edge belongs to exactly one pair at each of its endpoints, and hence belongs to exactly two pairs in total. Since each edge e of M X corresponds to an edge of G, we may use e to denote both interchangeably. For every pair {e, e } at some x i , each edge has a unique endpoint in X i , say u and u respectively. We create a new dummy edge f = uu associated with the pair {e, e } (note that f may be a loop). For every 1 i k, let F i be the edge set of G[X i ] and F i be the set of all dummy edges on X i , and let G i = (X i , F i ∪ F i ). We say that the multigraphs G 1 , ..., G k are inherited from X . Clearly,

d G i (v) = d G (v) for every v ∈ X i .
The following lemma asserts that there is a partition such that the inherited multigraphs are 4-edge-connected and Eulerian, which are essential conditions to employ Theorem 4.6. For the sake of clarity, we do not consider edge-connectivity of multigraphs on a single vertex.

LEMMA 4.9

Given an Eulerian multigraph G = (V, E), there exists a partition X of V such that M X is a cactus, and every G i inherited from X is either a single vertex with loops or a 4-edge-connected Eulerian multigraph.

Proof. The proof is by induction on |V|. For the case |V| = 2, let V = {u, v}. If G has only two edges between u and v, then X = {{u}, {v}}; otherwise, X = {{u, v}}. The lemma holds for |V| = 2.

For the case |V| > 2, if G is 4-edge-connected, then X = {V(G)}. Otherwise, G contains an edge-cut of size 2, i.e. an edge-cut consisting of two edges. Consider an edge-cut partitioning V into X 1 and V such that |X 1 | is minimum among all possible edge-cuts of size 2. Let us call the two edges of the cut u 1 v 1 and u 2 v 2 , where u 1 , u 2 ∈ X 1 and v 1 , v 2 ∈ V . We create two dummy edges

f = u 1 u 2 and f = v 1 v 2 . Let F 1 = { f }, and F 1 = E(G[X 1 ]). Let G 1 = (X 1 , F 1 ∪ F 1 ) and G = (V , E(G[V ]) ∪ { f }).
There are at least two edge-disjoint paths in G between any two distinct vertices of X 1 . If both paths contains vertices of V , then the edge-cut must has size at least 4, a contradiction. Therefore there is a path in G[X 1 ] between any two distinct vertices of

X 1 . Thus if |X 1 | > 1 then G 1 is
connected, and hence is Eulerian since the degree of every vertex of G 1 is even. Similarly, G is Eulerian. Suppose that G 1 contains an edge-cut of size 2 partitioning X 1 into X 1 and X 1 . If u 1 and u 2 are in the same partition, say X 1 , then that edge-cut is also an edge-cut of G partitioning V into X 1 and V ∪ X 1 , which contradicts the minimality of |X 1 |. If u 1 ∈ X 1 and u 2 ∈ X 1 then that edge-cut consists of f and another edge, say e. Then {e, u 1 v 1 } is an edge-cut of G partitioning V into X 1 and V ∪ X 1 , a contradiction again. It follows that G 1 contains no edge-cut of size 2, and so is 4-edge-connected.

Applying induction hypothesis to the Eulerian multigraph G gives a partition of V into X = {X 2 , ..., X k } such that M X and G 2 , ..., G k inherited from X satisfy Lemma 4.9. Let x i ∈ M X corresponds to X i for every 2 i k. Set X = X ∪ {X 1 } and construct M X as follows:

(a) If v 1 , v 2 ∈ G i for some i, then M X is obtained from M X by adding x 1 and two parallel edges x 1 x i , corresponding to edges u 1 v 1 and u 2 v 2 of G. Hence there is only one pair at x 1 : {u 1 v 1 , u 2 v 2 }, and f is its associated dummy edge. There is one more pair at x i in M X comparing with x i in M X : {v 1 u 1 , v 2 u 2 }, and f is its associated dummy edge.

(b) Otherwise, v 1 ∈ G i and v 2 ∈ G j for some i = j. There must be an edge x i x j in M X corresponding to f in G . We obtain M X from M X by adding vertex x 1 , edge x 1 x i corresponding to u 1 v 1 and edge x 1 x j corresponding to u 2 v 2 together with deleting the edge x i x j corresponding to f . There is only one pair at x 1 : {u 1 v 1 , u 2 v 2 }, and f is its associated dummy edge. The set of pairs at x i (res. x j ) of M X are identical to the set of pairs at x i (res. x j ) of M X , except that v 1 u 1 (res. v 2 u 2 ) replaces f in some pair at x i (res. at x j ).

The multigraphs G 2 , ..., G k inherited from X in this construction are identical to the multigraphs G 2 , ..., G k inherited from X . By induction hypothesis, for every i 2, if G i has more than one vertex then it is 4-edge-connected and Eulerian. Note that x 1 has degree 2, and M X is a cactus, then so is M X . This proves the lemma.

Given an Eulerian tour

E of G and a subset X of V, a segment v 1 v 2 ...v r (r 3) of E is an X-boomerang if v 1 , v r ∈ X and v 2 , ..., v r-1 / ∈ X.
A projection of E on X is an Eulerian tour E X obtained from E by replacing every X-boomerang, say v 1 v 2 ...v r , by a dummy edge (possibly a loop) between v 1 and v r . If E X is a projection of E , we say E and E X are compatible.

Let G be an Eulerian multigraph and X be a partition of G together with M X and inherited G 1 , ..., G k given by Lemma 4.9. For every i, let E i be an arbitrary Eulerian tour of G i .

CLAIM 4.10

There exists an Eulerian tour E of G compatible with all E i . Furthermore, for every pair {e, e } at some x i , there is an X i -boomerang of E starting and ending by e and e .

Proof. We reuse all notations in the proof of Lemma 4.9 and proceed by induction on k. The claim clearly holds for k = 1. For k > 1, recall that by the algorithm in the proof of Lemma 4.9, the Eulerian multigraph G has k -1 inherited multigraphs identical to G 2 , ..., G k of G. Hence, by the induction hypothesis applied on G , there exists an Eulerian tour E of G compatible with all E i , i 2, and for every pair {e, e } at some x i , i 2, there is an X i -boomerang of E starting and ending by e and e . Note that in cases (a) and (b) of the proof of Lemma 4.9, the only pair at x 1 is {u 1 v 1 , u 2 v 2 } associated with f . Let W 1 be the walk obtained from E 1 by removing f , and E be the Eulerian tour on G obtained from E by replacing f by the segment v 1 u 1 W 1 u 2 v 2 . It is straightforward that, in both cases (a) and (b), the tour E satisfies Claim 4.10.

Let {e, e } be a pair at some x i , and W be the X i -boomerang of E starting and ending by e and e . Let W be the segment obtained from E by removing W.

CLAIM 4.11

If W visits a vertex v / ∈ X i , then W does not visit v.

Proof. Suppose that the claim was false. Let v ∈ X j for some j = i. Contracting every X i to x i naturally yields from W and W two edge-disjoint walks W X and W X in M X , respectively. By following W X from x i to x j and return to x i , and then following W X to x j , we obtain three edge-disjoint walks between x i and x j , contrary to Proposition 4.8.

CLAIM 4.12

If G has minimum degree d, then whenever E leaves X i , it takes at least d steps to return to X i .

Proof. The claim is equivalent to that every X i -boomerang W has length at least d. Suppose that W visits vertex v / ∈ X i . By Claim 4.11, W must contains all edges incident with v, and hence has length at least d.

We are ready to prove Theorem 4.3.

Proof of Theorem 4.3. Let G be an Eulerian graph with minimum degree at least d , the constant of Theorem 4.6. There is a partition X = {X 1 , ..., X k } of V(G) together with inherited multigraphs G 1 , ..., G k satisfying Lemma 4.9.

If G i consists of only one vertex and some loops, let E i be an arbitrary Eulerian tour of G i . Otherwise, Lemma 4.9 asserts that G i is Eulerian, 4-edge-connected, and

d G i (v) = d G (v)
d for any v ∈ X i . Also note that G[X i ] is a simple subgraph of G i . We thus get, by Theorem 4.6, an Eulerian tour E i of G i of which every segment of length at most and containing only edges of G[X i ] is a path. Claim 4.10 gives an Eulerian tour E of G compatible with all E i . The proof is completed by showing that every segment W of length at most of E is a path. Suppose that W = W 1 e 1 W 2 e 2 ...e t-1 W t , where each W s (possibly of length 0) contains only vertices of some X i s , and e s is an edge between two distinct sets X i s and X i s+1 . By Claim 4.12, whenever E leaves some X i s , it takes at least d > steps to return to X i s , while the length of W is at most . Therefore X i s = X i r for every s = r. Because E is compatible with E i s , and W s contains only vertices of X i s , we have that W s is a segment of E i s . Since W s ⊆ G[X i s ] and has length at most , it is a path by Theorem 4.6. This means that W is a path, and the proof is complete.

Self-avoiding tours on Eulerian multigraphs

In this section, we will prove Theorem 4.6 to complete the proof of Theorem 4.3. We start with the proof of Theorem 4.5.

Proof of Theorem 4.5. Following the arguments in the second paragraph of Theorem 3.2, we can extract from G two trees T 1 and T 2 so that T 1 ∪ T 2 is 1/2-sparse in G. Let G 1 := T 1 ∪ T 2 , and G 2 := G\G 1 . Then G 1 is 2-edge-connected, and G 2 is 1/2-dense. Applying Lemma 3.15, we can express G as a connected [ , + 3]collection P with conf(P ) < 1/2( + 10). Since G is Eulerian, so is P. Hence P has non-conflicting Eulerian tours according to Theorem 3.17, and these tours do not have cycles of length at most since all paths of P have length at least . Suppose that we have a decomposition P of an Eulerian graph G with all paths of length at least . Then just by concatenating the paths arbitrarily, we obtain a decomposition of G into several circuits since G is Eulerian. If every two consecutive paths (i.e., they are concatenated) are non-conflicting, then all circuits are -step selfavoiding. Theorem 3.10 provides a low conflicting decomposition for this purpose. In order to obtain an -step self-avoiding Eulerian tour, it is necessary that the process of concatenating returns a single circuit; this is taken care by Lemma 3.11.

The proof of Theorem 4.6 is partly similar to the proof of Theorem 4.5 but more involved. The main difficulty here is that certain arguments on simple graphs in the proof of Theorem 4.5 could not be extended to multigraphs. To overcome these difficulties, we introduce the notions of F-paths and F-path-collections as an extension of paths and path-collections in Section 3.2.

F-path-collections

Given a multigraph G = (V, E) and a subgraph G = (V, F) satisfying the hypotheses of Theorem 4.6, the goal is to find an Eulerian tour E of G such that every segment of E of length at most and consisting of only edges of F is a path. To this end, we introduce a relaxation of path, called F-path, to depict the characteristics of segments of the tour. Let G = (V, E) be a multigraph and F be a subset of E. A walk W in G is called an F-path if every subwalk of W containing only edges of F is a path. An F-path W is covered if all edges of W belong to F, and is uncovered otherwise. It is immediate that a covered F-path is a path.

An F-collection P on G is a set of edge-disjoint F-paths of G. We denote by U P = (V, E ) the multigraph where E is the set of edges of F-paths in P. If U P = G, then P is called an F-decomposition of G. We denote by H P = (V, E ) the multigraph where each edge (possibly a loop) uv ∈ E corresponds to an F-path between u and v in P. The degree of a vertex v in P, denoted d P (v), is the degree (with multiplicity, and a loop contributes two) of v in H P .

Given an F-path P = ve 1 v 1 ...e t v t , the ray of P from v, denoted by P v|F , is the longest subwalk ve 1 v 1 ...e s v s (possibly of length 0) of P such that e 1 , ..., e s ∈ F. There are several remarks. First, every ray is a path. Second, each F-path P has exactly two rays; these rays are identical to P if P is covered, and are edge-disjoint if P is uncovered. Third, if P is a closed (obviously uncovered) F-path from v to v, then both of its rays are from v. We now would like to measure the conflict between two rays. We first agree that two rays of the same F-path do not conflict each other, even if they may intersect at some vertex. Two rays P v|F and P v|F (with P = P ) issued from some vertex v are conflicting if P v|F and P v|F also intersect at some vertex different from v. For every v ∈ V, let P (v) be the set of F-paths in P containing v as an endpoint, and P (v|F) be the set of rays from v of F-paths in P, where a closed F-path with endpoint v contributes two rays. We define the conflict ratio of v in P as conf P (v|F) := max w =v {P v|F ∈ P (v|F) : w ∈ P v|F } d P (v) .

We denote the conflict ratio of P by conf(P |F) := max v conf P (v|F). We always have conf(P |F) 1 since P (v|F) = d P (v). Note that, when P is a collection, the definitions of P (v) and conflict ratio coincide with the definitions given in the beginning of Section 3.2.

The the proof of Theorem 4.6 is similar to the proof of Theorem 4.5 but more involved. Let us first prove an extension of Theorem 3.10 to F-decompositions. By saying a ray of P, we mean a ray of some F-path of P.

LEMMA 4.13

Let be a positive integer, and ε > 0 sufficiently small. There is an integer L ,ε such that for every multigraph G with minimum degree at least L ,ε and every simple d P 1 (v) = d P (v). Besides, each ray of P 1 is the end-segment of some path of P . Therefore two rays of P 1 are conflicting only if their corresponding paths in P are conflicting. Thus all of the following hold true:

• Every ray of P 1 has length at most + 1, since it is either a path or an endsegment of some path of P .

• Every covered F-path of P 1 has length at least , since it is a path of P .

• conf P 1 (v|F) conf P (v) 1/4( + 10) for every vertex v.

• (1 -ε)d G (v) d P 1 (v) (1 + ε)d G (v) for every v since d P 1 (v) = d P (v).
We now turn our attention to P 2 . Every circuit C ∈ P 2 contains at least one dummy edge. We associate C with some vertex v such that v is the endpoint of some dummy edge of C. For every v ∈ V, let C 1 , ..., C t be the circuits (if any) associated with v, where every C s = ve s W s v with dummy edge e s . Let P v = ve 1 W 1 ve 2 W 2 ...ve t W t v be the walk starting and ending at v obtained by concatenating all C s in that fashion. Clearly, P v is an uncovered F-path, of which one ray is v (length 0) and another ray is W t , a middle-segment of length at most + 1. Note that for every v, we have at most one such P v . Let P 2 = { P v : v ∈ V}. Then P 2 is an F-collection of G and U P 1 ∪ U P 2 = G. Hence P = P 1 ∪ P 2 is an F-decomposition of G. Then every ray of P has length at most + 1, and every covered F-path of P has length at least . For every v, the number of rays from v of P is at most the number of rays from v of P 1 plus two (two rays of P v if it exists). Hence d P 1 (v) d P (v) d P 1 (v) + 2, and so by definition of conflict ratio, we have conf P (v|F)

d P 1 (v)conf P 1 (v|F) + 2 d P (v) conf P 1 (v|F) + 2 d P (v) 1 4( + 10) + 2 d P (v) 1 4( + 9)
.

Finally, we have (1

-ε)d G (v) d P 1 (v) d P (v). And since L ,ε 2 /ε, we have d P (v) (d P (v) + 2) (1 + 2ε)d G (v).
The proof is complete.

Lemma 4.13 gives us a good F-decomposition P of G. We wish to concatenate the F-paths of P to an Eulerian tour. If H P has an Eulerian tour, we naturally obtain an Eulerian tour of G by replacing each edge of H P by its corresponding F-path of P. Hence the goal is achieving the connectivity of H P , which immediately yields Eulerianity thank to the fact that every vertex of H P has even degree.

LEMMA 4.14

Given a positive integer , there is an integer L such that for every 4-edge-connected Eulerian multigraph G with minimum degree at least 100L and every simple subgraph (V, F) of G, there is an F-decomposition P of G satisfying:

• Every ray of P has length at most + 3.

• Every covered F-path of P has length at least .

• conf(P |F) 1/2( + 9).

• H P is Eulerian and spans V(G).

Proof. Let us first outline the proof. We wish to obtain connectivity of P. To this end, we decompose G into a collection P 0 satisfying Lemma 3.11 and two F-collections P 1 and P 2 satisfying Lemma 4.13. Then we use P 0 , which contains only paths of short length, to extend F-paths of P 1 obtaining a new F-collection P 1 such that H P 1 is connected. Finally, we merge P 1 with P 2 to obtain P, which inherits connectivity from P 1 and low conflict ratio from P 2 .

Because G is 4-edge-connected, by Proposition 3.6, there is an orientation

D of G such that D is 2-arc-strong and |d + D (v) -d - D (v)|
1 for every v. Applying Proposition 3.7 to D with an arbitrary vertex z gives us two arc-disjoint out-arborescences, T 1 , T 2 , rooted at z. Each vertex v has indegree at most 1 in each T i (z has indegree 0). This gives

d T 1 ∪T 2 (v) d + D (v) + 2 d G (v)/2 + 3 for every vertex v since |d + D (v) -d - D (v)| 1.
Because T 1 ∪ T 2 is loopless and 2-edge-connected, we obtain a collection P 0 on T 1 ∪ T 2 satisfying Lemma 3.11.

Let G = G\U P 0 . Then d U P 0 (v) d T 1 ∪T 2 (v) d G (v)/2 + 3,
and so G has minimum degree at least 100 L /2 -3 48 L . By Proposition 3.3, G has an improper coloring by 45 colors such that |d i (v)d j (v)| 4 for every vertex v and every pair of colors i = j. Let G 1 be the subgraph of G with edge set of the first color, and

G 2 = G \G 1 . Thus d G 1 (v) 1 45 -1 d G 2 (v) + 4 d G 2 (v) 40 .
The minimum degrees of both G 1 and G 2 are at least 48 L /45 -4 L . Therefore there are F-decompositions P 1 of G 1 and P 2 of G 2 , both satisfying Lemma 4.13. Hence

d P 1 (v) 1 + 2ε d G 1 (v) 1 + 2ε 40 2 d G 2 (v) 1 + 2ε 40 (1 -ε) d P 2 (v),
for every vertex v, with an arbitrary small parameter ε. Set ε small enough (i.e. set L high enough) such that for every v,

d P 1 (v) 1 4( + 9) d P 2 (v) -3. (4.1)
Such structured-tree T clearly exists by choosing T equal to H P 0 rooted at z, in which each Y i contains a single vertex, and each R i is empty. Our goal is to repeatedly merge vertices of T until T is the singleton graph, which completes the process of concatenating. We consider a leaf Y i of T with parent Y j , corresponding to path P = v i ...v j of P 0 with v i ∈ Y i and v j ∈ Y j . Suppose that g 1 (P) = v j ...y and g 2 (P) = v j ...z.

• If y ∈ Y k for some k = i, we concatenate P and g 1 (P) at v j and get a F-path P * .

Then we merge

Y i into Y k to form new set Y ik (inheriting the position of Y k in tree T ). Let R ik = R i ∪ R k ∪ {P * }. Since P * connects two vertices of R i and R k , we have that H R ik is connected and spans Y ik . • If y ∈ Y i , we merge Y i to Y j to form new set Y ij (inheriting the position of Y j in tree T ). Set R ij = R i ∪ R j ∪ {g 1 (P)}.
Since g 1 (P) connects two vertices of R i and R j , we have that H R ij is connected and spans Y ij . We also concatenate P with g 2 (P) at v j to get another F-path and put it back into P 1 .

The number of vertices of T is reduced by 1 after each step, while T still satisfies both properties. Once the process is complete, we end up with a singleton T and an F-collection R such that H R is connected and spans V. Note that P 0 is empty at the end of the process, since exactly one path of P 0 is used at each step. We merge R with P 1 to obtain a new collection P 1 . Consequently, H P 1 is connected.

Let P = P 1 ∪ P 2 . Note that U P = U P 1 ∪ U P 2 = G, so P is an F-decomposition of G and H P is connected. The degrees of all vertices of G are even, then so are the degrees of vertices of H P , and hence H P is Eulerian. The process of concatenating also ensures that every ray of P has length at most + 3 and that every covered F-path of P has length at least .

It remains to prove that conf(P |F)

1/2( + 9). In the following, by saying P 0 or P 1 , we mean the collection before the process of concatenating. Recall that H P 0 is subcubic, so for every vertex v, the number of F-paths with endpoint v in P 1 is at most the number F-paths with endpoint v in P 1 plus 3. Combining with (4.1) yields d P 1 (v) d P 1 (v) + 3 d P 2 (v)/4( + 9). Recall that conf P 1 (v|F) 1 and conf P 2 (v|F) 1/4( + 9). Hence for every vertex v, by definition of conflict ratio we have conf P (v|F)

d P 2 (v)conf P 2 (v|F) + d P 1 (v)conf P 1 (v|F) d P 2 (v) + d P 1 (v) < conf P 2 (v|F) + d P 1 (v)conf P 1 (v|F) d P 2 (v) 1 4( + 9) + 1 4( + 9) 1 2( + 9)
.

By setting k = 1 and β(v) = 0 for every v, we obtain that every 6-edge-connected graph has a 3-flow. A natural question is whether a weighted version of Theorem 5.1 exists. Given a graph G = (V, E), a p-boundary β of G and a mapping f :

E → Z p \ {0}, an orientation G of G is called an f -weighted β-orientation if ∂ f (v) ≡ β(v) (mod p) for every v, where ∂ f (v) = ∑ e∈E + G (v) f (e) -∑ e∈E - G (v) f (e).
Note that if f (e) ≡ 1 (mod p) for every edge e, an f -weighted β-orientation is precisely a β-orientation.

QUESTION 5.2

For which mapping f : E → Z 2k+1 \ {0} and (2k + 1)-boundary β, every highly edge-connected graph G has an f -weighted β-orientation?

An immediate observation is that if we wish to have a general result of Question 5.2, it is necessary to assume that 2k + 1 is a prime number. For instance, take G to consist of two vertices u, v with an arbitrary number of edges between u and v, consider a non-trivial divisor p of 2k + 1, and ask for a p-weighted (2k + 1)-orientation G of G (here, p denotes the function that maps each edge to p (mod 2k + 1)). Note that for any orientation, ∂p(v) is in the subgroup of Z 2k+1 generated by p, and this subgroup does not contain 1, -1 (mod 2k + 1). In particular, there is no p-weighted (2k + 1)-orientation of G with boundary β satisfying β(u) ≡ -β(v) ≡ 1 (mod 2k + 1).

We will show later on that when k is a prime number, the answer for Question 5.2 is affirmative for every mapping f and boundary β.

THEOREM 5.3

Let p

3 be a prime number and let G = (V, E) be a (6p -8)(p -1)-edgeconnected graph. For any mapping f : E → Z p \ {0} and any p-boundary β, G has an f -weighted β-orientation.

Theorem 5.3 is indeed a direct corollary of a special case of Jaeger-Linial-Payan-Tarsi's conjecture [START_REF] Jaeger | Group connectivity of graphs-a nonhomogeneous analogue of nowhere-zero flow properties[END_REF] on additive basis of the vector space Z n p , which we will present and prove in the next section. We will also discuss various results on orientations and flows in Z p obtained from that special case of Jaeger-Linial-Payan-Tarsi's conjecture.

Jaeger-Linial-Payan-Tarsi's conjecture

An additive basis B of a vector space F is a multiset of elements from F such that for all β ∈ F, there is a subset of B which sums to β. Let Z n p be the n-dimensional linear space over the prime field Z p . The following result is a simple consequence of the Cauchy-Davenport Theorem [START_REF] Davenport | On the addition of residue classes[END_REF] (see also [START_REF] Alon | The polynomial method and restricted sums of congruence classes[END_REF]).

COROLLARY 5.7

Let p 3 be a prime number. For any t 8( p 2 )(3p -4) + p -2 linear bases B 1 , ..., B t of Z n p such that the support of each vector has size at most 2, t s=1 B s forms an additive basis of Z n p .

Another interesting consequence of Theorem 5.6 concerns the linear subspace (Z n p ) 0 of vectors of Z n p whose entries sum to 0 (mod p).

COROLLARY 5.8

Let p 3 be a prime number. For any t 4(p -1)(3p -4) + p -2 linear bases B 1 , ..., B t of (Z n p ) 0 such that the support of each vector has size at most 2, t s=1 B s forms an additive basis of (Z n p ) 0 .

Proof. Note that for any 1 s t, the linear basis B s consists of n -1 vectors, each of which has a support of size 2, and the two elements of the shadow sum to 0 (mod p).

In particular, at most p-1 2 different shadows appear among the vectors of the linear bases B 1 , ..., B t . It is convenient to view each B s as a matrix in which the elements of the basis are column vectors. For each 1 s t, let B s be obtained from B s by deleting the last row. It is easy to see that B s is a linear basis of Z n-1 p . Moreover, at most p-1 2 different shadows of size 2 appear among the vectors of the linear bases B 1 , ..., B t (note that the removal of the last row may have created vectors with shadows of size 1). In particular, it follows from Theorem 5.6 that for any vector β = (β 1 , . . . , β n ) ∈ (Z n p ) 0 , the vector (β 1 , . . . , β n-1 ) ∈ Z n-1 p can be written as a sum of a subset of elements of t s=1 B s . Clearly, the corresponding subset of elements of t s=1 B s sums to β. This concludes the proof of Corollary 5.8.

Corollaries on Z p -flows

Theorem 5.3 turns out to be equivalent to the following seemingly more general result. Assume that we are given a directed graph G = (V, E) and a p-boundary

β. A p-flow with boundary β in G is a mapping f : E → Z p such that ∂ f (v) ≡ β(v) (mod p)
for every v. In other words, f is a p-flow with boundary β in G = (V, E) if and only if G is an f -weighted β-orientation of its underlying non-oriented graph G = (V, E), where f is extended from E to E in the natural way (i.e. for each e ∈ E, f (e) := f ( e)).

In the rest of this chapter we will say that a directed graph G is t-edge-connected if its underlying graph, denoted by G, is t-edge-connected.

THEOREM 5.9

Let p 3 be a prime number and let G = (V, E) be a directed (6p -8)(p -1)edge-connected graph. For any arc e ∈ E, let L( e) be a pair of distinct elements of Z p . Then for every p-boundary β, G has a Z p -flow f with boundary β such that for any e ∈ E, f ( e) ∈ L( e).

To see that Theorem 5.9 implies Theorem 5.3, simply fix an arbitrary orientation of G and set L( e) = { f (e),f (e)} for each arc e. We now prove that Theorem 5.3 implies Theorem 5.9. We actually prove a slightly stronger statement (holding in Z 2k+1 for any integer k 1).

LEMMA 5.10

Let k

1 be an integer, and let G = (V, E) be a directed graph such that the underlying non-oriented graph G has an f -weighted β-orientation for any mapping f : E → Z 2k+1 \ {0} and any (2k + 1)-boundary β. For every arc e ∈ E, let L( e) be a pair of distinct elements of Z 2k+1 . Then for every (2k + 1)-boundary β, G has a (2k + 1)-flow g with boundary β such that g( e) ∈ L( e) for every e.

Proof. Let β be a (2k + 1)-boundary of G. Consider a single arc e = (u, v) of G. Choosing one of the two values of L( e), say a or b, will either add a to ∂g(u) and subtract a from ∂g(v), or add b to ∂g(u) and subtract b from ∂g(v). Note that 2 and 2k + 1 are relatively prime, so the element 2 -1 is well-defined in Z 2k+1 . If we now add 2 -1 (a + b) to β(v) and subtract 2 -1 (a + b) from β(u), the earlier choice is equivalent to choosing between the two following options: adding 2 -1 (ab) to ∂g(u) and subtracting 2 -1 (ab) from ∂g(v), or adding 2 -1 (ba) to ∂g(u) and subtracting 2 -1 (ba) from ∂g(v). This is equivalent to choosing an orientation for an edge of weight 2 -1 (ab). It follows that finding a (2k + 1)-flow g with boundary β such that for any e ∈ E, g( e) ∈ L( e) is equivalent to finding an f -weighted β -orientation for some other (2k + 1)-boundary β of G, where the weight f (e) of each edge e is 2 -1 times the difference between the two elements of L( e).

We now consider the case where L( e) = {0, 1} for every arc e ∈ E. Let f 2 -1 : E → Z 2k+1 denote the function that maps each arc e to 2 -1 (mod 2k + 1). The same argument as in the proof of Lemma 5.10 implies that if G has an f 2 -1 -weighted βorientation for every (2k + 1)-boundary β, then for every (2k + 1)-boundary β, the digraph G has a (2k + 1)-flow f with boundary β such that f ( e) ∈ L( e) for every e.

The following is a simple corollary of Theorem 5.1.

COROLLARY 5.11

Let 1 be an odd integer and let k 1 be relatively prime with . Let G = (V, E) be a (3 -3)-edge-connected graph, and let k : E → Z be the mapping that assigns k (mod ) to each edge e ∈ E. Then for any -boundary β, G has a k-weighted βorientation.

Proof. Observe that β = k -1 • β is a -boundary (k -1 is well defined in Z ). It follows from Theorem 5.1 that G has a β -orientation. Note that this corresponds to a kweighted β-orientation of G, as desired.

As a consequence, the following is an equivalent version of Theorem 5.1 (see also [START_REF] Jaeger | Group connectivity of graphs-a nonhomogeneous analogue of nowhere-zero flow properties[END_REF][START_REF] Lai | Additive bases and strongly z_2s+1connectedness[END_REF]).

THEOREM 5.12

Let k 1 be an integer and let G = (V, E) be a directed 6k-edge-connected graph. Then for every (2k + 1)-boundary β, G has a (2k + 1)-flow f with boundary β such that f ( E) ∈ {0, 1} (mod 2k + 1).

Additive bases in matrices with small support

This section is devoted to prove Theorem 5.6 and show how it implies Theorem 5.3. We first recall the following (weak form of a) classical result by Mader (see [START_REF] Diestel | Graph theory[END_REF], Theorem 1.4.3). Note that the average degree of a graph G is

|E(G)| |V(G)| .

LEMMA 5.13

Given an integer k 1, if G = (V, E) is a graph with average degree at least 4k, then there is a subset X of V such that |X| > 1 and G[X] is (k + 1)-edge-connected.

We will also need the following result of Thomassen [START_REF] Thomassen | Graph factors modulo k[END_REF], which is a simple consequence of Theorem 5.1.

THEOREM 5.14 [Tho14]

Let k 3 be an odd integer, G = (V 1 , V 2 , E) be a bipartite graph, and f :

V 1 ∪ V 2 → Z k be a mapping satisfying ∑ v∈V 1 f (v) ≡ ∑ v∈V 2 f (v) (mod k). If G is (3k -3)-edge-connected, then G has a spanning subgraph H such that for any v ∈ V, d H (v) ≡ f (v) (mod k).
Let G be a graph, and let X and Y be two disjoint subsets of vertices of G. The set of edges of G with one endpoint in X and the other in Y is denoted by E(X, Y).

We are now ready to prove Theorem 5.6.

ADDITIVE BASES IN MATRICES WITH SMALL SUPPORT | 75

Proof of Theorem 5.6. We proceed by induction on n. For n = 1, this is a direct consequence of Theorem 5.4, so suppose that n 2. Each basis B s can be considered as an n × n matrix where each column is a vector with support of size at most 2. Let B = t i=1 B i . For 1 i n, a vector is called an i-vector if its support is the singleton {i} (in other words, the i-th entry is non-zero and all the other entries are zero). Suppose that for some 1 i n, B contains at least p -1 i-vectors. Let C be the set of i-vectors of B. Clearly, each basis contains at most one i-vector. For every B s , let B s be the matrix obtained from B s by removing its i-vector (if any) and the i th row. Clearly B s is or contains a basis of Z n-1 p . By induction hypothesis, t s=1 B s forms an additive basis of Z n-1 p . In other words, for any vector β = (β 1 , ..., β i , ..., β n ) ∈ Z n p , there is a subset Y 1 of B \ C which sums to (β 1 , ..., βi , .., β n ) for some βi . Since |C| p -1, it follows from Theorem 5.4 that there is a subset Y 2 of C which sums to (0, ..., β i -βi , .., 0). Hence Y 1 ∪ Y 2 sums to β.

Thus we can suppose that there are at most p -2 i-vectors for every i. Then there are at least 8 (3p -4)n vectors with a support of size 2 in B. Since there are at most distinct shadows of size 2 in B, there are at least 8(3p -4)n vectors with the same (unordered) shadow of size 2, say {a 1 , a 2 } (recall that shadows are multisets, so a 1 and a 2 might coincide).

Let G be the graph (recall that graphs in this chapter are allowed to have multiple edges) with vertex set V = {v 1 , ..., v n } and edge set E, where edges v i v j are in one-toone correspondence with vectors of B with support {i, j} and shadow {a 1 , a 2 }. Then G contains at least 8(3p -4)n edges.

We now consider a random partition of V into 2 sets V 1 , V 2 (by assigning each vertex of V uniformly at random to one of the sets V k , k = 1, 2). Let e = v i v j be some edge of G. Recall that e corresponds to some vector with only two non-zero entries, say without loss of generality a 1 at i th index and a 2 at j th index. The probability that v i is assigned to V 1 and v j is assigned to V 2 is at least 1 4 . As a consequence, there is a partition of V into 2 sets V 1 , V 2 and a subset E ⊆ E(V 1 , V 2 ) of at least 8(3p -4)n/4 = 2(3p -4)n edges such that for every e ∈ E , the vector of B corresponding with e has entry a 1 (resp. a 2 ) at the index associated to the endpoint of e in V 1 (resp. V 2 ).

Since the graph G = (V, E ) has average degree at least 4(3p -4), it follows from Lemma 5.13 that there is a set

X ⊆ V of at least 2 vertices, such that G [X] is (3p -3)- edge-connected. Set H = G [X] and F the edge set of H. Note that H is bipartite with bipartition X 1 = X ∩ V 1 and X 2 = X ∩ V 2 .
For each integer 1 s t, let B * s be the matrix obtained from B s by doing the following: for each vertex v i in X 1 (resp. X 2 ), we multiply all the elements of the i th row of B s by a -1 1 (resp. -a -1 2 ), noting that all the operations are performed in Z p . Let B * = t s=1 B * s . Note that each vector of B * corresponding to some edge e ∈ F has shadow {1, -1} (1 is the entry indexed by the endpoint of e in X 1 and -1 is the entry indexed by the endpoint of e in X 2 ). It is easy to verify the following.

• Each B * s is a linear basis of Z n p . • B is an additive basis if and only if B * is an additive basis.

Hence it suffices to prove that B * is an additive basis.

Without loss of generality, suppose that X = {v m , ..., v n } for some m n -1. By contracting k rows of a matrix, we mean deleting these k rows and adding a new row consisting of the sum of the k rows. For each 1 s t, let B s be the matrix of m rows obtained from B * s by contracting all m th , (m + 1) th , ..., n th rows. Note that the operation of contracting k rows decreases the rank of the matrix by at most k -1 (since it is the same as replacing one of the rows by the sum of the k rows, which preserves the rank, and then deleting the k -1 other rows). Let B = t s=1 B s . Since each B * s is a linear basis of Z n p , each B s has rank at least m and therefore contains a basis of Z m p . Hence, by induction hypothesis, B \ B 0 is an additive basis of Z m p , where B 0 is the set of all columns with empty support in B . For every β = (β 1 , ...,

β n ) ∈ Z n p , let β = (β 1 , ..., β m-1 , ∑ n i=m β i ) ∈ Z m p .
Then there is a subset Y of B \ B 0 which sums to β . Let Y * and B * 0 be the subsets of B * corresponding to Y and B 0 , respectively. Then Y * sums to some β = (β 1 , ..., β m-1 , βm , ..., βn ), where ∑ n i=m βi ≡ ∑ n i=m β i (mod p). Recall that for each edge e ∈ F, the corresponding vector in B * has precisely two non-zero entries, (1, -1), each with index in X. Hence the vector corresponding to each e ∈ F in B has empty support. Thus the set of vectors in B * corresponding to the edge set F is a subset of B * 0 , which is disjoint from Y. For each

v i ∈ X 1 , let β X (v i ) = β i -βi , and for each v i ∈ X 2 , let β X (v i ) = βi -β i . Since ∑ n i=m βi ≡ ∑ n i=m β i (mod p), we have ∑ v i ∈X∩V 1 β X (v i ) = ∑ v i ∈X∩V 2 β X (v i ).
Since H is (3p -3)-edge-connected, it follows from Theorem 5.14 that there is a subset F ⊆ F such that, in the graph (X, F ), each vertex v i ∈ X 1 has degree β i -βi (mod p) and each vertex v i ∈ X 2 has degree βiβ i (mod p). Therefore, F corresponds to a subset Z * of vectors of B * 0 , summing to (0, . . . , 0, β m -βm , . . . , β n -βn ). Then Y * ∪ Z * sums to β. It follows that B * is an additive basis of Z n p , and so is B. This completes the proof.

Proofs of Theorem 5.3

We will complete this chapter with two proofs of Theorem 5.3. The first one is a direct application of Corollary 5.8, but requires a stronger assumption on the edgeconnectivity of G (24p 2 -54p + 28 instead of 6p 2 -14p + 8 for the second proof).

First proof of Theorem 5.3. We fix some arbitrary orientation G = (V, E) of G and denote the vertices of G by v 1 , . . . , v n . The number of edges of G is denoted by m. For each arc e = (v i , v j ) of G, we associate e to a vector x e ∈ (Z n p ) 0 in which the i th -entry is equal to f (e) (mod p), the j th -entry is equal tof (e) (mod p) and all the remaining entries are equal to 0 (mod p).

Let us consider the following statements.

(a) For each p-boundary β, there is an f -weighted β-orientation of G.

(b) For each p-boundary β there is a vector (a e ) e∈E ∈ {-1, 1} m , such that ∑ e∈E a e x e ≡ β (mod p).

(c) For each p-boundary β there is a vector (a e ) e∈E ∈ {0, 1} m such that ∑ e∈E 2a e x e ≡ β (mod p).

Clearly, (a) is equivalent to (b). We now claim that (b) is equivalent to (c). To see this, simply do the following for each arc e = (v i , v j ) of G: add f (e) to the j th -entry of x e and to β(v j ), and subtract f (e) from the i th -entry of x e and from β(v i ). To deduce (c) from Corollary 5.8, what is left is to show that {a e : e ∈ E} can be decomposed into sufficiently many linear bases of (Z n p ) 0 . This follows from the fact that G is (8(p -1)(3p -4) + 2p -4)-edge-connected (and therefore contains 4(p -1)(3p -4) + p -2 edge-disjoint spanning trees) and that the set of vectors a e corresponding to the edges of a spanning tree of G forms a linear basis of (Z n p ) 0 (see [START_REF] Jaeger | Group connectivity of graphs-a nonhomogeneous analogue of nowhere-zero flow properties[END_REF]).

A second proof consists in mimicking the proof of Theorem 5.6 (it turns out to give a better bound for the edge-connectivity of G).

Second proof of Theorem 5.3. As before, all values and operations are considered modulo p. We can assume without loss of generality that f (E) ∈ {1, 2, . . . , p-1 2 }, since otherwise we can replace the value f (e) of an edge e byf (e), without changing the problem.

We prove the result by induction on the number of vertices of G. The result is trivial if G contains only one vertex, so assume that G has at least two vertices.

For any 1 i k, let E i be the set of edges e ∈ E with f (e) = i, and let

G i = (V, E i ). Since G is (6p -8)(p -1)-edge-connected, G
has minimum degree at least (6p -8)(p -1) and then average degree at least (6p -8)(p -1). As a consequence, there exists i such that G i has average degree at least 12p -16. By Lemma 5.13, since 12p-16 4

+ 1 = 3p -3, G i has an induced subgraph H = (X, F) with at least two vertices such that H is (3p -3)-edge-connected. Let G/X be the graph obtained from G by contracting X into a single vertex x (and removing possible loops). Since H contains more than one vertex, G/X has less vertices than G (note that possibly, X = V and in this case G/X consists of the single vertex x). Since G is (6p -8)(p -1)-edgeconnected, G/X is also (6p -8)(p -1)-edge-connected. Hence by the induction hypothesis it has an f -weighted β-orientation, where we consider the restriction of f to the edge-set of G/X, and we define β(x) = β(X). Note that this orientation corresponds to an orientation of all the edges of G with at most one endpoint in X.

The Erdős and Hajnal conjecture [START_REF] Erdös | Ramsey-type theorems[END_REF], however, asserts that every pattern has the Erdős-Hajnal property.

CONJECTURE 6.2 The Erdős-Hajnal conjecture [EH89]

Every graph has the Erdős-Hajnal property.

Very few primitive1 patterns are known to have the Erdős-Hajnal property [START_REF] Chudnovsky | The erdös-hajnal conjecture-a survey[END_REF], including C 5 -the cycle of length 5, P 4 -the path of length 4, the complement of P 4 , and the bull graph (see Figure 6.1). FIGURE 6.1 -Left: the complement of P 4 , and right: the bull graph.

The Erd ős-Hajnal conjecture -tournament version

Recall that a directed graph T is a tournament if there is exactly one arc between every pair of distinct vertices of T, and a tournament is transitive (or acyclic) it it does not contain any directed cycle. It is well-known that undirected graphs and tournaments are "equivalent" notions in the sense that every enumerated (i.e. vertices are enumerated) graph can be bijectively mapped to an enumerated tournament, where an edge is mapped to a forward arc and a non-edge is mapped to a backward arc. This mapping also shows that a transitive tournament is equivalent to either a clique or a stable set (depending on the direction of the arcs).

An equivalent version of the Erdős-Hajnal conjecture on tournament was proposed by Alon, Pach and Solymosi [START_REF] Noga Alon | Ramsey-type theorems with forbidden subgraphs[END_REF], where undirected graphs are replaced by tournaments and cliques and stables sets are replaced by transitive tournaments. For the rest of Part II, the notion patterns will be used to mention tournaments instead of undirected graphs. If a tournament T does not contain any subtournament isomorphic to a pattern H, we say that T is H-free (the term induced subtournament is unnecessary since a tournament contains exactly one arc between every pair of vertices). We start with the tournament version of the Erdős-Hajnal property.

DEFINITION 6.3

We say that a pattern H has the Erdős-Hajnal property if there exists a constant ε(H) > 0 such that every H-free tournament T contains a transitive tournament of size at least |V(T)| ε (H) .

And similarly, we have the tournament version of the Erdős-Hajnal conjecture.

CONJECTURE 6.4 The Erdős-Hajnal conjecture -tournament version, [APS01]

Every tournament has the Erdős-Hajnal property.

The tournament version of the conjecture offers certain advantages comparing to its undirected version. For instance, given two undirected graphs H and H where H ⊆ H , it is possible that a graph G is H-free but not H -free (for example, P 2 ⊆ K 3 , and K 4 is P 2 free but not K 3 -free). However, given two tournaments H and H where H ⊆ H , if a tournament T is H-free, then T is H -free. This immediately implies that if a tournament H has the Erdős-Hajnal property, then so does every subtournament of H, which does not hold for the undirected version.

Celebrities and heroes

Similar to the undirected version, finding patterns satisfying the Erdős-Hajnal property for tournament is challenging. One may wish to address an extremal case of the conjecture: Which patterns have the Erdős-Hajnal property where the largest transitive subtournament of T have linear size, i.e. the constant ε is 1?

DEFINITION 6.5

We say that a pattern H is a celebrity if there exists a constant δ(H) > 0 such that every H-free tournament T contains a transitive tournament of size at least δ(H)|V(T)|.

Similarly, if H is a celebrity, then every subtournament of H is a celebrity. A major result was achieved in 2013 [BCC + 13], in which they completely characterized the family of celebrities and so added an infinite family of tournaments to the list of patterns satisfying the Erdős-Hajnal property. The proof of their result was not done via directly characterizing the family of celebrities, but another the family of patterns instead -the heroes. Unlike the celebrities, which forbidding forces the tournament to have a large transitive subtournament, forbidding a hero causes the tournament to be less colorful. We recall that a vertex-coloring (or coloring for short) of a digraph D is an assignment of each vertex of D to a color from a set of given colors. The definition of proper coloring digraph is slightly different from that of simple graphs: a coloring is proper if D does not contain any directed cycle of where all vertices have same color.

DEFINITION 6.6

We say that a pattern H is a hero if there exists a constant c(H) > 0 such that every H-free tournament T can be properly colored by c(H) colors.

Coloring tournaments can be viewed alternatively as partitioning tournaments into subtournaments. A partition of a tournament T is a set of subtournaments

T 1 , ..., T k such that k i=1 V(T i ) = V(T) and V(T i ) ∩ V(T j ) = ∅ for every i = j.

PROPOSITION 6.7

A tournament can be properly colored by k colors if and only if it can be partitioned into k transitive subtournaments.

The proof is simple. If a tournament T can be colored by k colors, then consider a proper coloring of G with colors 1, ..., i. For each color i, we assign T i to be the subtournament of T on the set of vertices with color i. By the definition of proper coloring, each subtournament T i is transitive. The converse direction is similar. It is now straightforward that the family of heroes is contained in the family of celebrities. Indeed, for every hero H, there is a constant c(H) such that every H-free tournament T can be partitioned into c(H) transitive tournaments. Then one of these tournament must have size at least 1 c(H) |V(T)|. Hence H is a celebrity. In the proof of Berger et al [BCC + 13], they first showed that the two familys are identical.

THEOREM 6.8 [BCC + 13]

Every celebrity is a hero.

Then they characterized all heroes as follows. Given tournaments H 1 , H 2 , H 3 , we denote by H 1 ⇒ H 2 the vertex-disjoint union of H 1 and H 2 with all arcs from H 1 to H 2 , and ∆(H 1 , H 2 , H 3 ) the vertex-disjoint union of H 1 , H 2 , H 3 with all arcs from H 1 to H 2 , from H 2 to H 3 , and from H 3 to H 1 . For every integer k 1, let T k denote the transitive tournament on k vertices. The family of heroes are constructed as follows:

• The singleton T 1 is a hero.

• If H 1 and H 2 are heroes, then H 1 ⇒ H 2 is a hero.

• If H is a hero, then ∆(H, T k , T 1 ) and ∆(H, T 1 , T k ) are heroes for every k 1.

Any tournament that cannot be constructed by this process is not a hero.

The combination of Theorems 6.8 with 6.9 gives a complete characterization of the set of celebrities, i.e. a complete characterization of patterns satisfying the Erdős-Hajnal property with constant ε = 1. A similar result was achieved one year later for the case ε 5/6 [START_REF] Choromanski | Tournaments with near-linear transitive subsets[END_REF].

A conjecture by Berger et al

The main objective of Theorem 6.9 is to show that every H-free tournament T can be colored by a few colors. The authors observed that in order to reach that conclusion, they went cross in the proof multiple times the fact that every local region (the outneighborhood a vertex) of T can be colored by a few colors as well. This leads to the question whether the local colorfulness of a tournament dictates its global colorfulness. In other words, whether it is true that if every local region of a tournament can be colored by a few colors, then so does the whole tournament. This is another vivid example about how local properties may affect the global behavior and structure of a large graph. More formally, given t 1, a tournament T is t-local if for every vertex v, the subtournament of T on the set of out-neighbors of v can be colored by t colors.

CONJECTURE 6.10 Berger et al, 2013

There is a function f such that every t-local tournament T can be properly colored by f (t) colors. Conjecture 6.10 was proved recently for the case t = 2 in [CKL + 18]. In this chapter, we will verify the conjecture for all t. We also generalize it to dense digraphs, which is a key result to extend the family of celebrities and the Erdős-Hajnal conjecture to dense digraphs in the next chapter.

Proof of Berger et al's conjecture

To proceed the proof of Conjecture 6.10, we need several definitions. We will provide the definitions in general digraphs for later use. The chromatic number χ(D) of a di-graph D, is the minimum number k such that D can be properly colored by k colors. Given a subset A of V(D), we usually denote by χ(A) the chromatic number of the digraph D[A] when it is clear from the context. Given a digraph D and a set S ⊂ V(D), we say that S is a dominating set of D if every vertex in V(D) \ S has an in-neighbor in S. The domination number γ(D) of a digraph D is the smallest number k such that D has a dominating set of size k. Recall that for every vertex v in a digraph D, we denote by

N + D (v) the set of out-neighbors of v in D. Given a subset X of V(D), let N + D (X) denote the union of all N + D (v), for v ∈ X, and denote by N + D [X] := X ∪ N + D (X)
. We first have the following property of t-local tournaments.

PROPOSITION 6.11

Let T be a t-local tournament. Then for every subset X of V(T), χ(N + [X]) t|X|.

Proof. Observe that for every v, we can color N + [v] with t colors by first coloring N + (v) with t colors and then coloring arbitrarily v with one of these t colors (since v dominates N + (v), coloring v does not create any monochromatic directed cycle). To color N + [X], we color N + [v] sequentially for every v ∈ X. For each v ∈ X, we color the uncolored vertices in N + [v] with t new colors. Thus we can color N + [X] with t|X| colors.

Let C be a class of tournaments closed under taking subtournaments. We say that C is tamed if for every integer k there exists K and such that every tournament T ∈ C with χ(T) K contains a set A of vertices such that χ(A) k. Note that a class of tournaments with bounded chromatic number is indeed tamed.

THEOREM 6.12

For every t, the class of t-local tournaments is tamed.

Thank to Theorem 6.12, we can show that Conjecture 6.10 is true.

THEOREM 6.13

There is a function f such that every t-local tournament T satisfies χ(T) f (t).

Proof. Since the class of t-local tournaments is tamed, by the tamed property applied to k = t + 1, there exists (K, ) such that every t-local tournament T with χ(T) K contains a set A of vertices and χ(A) t + 1. If a vertex v ∈ V(T)\A does not have an in-neighbor in A, then A ⊆ N + (v), and so t + 1 χ(A) χ(N + (v)) t, a contradiction. Hence, A is a dominating set of T. Thus, χ(T) = χ(N + [A]) t|A| = t. Consequently, t-local tournaments have chromatic number at most f (t) := max(K, t).

We now prove Theorem 6.12.

Proof of Theorem 6.12. We fix some arbitrary t and show the property by induction on k. The claim is trivial for k = 1. For k = 2, we can choose K = 2 and = 3. Indeed, if a tournament T satisfies χ(T) K = 2, it contains an oriented triangle S of size = 3 and χ(S) k = 2.

Assuming now that (K, ) exists for k, we want to find (K , ) for k + 1. For this, we set K := 2kt(K + t + 1), and fix later. Let T be a t-local tournament such that χ(T) K . Let D be a dominating set of T of minimum size d. By Proposition 6.11, we have χ(T) = χ(N + [D]) td. In particular, d 2k(K + t + 1). Consider a subset W of D of size k(K + t + 1). By Proposition 6.11, we have χ(N + [W]) kt(K + t + 1), and hence

χ(V \ N + [W]) χ(T) -χ(N + [W]) kt(K + t + 1) K,
where V is the vertex set of T. In particular, by the tamed property applied to k, one can find a set A ⊆ V \ N + [W] such that A has vertices and χ(A) k. Note that by construction, A ∩ W = ∅ and all arcs between A and W are directed from A to W.

Consider now a subset S of W of size K + t + 1. We claim that χ(N + (S)) K + t.

If not, we can cover N + (S) by at most K + t -1 transitive sets. Since every transitive tournament has a dominating set of size 1, we can choose a dominating set S of N + (S) of size at most K + t -1. Note that x dominates S for any x ∈ A, and so S ∪ {x} dominates N + [S]. Hence (D \ S) ∪ S ∪ {x} would be a dominating set of T of size less than |D|, which contradicts the minimality of |D|. Therefore, χ(N + (S)) K + t.

Let N be the set of vertices N + (S) \ N + (A). Observe that all the arcs between N and A are directed from N to A, and that by Proposition 6.11 applied to N + (A), we have χ(N + (A))

t, and so

χ(N ) χ(N + (S)) -χ(N + (A)) K + t -t = K.
Thus, by the tamed property applied to k, there is a subset A S of N such that |A S | = and χ(A S ) k. Note that by construction, A S ∩ A = ∅ and all arcs between A S and A are directed from A S to A.

We now construct our subtournament of T with chromatic number at least k + 1. For this we consider the set of vertices A ∪ W to which we add the collection of A S , for all subsets S ⊆ W of size K + t + 1. Call A this new tournament and observe that its number of vertices is at most

:= + k(K + t + 1) + k(K + t + 1) K + t + 1 .
To conclude, it is sufficient to show that χ(A ) k + 1. Suppose not, and for contradiction, take a k-coloring of A . Since |W| = k(K + t + 1) there is a monochromatic set S in W of size K + t + 1 (say, colored 1). Recall that we have all arcs from A S to A and all arcs from A to S, and note that since χ(A) k and χ(A S ) k, both A and A S have a vertex of each of the k colors. Hence there are u ∈ A and w ∈ A S colored 1.

Since A S ⊆ N + (S), there is v ∈ S dominating w. We then obtain the monochromatic cycle uvw of color 1, a contradiction. Thus, χ(A ) k + 1, completing the proof.

Generalizing to dense digraphs

The term digraphs in Part II is used to mention simple, loopless and finite digraphs, where a digraph D is simple if for every two vertices u and v of D, there is at most one arc with endpoints {u, v}. The purpose of this section is to extending Conjecture 6.10 from tournaments to dense digraphs, which will serve as a key tool for the results in the next chapter.

Besides the out-and in-neighbors

N - D (v) and N + D (v) of a vertex v in a digraph D, we also denote by N o D (v) the set of vertices non-adjacent to v in D. For a subset X of V(D), we denote by N o D (X) the set of vertices of V non-adjacent to at least one vertex in X. A stable set in a digraph is a set of vertices pairwise non-adjacent. Given a positive integer α, a digraph D is called α-dense 2 if it contains no stable set of size α + 1. Given t 1, a digraph D is t-local if for every vertex v we have χ(N + (v)) t.
The extension of Conjecture 6.10 to dense digraphs is as follows.

THEOREM 6.14

For every positive integers α and t, there is a function f α (t) such that every α-dense t-local digraph D can be properly colored by f α (t) colors.

And we have a similar version of Proposition 6.11.

PROPOSITION 6.15

Given a t-local digraph D, for every subset X of V(D), χ N + [X]) t|X|.

We also have another observation regarding dominating sets in an acyclic digraph.

PROPOSITION 6.16

An acyclic digraph D has a dominating set which is also a stable set.

Proof. We proceed by induction on |D| to show that every acyclic digraph D has a dominating set S which is stable. The statement clearly holds for |D| = 1. For |D| > 1, since D is acyclic, there is a vertex v with no in-neighbors. Then V(D)\{v} =

χ(M -(W)) χ(D) -χ(N + [W]) -χ(N o (W)) K -kt(αs + 1) -∑ x∈W χ(N o (x)) K -k(αs + 1)(t + f α-1 (t) + 1) K /2 K.
In particular, by the tamed property applied to k, one can find a set A ⊂ M -(W) such that A has vertices and χ(A) k.

Consider now a subset S of W of size αs + 1. We claim that χ(N + (S)) s. If not, we can cover N + (S) by at most s -1 acyclic sets. Since every acyclic set has independence number at most α, it has a dominating set of size at most α by Proposition 6.16. Hence N + (S) has a dominating set, say S of size at most α(s -1) |S| -2. But this yields a contradiction since the set (B \ S) ∪ S ∪ {x}, where x is an arbitrary vertex in A, would be a dominating set of T of size less than |B|. Therefore, χ(N + (S)) s.

By Proposition 6.15 applied to N + (A), we have χ(N + (A))

t. Hence

χ(N + (S) ∩ M -(A)) χ(N + (S)) -χ(N + (A)) -χ(N o (A)), s -t -∑ x∈A χ(N o (x)), (K + f α-1 (t) + t) -t -|A| f α-1 (t), = K.
Thus, by the tamed property applied to k, there is a subset

A S of N + (S) ∩ M -(A) such that |A S | = and χ(A S ) k.
We now construct our subset of V with chromatic number at least k + 1. For this we consider the set A consisting of vertices A ∪ W to which we add the collection of A S , for all subsets S ⊆ W of size αs + 1. Observe that the number of vertices of A is at most

:= + k(αs + 1) + k(αs + 1) s α + 1.
To conclude, it is sufficient to show that χ(A ) k + 1. Suppose not, and for contradiction, take a k-coloring of A . Since |W| = k(αs + 1) there is a monochromatic set S in W of size αs + 1 (say, colored 1). Recall that A S ⊆ M -(A) and A ⊆ M -(W) ⊆ M -(S), so we have all arcs from A S to A and all arcs from A to S, and note that since χ(A) k and χ(A S ) k, both A and A S have a vertex of each of the k colors. Hence there are u ∈ A and w ∈ A S colored 1. Since A S ⊆ N + (S), there is v ∈ S such that vw is an arc. We then obtain the monochromatic cycle uvw of color 1, a contradiction. Thus, χ(A ) k + 1, completing the proof of the claim.

We conclude the chapter by mentioning another version of Theorem 6.14, where the tamed property is applied to in-neighbors instead of out-neighbors. The theorem can be obtained easily form Theorem 6.14 by just reversing the directions of all arcs.

THEOREM 6.18

For every t and α, there is f α (t) such that every α-dense digraph D with χ(N -(v)) t for every v ∈ V(D) has chromatic number at most f α (t).

Conjecture 7.2 should be substantially harder than the Erdős-Hajnal conjecture (since it generalizes the class of both patterns and large graphs from tournaments to digraphs). Even a very simple pattern as the directed triangle C 3 is not known to have the general Erdős-Hajnal property. So far, the transitive tournaments T k are the only digraphs known to have the general property. The proof is quite simple. Let D be a T k -free digraph. We enumerate the vertices of D arbitrarily and consider a mapping from D to an undirected graph G where a forward arc of D is mapped to an edge of G, and a backward arc or a non-edge of D is mapped to a non-arc of G. Then G does not have any clique of size k, and so has a stable set S of linear size. Note that the induced subgraph D[S] contains only backward arcs or non-edges. Since the underlying graph of D[S] contains no clique of size k, it must contain a stable set of linear size, which is also a stable set in D.

While we could not provide any non-trivial pattern having the general Erdős-Hajnal property, we will show in this chapter a family of patterns having a weaker property than the general one (which requires to hold for all H-free digraphs) but stronger than the original one (requiring to hold for all H-free tournaments), which we called the extended Erdős-Hajnal property (requiring to hold for all H-free dense digraphs). Recall that given a positive integer α, a digraph D is called α-dense if it contains no stable set of size α + 1.

DEFINITION 7.3

We say that a digraph H has the extended Erdős-Hajnal property if there exists a constant ε(H, α) > 0 such that every H-free digraph D contains an acyclic subdigraph of size at least |V(D)| ε (H,α) .

Clearly, every tournament with the general Erdős-Hajnal property must have the extended one, and every tournament with the extended property must have the original one. One idea to prove Conjecture 7.2, which asserts that every digraph has the general property, is to show that the converse of the two observations above holds as well, i.e., every tournament with the original property has the extended one, and every tournament with the extended property has the general one. To support Conjecture 7.2, we will prove in this chapter that the family of celebrities have the extended Erdős-Hajnal property, and so characterize all tournaments having the extended property with a linear size acyclic set.

DEFINITION 7.4

We say that a digraph H is a superstar if for every positive integer α, there exists a constant δ(H, α) > 0 such that every α-dense H-free digraph D contains an acyclic subgraph of size at least δ(H, α)|V(D)|.

The first observation is that every superstar is a celebrity. In the rest of this chapter, we will show that the converse is true. Every superstar is a celebrity.

To prove Theorem 7.5, we follow Berger et al [BCC + 13] and resort to the coloring of digraphs.

DEFINITION 7.6

We say that a digraph H is a superhero if for every positive integer α, there exists a constant c(H, α) > 0 such that every α-dense H-free digraph D can be properly colored by c(H, α) colors.

Similarly, it is not hard to see that every superhero is a superstar. Thus, we have:

F superheroes ⊆ F superstars ⊆ F heroes = F celebrity ,
where F x is the family of patterns x. Let us recall that given tournaments H 1 , H 2 , H 3 , we denote by H 1 ⇒ H 2 the vertex-disjoint union of H 1 and H 2 with complete arcs from H 1 to H 2 , and ∆(H 1 , H 2 , H 3 ) the vertex-disjoint union of H 1 , H 2 , H 3 with complete arcs from H 1 to H 2 , from H 2 to H 3 , and from H 3 to H 1 . For every integer k 1, let T k denote the transitive tournament on k vertices. To prove Theorem 7.5, it is sufficient to show that every hero is a superhero. More precisely, it is sufficient to prove the following theorem, which was a conjecture of Aboulker, Charbit and Naserasr (private communication, 2016).

THEOREM 7.7

The family of superheroes are constructed as follows:

• The singleton T 1 is a superhero.

• If H 1 and H 2 are superheroes, then H 1 ⇒ H 2 is a superhero.

• If H is a superhero, then ∆(H, T k , T 1 ) and ∆(H, T 1 , T k ) are superheroes for every k 1.

Any tournament that cannot be constructed by this process is not a superhero.

Obviously T 1 is a superhero. Thus to prove Theorem 7.7, it suffices to prove the following two theorems.

THEOREM 7.8

If H 1 and H 2 are superheroes, then H 1 ⇒ H 2 is a superhero.

THEOREM 7.9

If H is a superhero, then ∆(H, T 1 , T k ) and ∆(H, T k , T 1 ) are superheroes for any k 1.

Notation and remarks

The proofs of Theorems 7.8 and 7.9 are considerably technical. Thus, we recall here thoroughly the necessary notation. Given a digraph D, we say that u sees v and v is seen by u if uv is an arc in D. For every v ∈ V(D), we denote by

N + D (v) (res. N - D (v)) the set of out-neighbors (res. in-neighbors) of v in D. Let N(v) = N + D (v) ∪ N - D (v). For every X ⊆ V(D), let N + D (X) = v∈X N + D (v) (res. N - D (X) = v∈X N - D (v)
), the set of vertices seen by (res. seeing) at least one vertex of X, and let

M + D (X) = v∈X N + D (v) (res. M - D (X) = v∈X N - D (v)
), the set of vertices seen by (res. seeing) all vertices of X.

Let N D (X) denote N + D (X) ∪ N - D (X). For every v ∈ V(D), we denote by N o D (v) the set non-adjacent vertices of v in D.
For a subset X of V(D), we denote by N o D (X) the set of vertices of V non-adjacent to at least one vertex of X. When it is clear in the context (most of the time), we omit the subscript D in this notation. We will use throughout this chapter the fact that

V(D)\X = M + D (X) ∪ N - D (X) ∪ N o D (X) for any X ⊆ V(D). Given a digraph D and two disjoint sets X, Y ⊆ V(D), we denote X → D Y (or just X → Y) if there is no arc from Y to X in D. A key observation is that if X → Y, then χ(X ∪ Y) = max χ(X), χ(Y) .
A side remark is that some proofs in this chapter proceeding by induction on α use the fact that if D is α-dense, then N o (v) is (α -1)-dense for every v, and thus χ(N o (v)) is bounded. In these inductive proofs, we often cite known results on tournaments for the base case α = 1. However, the proofs here are indeed self-contained since to prove the base case α = 1, we just repeat the same arguments and use the fact that in a tournament, N o (v) = ∅ for any vertex v. Hence for example, the proof of Theorem 7.9 can serve as an alternative proof for Theorem 4.1 in [BCC + 13] (that if H is a hero, then so are ∆(H, T k , T 1 ) and ∆(H, T 1 , T k )).

Chains of superheroes

In this section, we will prove Theorem 7.8, which states that if H 1 and H 2 are superheroes, then so is H 1 ⇒ H 2 . We will reuse the notions of r-mountains and (r, s)-cliques introduced in [BCC + 13]. Let us first give the idea of the proof of Theorem 7.8 for a special case: (C 3 ⇒ C 3 )-free tournaments have bounded chromatic number. Given a (C 3 ⇒ C 3 )-free tournament T, suppose that there is a small set Q in T with chromatic number 3. Then for any partition of Q into Q 1 , Q 2 , at least one part of the partition has chromatic number at least 2, and so contains a copy of C 3 . Let Y Q 1 ,Q 2 ⊆ V(D)\Q be the set of vertices seeing all vertices of Q 1 and seen by all vertices of

Q 2 . Observe that Y Q 1 ,Q 2 is C 3 -free, otherwise a copy of C 3 in Y Q 1 ,Q 2 together with a copy of C 3 in either Q 1 or Q 2 forms a copy of C 3 ⇒ C 3 . Note that V(T)\Q is covered by only 2 |Q| such sets Y Q 1 ,Q 2 ,
and hence χ(T) is bounded.

Hence we wish to find such a small set of vertices Q with chromatic number 3. To this end, we call an arc uv of T thick if N -(u) ∩ N + (v) contains a copy of C 3 . If T has no thick arcs, then intuitively T should have simple structure, and thus, bounded chromatic number. Suppose that T contains a (not necessarily directed) triangle uvw where all of the three arcs are thick. Then for each of the three thick arcs, we take its thickness-certificate (i.e., a copy of C 3 ) and together with u, v, w we obtain a set Q of at most 12 vertices. It is straightforward to verify that Q has chromatic number at least 3, and thus, by the argument above χ(T) is bounded. If T contains no triangle of thick arcs, then for any vertex v, the set of vertices adjacent to v by a thick arc induces a thick-arc-free tournament, which, intuitively, should have bounded chromatic number. We then easily bound the chromatic number of the sets of non-thick in-neighbors and non-thick out-neighbors of v, and hence bound the chromatic number of T.

The proof of the general case is in the same vein. Intuitively, we search for a small set Q with large chromatic number as described above. We will capture the notion of the set Q with the definition of an object called an r-mountain, and the notion of a triangle of thick arcs with objects called (r, s)-cliques. Given a digraph D, the formal definitions (which are borrowed from [BCC + 13]) of r-thick-arc, (r, s)-clique, and r-mountain in D are defined inductively on r as follows. Every vertex of D is a 1mountain. For every r, s 1,

• An arc e of D is r-thick if N -(u) ∩ N + (v) contains an r-mountain. An r-mountain in N -(u) ∩ N + (v) is a certificate of r-thickness of e.

• An (r, s)-clique of D is a set S ⊆ V(D) such that |S| = s, and for every distinct vertices u, v ∈ S, either uv or vu is an arc that is r-thick.

• Given an (r, r + 1)-clique S and a certificate C u,v for every distinct u, v ∈ S, then the tournament induced on S ∪ ( u,v∈S C u,v ) is an (r + 1)-mountain of D.

Note that if a digraph D contains an (r, r + 1)-clique, then D contains an (r + 1)mountain, which is the (r, r + 1)-clique together with certificates of all r-thick arcs of that (r, r + 1)-clique. Hence, if D contains no (r + 1)-mountain, then D contains no (r, r + 1)-clique. • Every α-dense (H 1 ⇒ H 2 )-free digraph D containing no r-mountain has

χ(D) < b 2 .
Then there is b 3 such that every α-dense (H 1 ⇒ H 2 )-free digraph D containing no (r, s + 1)-clique has χ(D) < b 3 .

Proof. A small remark is that the second hypothesis seems redundant since if D contains no (r, 2)-clique, then D contains no r-thick arc, and so contains no r-mountain. However, the second hypothesis is necessary for the case s=1.

First, note that since H 1 and H 2 are superheroes, there is b 4 such that every αdense H 1 -free (or H 2 -free) digraph D has χ(D) b 4 . We first identify all r-thick arcs of D. Fix an arbitrary vertex v. Then V(D)\{v} can be partitioned into four sets: N * the set of neighbors of v that are connected to v by an r-thick arc;

N -= N -(v)\N * ; N + = N + (v)\N * ; and N o (v). Note that N o (v) is (H 1 ⇒ H 2 )
-free and (α -1)-dense, and so by the first hypothesis, χ(N o (v)) b 0 . The crucial fact is that the digraph induced by the set N * does not contain an (r, s)-clique; indeed, an (r, s)-clique together with v would form an (r, s + 1)-clique, a contradiction to the fact that D has no (r, s + 1)-cliques. Hence by the second hypothesis, χ(N * ) b 1 .

CLAIM 7.12

There is b 5 such that either χ(N -) b 5 or χ(N + ) b 5 .

Proof. Suppose that χ(N -) b 4 , then N -contains a copy of H 1 , say H 1 . Note that

N + = M + ( H 1 ) ∩ N + ∪ N o ( H 1 ) ∩ N + ∪ N -( H 1 ) ∩ N + . • If χ(M + ( H 1 ) ∩ N + ) b 4 , then M + ( H 1 ) ∩ N + contains
) ∩ N + ) b 4 • For each u ∈ H 1 , we have N o (u) ∩ N + is (α -1)-dense, so χ(N o (u) ∩ N + ) b 0 . • For each u ∈ H 1 , if χ(N -(u) ∩ N + )
b 2 , then N -(u) ∩ N + contains a rmountain. This means that uv is an r-thick arc, contradicting u / ∈ N * . Hence

χ(N -(u) ∩ N + ) b 2 , for each u ∈ H 1 .

CHAINS OF SUPERHEROES | 99

Thus we have, Note that N + (v) ⊆ N + ∪ N * , and so χ(N + (v))

χ(N + ) χ(M + ( H 1 ) ∩ N + ) + ∑ u∈ H 1 χ(N o (u) ∩ N + ) + χ(N -(u) ∩ N + ) b 4 + |H 1 |(b 0 + b 2 ).
χ(N + ) + χ(N * ). Similarly, χ(N -(v)) χ(N -) + χ(N * ). Hence for every v ∈ V(D), either χ(N + (v)) b 5 + b 1 or χ(N -(v)) b 5 + b 1 . Let R be the set of all vertices v ∈ V(D) with χ(N + (v)) b 5 + b 1 and B be the set of all vertices v ∈ V(D) with χ(N -(v)) b 5 + b 1 . Note that R ∪ B = V(D).
Observe that R is an α-dense digraph, and Recall that if D contains no (r + 1)-mountain, then D contains no (r, r + 1)-clique. We are now ready to show that digraphs which do not contain a mountain have bounded chromatic number.

χ(N + R (v)) χ(N + D (v)) b 5 + b 1 for every v ∈ R.

LEMMA 7.13

Let α 2, and suppose that every (α -1)-dense (H 1 ⇒ H 2 )-free digraph D has χ(D) < b 0 for some b 0 . Then for every r, there exists g α (r) such that every α-dense (H 1 ⇒ H 2 )-free digraph not containing an r-mountain has χ(D) g α (r).

Proof. We proceed by induction on r. If D contains no 1-mountain, then D has no vertices, and we can set g α (r) := 0. Now suppose by induction that g α (r) exists. We will show that g α (r + 1) exists. First, we claim the following.

(A) For every s, there exists function g α,r (s) such that if D contains no (r, s)-clique, then χ(D) g α,r (s).

We prove (A) by induction on s. For s = 1, if D contains no (r, 1)-clique, then D has no vertex, so g α,r (s) = 0. Suppose, by induction, that g α,r (s) exists. Let D be a digraph not containing a (r, s + 1)-clique. Applying Lemma 7.11 with b 1 = g α,r (s) and b 2 = g α (r), we deduce that g α,r (s + 1) exists. This proves (A).

If D contains no (r + 1)-mountain, then D contains no (r, r + 1)-clique, implying χ(D) g α,r (r + 1). Set g α (r + 1) := g α,r (r + 1). This completes the proof.

100| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE

To prove Theorem 7.8, it suffices to prove the following lemma.

LEMMA 7.14

For every integer α 1, there exists f (α) such that every α-dense (H 1 ⇒ H 2 )-free digraph D has χ(D) f (α).

Proof. We proceed by induction on α. Since H 1 ⇒ H 2 is a hero (see [BCC + 13], Theorem 3.2), Lemma 7.14 is true for α = 1. Suppose that Lemma 7.14 is true for α -1 and let c 0 = f (α -1). Since both H 1 and H 2 are superheroes, there exists c 1 such that if D is any H 1 -free or H 2 -free digraph, then χ(D) c 1 . Let D be an α-dense (H 1 ⇒ H 2 )free digraph with vertex set V. If D does not contain a (c 0 + 2c 1 )-mountain, then by applying Lemma 7.13 to D with b 0 = c 0 , there is c 2 such that χ(D) c 2 . Thus, it remains to consider the case that D contains a (c 0 + 2c 1 )-mountain.

CLAIM 7.15

There is c 3 such that if D contains a (c 0 + 2c 1 )-mountain, then χ(D) c 3 .

Proof. Let Q be a (c 0 + 2c 1 )-mountain of D. Then by Lemma 7.10, |Q| ((c 0 + 2c 1 )!) 2 and χ(Q) c 0 + 2c 1 . For every partition Q into three sets Q

0 , Q 1 , Q 2 , let Y Q 0 ,Q 1 ,Q 2 be the set of vertices v ∈ V\Q such that Q 0 ⊆ N o (v), Q 1 ⊆ N + (v), and Q 2 ⊆ N -(v).
Note that for every vertex v ∈ V\Q, there always exists a partition of Q into some sets Q 0 , Q 1 , Q 2 such that v is non-adjacent with every vertex in Q 0 , sees every vertex in Q 1 and is seen by every vertex in Q 2 . Hence, V\Q can be written as the union of all possible

Y Q 0 ,Q 1 ,Q 2 . There are 3 |Q| sets Y Q 0 ,Q 1 ,Q 2 . (B) χ(Y Q 0 ,Q 1 ,Q 2 ) c 1 for every partition (Q 0 , Q 1 , Q 2 ) of Q. Indeed, if Y Q 0 ,Q 1 ,Q 2 = ∅, then (B) clearly holds. Otherwise, Q 0 ⊆ N o (v) for any v ∈ Y Q 0 ,Q 1 ,Q 2 . Note that the digraph Q 0 is (H 1 ⇒ H 2 )
-free and (α -1)-dense, and so by induction hypothesis, χ(Q 0 ) c 0 . This gives

χ(Q 1 ∪ Q 2 ) χ(Q) -χ(Q 0 ) 2c 1 , implying that either χ(Q 1 ) c 1 or χ(Q 2 ) c 1 . If χ(Q 1 ) c 1 , then Q 1 contains a copy of H 2 , say H 2 . If χ(Y Q 0 ,Q 1 ,Q 2 ) c 1 , then Y Q 0 ,Q 1 ,Q 2 contains a copy of H 1 , say H 1 . Then H 1 ⇒ H 2 forms a copy of H 1 ⇒ H 2 , a contradiction. Hence, χ(Y Q 0 ,Q 1 ,Q 2 ) c 1 .
A similar argument establishes the case χ(Q 2 ) c 1 . This proves (B).

CYCLES OF SUPERHEROES | 101

Hence

χ(D) χ(Q) + χ(V\Q) |Q| + χ( (Q 0 ,Q 1 ,Q 2 ) Y Q 0 ,Q 1 ,Q 2 ) |Q| + ∑ (Q 0 ,Q 1 ,Q 2 ) χ(Y Q 0 ,Q 1 ,Q 2 ) ((c 0 + 2c 1 )!) 2 + 3 ((c 0 +2c 1 )!) 2 c 1 .
Set c 3 := ((c 0 + 2c 1 )!) 2 + 3 ((c 0 +2b 1 )!) 2 c 1 . This completes proof of the claim.

Hence χ(D) max(c 2 , c 3 ). Setting f (α) := max(c 2 , c 3 ) completes the proof of Lemma 7.14, thus proving Theorem 7.8.

Cycles of superheroes

We will conclude this chapter with the proof of Theorem 7.9, which states that if H is a superhero, then so are ∆(H, T k , T 1 ) and ∆(H, T 1 , T k ) for any integer k 1. We will prove that if H is a superhero, then so is ∆(H, T k , T 1 ) for any k 1. This is sufficient. Indeed, if H is a superhero, then so is H rev , the digraph obtained from H by reversing all its arcs. Thus, ∆(H rev , T k , T 1 ) rev = ∆(H, T 1 , T k ) is also a superhero.

THEOREM 7.16

For every superhero H and every pair of integers k, α 1, there is a number f (H, k, α) such that every α-dense ∆(H, T k , T 1 )-free digraph D has χ(D) f (H, k, α).

Before starting the proof of Theorem 7.16, we would like to mention that T k -free digraphs have bounded number of vertices, and so have bounded number of chromatic number. Indeed, it is proved in [START_REF] Stearns | The voting problem[END_REF] that for each integer k 1, every tournament with at least 2 k-1 vertices contains a copy of T k . Let R(a, b) be the Ramsey number of (a, b), i.e., the smallest n such that any graph on n vertices either contains a stable set of order a or a clique of order b.

PROPOSITION 7.17

For each integer k 1, every α-dense T k -free digraph D has at most R(α + 1, 2 k-1 ) vertices.

Proof. Suppose for a contradiction that there is a T k -free digraph D with at least R(α + 1, 2 k-1 ) vertices. Then the underlying graph of D contains either a stable set of size 102| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE α + 1 or a clique of size 2 k-1 . The former case is impossible since D is α-dense. Thus D contains a tournament of size 2 k-1 , and hence contains a copy of T k , a contradiction.

The idea of the proof of Theorem 7.16 is as follows. Fix a large number c and call a subset B of V(D) with χ(B) = c a bag. We aim at finding a longest chain of disjoint bags B 1 , ..., B t in V(D), together with a partition V(D)\ B i into sets we call zones Z 0 , ..., Z t such that there is no backward arc in D (where uv is a backward arc if the bag or zone containing u has higher index than the bag or zone containing v). Then, using maximality of t, we show that the chromatic number of every zone is bounded. Once proving this, we observe that all B i and Z i have bounded chromatic number and since D has no backward arc, D has bounded chromatic number. However, the requirement that there is no backward arc in D is too strong and so we will have to slightly relax it. In doing so, we will need to allow some backward arcs, but we will want to do so in a very controlled manner. This leads us to the following definitions.

Given an integer c

1 and an α-dense ∆(H,

T k , T 1 )-free digraph D, a set B ⊆ V(D) with χ(B) = c is called a c-bag. A family of pairwise disjoint c-bags B 1 , ..., B t is a c-bag-chain if for every i and every v ∈ B i , we have χ(N + (v) ∩ B i-1 ) c 1 and χ(N -(v) ∩ B i+1 ) c 1 , where c 1 is a fixed number satisfying • c 1 R(α + 1, 2 k-1 ), and • c 1 χ(D) for every α-dense H-free digraph D.
Since H is a superhero, such c 1 clearly exists. Note that every α-dense T k -free digraph D has at most c 1 vertices by Proposition 7.17, and so has chromatic number at most c 1 .

Proof of Theorem 7.16. We proceed by induction on α. Since ∆(H, T k , T 1 ) is a hero (see [BCC + 13], Theorem 4.1), the theorem holds for α = 1. Suppose that Theorem 7.16 is true for α -1 and let c 0 = f (H, k, α -1). Let D be an α-dense ∆(H, T k , T 1 )-free digraph with vertex set V. An important observation is that for every v ∈ V, the digraph N o (v) is ∆(H, T k , T 1 )-free and is (α -1)-dense, and hence

χ(N o (v)) f (H, k, α -1) = c 0 . ( 7.1)
We also would like to recall some useful formulas. For every v ∈ X ⊆ V,

χ(N + (X)) ∑ v∈X χ(N + (v)) and χ(N o (X)) ∑ v∈X χ(N o (v)), (7.2)
and if Y ⊆ V and Y ∩ X = ∅, then (recalling that M + (X) is the set of vertices seen by all vertices of X)

Y = (M + (X) ∩ Y) ∪ (N -(X) ∪ N o (X)) ∩ Y . ( 7.3)
Let |H| = h and set c := 2(c 0 + c 1 )(h + k). Let us assume that B 1 , ..., B t is a c-bagchain of D with t as large as possible. In the proof of this theorem, we drop prefix cof c-bag and c-bag-chain for convenience. By definition of bag-chain, every bag has few backward arcs with bags preceeding or succeeding it. In the following claim, we show that every bag in fact has few backward arcs with any other bag.

CLAIM 7.18

For every i and v ∈ B i , and for every r > 0,

(a) χ(N + (v) ∩ B i-r ) c 1 , and (b) χ(N -(v) ∩ B i+r ) c 1 .
Proof. We proceed by induction on r. For r = 1, both (a) and (b) holds by definition of bag-chain. Suppose that both statements are true for r -1. We now prove (a) for r. Suppose for a contradiction that there is v in some B i such that χ(N + (v) ∩ B i-r ) c 1 . Then N + (v) ∩ B i-r has a copy of H, say H. Then by applying (7.3) we have

B i-1 = M + ( H) ∩ B i-1 ∪ N -( H) ∪ N o ( H) ∩ B i-1 , and B i-1 = N -(v) ∩ B i-1 ∪ N + (v) ∪ N o (v) ∩ B i-1 .

Thus (by using the fact that if

A = B ∪ C = B ∪ C , then A = (B ∩ B ) ∪ C ∪ C ) we have B i-1 = M + ( H) ∩ N -(v) ∩ B i-1 ∪ N -( H) ∪ N o ( H) ∩ B i-1 ∪ ∪ N + (v) ∪ N o (v) ∩ B i-1 . (7.4)
For each x ∈ H, by (7.1) we have χ(N o (x) ∩ B i-1 ) c 0 , and by induction hypothesis of (b) applied to x and r -1, we have χ(N -(x) ∩ B i-1 ) c 1 . We also have χ(N o (v) ∩ B i-1 ) c 0 by (7.1) and χ(N + (v) ∩ B i-1 ) c 1 by definition of a bag-chain. Combining with (7.4) and (7.2) we have

χ(M + ( H) ∩ N -(v) ∩ B i-1 ) χ(B i-1 ) -∑ x∈ H∪{v} χ(N o (x) ∩ B i-1 ) -∑ x∈ H χ(N -(x) ∩ B i-1 ) -χ(N + (v) ∩ B i-1 ), 2(c 0 + c 1 )(h + k) -c 0 (h + 1) -c 1 h -c 1 , c 1 .

104| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE

Then there exists a copy of T k in M + ( H) ∩ N -(v) ∩ B i-1 , say T k . Note that by construction, we have all arcs from H to T k , from T k to v and from v to H. Then ∆( H, T k , v) forms a copy of ∆(H, T k , T 1 ), a contradiction.

The proof of (b) for r is similar but not symmetric. In order to obtain a copy of ∆(H, T k , T 1 ), we first get a copy of T k in B i+r , and then a copy of H in B i+1 . This proves the claim.

We next prove a stronger statement that every bag has few backward arcs with the union of all other bags proceeding or succeeding it. Let B i,j = j s=i B s for any 1 i j t (if i < 1 or j > t or j < i, we set B i,j = ∅).

CLAIM 7.19

For every i and v ∈ B i ,

• χ(N + (v) ∩ B 1,i-2 ) c 1 , and • χ(N -(v) ∩ B i+2,t )) c 1 .
Proof. We repeat the same argument as in the proof of Claim 7.18. Suppose for a contradiction that the first statement is false, i.e., there is v in some B i such that χ(N + (v) ∩ B 1,i-2 ) c 1 . Then N + (v) ∩ B 1,i-2 has a copy of H, say H. For each x ∈ H, we have χ(N o (x) ∩ B i-1 ) c 0 by (7.1), and χ(N -(x) ∩ B i-1 ) c 1 by Claim 7.18. We also have χ(N o (v) ∩ B i-1 ) c 0 and χ(N + (v) ∩ B i-1 ) c 1 . Thus by the same computation as in Claim 7.18, we obtain a copy of T k in B i-1 and reach the contradiction. The proof of the second statement is similar. From Claim 7.19 we have the following immediate corollary.

CLAIM 7.20

For every i and v ∈ B i ,

• χ(N + (v) ∩ B 1,i-1 ) 2c 1 . • χ(N -(v) ∩ B i+1,t ) 2c 1 .
We now show that the union of all bags has bounded chromatic number. We note that in the following proof, we will use only two hypotheses: Claim 7.20 and that χ(B i ) is bounded for every i. The reason for our remark is that we will re-use the arguments of this proof for subsequent claims.

CLAIM 7.21

Proof. The former inequality is obvious by the partition criterion. For the latter, the proof follows the same idea as that of Claim 7.18, but is a bit more involved. Suppose for a contradiction that χ(N + (v) ∩ B i-r ) c 1 for some r 2. Then there is a copy of

H in N + (v) ∩ B i-r , say H. Since χ(N -(v) ∩ B i ) c 1 by partition criterion, there is a copy of T k in N -(v) ∩ B i , say T k .
Then by applying (7.3) we have

B i-1 = M + ( H) ∩ B i-1 ∪ N -( H) ∪ N o ( H) ∩ B i-1 , B i-1 = M -( T k ) ∩ B i-1 ∪ N + ( T k ) ∪ N o ( T k ) ∩ B i-1 , and B i-1 = N + (v) ∪ N -(v) ∩ B i-1 ∪ N o (v) ∩ B i-1 . Let R = M + ( H) ∩ M -( T k ) ∩ N + (v) ∪ N -(v) ∩ B i-1 . Then we have B i-1 = R ∪ N -( H) ∪ N o ( H) ∩ B i-1 ∪ ∪ N + ( T k ) ∪ N o ( T k ) ∩ B i-1 ∪ N o (v) ∩ B i-1 . For each x ∈ H ∪ T k ∪ {v}, we have χ(N o (x) ∩ B i-1 ) c 0 . By Claim 7.18, we have χ(N -(x) ∩ B i-1 ) c 1 for each x ∈ H and χ(N + (x) ∩ B i-1 ) c 1 for each x ∈ T k . Then χ(R) χ(B i-1 ) - ∑ x∈ H∪ T k ∪{v} χ(N o (x) ∩ B i-1 ) -∑ x∈ H χ(N -(x) ∩ B i-1 ) -∑ x∈ T k χ(N + (x) ∩ B i-1 ) 2(c 0 + c 1 )(h + k) -c 0 (h + k + 1) -c 1 h -c 1 k 2c 1 . Let R 1 = R ∩ N + (v) and R 2 = R ∩ N -(v). Note that R = R 1 ∪ R 2 , and so either χ(R 1 ) c 1 or χ(R 2 ) c 1 . If χ(R 1 ) c 1 , there is a copy of H in R 1 , say H . Then ∆( H , T k , v) forms a copy of ∆(H, T k , T 1 ), a contradiction. If χ(R 2 )
c 1 , there is a copy of T k in R 2 , say T k . Then ∆( H, T k , v) forms a copy of ∆(H, T k , T 1 ), a contradiction again. This proves the claim. While Claim 7.22 shows that every zone has few backward arcs with every sufficiently far bag. The next claim shows the converse, i.e., every bag has few backward arcs with every sufficiently far zone.

CLAIM 7.23

For every i and v ∈ B i ,

• χ(N + (v) ∩ Z i-r ) c 1 for every r 2, and • χ(N -(v) ∩ Z i+r ) c 1 for every r 3.

108| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE

Proof. We repeat the argument in the proof of Claim 7.18. Suppose for a contradiction that the first statement is false, i.e., there is v in some B i and r 2 such that χ(N + (v) ∩ Z i-r ) c 1 . Then N + (v) ∩ Z i-r has a copy of H, say H. For each x ∈ H, we have χ(N o (x) ∩ B i-1 ) c 0 by (7.1), and χ(N -(x) ∩ B i-1 ) c 1 by the first inequality in Claim 7.22. We also have χ(N o (v) ∩ B i-1 ) c 0 and χ(N + (v) ∩ B i-1 ) c 1 by definition of bag-chain. Thus by the same computation as in Claim 7.18, we obtain a copy of T k in B i-1 and reach the contradiction. The proof of the second statement is similar.

The next claim is a counterpart of Claim 7.20 for zones, and will be used to bound the chromatic number of the union of zones.

CLAIM 7.24

For every i and v ∈ Z i ,

• χ(N + (v) ∩ i-3 s=0 Z s ) c 1 , and • χ(N -(v) ∩ t s=i+3 Z s ) c 1 .
Proof. Suppose for a contradiction that χ(N + (v) ∩ i-3 s=0 Z s ) c 1 , then there is a copy of H in N + (v) ∩ i-3 s=0 Z s , say H. For each x ∈ H, we have χ(N o (x) ∩ B i-2 ) c 0 by (7.1), and χ(N -(x) ∩ B i-2 ) c 1 by the first inequality in Claim 7.22. We also have χ(N o (v) ∩ B i-2 ) c 0 and χ(N + (v) ∩ B i-2 ) c 1 by the second inequality in Claim 7.22. Thus by the same computation as in Claim 7.18, we obtain that

χ(M + ( H) ∩ N -(v) ∩ B i-2 ) c 1 implying that there is a copy of T k in M + ( H) ∩ N -(v) ∩ B i-2
, reaching a contradiction. The proof of the second statement is similar, where we use B i+1 instead of B i-2 .

In order to bound the chromatic number of the union of zones, we also need that each zone has bounded chromatic number. We will prove this by employing the assumption that the bag-chain B 1 , ..., B t is of maximum length.

CLAIM 7.25

No zone Z i contains a bag-chain of length 6.

Proof. Suppose that some Z i contains a bag-chain of length 6, say Y 1 , ..., Y 6 . Note that we have

• χ(N + (v) ∩ B i-3 ) c 1 for every v ∈ Y 1 by Claim 7.22 and χ(N -(v) ∩ Y 1 ) c 1
for every v ∈ B i-3 by Claim 7.23; and

Proof. Let K be the tournament of J ⇒ J ⇒ ... ⇒ J (2c 1 + 2 times J). Since J is a superhero, then so is K by Theorem 7.8. Hence there is d 1 such that every α-dense K-free digraph D has chromatic number at most d 1 . Suppose that U contains a copy of K, say K. Since every ball is either red or blue, we can find c 1 + 1 vertex-disjoint monochromatic balls J 1 , ..., J c 1 in K such that J i has complete arcs to J j for every i < j.

Then either vertices of J 1 are blue or vertices of J c 1 +1 are red, a contradiction with the fact that all vertices of U are uncolored. Hence U is K-free, and so χ(U) d 1 .

It remains to show that R and B have bounded chromatic number, which can be done by applying Theorems 6.14. To do so, we need to prove that N + (v) has bounded chromatic number for every v ∈ R.

CLAIM 7.30

There is d 2 such that χ(N + (v)) d 2 for every v ∈ R.

Proof. Fix v ∈ R. Then there are vertex-disjoint red balls J 1 , ..., J c 1 +1 where v ∈ J c 1 +1 and J i has complete arcs to J j for every i < j. Let L = c 1 i=1 J 1 . Note that v is seen by all vertices of L. For every u ∈ L, we have χ

(N + (v) ∩ N o (u)) c 0 . Hence χ(N + (v) ∩ N o (L)) ∑ u∈L χ(N + (v) ∩ N o (u)) |L|c 0 .
For every partition of L into L 1 , L 2 (L 1 or L 2 may be empty), let

Y L 1 ,L 2 = N + (v) ∩ M -(L 1 ) ∩ M + (L 2 ). Observe that for every vertex x ∈ N + (v)\N o (L) (note that x / ∈ L since v ∈ J c 1 +1
), there is a partition of L into some L 1 , L 2 such that x sees all vertices of L 1 and is seen by all vertices of L 2 , and so x ∈ Y L 1 ,L 2 . Hence

N + (v)\N o (L) = (L 1 ,L 2 ) Y L 1 ,L 2 . We now show that χ(Y L 1 ,L 2 ) d for every Y L 1 ,L 2 . • If, for some 1 i c 1 , there is J i ⊆ L 2 , recall that χ(M + ( J i )) d since J i is red. Since Y L 1 ,L 2 ⊆ M + (L 2 ) ⊆ M + ( J i ), we have that χ(Y L 1 ,L 2 ) d.
• Otherwise, if there is no J i ⊆ L 2 , then L 1 contains at least one vertex of each J i , 1 i c 1 , and so |L 1 | c 1 . Hence L 1 has a copy of T k , say T k . Note that all vertices of T k see

v since v ∈ J c 1 +1 . If χ(Y L 1 ,L 2 ) c 1 , then Y L 1 ,L 2 contains a copy of H, say H, then ∆( H, T k , v) forms a copy of ∆(H, T k , T 1 ), a contradiction. Hence χ(Y L 1 ,L 2 ) c 1 d.

112| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE

Note that |L| = |J|c 1 = (h + k)c 1 . Thus, there are 2 (h+k)c 1 possible ways to partition L into L 1 , L 2 . Hence

χ(N + (v)) χ N + (v) ∩ N o (L) + χ N + (v)\N o (L) |L|c 0 + ∑ (L 1 ,L 2 ) χ(Y L 1 ,L 2 ) (h + k)c 1 c 0 + 2 (h+k)c 1 d. Set d 2 := (h + k)c 1 c 0 + 2 (h+k)c 1 d. This completes the proof of the claim. Then χ(N + (v) ∩ R) χ(N + (v)) d 2 for every v ∈ R.
Then by applying Theorem 6.14 for digraph R with t = d 2 , we have χ(R) d 3 for some d 3 .

We now prove that B has bounded chromatic number. The proof is slightly different from that of Claim 7.30 due to asymmetry of ∆(H, T k , T 1 ).

CLAIM 7.31

There is d 4 such that χ(N -(v)) d 4 for every v ∈ B.

Proof. Fix v ∈ B. Then there are vertex-disjoint blues balls J 1 , ..., J c 1 +1 where v ∈ J 1 and J i has complete arcs to J j for every i < j. Let L = c 1 +1 i=2 J i . Note that v sees all vertices of L. For every u ∈ L, we have

χ(N -(v) ∩ N o (L)) ∑ u∈L χ(N -(v) ∩ N o (u)) |L|c 0 . For every partition of L into L 1 , L 2 (L 1 or L 2 may be empty), let Y L 1 ,L 2 = N -(v) ∩ M -(L 1 ) ∩ M + (L 2 ). Observe that for every vertex x ∈ N -(v)\N o (L) (note that x / ∈ L since v ∈ J 1 )
, there is a partition of L into some L 1 , L 2 such that x sees all vertices of L 1 and is seen by all vertices of L 2 , and so

x ∈ Y L 1 ,L 2 . Hence N -(v)\N o (L) = (L 1 ,L 2 ) Y L 1 ,L 2 . We now show that χ(Y L 1 ,L 2 ) d for every Y L 1 ,L 2 . • If there is J i ⊆ L 2 , then J i contains a copy of H, say H. Note that v is in the first ball, so v sees all vertices of H. If χ(Y L 1 ,L 2 ) c 1 , then Y L 1 ,L 2 contains a copy of T k , say T k , then ∆( H, T k , v) forms a copy of ∆(H, T k , T 1 ), a contradiction. Hence χ(Y L 1 ,L 2 ) c 1 d. • If J c 1 +1 ⊆ L 1 , recall that χ(M -( J c 1 +1 )) d since J c 1 +1 is blue. Since Y L 1 ,L 2 ⊆ M -(L 1 ) ⊆ M -( J c 1 +1 ), we have that χ(Y L 1 ,L 2 ) d.
• Otherwise, we have two remarks:

(i) J c 1 +1 must have a vertex in L 2 , say z, and

(ii) (2) Every J i , 2 i c 1 must have a vertex in L 1 .
Then |L 1 ∪ {v}| c 1 , and so L 1 ∪ {v} contains a copy of T k , say T k , such that all vertices of T k are in one of the J i , 1 i c 1 (note that v ∈ J 1 ). Observe that z is seen by all vertices of T k since z

∈ J c 1 +1 . If χ(Y L 1 ,L 2 ) c 1 , then Y L 1 ,L 2 contains a copy of H, say H , then ∆( H , T k , z) forms a copy of ∆(H, T k , T 1 ), a contradiction. Hence χ(Y L 1 ,L 2 ) c 1 d.
Hence using a computation similar to the claim above, we have

χ(N -(v)) d 4 , where d 4 := (h + k)c 1 c 0 + 2 (h+k)c 1 d. This completes the proof of the claim. Then χ(N -(v) ∩ B) χ(N -(v)) d 4 for every v ∈ B.
Then by applying Theorem 6.18 to the digraph B with t = d 4 , we have χ(B) d 5 for some d 5 . Hence

χ(D) χ(B) + χ(R) + χ(U) d 1 + d 3 + d 5 .
This completes the proof of Lemma 7.27.

We are now ready to prove Lemma 7.26.

CLAIM 7.32

If an α-dense ∆(H, T k , T 1 )-free digraph D contains no c-bag-chain of length 6, then χ(D) g(g(g(c))) where g is the function in Lemma 7.27.

Proof. Suppose for a contradiction that χ(Z i ) g(g(g(c))). We will show that D contains a c-bag-chain of length 8. By applying Lemma 7.27 to D with d := g(g(c)), we have that D contains a g(g(c))-bag-chain of length two, say X 1 , X 2 . Hence χ(X 1 ) = χ(X 2 ) = g(g(c)) and

• χ(N + (v) ∩ X 1 ) c 1 for every v ∈ X 2 , and • χ(N -(v) ∩ X 2 ) c 1 for every v ∈ X 1 .
Apply Lemma 7.27 again to X 1 (res. X 2 ) with d := g(c), we obtain a g(c)-bag-

chain of length two, say Y 1 , Y 2 in X 1 (res. Y 3 , Y 4 in X 2 ). Since Y 2 ⊂ X 1 and Y 3 ⊂ X 2 , we have • χ(N + (v) ∩ Y 2 ) c 1 for every v ∈ Y 3 , and • χ(N -(v) ∩ Y 3 ) c 1 for every v ∈ Y 2 .

114| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE

Hence by definition, Y 1 , ..., Y 4 forms a g(c)-bag-chain of length 4. Note that χ(Y s ) = g(c) for every 1 s 4. Repeating the argument we obtain a c-bag-chain of length 2 inside each Y s , and hence obtain a c-bag-chain B 1 , ..., B 8 of length 8 inside D. This contradicts the fact that D has no c-bag-chain of length 6, and so completes the proof. Claim 7.32 proves Lemma 7.26, concluding the proof of Theorem 7.16.

Chapter 8

Dense Triangle-Free Digraphs

Coloring triangle-free digraphs

This chapter is devoted to investigate a special case, where the pattern is the directed triangle C 3 . The aim of this chapter is to present a potential direction to prove that C 3 has the general Erdős-Hajnal property (recall that no nontrivial pattern, even C 3 , is known to have the general property). We believe that the following conjecture, which is a stronger statement than the general property of C 3 , is true.

CONJECTURE 8.1

There is an integer such that for every positive integer α, if D is an α-dense C 3 -free digraph, then D can be properly colored by α colors. Indeed, if Conjecture 8.1 is true, then every C 3 -free digraph D either has a stable (hence, acyclic) set of size n 1/2 or can be colored by (n 1/2 ) = √ n colors, and hence has an acyclic set of size n/ √ n = √ n. Thus C 3 has the general Erdős-Hajnal property.

While targeting a polynomial bound for the number of colors in Conjecture 8.1, we could not even achieve an exponential bound. However, by an algorithmic approach, we are able to obtain a factorial bound, and the coloring process can be done in polynomial time.

The content of this chapter is covered in parts of papers Coloring dense digraphs, Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, and Stéphan Thomassé, Combinatorica, to appear, and Domination and fractional domination in digraphs, Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, and Stéphan Thomassé, Electronic Journal of Combinatorics, to appear.

THEOREM 8.2

For every positive integer α, if D is an α-dense C 3 -free digraph, then D can be properly colored by 35 α-1 α! colors, and such a coloring can be found in polynomial time.

In this section, we prove Theorem 8.2. We present an efficient algorithm to color every α-dense C 3 -free digraph with at most 35 α-1 α! colors. For a digraph D, let n = |V(D)| denote the size of its vertex set. Let poly(n) denote the function n k for some rational number k > 0.

For each integer α 1, define h(α) to be the minimum number such that every α-dense C 3 -free digraph D has chromatic number at most h(α). Conjecture 8.1 asserts that h(α) α for some . Clearly h(1) = 1 since every C 3 -free tournament is acyclic. However, h(α) is still unknown for all α 2. We believe that h(2) = 2 or 3 even though the best bound we have is h(2) 18 (by tweaking the proof of Theorem 8.2). Theorem 8.2 gives an factorial upper bound for h(α) by the function g(α) := 35 α-1 α!. Since our proof of Theorem 8.2 will use induction, we will assume that every (α -1)dense C 3 -free digraph can be colored with at most 35 α-2 (α -1)! colors. This is true for α = 1, and we will prove it for α > 1 by induction.

We begin with some observations regarding the size of a dominating set in a digraph.

PROPOSITION 8.3

A digraph D has an acyclic dominating set, and this set can be found in time poly(n).

Proof. We proceed by induction on n. The statement clearly holds for n = 1. For n > 1, pick an arbitrary vertex v. Then V(D) We now show that Y is a set with the desired properties. Suppose for a contradiction that there is v / ∈ Y ∪ N o (Y) ∪ N + (Y). Then Y ⊆ N + (v) and v / ∈ S since Y dominates all vertices of S. There is u ∈ S seeing v since S is a dominating set of D. Note that u / ∈ Y; otherwise this contradicts Y ⊆ N + (v). There is y ∈ Y seeing u since Y is a dominating set of S. Then u, v, y are distinct vertices where u sees v, v sees y, and y sees u. Hence we obtain a copy of C 3 in D, a contradiction.

\ v = N o (v) ∪ N -(v) ∪ N + (v)
We now present some definitions and useful lemmas. First, we re-define a bag so that it inherits all properties of a bag as defined in Section 7.3 and so that it can be tested efficiently.

DEFINITION 8.5

For a digraph D, we say that B ⊆ V(D) is a bag of D, if every three distinct vertices {x, y, z} ∈ V(D) \ B have a common neighbor in B.

Recall that u and v are neighbors if either uv or vu is an arc. We can check in poly(n) time (e.g. O(n 4 )) whether or not a set B is a bag of D by exhaustively checking all triples in V(D) \ B. Suppose that the n vertices of a digraph can be partitioned into disjoint sets such that the subgraph induced on each set is (α -1)-dense. Let time(α -1, n) denote the maximum (over all such possible partitions of the vertices) total time required by our algorithm (the algorithm COLOR-DIGRAPH, which we will define shortly) to color all of the subgraphs, each with at most 35 α-2 (α -1)! colors by induction. The following claim follows from this definition.

CLAIM 8.6

Suppose ∑ i=1 n i = n, where n i 1 is an integer. Then ∑ i=1 time(α, n i ) time(α, n).

We now fix an arbitrary α-dense C 3 -free digraph D, and we omit the subscript D from the relevant notation when the context is clear. To simplify, let us set β = 35 α-2 (α -1)!.

CLAIM 8.7

If S ⊂ V(D) is not a bag of D, then: (a) We can partition S into three disjoint sets, S 1 , S 2 and S 3 , each is (α -1)dense. This procedure takes time poly(n).

(b) We can color S with 3β colors in time time(α -1, |S|).

118| DENSE TRIANGLE-FREE DIGRAPHS

Proof. If S is not a bag of D, then we can, in time poly(n), find a triple {x, y, z} ∈ V(D) \ S such that every v ∈ S is not incident to at least one of x, y or z. Thus, each vertex v ∈ S belongs to either N o (x) ∩ S, N o (y) ∩ S or N o (z) ∩ S. Each of these sets is (α -1)-dense. The total time for this procedure is poly(n). The second assertion follows from the (a) and from the definition of the function time(α, n). For v ∈ Y R , note that N + (v) ∩ R is not a bag, and so by (a) from Claim 8.7, we can partition N + (v) ∩ R into three (α -1)-dense sets. Additionally, we have the set N o (v) ∩ R is also (α -1)-dense. Overall, we can partition R \ Y R into 4α sets, each is (α -1)dense. In general, we do not know how to color a bag efficiently, and a bag may be very large (e.g. V(D) is a bag). Our aim is therefore to find poor bags, since these can be colored using Claim 8.9. The first step of our algorithm is to find a chain of poor bags.

DEFINITION 8.10

Observe that each v ∈ B \ C is either (i) some v i in the output sequence returned by FIND-CHAIN(D, B), or (ii) belongs to N o (v i ) for some v i in this output sequence. For any v ∈ V(D), the set N o (v) is (α -1)-dense. Therefore, the vertices in t-1 i=1 N o (v i ) can be colored with (t -1)β colors. Note that v i can be colored with an arbitrary color from the color palette used for N o (v i ). This coloring can be found in time poly(n) + time(α -1, |B \ C|).

COROLLARY 8.14

Either FIND-CHAIN(D, B) returns a chain of t poor bags, or B can be colored using 8αβ + (t -2) • β colors.

We now have the tools to outline our main coloring algorithm.

COLOR-DIGRAPH(D)

If D is acyclic, color D with one color and terminate. Proof. If V(D) is a poor bag, then we can apply Claim 8.9. Hence we may suppose that V(D) is not a poor bag.

Note that the updated chain C resulting from Step 3 (a) is still a chain of poor bags, due to properties (b) and (c) from Claim 8.11. After Step 3 finishes, the chain C is maximal in that the procedure FIND-CHAIN(D, Z i ) will not find a chain of three poor bags in any zone Z i . Using Corollary 8.14, we can therefore color each zone 122| DENSE TRIANGLE-FREE DIGRAPHS using (8α + 1)β colors. Applying property (d) from Claim 8.11, we can use at most (24α + 3) • β colors to color all vertices in V(D) \ C. Each bag B i in the chain C is a poor bag, so we can color B i with 8αβ colors by Claim 8.9. Moreover, since B i → B j for every i < j (by property (a) from Claim 8.11), we need 8αβ colors to color the entire chain C. Thus, we can color D with (32α + 3)β 35αβ colors.

CLAIM 8.16

The procedure COLOR-DIGRAPH(D) uses 35 α-1 α! colors.

Proof. We proceed by induction on α. If α = 1, then we use one color, since every C 3 -free tournament is acyclic. Suppose that the algorithms colors each (α - Proof. We now analyze the running time. Finding a maximal chain C takes poly(n) time, as does the procedure of partitioning the vertices in V(D) \ C into zones. Once we have found this partitioning, we can color the vertices in C in time poly(n) + time(α -1, |C|) using Claim 8.9, and we can color each zone Z i in time poly(n) + (α -1, |Z i |) using Claim 8.13 and Corollary 8.14. So applying Claim 8.6, the total running time of COLOR-DIGRAPH(D) is at most poly(n) + time(α -1, n). This leads to the following recurrence relation:

time(α, n) = poly(n) + time(α -1, n) = α • poly(n).
Since α n, we have that time(α, n) = poly(n).

We note that our algorithm is actually just partitioning V(D) into disjoint (α -1)dense subsets. In other words, it first partitions the vertices in V(D) into sets where each set is a poor bag or not a bag (for example, a zone Z i is either a poor bag or not a bag). Then, it further partitions these sets into (α -1)-dense sets. (For example, by Claim 8.7, a set that is not a bag can be partitioned into three disjoint sets, each is (α -1)-dense. Similarly, in the proof of Claim 8.9, a poor bag is partitioned into 8α disjoint sets, each is (α -1)-dense.) Once the subgraphs on these induced subsets are colored (recursively) using β colors, then certain subsets are allowed to use the same color palette, and these color palettes can be coordinated in time poly(n). The initial partitioning procedure and the final coordinating procedure require poly(n) time, while the recursive coloring requires time(α -1, n) time.

DOMINATION IN TRIANGLE-FREE DIGRAPHS | 123

Theorem 8.2 follows from Claims 8.15, 8.16 and 8.17.

Finally, we remark that Theorem 8.2 yields a bound on the size of a maximum acyclic subgraph of α-dense C 3 -free digraphs.

|A| 2 + n 4 • 35 α-1 α! n α • 35 α-1 α! -1 .
Let c be an absolute constant. Then

c α = 1 c • α • (35 α-1 α!) 2
satisfies the theorem.

Domination in triangle-free digraphs

Before concluding this thesis, we will discuss briefly about dominating sets in dense C 3 -free digraphs. As we shown through previous chapters, there is a tight bond between domination and coloring in digraphs. Another example is that for any α-dense digraph D, we have γ(D) αχ(D), which follows from the fact that in a proper coloring, each color class forms an induced acyclic digraph and every acyclic digraph has a stable dominating set (by Proposition 6.16). Thus, combining with Theorem 8.2, we have that α-dense C 3 -free digraph D has the domination number at most α35 α-1 α!. However, a better bound can be achieved, where 35 α-1 is dropped.

THEOREM 8.19

For every positive integer α and any α-dense C 3 -free digraph D, we have γ(D) αα!.

124| DENSE TRIANGLE-FREE DIGRAPHS

For small cases, we can provide better bounds, for example, the tight bound γ(D)

3 when α = 2, or γ(D) 8 when α = 3. Similar to Conjecture 8.1, we also believe that a polynomial bound for the size of dominating sets in dense C 3 -free digraphs.

CONJECTURE 8.20

There is an integer such that for every positive integer α, if D is an α-dense C 3 -free digraph, then D has a dominating set of size α .

We now prove Theorem 8.19.

Proof of Theorem 8.19. Let h(1) = 1 and h(k) = k • (h(k -1) + 1) for every k > 1. We proceed by induction on α that γ(D) h(α). If α = 1, then D is a C 3 -free tournament, and so D is acyclic. Then there is a vertex that dominates V(D). So h(1) = 1.

If α > 1, we first apply Proposition 8.3 to find an acyclic dominating set A of D. Then we apply Proposition 6.16 to find a dominating set S ⊆ A of A. Note that |S| α since S is stable. Let Y denote the set of vertices in V(D) \ A that are not dominated by any vertex in S.

We observe that each vertex y ∈ Y belongs to N o (s) for some s ∈ S. Suppose this were not the case. Then a vertex y ∈ Y has arcs to all s ∈ S. Since A dominates V, there is some a ∈ A \ S such that ay ∈ E(D). Since S dominates A, there is s ∈ S such that sa ∈ E(D). This yields the triangle ysa, which is a contradiction to D being C 3free. Hence, for every y ∈ Y, there is s ∈ S such that ys / ∈ E(D). By the definition of Y, it follows that sy / ∈ E(D). We conclude that s and y are independent and therefore y ∈ N o (s).

We partition Y into |S| subsets, where for each s ∈ S, Y s is a subset of N o (s). Observe that Y = s∈S Y s is dominated by s∈S B s , and V \ Y is dominated by S by definition of Y. Thus, B is a dominating set of D, which proves the theorem.

Conclusion

Throughout the thesis, we have studied the relation between patterns and large graphs. Let us sum up the results and propose some directions for further work.

In Part I, we discussed about the sufficient conditions so that a large graph can be decomposed into copies of a given pattern. In Chapter 2, we proved the Bárat-Thomassen conjecture that every highly edge-connected graph can be decomposed into copies of a given tree. We provided a large exponential upper bound on the edge-connectivity which holds for all patterns. One direction for future work could be improving this general bound, or bounds for specific patterns. Another idea could be finding some lower bounds on the edge-connectivity for specific patterns. For example, we showed in Chapter 3 that when the pattern is P 9 , the bound on the edgeconnectivity must be at least 3. These lower bounds could give insight to the true sharp bound of the Barát-Thomassen conjecture.

One could also investigate a counterpart of the Barát-Thomassen conjecture for patterns which are not a tree (i.e. containing a cycle). There are numerous works on that topic, mainly focusing on the cases where the pattern is a cycle or a complete graph, for example, [START_REF] Richard M Wilson | Decompositions of complete graphs into subgraphs isomorphic to a given graph[END_REF][START_REF] Barber | Edgedecompositions of graphs with high minimum degree[END_REF][START_REF] Bryant | Decomposing graphs of high minimum degree into 4-cycles[END_REF]. However, it is easy to notice that in this case, high edge-connectivity is not sufficient; the large graph needs to have small girth, too. Indeed, suppose that the pattern contains a cycle of length , then the large graph must contains many cycles of length as well.

In Chapter 3, we showed that when the pattern is a path, it is possible to replace the edge-connectivity condition in the Barát-Thomassen conjecture by a cheaper one -the minimum degree. Whether it is possible to improve the Barát-Thomassen conjecture when the pattern is a tree is still open.

In Chapter 4, we proved a conjecture by Häggkvist and Kriesell that every Eulerian graph with high minimum degree admits an -step self-avoiding Eulerian tour. Which immediately implies that every Eulerian graph with high minimum degree can be decomposed into copies of a given path, i.e. replacing the high edge-connectivity condition of the Barát-Thomassen conjecture by Eulerianity and high minimum degree. Oksimets [START_REF] Oksimets | Triangle-free eulerian tours in graphs with minimum degree at least 6[END_REF] showed that 6 is a sharp bound for = 3. Finding sharp 125 126| DENSE TRIANGLE-FREE DIGRAPHS bounds for other patterns could be a direction for future work.

In Chapter 5, we proved Jaeger-Linial-Payan-Tarsi's conjecture on additive bases in the case the vectors has support at most 2. This results implies several results on flows and orientations in graphs. Improving the bound on the number of bases will subsequently improve the bound on the edge-connectivity condition of its corollaries on flows and orientations in graphs. Since a vector of support 2 can be mapped into an edge, a result similar where vectors have support at most 3 could imply similar corollaries for hypergraphs with edge size at most 3. A general result without bounded support size would give results on flows and orientations in general hypergraphs.

Part II was dedicated to the tournament version of the Erdős-Hajnal conjecture. In Chapter 6, we proved a conjecture of Berger et al that if a tournament is nowhere locally colorful, then it is not globally colorful. It is natural to ask the reverse question: If a large tournament is colorful, is it true that it is locally colorful somewhere, i.e. can we say that it must contain a small but colorful subtournament? This turns out to be false; an counterexample could be found at [START_REF] Harutyunyan | Coloring tournaments: from local to global[END_REF]. In [START_REF] Harutyunyan | Coloring tournaments: from local to global[END_REF], we indeed presented a stronger result that the size of local domination sets dictates the global colorfulness of a tournament. This again shows the close tie between domination and coloring in graphs. Hence, it is natural to ask whether the size of local domination sets dictates the size of the global domination set. This question is still open.

In Chapter 7, we discussed the general Erdős-Hajnal conjecture on digraphs and extended the result of Berger et al [BCC + 13] to dense digraphs, and discussed in detail the case where the pattern is the directed-triangle in Chapter 8. An imminent direction for future work could be proving the general Erdős-Hajnal conjecture for some small patterns, such as the directed-triangle. Another idea could be replacing the dense condition by some weaker ones, such as high average degree or high minimum degree.

  (a) Can G be partitioned into copies of H? (b) If G does not contain any copy of H, which properties does G have? These questions are closely linked to some of the most important conjectures in Graph 4| INTRODUCTION Theory: the Tutte's flow conjectures on flows in graphs and the Erdős-Hajnal conjecture mentioned above.

FIGURE 1 . 2 -

 12 FIGURE 1.2 -The two figures in the left and right are isomorphic. Both of them are the cycle of length 5 C 5 .

CONJECTURE 2 . 2 CONJECTURE 2 . 3

 2223 Tutte's 3-flow Conjecture Every 4-edge-connected graph admits a 3-flow. Tutte's 5-flow Conjecture Every 2-edge-connected graph admits a 5-flow.

Figure 2 .

 2 1 shows a C 5 -decomposition of the complete graph K 5 .

2. 2 FIGURE 2 . 1 -

 221 FIGURE 2.1 -A decomposition of a the complete graph K 5 into two copies of C 5 .

FIGURE 3 . 1 -

 31 FIGURE 3.1 -Part of the construction for obtaining 2-edge-connected graphs with arbitrarily large minimum degree but no P 9 -decomposition.

  (i) |S v (e)| 1 2 d(v) -1 when d(v) ≡ 0(mod 4) or d(v) = 2, and (ii) |S v (e)| 1 2 d(v) -2, otherwise.

FIGURE 6 . 2 -

 62 FIGURE 6.2 -Left: the tournament C 3 ⇒ C 3 , and right: the tournament ∆(C 3 , T 2 , T 1 ).

THEOREM 6 .

 6 9 [BCC + 13]

7. 1

 1 THE ERDŐS-HAJNAL PROPERTY IN DIGRAPHS | 95 THEOREM 7.5

LEMMA 7 .. 11 Fix α 2

 7112 10 [BCC + 13], Lemma 3.3 Every r-mountain has chromatic number at least r, and has at most (r!) 2 vertices. Fix two superheroes H 1 and H 2 . 98| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE LEMMA 7and r, s 1, suppose that there are b 0 , b 1 , b 2 such that • Every (α -1)-dense (H 1 ⇒ H 2 )-free digraph D has χ(D) < b 0 . • Every α-dense (H 1 ⇒ H 2 )-free digraph D containing no (r, s)-clique has χ(D) < b 1 .

Set b 5 := b 4 +

 54 |H 1 |(b 0 + b 2 ). We have just shown that if χ(N -) b 4 , then χ(N + ) b 5 . Hence either χ(N -) b 4 b 5 or χ(N + ) b 5 . This proves the claim.

  Then applying Theorem 6.14 to R with t = b 5 + b 1 , there is b 6 such that χ(R) b 6 . Similarly, by Theorem 6.18, there is b 7 such that χ(B) b 7 . Hence χ(D) χ(R) + χ(B) b 6 + b 7 . Setting b 3 := b 6 + b 7 completes the proof of Lemma 7.11.

. 4

 4 Applying induction to the subgraph, D[N o (v) ∪ N -(v)], we obtain an acyclic dominating set S . Then S := S ∪ {v} is a dominating set of D. Note that S ⊆ N o (v) ∪ N -(v), so v does not see any vertex of S . Hence S is an acyclic set since S is an acyclic set. The running time for this procedure is poly(n).PROPOSITION 8Given an α-denseC 3 -free digraph D, there is a set Y ⊆ V(D) of size at most α such that V(D) = Y ∪ N o (Y) ∪ N + (Y),and this set can be found in time poly(n). Proof. First apply Proposition 8.3 to obtain an acyclic dominating set S of D. Then apply Proposition 6.16 to D[S] to obtain a stable dominating set Y of D[S] of size at most α(D) in time poly(n).

DEFINITION 8. 8 A

 8 bag B ⊆ V(D) is poor if for every vertex v ∈ B, either N -(v) ∩ B or N + (v) ∩ B is not a bag of D.We can check in poly(n) time (e.g. O(n 5 )) if a bag B is poor by testing whether or not N -(v) ∩ B and N + (v) ∩ B are bags for every v ∈ B.CLAIM 8.9If B ⊆ V(D) is a poor bag, then we can color B with 8αβ colors in time poly(n) + time(α -1, |B|).

  Proof. Since B is poor, then for each v ∈ B, eitherN -(v) ∩ B or N + (v) ∩ B is not a bag of D.Then we can partition B into two sets, L and R, where N -(v) ∩ B is not a bag for every v ∈ L, and N + (v) ∩ B is not a bag for every v ∈ R.Applying Proposition 8.4 to R, we can find a set Y R ⊆ R such that |Y R | α and R ⊆ Y R ∪ N + (Y R ) ∪ N o (Y R ).And so: R = v∈Y R N + (v) ∪ N o (v) ∪ {v} ∩ R .

  Similarly, one can find a set Y L ⊆ L such that |Y L | α and L \ Y L can be partitioned into 4α(α -1)-dense sets. Therefore, in time poly(n), we can partition B \ Y R ∪ Y L , and in time time(α -1, |B|) we can color B \ {Y r ∪ Y L } with 8αβ colors. We can then color each v ∈ Y R (respectively, v ∈ Y L ) with an arbitrary color used to color the set N o (v) ∩ R (respectively, N o (v) ∩ L).

  Run FIND-CHAIN(D, V(D)) and let C := {B 1 , . . . , B t } denote the chain of poor bags that it outputs. (ii) Assign each vertex in V(D) \ C to a zone Z i for i ∈ [0, t]. (iii) While FIND-CHAIN(D, Z i ) returns a chain of poor bags B 1 , B 2 , . . . , B k for k 3: (i) Update chain: C := {B 1 , . . . , B i-2 , B 1 , B 2 , . . . , B k , B i+1 , . . . , B t }.(ii) Re-assign each vertex in V(D) \ C to a zone. (iv) Color all vertices in the chain C with 8αβ colors. (v) Color all vertices in the zones of C with 3(8α + 1)β colors. CLAIM 8.15 COLOR-DIGRAPH(D) colors D with at most 35α • β colors.

  1)-dense C 3 -free digraph D using at most β colors. Then by Claim 8.15, the procedure COLOR-DIGRAPH(D) colors D with at most 35αβ = 35α • 35 α-2 (α -1)! = 35 α-1 α! colors. CLAIM 8.17 COLOR-DIGRAPH(D) runs in time poly(n).

THEOREM 8. 18

 18 Let D = (V, A) be an α-dense C 3 -free digraph. Then D contains an acyclic subset of arcs, A ⊆ A, with cardinality|A | |A| • ( 1 2 + c α ), where c α is a constant depending on α.Proof. Since D can be colored with 35 α-1 α! colors, there is a color class contains at least n 35 α-1 α! vertices, and by Turan's Theorem, its induced subgraph contains at leastn 2 • 35 α-1 α! n α • 35 α-1 α! -1arcs. Thus, D contains a maximum acyclic subgraph of size at least

  Note that D[N o (s)] is (α -1)-dense, then so is D[Y s ]. By the induction hypothesis, there is a set B s of size at most h(α -1) dominating Y s . Let B = S ∪ s∈S B s . Then |B| |S| + |S| • h(α -1) h(α) < αα!.

there are at least (1 -δm)d H (v|t) pseudo-copies of T in N H (v|t) that inter- sect H only in v. Since d H (v|t)

  2 n) .

	Proof of Lemma 2.18: Consider a pseudo-tree H ∈ N H (v|t), and let u ∈ V(H) \ {v}.
	Since conf(H |t)	δ, there are no more than δd H (v|t) trees in N H (v|t) containing
	u. Thus, εd H (v|t), we can associate a set S(H) of 1-δm ε pseudo-copies in N H (v|t) with each H ∈ N H (v|t) such that each element of N H (v|t)
	is contained in at most one of these sets. We define the function f t by choosing f t (H)
	uniformly at random from one of the pseudo-trees in S(H). Clearly, any such func-
	tion will satisfy the first two conditions of Lemma 2.18. All that remains to show is
	that with positive probability d f t (H) (v|t )	3εd H (v|t ) holds for every compatible
	v

  ) . 28| THE BARÁT-THOMASSEN CONJECTURE Let A v,t be the event that d f t (H) (v|t ) > 3εd H (v|t ). Note that d f t (H) (v|t ) is completely determined by at most d H (v|t ) independent trials. Since the outcome of each trial can affect d f t (H) (v|t ) by at most 1, the Simple Concentration Bound gives

  2, we need some notions about Eulerian graphs, which we will study in details in Chapter 4. We call P an Eulerian collection if H P is Eulerian. From an Eulerian tour in H P , we naturally get a corresponding Eulerian tour in P. Such a tour is non-conflicting if every two of its consecutive paths are non-conflicting. It was proved, under the following different terminology, by Jackson (cf. [Jac93], Theorem 6.3) that Eulerian collections with somewhat low conflicts have non-conflicting Eulerian tours.

  a copy of H 2 , say H 2 , and we have H 1 ⇒ H 2 forming a copy of H 1 ⇒ H 2 , a contradiction. Hence, χ(M + ( H 1

A bistar is a tree with diameter at most 3.

The diameter of a graph G is the maximum length of a path in G.

The content of this chapter is covered in paper Edge-partitioning a graph into paths: beyond the barátthomassen conjecture, Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, and Stéphan Thomassé, Combinatorica, pages 1-25, 2018.

This implies conf(P |F) 1/2( + 9), and the lemma follows.

A pattern created by "substituting" two patterns with the Erdős-Hajnal property also has the Erdős-Hajnal property; these pattern are not considered primitive. The definition of substitution of two graphs is beyond the scope of this thesis.

In liturature, an α-dense digraph is called a digraph with independence number at most α.

All these papers (except[START_REF] Le | Locally self-avoiding Eulerian tours[END_REF]) have not been accepted in whole, or in part, for any other degree or diploma of the author. A part of[START_REF] Le | Locally self-avoiding Eulerian tours[END_REF] appeared in his master report.

128| DENSE TRIANGLE-FREE DIGRAPHS

Acknowledgements v

Acknowledgements

Printed version only... v

Contributions

The results presented in this thesis are from: 1

Chapter 4

Decomposing Eulerian Graphs

Häggkvist and Kriesell's conjecture

In this chapter, we will investigate pattern-decompositions of large Eulerian graphs. Another equivalent definition of an Eulerian graph is that it is connected and the degree of all vertices are even, which is relatively cheap to achieved just by arbitrarily pairing odd-degree vertices and add an edge between each pair. Thank to the even-degree property, Eulerian graphs offers a significant advantage for both flows in graphs and path-decomposition, since the main task in these problems is pairing incident edges. That advantage is verified by the fact that a connected graph has a 2-flow if and only if it is Eulerian. Besides, the proof of Theorem 3.2 in Section 3.4 also employs some arguments on Eulerian graphs. In fact, it is not very hard to see that if the graph is Eulerian, then we can reduce the edge-connectivity to 4.

THEOREM 4.1

For every positive integer , there is an integer d such that every 4-edge-connected Eulerian graph G with minimum degree at least d and size divisible by admits a P -decomposition.

The proof of Theorem 4.1 will be presented in Section 4.3. It is natural to ask whether we can remove the 4-edge-connected condition, i.e, whether every Eulerian graph with high minimum degree and size divisible by admits a P -decomposition. It turns The content of this chapter is covered in paper Locally self-avoiding Eulerian tours, Tien-Nam Le, Journal of Combinatorial Theory, Series B, to appear, and in a part of paper Edge-partitioning a graph into paths: beyond the barát-thomassen conjecture, Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, and Stéphan Thomassé, Combinatorica, pages 1-25, 2018. subgraph (V, F) of G, there is an F-decomposition P of G satisfying:

• Every ray of P has length at most + 1.

• Every covered F-path of P has length at least .

• conf(P |F) 1/4( + 9).

Proof. Set L ,ε = max(L ,ε , 2 /ε), where L ,ε is the constant of Theorem 3.10. We call all edges of F = E\F dummy (note that a dummy edge may be a loop). The main idea is to replace every dummy edge by a pair of edges linking endpoints of the dummy edge to a big clique in order to obtain a simple graph to apply Theorem 3.10. For every dummy edge e = v e,1 v e,2 , we create a set of L ,ε + 1 new vertices X e = {x e,1 , ..., x e,L ,ε +1 }. Let E e = {x e,i x e,j : i = j} ∪ {v e,1 x e,1 , v e,2 x e,2 }. Let G be the multigraph with vertex set e∈F X e ∪ V and edge set E = e∈F E e ∪ F. It is immediate that G is simple and d G (v) = d G (v) for every v ∈ V, and so G has minimum degree at least L. Therefore G admits a decomposition P satisfying Theorem 3.10.

For every dummy edge e and every i = 1, 2, let P e,i be the path of P containing v e,i x e,i . We denote by P i,j the longest possible subwalk of P e,i such that P e,i = ...x e,i v e,i P e,i ... and all vertices of P e,i belong to V. If P e,i reach the end of P e,i , we call P e,i an end-segment; otherwise, we call it a middle-segment. The reader may see here the similarity between end-segments and rays. Clearly, if P e,i is a middle-segment, then P e,i = ...x e,i v e,i P e,i v e ,j x e ,j ... for some dummy edge e and j ∈ {1, 2} since P e,i leaves V right after finishing P e,i . Note also that the lengths of end-segments and middlesegments are at most + 1 and possibly 0.

For every dummy edge e and every i = 1, 2, we remove X e and E e , and concatenate P e,i with e at v e,i . After this process, we obtain a family of walks, in which each walk lies in one of the following types:

(1) An uncovered F-path P = P 1 e 1 P 2 ...e t-1 P t with dummy edges e 1 , ..., e t-1 , endsegments P 1 and P t , and middle-segments P 2 , ..., P t-1 . Note that the two endsegments are the rays of this uncovered F-path.

(2) A circuit without endpoint, consisting of middle-segments alternate with dummy edges but no end-segments.

Let P 1 be the set of all the walks of Type (1) together with all paths of P containing only vertices of V, and P 2 be the set of all circuits of Type (2). Note that P 1 is an Fcollection of G, and every edge of G belongs to exactly one F-path P 1 or one circuit of P 2 . The method of concatenating ensures that for every v ∈ V, the number of rays from v in P 1 is equal to number of paths with endpoint v in P . This gives We now turn our attention to the collection P 0 and the subcubic spanning tree H P 0 . Let us consider H P 0 as a tree rooted at an arbitrary vertex z. In the following claim, we collect two private F-paths in P 1 for each path in P 0 for the process of concatenating later on.

CLAIM 4.15

For every path P ∈ P 0 with endpoints say u, v where v is the parent of u in H P 0 , there are two F-paths of P 1 (v), named g 1 (P) and g 2 (P), such that their rays from v do not conflict with P (if g i (P) is closed, one of its rays satisfying that condition is sufficient). Furthermore, g i (P) = g j (P ) for any (i, P) = (j, P ).

Proof. We first apply Proposition 3.6 to have an orientation D of

This orientation yields a natural orientation of F-paths of P 1 . We denote by P + 1 (v|F) the set of rays from v of P leaving v with respect to D. Note that each closed F-path at v contributes with exactly one ray to P + 1 (v|F). This gives

Since H P 0 is subcubic, there are at most 3 paths of P 0 with endpoint v, say P s for 1 s 3. Note that each P s has length at most 2, and so they are incident with at most 6 vertices except v in total. Recall that conf P 1 (v|F) 1/4( + 9). For each vertex w among these 6 possible vertices, we have

Hence in total there are at most |P + 1 (v|F)|/2 rays of P + 1 (v|F) conflicting with some P s . This guarantees that there are at least half of rays in P + 1 (v) non-conflicting with all P s . We just pick 6 rays among them, and name the F-paths of these rays g i (P s ) arbitrarily (these F-paths are clearly pairwise distinct). Note also that P + 1 (v) ∩ P + 1 (v ) = ∅ for any v = v , so g i (P) = g j (P ) for any (i, P) = (j, P ).

We can now obtain the connectivity of H 1 by concatenating each P of P 0 to either g 1 (P) or g 2 (P). We again call a structured-tree T a rooted tree on vertex set {Y 1 , Y 2 , ..., Y t }, where {Y 1 , Y 2 , ..., Y t } is some partition of V with the following properties:

(A) For every edge Y i Y j of T , there is a corresponding path v i ...v j ∈ P 0 , where v i ∈ Y i and v j ∈ Y j .

(B) For every Y i , there is an F-collection R i such that H R i is connected and spans Y i , and each F-path in R i is either g 1 (P) or the concatenation of P and g 1 (P) for some P ∈ P 0 (if Y i contains a single vertex then R i is empty).

The final step is concatenating F-paths of P to obtain a well-behaved Eulerian tour of G, which can be done thank to Proposition 3.16.

Proof of Theorem 4.6. Let d = 100 L ,ε and G = (V, F). We first obtain an Fdecomposition P of G satisfying Lemma 4.14. For every ray P v|F of P, each vertex w ∈ P v|F is a conflict point between P v|F and at most d P (v)/2( + 9) other rays. Hence the number of rays conflicting with P v|F is at most ( + E of G by replacing every edge of E H P by its corresponding F-path of P. Note that every two consecutive (with respect to E ) rays of P are non-conflicting.

Let W be a segment of E of length at most and consisting of only edges of F. It remains to prove that W is a path. Let P 1 , P 2 ..., P r be consecutive (with respect to E ) F-paths of P such that W is a subwalk of P 1 P 2 ...P r and W ∩ P 1 , W ∩ P r = ∅. If r 3 then W must contain entirely P 2 . All edges of W belong to F, then so does P 2 . Hence P 2 is a covered F-path of length at most -2, contrary to the fact that every covered F-path of P has length at least . If r = 2, note that the rays from v of P 1 and P 2 are non-conflicting, and W is a subwalk of the concatenation of these two rays. Hence W is a path. If r = 1 then clearly W is a path, the desired conclusion.

Chapter 5 Additive Bases and Flows

Flows and weighted flows

In this final chapter of Part I, we will return to flows and discuss several results in flows, weighted flows and weighted orientations in graphs. All of them are derived from a special case of a conjecture by Jaeger, Linial, Payan and Tarsi [START_REF] Jaeger | Group connectivity of graphs-a nonhomogeneous analogue of nowhere-zero flow properties[END_REF]. Unlike previous chapters, graphs considered in this chapter may have multiple edges but no loops (i.e. multigraphs in previous chapters). As we mentioned before, the result 8-edge-connected graphs having a 3-flow by Thomassen [START_REF] Thomassen | The weak 3-flow conjecture and the weak circular flow conjecture[END_REF] was improved by [START_REF] Miklós | Nowhere-zero 3-flows and modulo k-orientations[END_REF] to 6-edge-connected graphs. In fact, in [START_REF] Miklós | Nowhere-zero 3-flows and modulo k-orientations[END_REF], they proved a more general result -Theorem 5.1, that edges of a highly edge-connected graph can be oriented so that any prescribed value modulo k at every vertex can be realized.

Recall that an orientation G = (V, E) of a graph G = (V, E) is obtained by giving each edge of E a direction. For each edge e ∈ E, we denote in this chapter the corresponding arc of E by e, and vice versa. For an integer p 2, a mapping

THEOREM 5.1 [LTWZ13]

For any k 1, any 6k-edge-connected graph G and any (2k + 1)-boundary β of G, the graph G has a β-orientation.

The content of this chapter is covered in paper Additive bases and flows in graphs, Louis Esperet, Rémi de Joannis de Verclos, Tien-Nam Le, and Stéphan Thomassé, SIAM Journal of Discrete Mathematics, 32:534-542, 2018.

THEOREM 5.4 [Dav35]

For any prime p, any multiset of p -1 non-zero elements of Z p forms an additive basis of Z p .

This result can be rephrased as: for n = 1, any family of p -1 linear bases of Z n p forms an additive basis of Z n p . A natural question is whether this can be extended to all integers n. Given a collection of sets X 1 , ..., X k , we denote by k i=1 X i the union with repetitions of X 1 , ..., X k . Jaeger, Linial, Payan and Tarsi [START_REF] Jaeger | Group connectivity of graphs-a nonhomogeneous analogue of nowhere-zero flow properties[END_REF] conjectured the following, which as we will see is a generalization of important results regarding flows in graphs.

CONJECTURE 5.5 [JLPT92]

For every prime number p, there is a constant c(p) such that for any t c(p) linear bases B 1 , ..., B t of Z n p , the union t s=1 B s forms an additive basis of Z n p .

Alon, Linial and Meshulam [START_REF] Alon | Additive bases of vector spaces over prime fields[END_REF] proved a weaker version of Conjecture 5.5, that the union of any p log n linear bases of Z n p contains an additive basis of Z n p (note that unlike Conjecture 5.5, their bound depends on n).

Let us call the support of a vector x = (x 1 , . . . , x n ) ∈ Z n p the set of indices i such that x i = 0, and the shadow of a vector x the (unordered) multiset of non-zero entries of x. Note that sizes of the support and of the shadow of a vector are equal. We will prove, as the main result in this chapter, that Conjecture 5.5 holds if the support of each vector has size at most two.

THEOREM 5.6

Let p 3 be a prime number. For some integer 1, consider t 8 (3p -4) + p -2 linear bases B 1 , ..., B t of Z n p , such that the support of each vector has size at most 2, and at most different shadows of size 2 appear among the vectors of B = t s=1 B s . Then B forms an additive basis of Z n p .

While Theorem 5.3, a generalization of Theorem 5.1, can be implied from Theorem Theorem 5.6, Theorem 5.6 will indeed be proved in using Theorem 5.1.

Corollaries on additive bases and flows

Corollaries on additive bases

Observe that the number of possibilities for an (unordered) multiset of Let C be a class of digraphs closed under taking subdigraphs. We say that C is tamed if for every integer k there exists K and such that every digraph T ∈ C with χ(T) K contains a set A of vertices such that χ(A) k. Note that a class of digraphs with bounded chromatic number is indeed tamed.

We proceed the proof of Theorem 6.14 by induction on α. The case α = 1 is Conjecture 6.10. The following lemma is analogous to Theorem 6.12. LEMMA 6.17

Suppose that Theorem 6.14 is true for α -1, i.e., f α-1 (t) exists for every t. For every t, the class of α-dense t-local digraphs is tamed.

We now can finish the proof of Theorem 6.14.

Proof of Theorem 6.14. Suppose that the theorem is true for α -1, i.e., f α-1 (t) exists for every t. We now show that it is true for α. Since the class of α-dense t-local digraphs is tamed, by applying tamed property for k = t + f α-1 (t) + 1, we have that there exist (K, ) such that every α-dense t-local digraph D χ(D) K contains a set A of vertices and χ(A) t + f α-1 (t) + 1. We claim that A is a dominating set. If not, then there is a vertex v such that A ⊆ N o (v) ∪ N + (v). Then χ(A) χ(N o (v)) + χ(N + (v)) t + f α-1 (t), a contradiction. Hence, A is a dominating set of D. Thus, χ(D) = χ( x∈A (N + (x) ∪ {x})) (t + 1)|A| = + t. Consequently, t-local digraphs have chromatic number at most f (t) := max(K, + t).

Proof. We fix some arbitrary t and show the property by induction on k. The claim is trivial for k = 1. Assuming now that (K, ) exists for k, we want to find (K , ) for k + 1. For this, we set s := K + f α-1 (t) + t and K := 2k(αs + 1)(t + f α-1 (t) + 1), and fix later.

Let D be an α-dense t-local digraph with vertex set V such that χ(D) K . Let B be a dominating set of D of minimum size b. By Proposition 6.15, we have

tb. In particular, b K /t 2k(αs + 1). Consider a subset W of B of size k(αs + 1). By Proposition 6.15, we have χ(N + (W))

kt(αs + 1). By induction hypothesis on α -1, for every x ∈ W, we have χ(N o (x))

for any X ⊆ D, the set of common in-neighbors of all vertices of X. Then we have,

Chapter 7

Generalizing the Erd ős-Hajnal conjecture

The Erd ős-Hajnal property in digraphs

Recall the Erdős-Hajnal conjecture that for every tournament H, there exists a constant ε(H) > 0 such that every H-free tournament T contains a transitive tournament with at least |V(T)| ε(H) vertices. Since the conjecture is confined in tournaments, it is natural to ask whether the result can be extended to general digraphs. This was in fact a conjecture by Harutyunyan and McDiarmid [HM12]. A set of vertices A in a digraph D is acyclic if the induced subgraph D[A] is acyclic.

DEFINITION 7.1

We say that a digraph H has the general Erdős-Hajnal property if there exists a constant ε(H) > 0 such that every H-free digraph D contains an acyclic set of size at least |V(D)| ε(H) . [START_REF] Harutyunyan | Large acyclic sets in oriented graphs[END_REF] conjectured that every digraph has the general Erdős-Hajnal property.

Harutyunyan and McDiarmid

CONJECTURE 7.2 [HM12]

Every digraph has the general Erdős-Hajnal property.

The content of this chapter is covered in paper Coloring dense digraphs, Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, and Stéphan Thomassé, Combinatorica, to appear.

Proof. An arc uv with u ∈ B j , v ∈ B i , and j > i is called a backarc with span ji. For every i and every

We have a formula similar to (7.4):

c 0 . Note also that from Claim 7.20, we have

contains a copy of H, say H. Then ∆( H, T k , v) forms a copy of ∆(H, T k , T 1 ), a contradiction. Hence

Then B i is a stable set in G for every i. We now (properly) color the vertices of G by c 1 colors as follows. First, color all B t properly by color 1. Suppose that we have already colored B i+1 , ..., B t . Every vertex v in B i is incident (in G) with at most c 1 -1 vertices in B i+1,t (those belonging to F v ) and independent (in G) with all other vertices in B i , so we can always properly color v, and so properly color B i . When the process of coloring ends, we obtain a partition of B 1,t into c 1 sets of colors, say X 1 , ..., X c 1 , where each X s is a stable set in G. We now claim that the chromatic number of the digraph induced by X s is small. 106| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE (B) χ(X s ) 8c for every 1 s c 1 .

To prove (B), we define a sequence of indices i 1 , i 2 , ... inductively as follows. Let i 1 = 1, and for every r 1, let i r+1 > i r be the smallest index such that χ(B i r ,i r+1 ) > 4c. The sequence ends by i with χ(B i ,t ) 4c (i.e. there is no i +1 satisfying the condition). Set A r := B i r ,i r+1 -1 for every 1 r -1 and A := B i ,t . Then B 1,t = r=1 A r , and by definition of the sequence, χ(B i r ,i r+1 -1 ) 4c for every 1 r -1. In other words, for every 1 r ,

Suppose that there is a backarc uv with u / ∈ F v and u ∈ A r , v ∈ A r , where r r + 2. Suppose that u ∈ B j and v ∈ B j . Then j i r since B j ⊆ A r = B i r ,i r+1 -1 , and j < i r +1 since B j ⊆ A r = B i r ,i r +1 -1 , and so j < i r-1 since r + 1 r -1. Also note that χ(B i r-1 ,i r ) > 4c by definition of the sequence. Thus we have

This implies the observation that for any r r + 2, there is no backarc uv with u ∈ A r , v ∈ A r and u / ∈ F v .

Now fix an arbitrary X s and let X s,r = X s ∩ A r for every 1 r . Observe that if uv is an backarc with u, v ∈ X s , then u / ∈ F v (otherwise, u ∈ F v , so uv ∈ G and so X s is not stable in G, a contradiction). Hence combining with the observation in the paragraph above, we have that there is no backarc from X s,r to X s,r for any r, r with r r + 2; in other words, X s,r → X s,r for any r, r with r r + 2. By (7.5), we have that χ(X s,r ) 4c. Thus χ r 1 X s,2r-1 4c and χ r 1 X s,2r 4c. This gives χ(X s ) = χ r 1 X s,r 8c, which proves (B).

Hence

This completes the proof of Claim 7.21.

We now turn our attention to the vertices not in the bags. We partition V\B 1,t into sets Z 0 , ..., Z t called zones as follows. For every

We first show that every Z i has few backward arcs with any B j sufficiently far from it.

CLAIM 7.22

For every i and v ∈ Z i ,

• χ(N -(v) ∩ B i+r ) c 1 for every r 1, and

Thus by definition of bag-chain, B 1 , ..., B i-3 , Y 1 , Y 2 , ..., Y 6 , B i+3 , ..., B t is a bag-chain of length t + 1, which contradicts the maximality of t. Hence no Z i contains a bag-chain of length 6.

LEMMA 7.26

There is c such that if an α-dense ∆(H, T k , T 1 )-free digraph D does not contain any c-bag-chain of length 6, then χ(D ) c .

We defer the proof of Lemma 7.26 for now.

We now show that this is sufficient to prove the theorem. To do so, we group zones by indices modulo 3 and follow a similar argument as in Claim 7.21. Fixed 0 s 2, and for every i ≡ s mod 3, 1 i t, let Z s i/3 := Z i . Then χ(Z s j ) c for every j, and for every v ∈ Z s j , by Claim 7.24, we have

By applying Lemma 7.26 for D = Z i and using Claim 7.25, it is immediate that χ(Z i ) c for every i. Thus, χ(Z s j ) c for every j. We can repeat exactly the argument of Claim 7.21 (with c replaced by c and by using Claim 7.24 instead of Claim 7.20) to deduce χ r 0 Z s r 8c c 1 for every s = 0, 1, 2. (Remark: we may suppose that c c, which is necessary for the argument at the end of the proof of Property (A) that 3(c 1 + c 0 )(k + 1) 2c 2c ).

Hence

From Claims 7.21 and the above inequality, we have

which proves Theorem 7.16.

110| GENERALIZING THE ERDŐS-HAJNAL CONJECTURE

Proof of Lemma 7.26 Lemma 7.26 asserts that the absence of bag-chain of length 6 is enough to force a digraph (α-dense and ∆(H, T k , T 1 )-free) to have bounded chromatic number. It is trivial by definition that the absence of bag-chain of length 1 forces bounded chromatic number. In the next lemma, we show that the absence of bag-chain of length 2 forces bounded chromatic number, which contains most of the difficulty of the proof of Lemma 7.26. In the following lemma, c, c 0 , c 1 , h, k are the values as in the proof of Theorem 7.16. Recall that c = 2(c 0 + c 1 )(h + k).

LEMMA 7.27

For every d c, there is g(d) such that if an α-dense ∆(H, T k , T 1 )-free digraph D contains no d-bag-chain of length 2, then χ(D) g(d).

Proof. Let J be the tournament H ⇒ T k . By Theorem 7.8, J is a superhero and contains both H and T k as subtournaments. Let D be a digraph with vertex set V and satisfying the hypotheses of the lemma. A copy of

d (note that we do not color vertices of a ball but color the ball as a single object). A ball certainly can be both red and blue, in which case we color it arbitrarily with one of the colors.

CLAIM 7.28

Every ball is either red or blue.

Proof. Suppose for a contradiction that a ball J is neither red nor blue. Then there are

For every vertex v of V, we color v as follows. If there are c 1 + 1 vertex-disjoint red balls J 1 , ..., J c 1 +1 such that J i has complete arcs to J j for every i < j, and v ∈ J c 1 +1 , then we color v red. If there are c 1 + 1 blue balls J 1 , ..., J c 1 +1 such that J i has complete arcs to J j for every i < j, and v ∈ J 1 , then we color v blue. If v satisfies both conditions, we color v arbitrarily. After the process of coloring, we obtain a partition of V into R the set of red vertices, B the set of blue vertices, and U the set of uncolored vertices.

CLAIM 7.29

There is d 1 such that χ(U) d 1 .

A sequence of pairwise disjoint bags B 1 , . . . , B t forms a chain of bags if B i → B i+1 for every i ∈ [1, t).

Recall that B i+1 → B i means there is no arc from B i to B i+1 . Moreover, if each B i is a poor bag, then this sequence is a chain of poor bags. Given a chain of bags C = {B 1 , B 2 , . . . , B t } for D, we say that v ∈ C if v ∈ B i for some i ∈ [1, t]. We can partition the vertices in V(D) \ C into sets Z 0 , . . . , Z t , which we call zones, as follows. For every v ∈ V(D) \ C, let i be the largest index such that v is seen by at least one vertex in B i . Then vertex v is assigned to zone Z i . Otherwise, we assign v to zone Z 0 . This partition is unique and can be done in time poly(n). As in the case of the bags and zones used in Section 7.3, these bags and zones exhibit useful properties. The proofs we present here are similar, but much simpler.

CLAIM 8.11

Let C = {B 1 , . . . , B t } be a chain of bags, and let Z 0 , Z 1 , . . . , Z t be a partition of the vertices in V(D) \ C. For every i, the following properties hold: Proof. Property (a) holds for r = 1 by definition of a chain of bags. Suppose that (a) holds for r -1 > 1, and suppose that there is an arc uv with u ∈ B i+r and v ∈ B i . Since B i+1 is a bag, there is x ∈ B i+1 such that x is a common neighbor of u and v. Then by induction hypothesis, vx, xu are arcs, and so vxu is a copy of C 3 , a contradiction. Hence (a) holds for r.

Property (b) holds for all r 1 by the partitioning criterion of vertices into zones.

To prove property (c), suppose that there is an arc zv with z ∈ Z i+r and v ∈ B i for some r 2. Then there is u ∈ B i+r such that uz is an arc by the partitioning criterion of vertices into zones. Since B i+1 is a bag, there is x ∈ B i+1 such that x is a common neighbor of u, v, z. By property (a), vx and xu are arcs. If xz is an arc, then vxz is a copy of C 3 . Otherwise, zx is an arc, and so xuz is a copy of C 3 . Either way, we reach the contradiction, and so (c) holds for every r 2.

To prove property (d), suppose that there is an arc uv with u ∈ Z i+r and v ∈ Z i for some r 3. Since B i+1 is a bag, there is x ∈ B i+1 such that x is a common neighbor of all u and v. By property (b), vx is an arc, and by property (c), xu is an arc. Hence vxu is a copy of C 3 , a contradiction. Hence (d) holds for every r 3.

120| DENSE TRIANGLE-FREE DIGRAPHS

We now show how to find a chain of poor bags, which can be colored using Claim 8.9. (ii) Otherwise, return B.

The routine FIND-CHAIN(D, B) returns B 1 , v 1 , B 2 , . . . , v s-1 , B t , i.e. a sequence of sets B i alternating with vertices v i . We say that the sequence B 1 , B 2 , . . . , B t is the chain of poor bags output by the procedure FIND-CHAIN(D, B). Later on, we will use the vertices v i in the output sequence to facilitate the coloring of vertices outside the chain. Observe that if B is a poor bag or if B is not a bag, then FIND-CHAIN(D, B) returns a single set, namely B.

CLAIM 8.12

If bag B ⊆ V(D) is not poor, then FIND-CHAIN(D, B) returns a chain of poor bags B 1 , . . . , B t for some t 2 in time poly(n).

Proof. Let B 1 , . . . , B t be the chain of poor bags output by FIND-CHAIN(D, B). The bags in this chain are pairwise disjoint. From Step 1 of FIND-CHAIN, it follows that each B i is a bag. Furthermore, each B i must be poor; otherwise, Step 1 would be applied to B i to return poor bags inside B i . Observe that for every pair of consecutive bags B i , B i+1 in the chain, B i+1 ⊆ N + (v i ) and B i ⊆ N -(v i ). If there is an arc xy with x ∈ B i+1 and y ∈ B i , then v i xy is a copy of C 3 , a contradiction. Hence B 1 , . . . , B t is a chain of poor bags by definition. The procedure FIND-CHAIN(D, B) runs in time poly(n).

CLAIM 8.13

If FIND-CHAIN(D, B) returns a chain of t poor bags, then we can color B with 8αβ + (t -1) • β colors in time poly(n) + time(α -1, |B|).

Proof. Suppose that FIND-CHAIN(D, B) returns B 1 , v 1 , B 2 , . . . , v t-1 , B t and that C = {B 1 , . . . , B t } is the chain of poor bags output by the procedure. Since each B i is a poor bag, it can be colored using Claim 8.9. By Claim 8.11, B i → B j for every i < j, and so we can color the vertices in C using 8α • β colors in time poly(n) + time(α -1, |C|) time.