Keywords: mapping of the crosspolytope

Enfin, je tiens à remercier Manou, à qui je dédie ce manuscrit. Merci pour tous ces bons moments au coin du feu, où nous nous amusions à faire des maths. En m'apprenant à jouer à la géométrie, tu m'as fait un cadeau immense qui m'a conduite jusqu'ici.

The algorithmic questions raised by the colorful Carathéodory theorem concern, among other things, the complexity of finding a colorful set under the condition of the theorem, and more generally of deciding whether there exists such a colorful set when the condition is not satisfied. In 1997, Bárány and Onn defined colorful linear programming as algorithmic questions related to the colorful Carathéodory theorem. The two questions we just mentioned come under colorful linear programming. This thesis aims at determining which are the polynomial cases of colorful linear programming and which are the harder ones. New complexity results are obtained, refining the sets of undetermined cases. In particular, we discuss some combinatorial versions of the colorful Carathéodory theorem from an algorithmic point of view. Furthermore, we show that computing a Nash equilibrium in a bimatrix game is polynomially reducible to a colorful linear programming problem. On our track, we found a new way to prove that a complementarity problem belongs to the PPAD class with the help of Sperner's lemma. Finally, we present a variant of the "Bárány-Onn" algorithm, which is an algorithm computing a colorful set T containing 0 in its convex hull whose existence is ensured by the colorful Carathéodory theorem. Our algorithm makes a clear connection with the simplex algorithm. After a slight modification, it also coincides with the Lemke method, which computes a Nash equilibrium in a bimatrix game.

The combinatorial question raised by the colorful Carathéodory theorem concerns the number of positively dependent colorful sets. Deza, Huang, Stephen, and Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597-604 (2006)) conjectured that, when |S i | = d + 1 for all i ∈ {1, . . . , d + 1}, there are always at least d 2 + 1 colourful sets containing 0 in their convex hulls. We prove this conjecture with the help of combinatorial objects, known as the octahedral systems. Moreover, we provide a

Résumé

Le théorème de Carathéodory coloré, prouvé en 1982 par Bárány, énonce le résultat suivant. Etant donnés d + 1 ensembles de points S 1 , . . . , S d +1 dans R d , si chaque S i contient 0 dans son enveloppe convexe, alors il existe un sous-ensemble arc-en-ciel T ⊆ d +1 i =1 S i contenant 0 dans son enveloppe convexe, i.e. un sous-ensemble T tel que |T ∩ S i | ≤ 1 pour tout i et tel que 0 ∈ conv(T ). Ce théorème a donné naissance à de nombreuses questions, certaines algorithmiques et d'autres plus combinatoires. Dans ce manuscrit, nous nous intéressons à ces deux aspects.

En 1997, Bárány et Onn ont défini la programmation linéaire colorée comme l'ensemble des questions algorithmiques liées au théorème de Carathéodory coloré. Parmi ces questions, deux ont particulièrement retenu notre attention. La première concerne la complexité du calcul d'un sous-ensemble arc-en-ciel comme dans l'énoncé du théorème. La seconde, en un sens plus générale, concerne la complexité du problème de décision suivant. Etant donnés des ensembles de points dans R d , correspondant aux couleurs, il s'agit de décider s'il existe un sous-ensemble arc-en-ciel contenant 0 dans son enveloppe convexe, et ce en dehors des conditions du théorème de Carathéodory coloré. L'objectif de cette thèse est de mieux délimiter les cas polynomiaux et les cas "difficiles" de la programmation linéaire colorée. Nous présentons de nouveaux résultats de complexités permettant effectivement de réduire l'ensemble des cas encore incertains. En particulier, des versions combinatoires du théorème de Carathéodory coloré sont présentées d'un point de vue algorithmique. D'autre part, nous montrons que le problème de calcul d'un équilibre de Nash dans un jeu bimatriciel peut être réduit polynomialement à la programmation linéaire coloré. En prouvant ce dernier résultat, nous montrons aussi comment l'appartenance des problèmes de complémentarité à la classe PPAD peut être obtenue à l'aide du lemme de Sperner. Enfin, nous proposons une variante de l'algorithme de Bárány et Onn, calculant un sousensemble arc-en-ciel contenant 0 dans son enveloppe convexe sous les conditions du théorème de Carathéodory coloré. Notre algorithme est clairement relié à l'algorithme du simplexe. Après une légère modification, il coïncide également avec l'algorithme de Lemke, calculant un équilibre de Nash dans un jeu bimatriciel.

La question combinatoire posée par le théorème de Carathéodory coloré concerne Résumé le nombre de sous-ensemble arc-en-ciel contenant 0 dans leurs enveloppes convexes. Deza, Huang, Stephen et Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597-604 (2006)) ont formulé la conjecture suivante. Si |S i | = d + 1 pour tout i ∈ {1, . . . , d + 1}, alors il y a au moins d 2 + 1 sous-ensemble arc-en-ciel contenant 0 dans leurs enveloppes convexes. Nous prouvons cette conjecture à l'aide d'objets combinatoires, connus sous le nom de systèmes octaédriques, dont nous présentons une étude plus approfondie.

Introduction The colorful Carathéodory theorem

Given a set S of N ≥ 3 points in the plane and a point p in the convex hull of S, there is a triangle formed with points of S containing p in its convex hull. In general dimension d , the Carathéodory theorem states the following. Given a set S of N ≥ d + 1 points in R d and a point p in the convex hull of S, there is a subset T ⊆ S of size at most d + 1 containing p in its convex hull. Bárány [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF] proposed a generalization of this theorem, in which S is partitioned into d + 1 sets, or colors, and the set T is colorful, i.e. it intersects each color at most once.

Consider blue points, green points, and red points in the plane, such that there is a point p simultaneously in the convex hull of the blue points, in the convex hull of Introduction the green points, and in the convex hull of the red points. The colorful Carathéodory theorem, proved by Bárány in 1982, ensures the existence of a colorful triangle, i.e. a triangle formed with one blue point, one green point, and one red point, also containing p in its convex hull.

In general dimension d , the colorful Carathéodory theorem states the following.

Theorem. Given d + 1 sets S 1 , . . . , S d +1 , and any point p ∈ d +1 i =1 conv(S i ), there is a colorful set T containing p in its convex hull, that is a set T ⊆ d +1 i =1 S i such that |T ∩S i | ≤ 1 for all i ∈ [d + 1], and p ∈ conv(T ). The colorful Carathéodory theorem gave birth to this thesis and motivated most of the questions we considered during the course of my Doctoral study. Two main streams of questions are raised by this theorem: the computational problems on the one hand and a more combinatorial problem on the other hand. In the remaining of this introduction, we present these two streams. We end the introduction with applications of colorful linear programming.

with S 1 = • • • = S d +1 , corresponding to the usual Carathéodory theorem, is known to be computable in polynomial time via linear programming. However, the complexity of the colorful version remains an open question.

A second problem concerns the complexity of deciding whether there exists such a colorful set, in case the conditions of the colorful Carathéodory are not satisfied. More precisely, given k sets S 1 , . . . , S k in R d and a point p ∈ R d , the problem is to decide whether there is a colorful set containing p in its convex hull, i.e. a set T ⊆ k i =1 S i such that |T ∩ S i | ≤ 1 for all i ∈ [d + 1] and p ∈ conv(T ). This problem, often referred to as the colorful linear programming problem, is known to be NP-complete in general. Depending on the context, we may consider this problem with a linear programming point of view. Formally, the problem is the following. Given a d × n matrix A ∈ R d ×n , a vector b ∈ R d , and a partition of [n] into k sets I 1 , . . . , I k , decide whether there exists a solution x ∈ R n to the system

Ax = b, x ≥ 0, (1)
| supp(x) ∩ I j | ≤ 1, for all j ∈ [k],
where supp(x) is the set {i ∈ [n] | x i = 0}. We show that the problems of deciding whether a colorful solution exists and of optimizing a linear cost function over all colorful solutions can be polynomially reduced one to the other. Colorful linear programming either refers to one or the other version. A seemingly more general problem is obtained by replacing the constraints on the support by | supp(x) ∩ I j | ≤ j for all j ∈ [k], for some prefixed j ∈ Z + . We discuss the complexity of this generalization and get some partial results in Chapter 3. A polyhedral interpretation of colorful linear programming is also provided in the same chapter.

Another computational problem is raised by the Octahedron lemma, which is a theorem similar to the colorful Carathéodory. This theorem states that given d + 1 pairs of points in R d and a point p ∈ R d , all in general position, there is an even number of colorful sets containing p in their convex hulls. In particular, it shows that if p is contained in the convex hull of a colorful set, then p is contained in the convex hull of another colorful set. The related computational problem, known as find another colorful simplex is the following. Given d + 1 pairs of points in R d and a point p ∈ R d , all in general position, and given a colorful set containing p in its convex hull, compute another colorful set containing p in its convex hull. The complexity of this problem was an open question.

We obtain new results for these three computational problems. In particular, we provide combinatorial polynomial cases of the colorful Carathéodory theorem. We propose a variant of the "Bárány-Onn" algorithm, which computes a colorful set containing 0 in its convex hull. Our algorithm makes a clear connection with the simplex algorithm. We also extended the result of Bárány and Onn on the NP-completeness of colorful linear programming to the case with k = d + 1, answering one of their questions. Finally we proved that find another colorful simplex is PPAD-complete. The most surprising result we obtain is the fact that colorful linear programming contains the problem of finding a Nash equilibrium in a bimatrix game. Most of these results, presented in Chapter 2, can be found in the article F. Meunier and P. Sarrabezolles. Colorful linear programming, Nash equilibrium, and pivots. Discrete Applied Mathematics, under revision.

The colorful simplicial depth conjecture

Simplicial depth

Given a set S of real numbers, the median is a real number m such that half the numbers in S are not larger than m and half the numbers in S are not smaller than m. A median can equivalently be defined as a real number contained in the largest possible number of segments [a, b] with a, b ∈ S.

In 1990, Liu [START_REF] Liu | On a notion of data depth based on random simplices[END_REF] generalized the concept of median in higher dimension. This generalization, known as deepest point, is the following: given a set S of points in R d , a deepest point is a point m ∈ R d contained in the largest possible number of simplices formed with points of S. This notion has many applications in statistics and in data analysis.

A natural question raised by this notion is how deep is a deepest point, i.e. what is the maximal number of simplices formed with points of S whose convex hulls intersect? This geometric question has been asked earlier, and a first answer was given by Bárány using the colorful Carathéodory theorem.

Introduction

statement and a colorful triangle containing it are represented. There are in fact more colorful triangles containing this point p.

In 2006, Deza et al. [START_REF] Deza | Colourful simplicial depth[END_REF] conjectured that if each S i is of size at least d + 1, then any point p ∈ d +1 i =1 conv(S i ) is contained in the convex hulls of at least d 2 + 1 colorful sets. They proved in the same paper that the bound d 2 + 1 is tight. As a matter of fact, there are colorful point configurations, with d + 1 sets of d + 1 points in R d , such that there is a point p ∈ d +1 i =1 conv(S i ) contained in the convex hulls of exactly d 2 + 1 colorful sets, see Figure 3 for such a configuration in dimension 3. Bárány suggested a combinatorial approach to this problem. It consists in considering a special class of hypergraphs generalizing the colorful point configuration, the octahedral systems. Given a colorful point configuration, there is a corresponding octahedral system, whose edges are identified with the colorful sets containing 0 in their convex hulls. Hence a bound on the number of edges in an octahedral system gives a bound on the colorful simplicial depth. The octahedral systems are studied in Chapter 4 and Chapter 5. Using this approach, we improve the best known bound. This work appeared in the article A. Deza, F. Meunier, and P. Sarrabezolles. A combinatorial approach to colourful simplicial depth. SIAM Journal on Discrete Mathematics, 28(1): 306-322, 2014.

Finally, we prove the colorful simplicial depth conjecture, using the same approach. This proof appeared in the article Introduction P. Sarrabezolles. The colorful simplicial depth conjecture. Journal of Combinatorial Theory, Series A, 130(0): 119-128, 2015.

Our proof actually shows that if each S i is of size m ≥ d + 1, then any point p ∈ d +1 i =1 conv(S i ) is contained in the convex hulls of at least (m -2)(d + 1) + 2 colorful sets.

More generally, we formulate the following conjecture.

Conjecture. Consider a colorful point configuration with |S

1 | ≥ • • • ≥ |S d +1 | ≥ d + 1 ≥ 2. Any point p ∈ d +1 i =1 conv(S i ) is contained in the convex hulls of at least d +1 i =1 (|S i | -2) + 2 colorful sets.

Applications of colorful linear programming

The study of problems related to the colorful Carathéodory theorem is usually motivated in the literature by the many theoretical applications of this result in geometry, and by the challenging questions raised by these problems. We would like to give another motivation here, with practical applications of colorful linear programming, although these applications are not studied any further in the thesis. We are not aware of similar applications in the literature, with industrial problems explicitly formulated as colorful linear programs.

Colorful diet programming

We start with a famous application of linear programming: the diet programming problem. This problem was introduced during the Second World War and aimed at defining the daily diet of U.S. soldiers. More precisely, given a set of nutriments and a set of foods, each containing a certain amount of each nutriment, the problem is to find an optimal diet, with respect to some objective function, such that each nutriment is sufficiently provided. It was one of the first problem on which the simplex algorithm was tested, in 1947 [START_REF] Dantzig | Linear programming and extensions[END_REF]. Later, in 1990, Dantzig showed the limits of this model in an over-viewing paper [START_REF] Dantzig | The diet problem[END_REF], in which he described how he tried to apply the model to his own diet. The main struggle he encountered was "the lack of variety" of the solutions given by the model. Adding some upper bounds, he managed to avoid solutions using only one food, for instance bran, but got instead solutions with all foods belonging to the same category, for instance cereals. If he had known colorful linear programming, he might have been able to fix this problem. Indeed, colorful linear programming consists exactly in solving a linear program with the additional constraints that the variables belong to categories, and that the number of variables of each category used in a solution is bounded. Dantzig finally followed his wife advice, which was certainly even more efficient.

Formally, the original diet problem is the following. We are given n foods and m nutriments. Let a i j ∈ R + be the quantity of nutriment j in one unit of food i , let b j be the quantity of nutriment j needed by a soldier daily, and let X i be the maximal amount of aliment i a soldier can tolerate in one day. Finally, let c i be the cost of one unit of food i . We define the variables x 1 , . . . , x n ∈ R + , modeling the quantity of food i that will be recommended by the diet program. We also define slack variables z 1 , . . . , z m ∈ R + and y 1 , . . . , y n ∈ R + . The diet problem aims at solving

min n i =1 c i x i s.t. n i =1 a i j x i -z j = b j for all j ∈ [m], x i + y i = X i for all i ∈ [n],
x i , y i ≥ 0 for all i ∈ [n],

z j ≥ 0 for all j ∈ [m].
We now want to model the fact that for example a soldier does not eat more than three types of vegetables, two types of meat and one fruit each day, and so on. In general, the foods are partitioned into different categories, for instance vegetables, fruits,...:

[n] = I 1 ∪ • • • ∪ I k , and the number of different foods of each category h ∈ [k] a soldier will tolerate to eat in one day is bounded by some integer h . These combinatorial constraints can be modeled by adding the following constraints to the previous linear

Introduction program: | i ∈ I h | x i = 0 | ≤ h for all h ∈ [k].
This model is a colorful linear program.

In the same line of ideas, colorful linear programming appears in many problems for which variety is required. For instance, it may appear in production. Indeed, to prevent the risk of a lack of raw material, or the change of taste of its clients, a firm may require to produce various types of goods in addition to optimize its income. Similarly, while optimizing a stock option portfolio, it may be interesting to add the constraint that not all stock options belong to the same category.

Other application: sparse solutions of linear systems

Colorful linear programming is not the first variant of linear programming to which an additional constraint on the support of the solutions is added. Indeed, the problem of finding a sparse solution to an undetermined linear system also belongs to this class of problem. It has itself many applications in signal processing. In particular, it is a useful tool for encoding and recovering without errors messages, which may be corrupted during their transmissions, see Chapter 8.5 of [START_REF] Matoušek | Understanding and Using Linear Programming[END_REF] for more details on this problem.

Formally, the problem is the following. Given a matrix A ∈ R d ×n , a vector b ∈ R d , and a nonnegative integer r ∈ Z + , decide whether there is a solution x ∈ R n to the system

Ax = b, | supp(x)| ≤ r.
This problem is actually generalized by colorful linear programming, since it is a particular case with only one type of variable.

The colorful Carathéodory theorem and its relatives

In this chapter we present geometric results related to the colorful Carathéodory theorem and several variants of the theorem itself. Our aim is to give a survey of the many geometric results given by Bárány in his original paper proving the colorful Carathéodory theorem [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF] and to extend some of them. We also use this chapter to define most of the technical tools required for reading the thesis.

Definitions and preliminaries

In this section, we introduce the basic notions and terminology used in the thesis. More specific notions are introduced throughout the five chapters.

Basic geometric notions

R d denotes the d -dimensional Euclidean space. For a point x = (x 1 , . . . , x d ) ∈ R d , the Euclidean norm of x is x = x 2 1 + • • • + x 2 d . The distance between two points x, y ∈ R d is x -y . The distance between a point p ∈ R d and a set S ⊆ R d , denoted dist(p, S), is inf s∈S p -s . The support of a vector x ∈ R d , denoted supp(x), is the set i ∈ [d ] | x i = 0 . For a point x = (x 1 , . . . , x d ) ∈ R
(S) = t i =1 λ i s i | t i =1 λ i = 1, λ i ≥ 0 for all i ∈ [t ] .
A set S containing 0 in its convex hull is called positively dependent. Otherwise, S is positively independent.

A cone C ⊆ R d is a set such that for all x, y ∈ C and all α ∈ R + , we have αx + y ∈ C . In other words, any positive combination of points of C is in C . Note that a cone is always convex. The conic hull of a set S, denoted pos(S), is the smallest cone containing S. If S is finite, S = {s 1 , . . . , s t }, the following equality holds pos(S)

= t i =1 λ i s i | λ i ≥ 0 for all i ∈ [t ] .
An affine subspace H ⊆ R d is a set such that for all x, y ∈ H and all α ∈ R, we have αx + y ∈ H . In other words, any linear combination of points of an affine subspace H is in H . The affine hull of a set S, denoted by aff(S), is the smallest affine space containing S. If S is finite, S = {s 1 , . . . , s t }, the following equality holds aff(S)

= t i =1 λ i s i | λ i ∈ R for all i ∈ [t ] .
A set S such that a point in S is in the affine hull of the other points in S is affinely dependent. Otherwise, S is affinely independent.

Linear programming

For a matrix A ∈ R d ×n , let A j denote the j th column of A. Given a set I ⊆ [n], the matrix A I denotes the matrix formed with the columns in A j | j ∈ I , arranged in the same order.

A linear program, is an optimization problem which can be written as follows (standard form). A feasible basis is a basis B ⊆ [n] such that x B ≥ 0. In this case, x B is a feasible basic solution. An important result in linear programming states that, for any c, if the optimum of (1.1) is finite, then there is an optimal solution attained on a feasible basis [START_REF] Dantzig | Linear programming and extensions[END_REF].

The feasibility problem related to a linear program, refers to the decision problem: is there a solution to the system

Ax = b,
x ≥ 0?

The optimization problem above can be reduced to such a feasibility problem, using duality.

General position, degeneracy, perturbation

Points in R d are in general position if no k ≤ d + 1 points among them are affinely dependent. Given a point configuration X 0 , there are point configurations arbitrarily close to X 0 , whose points are in general position. A perturbation argument consists in showing that, if a statement is valid on configurations arbitrarily close to X 0 , then it is valid for X 0 as well. For instance, given a set S and a point p, we can perturb the points in S such that if p is contained in some simplex of the perturbed configuration, then it is also contained in the corresponding simplex of the original configuration. Furthermore, such a perturbation can be made in polynomial time, [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF].

Consider a linear program of the form (1.1 [START_REF] Megiddo | On the ε-perturbation method for avoiding degeneracy[END_REF] for more details.

Polytope, polyhedron, triangulation

A polyhedron P ⊆ R n is an intersection of finitely many closed half-spaces in R n . Note that a polyhedron is a convex set. A polytope is a bounded polyhedron. A polytope can equivalently be defined as the convex hull of finitely many points. The dimension of a polyhedron is the dimension of its affine hull.

A simplex is the convex hull of affinely independent points. A k-simplex is the convex hull of k + 1 affinely independent points. The dimension of a k-simplex is k.

A face of a polyhedron P is the intersection of P and a hyperplane in R n such that all the points of P lie on the same closed half-space defined by this hyperplane. Note that a face is also a polyhedron. Given a polyhedron P of dimension r , the facets of P are the faces of dimension r -1, the edges are the faces of dimension 1, and the vertices are the faces of dimension 0. By convention, the empty face is a face of the polyhedron and it is of dimension -1. The 1-skeleton of a polyhedron P is the graph whose vertices and edges are the vertices and edges of P . An elementary result in polyhedral theory is that the 1-skeleton of a polyhedron is connected, as soon as dim P ≥ 2.

Given a linear program of the form (1.1), the set of solutions A polyhedral complex K is a finite collection of polyhedra, called cells, such that

P = x ∈ R n | Ax = b, x ≥ 0 defines a polyhedron. When A ∈ R d ×n is of full rank, the dimension of P = x ∈ R n | Ax = b, x ≥ 0 is at most n -d . If
• the empty set is in K,

• if P is in K, then all faces of P are also in K,

• if P , Q are two polyhedra of K, then P ∩ Q is a (possibly empty) face of both P and Q.

A polyhedral complex whose polyhedra are all polytopes is a polytopal complex. The dimension of a polyhedral complex K is the largest dimension of a polyhedron in K. A simplicial complex is a polyhedral complex whose polyhedra are all simplices.

A simplicial complex T is a triangulation of the set S∈T S. The vertices of T , denoted by V (T), are the 0-simplices of the simplicial complex.

⊆ R d , a set T ⊆ k i =1 S i is colorful if |T ∩ S i | ≤ 1 for all i ∈ [k].
A colorful simplex is the convex hull of a colorful set whose points are affinely independent.

A colorful point configuration is a family of d + 1 sets of points S 1 , . . . , S d +1 in R d . These sets are referred as colors.

Given a colorful point configuration S 1 , . . . , S d +1 ⊆ R d , a transversal is a set T ⊆ d +1 i =1 S i such that |T ∩ S i | ≤ 1 for all i ∈ [d + 1] and |T | = d . In other words, T is a colorful set intersecting all colors but one. An i -transversal T is a transversal such that |T ∩ S i | = 0.
The colorful Carathéodory theorem proved by Bárány in 1982 and already given in Introduction can be rephrased as follows.

Theorem 1.2.1 (Colorful Carathéodory theorem, Bárány [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF]). Given d + 1 sets of points S 1 , . . . , S d +1 in R d , all positively dependent, there exists a positively dependent colorful set T .

In the same paper, Bárány gave the following conic version of the theorem. Other generalizations of the colorful Carathéodory theorem have been formulated. For instance, the condition 0 ∈ conv(S i ) for all i ∈ [d +1] can be replaced by 0 ∈ conv(S i ∪S j ) for all i , j ∈ [d + 1], i = j , see [START_REF] Arocha | Very colorful theorems[END_REF][START_REF] Holmsen | Points surrounding the origin[END_REF]. More generalizations are given in [START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF].

Proofs of the colorful Carathéodory theorem 1.3.1 Original proof by Bárány

We start this section with the original proof given by Bárány [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF]. We prove here Theorem 1.2.1, whereas this original proof showed the more general Theorem 1.2.2. The arguments are roughly the same, and the proof of Theorem 1.2.1 provides an algorithm computing the positively dependent colorful set.

Consider d + 1 sets of points S 1 , . . . , S d +1 in R d such that 0 ∈ d +1 i =1 conv(S i )
. Consider now a colorful set T = {t 1 , . . . , t d +1 } that is closest to 0. By closest, we mean a colorful set T minimizing dist 0, conv(T ) . If dist 0, conv(T ) = 0, then 0 ∈ conv(T ), and hence T satisfies the statement of the theorem. Otherwise, consider a point z 0 ∈ conv(T ) 1.3. Proofs of the colorful Carathéodory theorem minimizing z 0 2 . For all z ∈ conv(T ), we have z T 0 z > 0. Besides, z 0 can be written as a positive sum of points in T , namely z 0 = d +1 i =1 γ i t i , with γ i ≥ 0 for all i ∈ [d + 1] and one of the γ i 's equal to 0. Indeed, if conv(T ) is a simplex of dimension d , the projection of 0 lies on a face of the simplex, and if conv(T ) is of smaller dimension, then we can clearly set one of the γ i 's to zero. Without loss of generality, we assume that γ 1 = 0. Since t 1 ∈ conv(T ), we have z T 0 t 1 > 0. Since 0 ∈ conv(S 1 ), there is necessarily a vector t 1 ∈ S 1 such that z T 0 t 1 < 0. Replacing t 1 by t 1 in T we obtain a colorful set T , which is strictly closer to 0 than T. Indeed, for 0 ≤ α ≤ 1, we have (1 -α)z 0 + αt 1 ∈ conv(T ), and

dist(0, T ) 2 ≤ (1 -α)z 0 + αt 1 2 = (1 -α) 2 z 0 2 + 2α(1 -α)z T 0 t 1 + α 2 t 1 2 .
Choosing α > 0 small enough, we obtain dist(0, T ) < dist(0, T ). This contradiction shows that T must contain 0 in its convex hull. This proof provides an algorithm for finding a colorful set containing 0 in its convex hull. The algorithm goes roughly as follows. Choose a colorful set T . As long as T does not contain 0 in its convex hull, we can replace one point of T as in the previous proof and obtain a colorful set strictly closer to 0. Since there is a finite number of colorful sets, this algorithm ends and returns a positively dependent colorful set. This algorithm is not known to be polynomial and has been studied in [START_REF] Bárány | Colourful linear programming and its relatives[END_REF] and later in [START_REF] Deza | The colourful feasibility problem[END_REF]. We discuss it more thoroughly in Section 2.1.2.

Sperner's lemma proves the colorful Carathéodory theorem

We sketch here a new proof of Theorem 1.2.3, and hence of the strong version of the colorful Carathéodory theorem, namely Theorem 1.2.4. The proof uses the well-known Sperner's lemma, originally introduced to give a constructive proof of the Brouwer fixed point theorem [START_REF] Sperner | Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes[END_REF]. The motivation for this proof is to make a connection between two colorful results.

Consider a d -simplex ∆ d = conv{v 1 , . . . , v d +1 }, and a triangulation T of this simplex. A Sperner labeling is a map λ :

V (T) → [d +1] such that for v ∈ V (T), if F = conv(v i 1 , . . . , v i k ) is the smallest face of ∆ d containing v, then λ(v) ∈ {i 1 , . . . , i k }.
In particular, we have

λ(v i ) = i for all i ∈ [d + 1].
A simplex in the triangulation is fully-labeled if it is of dimension d and its vertices have pairwise distinct labels. Theorem 1.3.1 (Sperner's Lemma, Sperner [START_REF] Sperner | Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes[END_REF]). Given a triangulated simplex and a Sperner labeling of its triangulation, there exists an odd number of fully-labeled simplices.

The proof of this theorem is standard and may be found in [START_REF] Cohen | On the Sperner lemma[END_REF][START_REF] Scarf | The approximation of fixed points of a continuous mapping[END_REF]. Less formally, the label of a vertex identified with B is the index i maximizing |B ∩ B i |.

If there is more than one such i , then λ(B ) is chosen as the smallest among them. In particular, we have λ(B i ) = i .

Consider now B 1 and B 2 . Because of the connectedness of the 1-skeleton of the face P B 1 ∪B 2 , there is a path between the two vertices B 1 and B 2 in this graph. The vertices on this path correspond to bases B ⊆ B 1 ∪ B 2 , and hence having their labels equal to 1 or 2. Similarly, we define a path between B 1 and B 3 and a path between B 2 and B 3 . Again, by a connectedness argument, these three paths form the boundary of a polyhedral complex on the boundary of the face P B 1 ∪B 2 ∪B 3 of dimension 2. All the vertices of this complex clearly have their labels equal to 1, 2, or 3.

In general, given a set X ∈ [d ], we define R X to be a polytopal complex of dimension |X | -1 whose boundary is ∂R X = i ∈X R X \{i } . Such a complex exists, since the face P i ∈X B i is connected. In the end, we have a polyhedral complex K = R [d ] on the boundary of P , whose polyhedra are of dimension at most d -1. Furthermore, this polyhedral complex resembles the faces of ∆ d with the identfication "R X ∼ = face of ∆ d ". The labeling of this complex is a proper labeling for Sperner's lemma. Up to triangulating the polyhedra in K, we have thus at least one fully-labeled (d -1)-simplex,

and
. We have |B ∩ B i | ≤ |B ∩ B i 0 | = 1 for all i ∈ [d ].
Therefore, B is a colorful feasible basis, which proves the theorem.

There is an algorithmic proof of Sperner's lemma. Therefore, this new proof gives, in some sense, another algorithm for the colorful Carathéodory theorem. Here again we do not know the exact complexity but it might be exponential.

Applications in geometry

This section gathers applications of the colorful Carathéodory theorem in discrete geometry.

Tverberg's theorem

Given a set S of n points in R d , a Tverberg k-coloring of S is a partition of the points in S into k sets S 1 , . . . , S k such that k i =1 conv(S i ) is nonempty. Tverberg's theorem, proved in 1966 [START_REF] Tverberg | A generalization of Radon's theorem[END_REF], states the following. Sarkaria proposed a proof of this theorem using the colorful Carathéodory theorem [START_REF] Sarkaria | Tverberg's theorem via number fields[END_REF]. We present here a simplified version of this proof by Bárány and Onn [START_REF] Bárány | Colourful linear programming and its relatives[END_REF].

Proof. Consider a finite set S = {v 1 , . . . , v n } ⊆ R d and an integer k such that n ≥ (k -1)(d + 1) + 1. Let N = (k -1)(d + 1). A Tverberg k-coloring of the points in {v 1 , . . . , v N +1 } induces a Tverberg k-coloring of S, by assigning the remaining points in S to any set of the partition. We can thus assume that n = N + 1. The idea of the proof is to define k copies of each point in S, numbered from 1 to k, in a space of higher dimension. A colorful set in this higher dimensional space will associate each point of S to one of its k copies, and hence will give a partition of S.

Choose arbitrarily a family f 1 , . . . ,

f k ∈ R k-1 such that f 1 + • • • + f k = 0,
and such that any subfamily is linearly independent. For i ∈ [n], define the set of k copies of v i by

T i = f j ⊗ v i 1 | j ∈ [k] ⊆ R k-1 ⊗ R d +1 .
We clearly have 0 ∈ conv(T i ) for all i ∈ [n]. Applying the colorful Carathéodory theorem, in dimension N , to the colors T 1 , . . . , T N +1 , we obtain a colorful set

T = f π(i ) ⊗ v i 1 | i ∈ [N + 1] containing 0 in its convex hull, where π(i ) ∈ [k] is the index j of the point of T i chosen in T . We have 0 = n i =1 α i f π(i ) ⊗ v i 1
, with α ≥ 0, which can be rewritten

0 = k j =1 i ∈π -1 ( j ) α i f j ⊗ v i 1 = k j =1 f j ⊗ i ∈π -1 ( j ) α i v i 1 .

Applications in geometry

Thus, by the assumption made on the f i 's, we have i ∈π -1 (1)

α i v i 1 = • • • = i ∈π -1 (k) α i v i 1 .
Let

M = i ∈π -1 (1) α i = • • • = i ∈π -1 (k) α i and define S j := v i ∈ S | i ∈ π -1 ( j ) for all j ∈ [k]. We have z = 1
M i ∈π -1 (1) α i v i ∈ conv(S j ), for all j ∈ [k].
We conclude that the partition S 1 , . . . , S k defines a Tverberg k-coloring of S.

First selection lemma

Given n points in the plane in general position, a result by Boros and Füredi [START_REF] Boros | The number of triangles covering the center of an n-set[END_REF] states that there is a point, not necessarily one of these n points, in at least 2 9 n 3 triangles spanned by these points, and that this is the best possible bound. A similar statement holds in arbitrary dimension, answering a question of Boros and Füredi. It was first proved by Bárány as an application of the colorful Carathéodory theorem. The proof by Bárány provides a constant c d equal to (d + 1) -(d +1) . A better bound was obtained by Gromov [START_REF] Gromov | Singularities, expanders and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry[END_REF][START_REF] Karasev | A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem[END_REF]

Weak ε-nets

Given a set X ⊆ R d in general position with |X| = n, and ε > 0, the set S ⊆ R d is a weak ε-net if it satisfies S ∩ conv(Y) = for all Y ⊆ X of size |Y| ≥ εn. The problem here is to find a weak ε-net as small as possible. Applying the first selection lemma, we can show the following theorem, better bounds have been obtained by Chazelle et al. [START_REF] Chazelle | Improved bounds on weak ε-nets for convex sets[END_REF].

Octahedron lemma: three proofs

The following lemma is ubiquitous in colorful linear programming. In dimension 2, it means that given two blue points, two red points, and two green points in the plane, in general position, any point in the plane is covered by an even number of colorful triangles, see Figure 1.3. This theorem has a similar flavor as the colorful Carathéodory theorem, and leads to similar algorithmic questions, studied in Chapter 2. It is also a key tool for counting the number of colorful simplices under the conditions of the colorful Carathéodory theorem, see Chapter 4 and Chapter 5.

We propose three different proofs of the Octahedron lemma. Although this theorem was known and used in [START_REF] Bárány | Quadratically many colorful simplices[END_REF][START_REF] Deza | The colourful feasibility problem[END_REF][START_REF] Deza | More colourful simplices[END_REF], the proof was not fully written before 2011 [START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF].

Topological proof

The first proof is topological and was mentioned by Bárány and Matoušek [START_REF] Bárány | Quadratically many colorful simplices[END_REF].

Topological proof of

Parity proof argument

The following proof was proposed by Meunier and Deza [START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF].

Proof of Theorem 1.5.1 using complementary pivots. Consider d + 1 pairs of points S 1 , . . . , S d +1 in R d and a point p ∈ R d in general position. Define a graph G = (V, E ) as follows. The vertices in V are identified with subsets of d +1 i =1 S i . We consider three types of subsets, defining three sets of vertices V 1 , V 2 , and V 3 . The vertices in V 1 correspond to the colorful sets containing p in their convex hull. The vertices in V 2

⊆ d +1 i =1 S i such that |T ∩ S i | ≤ 1 for all i ∈ [d ], S d +1 ⊆ T , |T | ≤ d + 1
, and p ∈ conv(T ). Note that since the points are in general position, the vertices in V 1 and V 2 correspond to sets of size d + 1. Hence, the vertices in V 2 correspond to sets missing exactly one color. Finally, the vertices of

V 3 correspond to sets T such that |T ∩ S i | ≤ 1 for all i ∈ [d ], S d +1 ⊆ T , |T | = d + 2, and p ∈ conv(T ). Two vertices are neighbors in G if one of them is in V 1 ∪ V 2 and
the other is in V 3 , and if the corresponding sets have d + 1 points in common. We show that the vertices in V 1 are of degree 1, and that the vertices in V 2 and V 3 are of degree 2. The graph G being a collection of cycles and paths with endpoints in V 1 , we conclude that |V 1 | is even.

Consider a vertex v ∈ V 3 and the corresponding set T . The neighbors of v correspond to sets T ⊆ T such that |T | = d + 1 and p ∈ conv(T ). By a usual argument in linear programming, there are exactly two of them. Consider a vertex v ∈ V 1 and the corresponding set T . It is clear that v has exactly one neighbor, which is the vertex of V 3 corresponding to T ∪ S d +1 . Finally, consider v ∈ V 2 and the corresponding set T . It misses one color S j = {s 1 j , s 2 j }, and hence v has exactly two neighbors being the vertices in V 3 corresponding to the sets T ∪ {s 1 j } and T ∪ {s 2 j }.

Geometric proof

The following proof was inspired by discussions with Raman Sanyal on the combinatorial proof of the colorful simplicial depth conjecture, see Chapter 4.

Geometric proof of

point p 0 ∈ R d not in conv( d +1 i =1 S i ).
The point p 0 is in no colorful simplices. Consider the line L joining p 0 and p. Up to slightly moving the point p 0 , we can assume that this line crosses the simplices in K in their interior and on distinct points. We denote by T 1 , . . . , T r the transversals corresponding to the simplices of K intersected by L in this order when going from p 0 to p, and by q 1 , . . . , q r the intersection points.

Clearly no colorful simplices contain a point in [p 0 , q 1 [. All points in ]q i , q i +1 [ are contained in exactly the same colorful simplices, for i ∈ [r -1], and all the points in ]q r , p] are contained in exactly the same colorful simplices.

We denote by Ω 0 the empty-set, by Ω i the set of colorful simplices containing the points in ]q i , q i +1 [ for i ∈ [r -1], and by Ω r the set of colorful simplices containing the points in ]q r , p]. Note that Ω r is exactly the set of colorful simplices containing p. Finally, for a transversal T , we note U (T ) the set of all colorful simplices having conv(T ) as a facet. We have |U (T )| = 2, since the S i 's are all of size 2.

Note that Ω i +1 = Ω i U (T i ), where denotes the symmetric difference (defined for two sets A and

B by A B = (A ∪ B ) \ (A ∩ B )). Since |Ω 0 | = 0 and |U (T i )| = 2 for all i ∈ [r ], we have that |Ω i | is even for all i ∈ [r ]. In particular, |Ω r | is even.
Considering more generally the S i 's being of even size, instead of being simply pairs, we get the following theorem with an almost identical proof. This theorem was given in [START_REF] Deza | A combinatorial approach to colourful simplicial depth[END_REF].

Theorem 1.5.2 (Extension of the Octahedron lemma). Consider d + 1 sets of points

S 1 , . . . , S d +1 in R d and a point p ∈ R d , all together in general position. If |S i | is even for all i ∈ [d + 1],
then the point p is covered by an even number of colorful simplices.

We now show that Theorems 1.5.1 and 1.5.2 are equivalent. It is clear that Theorem 1.5.2 implies the Octahedron lemma. The converse is also true: we can prove Theorem 1.5.2 from the Octahedron lemma.

Proof. Consider d + 1 sets S 1 , . . . , S d +1 , with |S i | even for all i ∈ [d + 1] and a point p ∈ R d in general position. For any X = X 1 ∪ • • • ∪ X d +1 with X i ⊆ S i and |X i | = 2
for all i , define N (X) to be the number of colorful simplices, formed with points in X, containing p. Let N be the total number of colorful simplices containing p. We have

X N (X) = N d +1 i =1 (|S i | -1), since every colorful simplex containing p is counted d +1 i =1 (|S i | -1)
times in this sum. The Octahedron lemma ensures that N (X) is even for all X.

Since d +1 i =1 (|S i | -1)
is odd, N is also even.

Other colorful results in geometry

We end this chapter with two colorful results in geometry, more or less related to the colorful Carathéodory theorem.

Colored Tverberg's theorem

Given d + 1 sets of points S 1 , . . . , S d +1 in R d , the problem, known as colored Tverberg, aims at finding a point in the convex hulls of many disjoint colorful sets. For d , r ∈ Z + we define t (d , r ) to be the minimal integer, independent from the S i 's, such that if

|S i | ≥ t (d , r
) for all i , then there are r disjoint colorful sets whose convex hulls intersect.

The following colored Tverberg theorem was conjectured by Bárány, Füredi, and Lovász in 1990 [START_REF] Bárány | On the number of halving planes[END_REF].

Theorem 1.6.1. t (d , r ) is finite for all d , r ∈ Z + .
A proof of t (d , 2) = 2 was first given by Lovász. His proof can be found in a paper by Bárány and Larman [START_REF] Bárány | A colored version of Tverberg's theorem[END_REF], in which they also proved that t (1, r ) = t (2, r ) = r , and conjectured that t (d , r ) = r for all d , r ∈ Z + .

The general case was first proved by Živaljević and Vrećica [START_REF] Živaljević | The colored Tverberg's problem and complexes of injective functions[END_REF], who also showed that for r prime, we have t (d , r ) ≤ 2r -1. Later Blagojević, Matschke, and Ziegler proved that for r + 1 prime, we have t (d , r ) = r , via a topological proof [START_REF] Blagojević | Optimal bounds for the colored Tverberg problem[END_REF]. The conjecture of Bárány and Larman remains open.

Colorful Helly's theorem

The second result we present here, known as colorful Helly theorem, was introduced by Lovász and presented by Bárány in 1982, in his paper on the colorful Carathéodory theorem [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF].

Other colorful results in geometry

Theorem 1.6.2 (Colorful Helly's theorem, Lovász [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF]). Let F 1 , . . . ,

F d +1 be d + 1 finite families of convex sets in R d . If for all choices of d + 1 sets F 1 ∈ F 1 , . . . , F d +1 ∈ F d +1 , we have d +1 i =1 F i = , then F ∈F i F = for some i ∈ [d + 1].
The usual Helly theorem, states that, given a family of n convex sets, if every d + 1 of them intersect, then they all intersect. This result is a corollary of Theorem 1.6.2, by taking

F 1 = • • • = F d +1 .
The key tools used by Bárány for proving Theorem 1.6.2 are the classical Helly theorem and the colorful Carathéodory theorem.

Computational problems

In 1997, Bárány and Onn defined algorithmic and complexity problems related to the colorful Carathéodory theorem [START_REF] Bárány | Colourful linear programming and its relatives[END_REF], giving birth to colorful linear programming. In their paper, the complexity question raised by the colorful Carathéodory theorem is referred as an "outstanding problem on the borderline of tractable and intractable problems".

In addition to provide a theoretical challenge, we have seen in Chapter 1 that the colorful Carathéodory theorem has several applications in discrete geometry (e.g. Tverberg partition, First selection lemma, see [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF]). Any efficient algorithm computing such a colorful set T would benefit these applications. In this chapter, we formally define three problems related to the colorful Carathéodory theorem. Section 2.1 focuses on the algorithmic question raised by the colorful Carathéodory theorem, Section 2.2 deals with the more general decision problem, usually known as colorful linear programming, and Section 2.3 tackles the algorithmic question raised by the Octahedron lemma. The last section focuses on combinatorial cases of these three problems. To ease the discussion on the complexity, the inputs of all the problems considered in this chapter are rational numbers.

Colorful linear programming, TFNP version 2.1.1 Definition

Given a colorful point configuration S 1 , . . . , S d +1 with the S i 's being positively dependent colorful sets, the colorful Carathéodory theorem ensures the existence of a positively dependent colorful set. We formally define the problem of finding such a colorful set T .

COLORFUL LINEAR PROGRAMMING (TFNP version)

Input. A configuration of d + 1 positively dependent sets of points S 1 , . . . ,

S d +1 in Q d .
Task. Find a positively dependent colorful set.

It is a search problem, which more specifically belongs to the TFNP class. A search problem is like a decision problem but a certificate is sought in addition to the 'yes' or 'no' answer. The class of search problems whose decision counterpart has always a 'yes' answer is called TFNP, where TFNP stands for "Total Function Non-deterministic Polynomial". As we have already mentioned, the complexity status is still open.

A more general problem, still in TFNP, has been recently proved to be PLS-complete by Mülzer and Stein [START_REF] Mülzer | Complexity of finding nearest colorful polytopes[END_REF]. The PLS class, where PLS stands for "Polynomial Local Search", is a subclass of the TFNP class and contains the problems for which local optimality can be verified in polynomial time [START_REF] Johnson | How easy is local search[END_REF]. Besides, the new proof of the colorful Carathéodory theorem, given in Section 1.3.2 and using Sperner's lemma, gives the intuition that the problem should belong to the class PPAD. The PPAD class, where PPAD stands for "Polynomial Parity Argument on Directed Graphs", is also a subclass of the TFNP class, see Section 2.3 for more details on this complexity class.

As for the colorful Carathéodory theorem, we have a linear programming formulation of this problem. Following is the TFNP problem corresponding to Theorem 1.2.3.

COLORFUL LINEAR PROGRAMMING (linear programming TFNP version)

Simplexification of Bárány-Onn algorithm

The original proof of the colorful Carathéodory theorem by Bárány naturally provides an algorithm computing a solution to this problem. This algorithm, known as the Bárány-Onn algorithm, was analyzed in [START_REF] Bárány | Colourful linear programming and its relatives[END_REF]. It is a pivot algorithm roughly relying on computing the closest to 0 facet of a simplex. Although not polynomial, this algorithm is quite efficient, as stated by Deza et al. through an extensive computational study [START_REF] Deza | The colourful feasibility problem[END_REF].

Algorithm

The pivoting algorithm proposed by Bárány and Onn for finding a positively dependent colorful set goes roughly as follows. The input is the sets S 1 , . . . , S d +1 of points in Q d , each of cardinality d + 1 and positively dependent. All points are moreover assumed to be in general position.

Bárány-Onn algorithm

• Choose a first colorful set T 1 of size d + 1 and let i := 0.

• Repeat:

-Let i := i + 1.
-If 0 ∈ conv(T i ), stop and output T i .

-Otherwise, find F i ⊆ T i of cardinality d such that aff(F i ) separates T i \ F i from 0; choose in the half-space containing 0 a point t of the same color as the singleton

T i \ F i ; define T i +1 := F i ∪ {t }.
Since each conv(S i ) contains 0, there is always a point of each color in the half-space delimited by aff(F i ) and containing 0. It explains why a point t as in the algorithm can always be found as long as the algorithm has not terminated.

The technical step is the way of finding the subset F i and requires a distance computation or a projection [START_REF] Bárány | Colourful linear programming and its relatives[END_REF], or the computation of the intersection of a fixed ray and conv(T i ) [START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF]. Deza et al. [START_REF] Deza | The colourful feasibility problem[END_REF] proceed to an extensive computational study of algorithms solving this problem, with many computational experiments. In addition to some heuristics, "multi-update" versions are also proposed, but they do not avoid this kind of operations.

We propose a modified approach that avoids this kind of computation. We add a dummy point v and define the following optimization problem. min z

s.t. Aλ + z v =       0 . . . 0 1       λ ≥ 0, z ≥ 0,
where v = (v , 1) and where A is the (d +1)×(d +1) 2 matrix whose columns are the points of d +1 i =1 S i with an additional 1 on the (d + 1)th row. This optimization problem simply looks for an expression of 0 as a convex combination of the points in {v } ∪ d +1 i =1 S i with a minimal weight on v . Especially, if 0 ∈ conv( i S i ), the optimal value is 0. The idea consists in seeking an optimal basis, with the terminology of linear programming, which in addition is required to be colorful. The colorful Carathéodory theorem ensures that such a basis exists. Now, choose a first transversal F 1 , which is a colorful set of cardinality d . Choose the dummy point v so that F 1 ∪ {v } contains 0 in the interior of its convex hull. Note that F 1 ∪ {v } is a feasible basis. The algorithm proceeds with simplex pivots, going from feasible colorful basis to feasible colorful basis, until an optimal colorful basis is found. We start with i := 0. We repeat then

-Let i := i + 1.
-Choose a point t of the missing color in F i with negative reduced cost. The reduced costs are computed according to the current basis F i ∪ {v }.

-Proceed to a simplex pivot operation with t entering the current basis.

-If v leaves the basis, stop and output F i ∪ {t } (it is an optimal colorful basis).

-Otherwise, define F i +1 to be the new basis minus v .

This algorithm eventually finds a positively dependent colorful set because of the following lemma. The remaining arguments are exactly the same as above: as long as a positively dependent colorful set has not been found, there is a point of the missing color in the half-space delimited by aff(F i ) and containing 0.

Lemma 2.1.1. The points in the half-space delimited by aff(F i ) and containing 0 are precisely the points with a negative reduced cost.

Proof. Let F i = {u 1 , . . . , u d } and let t be any other point in

d +1 j =1 S j \ F i . Consider x 1 , . . . , x d , r, s ∈ R such that r t + sv + d i =1 x i u i = 0, (2.1)
with r > 0 and r + s + d i =1 x i = 0. We have s = 0 by genericity assumption. The reduced cost of t is exactly s/r . Therefore, proving the lemma amounts to prove that s is negative exactly when t is in the half-space delimited by aff(F i ) and containing 0.

To see this, note that Equation (2.1) can be rewritten

r (t -u 1 ) + s(v -u 1 ) + d i =2 x i (u i -u 1 ) = 0. (2.2)
Now, take the unit vector n orthogonal to aff(F i ) and take the scalar product of Equation (2.2) and n. It gives

r n • (t -u 1 ) + sn • (v -u 1 ) = 0
and the conclusion follows since v and 0 are in the same half-space delimited by aff(F i ).

This approach is reminiscent of the "Phase I" simplex method, which is searching for a first feasible basis by solving an auxiliary linear program whose optimal value is 0 on such a basis.

Numerical results

We implemented our algorithm in C++. The tests are performed on a PC Intel ® Core ™ i3-2310M, with two 64-bit CPUs, clocked at 2.1 GHz, with 4 GB RAM. The instances are provided by five random generators, implemented by Huang in MATLAB. All the generators provide instances of (d + 1) 2 points in general position on the unit sphere, partitioned into d + 1 colors and such that the origin 0 is in the convex hull of each color. Descriptions of the generators can be found in [START_REF] Huang | MATLAB code for Colourful Linear Programming[END_REF]. At each iteration, we choose the entering point t that has the most negative reduced cost.

Table 2.1 presents the computational results on 50 instances by dimension and by generators. The columns "time" give the average execution time of the algorithm in milliseconds. The columns "# pivots" give the average number of pivots. The entry corresponding to the "tube" case in dimension 384 is empty, since we faced cycling behavior for some instances (we felt that adding anti-cycling pivot rules was not imperative for our experiments). We compared these results with those of the Bárány-Onn algorithm presented in the paper by Deza et al. [START_REF] Deza | The colourful feasibility problem[END_REF] using the same generators. In general, our number of pivots is slightly larger than what they get. Regarding the time per iteration, it is hard to draw a conclusion since their implementation was done in MATLAB and since they used a different machine (a server with eight 64-bit CPUs, clocked at 2.6 GHz, with 64 GB RAM). However, the time per iteration of our algorithm is of the order of a thousand times smaller.

Colorful linear programming, decision version

In addition to the TFNP version of COLORFUL LINEAR PROGRAMMING, Bárány and Onn formulated the following problem, which is in a sense more general.

COLORFUL LINEAR PROGRAMMING

Input. A configuration of k sets of points S 1 , . . . , S k in Q d .
Task. Decide whether there exists a positively dependent colorful set for this configuration of points. If there is one, find it.

The problem of computing the colorful set T of the colorful Carathéodory theorem corresponds to the special case of COLORFUL LINEAR PROGRAMMING with k = d + 1 and 0 ∈ d +1 i =1 conv(S i ). Bárány and Onn showed that the case of COLORFUL LINEAR PROGRAMMING with k = d is NP-complete even if each S i is of size 2, proving that the general case is NP-complete as well. It contrasts with the TFNP version of COLORFUL LINEAR PROGRAMMING. In this version, when each S i is of size 2, we clearly have a polynomial special case: select one point in each S i , find the linear dependency, and change for the other point in S i for those having a negative coefficient.

For a fixed q ∈ Z, we define CLP(q) to be the COLORFUL LINEAR PROGRAMMING problem with the additional constraint that kd = q. We have the two following lemmas.

Lemma 2.2.1. If CLP(q) is NP-complete, then CLP(q -1) is also NP-complete. Proof. Define d = d + 1. Let S 1 , . . . , S k in R d be an instance with k = d + q.
Embedding this instance in R d by adding a d th component equal to 0, we get an instance with k = d + q -1, every solution of which provides a solution for the case k = d + q, and conversely. This latter case being NP-complete, we get the conclusion. Lemma 2.2.2. If CLP(q) is NP-complete, then CLP(q + 1) is also NP-complete. and S k+2 entirely located at coordinate (0, . . . , 0, 1). We have thus an instance with k = d + q + 1, every solution of which provides a solution for the case k = d + q, and conversely. This latter case being NP-complete, we get the conclusion.

Combining the previous two lemmas, we obtain the following theorem.

Theorem 2.2.3. CLP(q) is NP-complete for any fixed q ∈ Z.

Proof of Theorem 2.2.3. CLP(0) is NP-complete according to Theorem 6.1 in [START_REF] Bárány | Colourful linear programming and its relatives[END_REF]. Lemmas 2.2.1 and 2.2.2 allow to conclude.

Polynomially checkable sufficient conditions ensuring the existence of a positively dependent colorful set exist: the condition of the colorful Carathéodory theorem is one of them. More general polynomially checkable sufficient conditions when k = d +1 are given in [START_REF] Arocha | Very colorful theorems[END_REF][START_REF] Holmsen | Points surrounding the origin[END_REF][START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF]. However, the fact that CLP(1) is NP-complete implies that there are no polynomially checkable conditions that are simultaneously sufficient and necessary for a positively dependent colorful set to exist when k = d + 1, unless P=NP. Remark 2.2.4. The instances built in the proof of Lemma 2.2.2 are not in general position, since 0 and the S i 's with i ≤ k are all in the same hyperplane. We could wonder whether the case k = d + 1 remains NP-complete when the points are in general position. The answer is yes, and we explain how to reduce the instance built in the proof of Lemma 2.2.2 to an instance in general position. First, the sets S k+1 and S k+2 can be slightly perturbed without changing the conclusion. Second, we slightly move 0 into one of the half-spaces delimited by the hyperplane containing the S i 's for i ≤ k. We choose the half-space containing S k+1 and S k+2 . This move must be sufficiently small so that 0 does not traverse another hyperplane generated by d points in k+2 i =1 S i . All coordinates being rational, Cramer's formula allows to compute a length of the displacement that ensures this condition. Third, we move each point of the k i =1 S i independently along a line originating from 0.

The following problem gives a linear programming formulation of COLORFUL LINEAR PROGRAMMING. As noted before, by a basic geometric argument, when there are no solutions to the system Ax = 0, x ≥ 0 , deciding whether b is a positive combination of the columns of A is equivalent to deciding if some point b is in the convex hull of the columns of Ã, with b ∈ R d -1 and à ∈ R (d -1)×n . Hence, adding the condition that there are no solutions to the system Ax = 0, x ≥ 0 , the two formulations of COLORFUL LINEAR PROGRAMMING are reducible one to the other.

COLORFUL LINEAR PROGRAMMING (linear programming decision version)

Find another colorful simplex 2.3.1 Main result

Another problem related to COLORFUL LINEAR PROGRAMMING was proposed by Meunier and Deza [START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF] as a byproduct of the Octahedron lemma, see Section 1.5. The problem we call FIND ANOTHER COLORFUL SIMPLEX is the following. Another positively dependent colorful set exists for sure. Indeed, by a slight perturbation, we can assume that all points are in general position, see Section 1.1.3. If there were only one positively dependent colorful set, there would also be only one positively dependent colorful set in the perturbed configuration, which violates the evenness property stated by the Octahedron lemma. In their paper, Meunier and Deza question the complexity status of this problem. We solve the question by proving that it is actually a generalization of the problem of computing a Nash equilibrium in a bimatrix game.

FIND ANOTHER COLORFUL SIMPLEX

Proposition 2.3.1. FIND ANOTHER COLORFUL SIMPLEX is PPAD-complete.
In [START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF], it was noted that FIND ANOTHER COLORFUL SIMPLEX is in PPA. The class PPA, also defined by Papadimitriou in 1994 [START_REF] Papadimitriou | On the complexity of the parity argument and other inefficient proofs of existence[END_REF], contains the class PPAD. PPA contains the problems that can be polynomially reduced to the problem of finding another degree 1 vertex in a graph whose vertices all have degree at most 2 and in which a degree 1 vertex is already given. The graph is supposed to be implicitly described by the neighborhood function, which, given a vertex, returns its neighbors in polynomial time. The PPAD class is the subclass of PPA for which the implicit graph is oriented and such that each vertex has an outdegree at most 1 and an indegree at most 1. The problem becomes then: given an unbalanced vertex, that is a vertex v such that deg

+ (v) + deg -(v) = 1,
find another unbalanced vertex. See [START_REF] Papadimitriou | On the complexity of the parity argument and other inefficient proofs of existence[END_REF] for further precisions.

We prove Proposition 2.3.1 in the next section, by first showing that FIND ANOTHER COLORFUL SIMPLEX is in PPAD. We proceed by showing that the existence of the other positively dependent colorful set is a consequence of Sperner's lemma [START_REF] Sperner | Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes[END_REF].

Our method for proving that FIND ANOTHER COLORFUL SIMPLEX belongs to PPAD is adaptable for other complementarity problems, among them BIMATRIX, see below the definition of this problem. We believe that our method is new. It avoids the use, as in [START_REF] Chen | Settling the complexity of computing two-player Nash equilibria[END_REF][START_REF] Kintali | Reducibility among fractional stability problems[END_REF][START_REF] Papadimitriou | On the complexity of the parity argument and other inefficient proofs of existence[END_REF][START_REF] Végh | Oriented Euler complexes and signed perfect matchings[END_REF], of oriented primoids or oriented duoids defined by Todd [START_REF] Todd | Orientation in complementary pivot algorithms[END_REF].

FIND ANOTHER is PPAD-complete

One of the multiple versions of Sperner's lemma is the following theorem, proposed by Scarf [START_REF] Scarf | The approximation of fixed points of a continuous mapping[END_REF], which involves a triangulation of a sphere, whose vertices are labeled, see Section 1.3.2 for another version of this theorem.

Theorem 2.3.2 (Sperner's lemma). Let T be a triangulation of an n-dimensional sphere S n and let V (T) be its vertex set. Assume that the elements of V (T) are labeled according to a map λ : V → E , where E is some finite set. If E is of cardinality n + 1, then there is an even number of fully-labeled n-simplices.

We first have the following proposition.

Proposition 2.3.3. FIND ANOTHER COLORFUL SIMPLEX is in PPAD.

Proof. By a perturbation argument, we can assume the points to be in general position, see Section 1.1.3 and the references therein for a description of such a polynomial-time computable perturbation. The proof consists then in proving the existence of another positively dependent colorful set via a polynomial reduction to Sperner's lemma.

We define a simplicial complex K with vertex set d +1 i =1 S i :

K = σ ⊆ d +1 i =1 S i | d +1 i =1 S i \ σ is positively dependent .
Since any superset of a positively dependent set is a positively dependent set, K is a simplicial complex. The points being in general position, the dimension of K is Chapter 2. Computational problems

2(d + 1) -(d + 1) -1 = d . Actually, K is a triangulation of S d .
It can be seen using Gale transform and Corollary 5.6.3 (iii) of [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF]. Now, for a vertex v of K, define λ(v) to be its color, i.e. the index i such that v ∈ S i . Any fully-labeled simplex σ of K is such that d +1 i =1 S i \ σ is a positively dependent colorful set and conversely. There is thus an explicit one-to-one correspondence between the fully-labeled simplices of K and the positively dependent colorful sets. Applying Theorem 2.3.2 (Sperner's lemma) with T = K, n = d , and E = [d + 1] shows that there is an even number of fully-labeled simplices in K, and hence, an even number of positively dependent colorful sets. Since there is a proof of Sperner's lemma using an oriented path-following argument [START_REF] Scarf | The approximation of fixed points of a continuous mapping[END_REF][START_REF] Meunier | Computing and proving with pivots[END_REF] and since the triangulation here can easily be encoded by a Turing machine computing the neighbors of any simplex in the triangulation, i.e. the ones sharing d points with it, in polynomial time, FIND ANOTHER COLORFUL SIMPLEX is in PPAD.

We now derive the hardness of FIND ANOTHER COLORFUL SIMPLEX from the complexity of BIMATRIX.

Proposition 2.3.4. FIND ANOTHER COLORFUL SIMPLEX is PPAD-complete.
The prove uses BIMATRIX we describe now.

A bimatrix game involves two m × n matrices with real coefficients A = (a i j ) and B = (b i j ). There are two players. The first player chooses a probability distribution on {1, . . . , m}, the second a probability distribution on {1, . . . , n}. Once these probability distributions have been chosen, a pair ( ī , j ) is drawn at random according to these distributions. The first player gets a payoff equal to a ( ī , j ) and the second a payoff equal to b ( ī , j ) . A Nash equilibrium is a choice of distributions in such a way that if a player changes his distribution, he will not get in average a strictly better payoff.

Let ∆ k be the set of vectors x ∈ R k + such that k i =1 x i = 1.
Formally, a Nash equilibrium is a pair (y * , z * ) with y * ∈ ∆ m and z * ∈ ∆ n such that y T Az * ≤ y * T Az * for all y ∈ ∆ m and y * T B z ≤ y * T B z * for all z ∈ ∆ n .

(2.

3)

It is well-known that if the matrices have rational coefficients, there is a Nash equilibrium with rational coefficients, which are not too large with respect to the input. BIMATRIX is the following problem: given A and B with rational coefficients, find a Nash equilibrium. Papadimitriou showed in 1994 that BIMATRIX is in PPAD [START_REF] Papadimitriou | On the complexity of the parity argument and other inefficient proofs of existence[END_REF]. Later, Chen, Deng, and Teng [START_REF] Chen | Settling the complexity of computing two-player Nash equilibria[END_REF] proved its PPAD-completeness.

A combinatorial approach to these equilibria consists in studying the complementary solutions of the two systems (2.5)

By complementary solutions, we mean a solution x A of (2.4) and a solution x B of (2.5) such that x A • x B = 0. Indeed, complementary solutions with supp(x A ) = {n + 1, . . . , n + m} or supp(x B ) = {1, . . . , n} give a Nash equilibrium. This point of view goes back to Lemke and Howson [START_REF] Lemke | Equilibrium points of bimatrix games[END_REF]. A complete proof within this framework can be found in Remark 6.1 of [START_REF] Meunier | Computing and proving with pivots[END_REF].

Proof of Proposition 2.3.1. We prove that the following version of FIND ANOTHER COL-ORFUL SIMPLEX with cones is PPAD-complete. By an usual geometric argument, this version is equivalent to FIND ANOTHER COLORFUL SIMPLEX.

FIND ANOTHER COLORFUL CONE

Input. A configuration of d + 1 pairs of points S 1 , . . . , S d +1 in Q d +1 , an additional point p in Q d +1 such that conv({p} ∪ d +1 i =1 S i )
does not contain 0, and a colorful set T such that p ∈ pos(T ). Task. Find another colorful set T such that p ∈ pos(T ).

The proof uses a reduction of BIMATRIX to FIND ANOTHER COLORFUL CONE. Consider an instance of BIMATRIX. First note that we can assume that all coefficients of A and B are positive. Indeed, adding the same constant to all entries of both matrices does not change the game. Build the (m

+ n) × (2(m + n)) matrix M = A I m 0 0 0 0 I n B T .
We denote by M i the i th column of M . Note that the vector u = (1, . . . , 1) ∈ R n+m is in the conic hull of T = {M n+1 , . . . , M n+m , M n+m+1 , . . . , M 2n+m }. Indeed, the corresponding sub-matrix is the identity matrix.

Let S i be the pair {M i , M m+n+i } for i = 1, . . . , m + n. Since all coefficients of A and B are positive, 0 is not in the convex hull of the columns of M and u. A polynomial time algorithm solving FIND ANOTHER COLORFUL CONE with T as input set would find another colorful set T such that u ∈ pos(T ). The decomposition of u on the points in T gives a vector x such that M x = u, x i x m+n+i = 0 for i = 1, . . . , m + n, and supp(x) = {n + 1, . . . , 2n + m}. Such an x can be written (x A , x B ) with x A , x B ∈ R m+n + satisfying x A • x B = 0 and such that either supp(x A ) = {n + 1, . . . , n + m} or supp(x B ) = {1, . . . , n}. In other words, x A and x B are complementary solutions and this would find a Nash equilibrium. BIMATRIX being PPAD-complete, Proposition 2.3.3 implies therefore that FIND ANOTHER COLORFUL SIMPLEX is PPAD-complete.

This proof shows that FIND ANOTHER COLORFUL SIMPLEX is more general than computing complementary solutions of Equations (2.4) and (2.5). In [START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF], a pivoting algorithm for solving FIND ANOTHER COLORFUL SIMPLEX is proposed. It reduces to the classical pivoting algorithm due to Lemke and Howson [START_REF] Lemke | Equilibrium points of bimatrix games[END_REF] used for computing such complementary solutions, see Section 3.2 for more details on this subject. Remark 2.3.5 (Complexity of Sperner's lemma). In the proof of Proposition 2.3.3, we reduced FIND ANOTHER COLORFUL SIMPLEX to the following Sperner-type problem.

Let T be a triangulation of the d -dimensional sphere involving 2(d + 1) vertices and let λ : V (T) → {1, . . . , d + 1} be a labeling. Given a fully-labeled simplex; find another fullylabeled simplex. Proposition 2.3.1 shows that this problem is actually PPAD-complete, even if each label appears exactly twice. Sperner-type problems have already been proved to be PPAD-complete [START_REF] Chen | On the complexity of 2D discrete fixed point problem[END_REF][START_REF] Papadimitriou | On the complexity of the parity argument and other inefficient proofs of existence[END_REF], but these latter problems are in fixed dimension, with an exponential number of vertices, and with a labeling given by an oracle, while the Sperner-type problem we introduced has an explicit description of the vertices and of the labeling. Note that the number of vertices is small. A computational problem with similar features has been proposed in a paper by Király and Pap [START_REF] Király | PPAD-completeness of polyhedral versions of Sperner's Lemma[END_REF], but it involves a polyhedral version of Sperner's lemma distinct from the classical Sperner's lemma. Remark 2.4.12 in Section 2.4.4 will exhibit some polynomial cases of the Sperner-type problem we introduced here.

Reduction of BIMATRIX to COLORFUL LINEAR PROGRAMMING Proposition 2.3.6. There is an explicit polynomial reduction of BIMATRIX to the decision version of COLORFUL LINEAR PROGRAMMING.

This proposition provides a concrete illustration of the fact that NP-complete problems are harder than PPAD problems. A similar method appears in [START_REF] Gilboa | Nash and correlated equilibria: Some complexity considerations[END_REF].

Proof of Proposition 2.3.6. Let A be an algorithm solving COLORFUL LINEAR PROGRAM-MING. We refer here to the decision problem of Section 2.2. We describe an algorithm solving FIND ANOTHER COLORFUL SIMPLEX, and therefore BIMATRIX because of the reduction described in Section 2.3.2, by calling exactly d + 1 times A . We get this way a polynomial reduction of BIMATRIX to COLORFUL LINEAR PROGRAMMING.

The input is given by the d + 1 pairs of points S 1 , . . . , S d +1 and the positively dependent colorful set T . The algorithm selects successively a point in each of the S i 's. Each iteration consists in testing with the help of A which point of S i is in a positively dependent colorful set compatible with the already selected points and in selecting such a point, with the priority given to S i \ T . A typical iteration is

• Define S i := S i \ T ; • Apply A to S 1 , . . . , S i , S i +1 , . . . , S d +1 ;
• if the answer is 'no', define instead S i := S i ∩ T .

At the end, the algorithm outputs d +1 i =1 S i .

Since we know that there is another positively dependent colorful set, the answer will be 'yes' for at least one i . The returned colorful simplex is therefore a positively dependent colorful set distinct from T . This algorithm returns another positively dependent colorful set after calling d + 1 times A .

Remark 2.3.7. The same approach shows that the TFNP version of COLORFUL LINEAR PROGRAMMING is polynomially reducible to the general version of COLORFUL LINEAR PROGRAMMING.

Combinatorial cases of colorful linear programming and analogues

In the paper proving the colorful Carathéodory theorem, Bárány gives an application of this theorem to colorful circuits in a directed graph, suggested by Frank and Lovász.

We consider here the computational problems raised by this application as well as additional combinatorial cases on directed graphs. The results of Sections 2.4.2 and 2.4.3 were found in collaboration with Wolfgang Mülzer and Yannik Stein.

Colorful linear programming, TFNP version

Even if the complexity of the TFNP version of COLORFUL LINEAR PROGRAMMING in the general case is unknown, the two problems presented here are polynomial cases of this problem.

Proposition 2.4.1. Let D = (V, A) be a directed graph with n vertices. Let C 1 , . . . ,C n be pairwise arc-disjoint circuits of D. Then there exists a circuit C sharing at most one arc with each of these C i . Moreover, such a circuit can be computed in polynomial time.

The existence of the colorful circuit as a consequence of the colorful Carathéodory theorem has already been noted and is attributed to Frank and Lovász [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF]. We give here another proof of existence, providing a polynomial time algorithm to compute the circuit.

Proof. Define a bipartite graph G = (V ∪ [n], E ). The vertices in V are identified with the vertices of D and the vertices in [n] are identified with the colors. There is an edge vi ∈ E if the vertex v belongs to C i . Suppose first that each X ⊆ V has a neighborhood in G of size at least |X |. Hall's marriage theorem ensures the existence of a perfect matching in the bipartite graph. We can then select for each vertex v ∈ V an arc a in δ -(v) belonging to a distinct C i . The subgraph induced by these arcs contains a circuit C as required.

Otherwise, there is a subset X ⊆ V with a neighborhood in G of cardinality at most |X |-1. One can remove X from D and apply induction. Note that the existence of such an X can be decided in polynomial time by a classical maximum matching algorithm, which also provides the set X itself if it exists.

The existence statement of the next proposition is a consequence of the conic version of the colorful Carathéodory theorem (Theorem 1.2.2). We provide a direct proof based on a greedy algorithm.

Proposition 2.4.2. Let D = (V, A) be a directed graph with n vertices. Let s and t be two vertices, and P 1 , . . . , P n-1 be pairwise arc-disjoint s-t paths. Then there exists an s-t path P sharing at most one arc with each P i . Moreover, such a path can be computed in polynomial time.

Proof. We build an arborescence rooted at s, step by step. We start with X = {s}. At each step, X is the set of vertices reachable from s in the partial arborescence. At step i , if X does not contain t , choose an arc a of P i belonging to δ + (X ) and add to X the endpoint of a not yet in X . This arc exists since by direct induction X is of cardinality i at step i and the s-t path P i leaves X .

Colorful linear programming, decision version

The decision version of COLORFUL LINEAR PROGRAMMING is NP-complete in general.

In this section, we show that the problem remains NP-complete in some combinatorial cases, but is polynomial in some others. We mainly focus on three cases: colorful path, colorful circuit, and colorful arborescence. Proof. The proof works by a reduction of 3-SAT. Consider an instance of 3-SAT: a set of variables {x 1 , . . . , x n } and a set of clauses C 1 , . . . ,C m , each containing three literals, a clause being a disjunction of literals. 3-SAT aims at deciding whether there is an assignment of the variables satisfying all the clauses. This problem is NP-complete, see [START_REF] Garey | Computers and intractability: A Guide to the Theory of NP-Completeness[END_REF].

COLORFUL PATH

Input. A directed graph D = (V, A),
For each variable x, we define p x the number of clauses containing the literal x and n x the number of clauses containing x. We define then p x n x colors λ i , j (x) where C i is a clause containing x and C j is a clause containing x.

We define a directed graph D = (V, A) as follows. For each clause C i we define a vertex v i . We also define a source v 0 ∈ V . For all i ∈ [m] we define three paths from v i -1 to v i , one for each literal in the clause C i . If the literal is positive, i.e. of the form x, the path from v i -1 to v i corresponding to this literal has a number of arcs equal to the number of clauses containing the literal x, colored with the color λ i , j (x) where C j is a clause containing x. Otherwise, if the literal is negative, i.e. of the form x, the path from v i -1 to v i corresponding to this literal has a number of arcs equal to the number of clauses containing the literal x, colored with the color λ j ,i (x) where C j is a clause containing x. In both cases, the path might be empty, in which case v i -1 and v i are mingled. See Figure 2.1 for an illustration of this construction.

Deciding whether there is a satisfying assignment is equivalent to deciding whether there is a colorful path from v 0 to v m . Indeed, suppose that such a colorful path exists.

v 0 v 1 v 2 v 3 λ 1,3 (x 1 ) λ 1,2 (x 2 ) λ 2 , 1 ( x 3 ) λ 3 , 1 ( x 3 ) λ 2,3 (x 1 ) λ 2,1 (x 3 ) λ 3,1 (x 3 ) λ 3,2 (x 2 ) λ 1,2 (x 2 ) λ 3,2 (x 2 ) λ 1 , 3 ( x 1 ) λ 2 , 3 ( x 1 ) Figure 2.1: Construction of D for the formula (x 1 ∨ x 2 ∨ x3 )∧(x 1 ∨ x2 ∨ x 3 )∧( x1 ∨ x2 ∨ x 3 )
Then, given a colorful path, we can assign values to the variables with the following rules. For all i ∈ [m], if the colorful path goes from v i -1 to v i through the edges corresponding to the literal x, then the corresponding variable is given the value 'true' (respectively 'false' if the literal is a negation, i.e. of the form x). This assignment is consistent, no variables is given both values true and false, since the path is colorful. Moreover, at least one literal of each clause is satisfied, hence the formula is satisfied. Conversely, if there is a satisfying assignment, we can choose for each i ∈ [m] a literal satisfied in the clause C i and the corresponding path from v i -1 to v i in D. Concatenating these paths, we obtain a colorful path from v 0 to v m . Indeed, in any subpath between two consecutives v i 's there are no two arcs of the same color, by construction. Moreover, if there were two arcs of the same color, say λ i , j (x), on the choosen path, it would then mean that x has been assigned a positive value to satisfy clause C i and a negative one to satisfy C j , which leads to a contradiction.

Since 3-SAT is NP-complete, COLORFUL PATH is NP-complete as well.

A proof of the NP-completeness of an undirected version of COLORFUL PATH can be found in [START_REF] Chakraborty | Hardness and algorithms for rainbow connection[END_REF]. Their proof can also be adapted to prove Proposition 2.4.3. Proof. We can easily reuse the proof of Proposition 2.4.3 for this proof, just by adding an arc from v m to v 0 .

COLORFUL CIRCUIT

Although COLORFUL LINEAR PROGRAMMING remains NP-complete for the two previous combinatorial cases, there are also some non trivial polynomial cases. COLORFUL ARBORESCENCE is one of these problems, since it corresponds to a standard matroid intersection problem, see Proposition 2.4.11. The two matroids involved here have the arcs of A as ground set. The independents of the first matroid are the colorful sets of arcs. The independents of the second matroid are the sets of arcs S ⊆ A satisfying |δ - S (x)| ≤ 1 for all vertices x ∈ V \ {s}, hence the bases of this matroid are the arborescences.

COLORFUL ARBORESCENCE

Input. A directed acyclic graph D = (V, A), whose arcs are partitioned into color classes C 1 , . . . ,C k and a root s ∈ V . Output. Decide whether there exists a colorful arborescence rooted at s.

Combinatorial cases of FIND ANOTHER

FIND ANOTHER COLORFUL SIMPLEX is PPAD-complete in general. We consider in this section the 'find another' versions of COLORFUL CIRCUIT and COLORFUL ARBORES-CENCE, which are both polynomial cases of FIND ANOTHER COLORFUL SIMPLEX or of its equivalent problem FIND ANOTHER COLORFUL CONE, defined in Section 2.3.2.

The following problem is a combinatorial case of FIND ANOTHER COLORFUL CONE. Proposition 2.4.5. Let D = (V, A) be an acyclic directed graph whose arcs are partitioned into n pairs C 1 , . . . ,C n , corresponding to colors, with n = |V | -1. If there is a colorful oriented arborescence of size n, rooted at a vertex s ∈ V , then there is another colorful oriented arborescence of size n also rooted at s, and it can be computed in polynomial time.

Proof. Let M D ∈ R (n+1)×2n be the incidence matrix of D, and b = (b v ) v∈V ∈ R n be defined by b s = n and b v = -1 for all v ∈ V \ {s}. An arborescence rooted at s is a solution of the linear program M D x = b, x ≥ 0. Since D is acyclic, 0 is not contained in the convex hull of the columns of M D . Hence, the rank of M D being n, the existence of the second arborescence is a consequence of the Octahedron lemma. To compute it, we use the following algorithm. Let T be the arborescence {a 1 , . . . , a n } ⊆ A. We start with i := 0. We repeat then 1. Set i := i + 1.

Let āi be the single arc in

C i \ a i .
3. Decide whether there is a colorful arborescence rooted at s and formed with arcs in { ā1 , . . . , āi } ∪ n k=i +1 C k .

4

. If the answer is 'no', let āi := a i .

Go back to step 1.

The algorithm ends when i = n + 1 and returns the set { ā1 , . . . , ān }. As the existence of another colorful tree is ensured by the colorful Carathéodory theorem, the algorithm eventually answers 'yes' in Step Since the cardinality of E is 2n, there is a cycle in G. Consider such a cycle L. Each vertex of G in [n] is incident to exactly two edges, and exactly one from M . Hence, the cycle is of even length and edges from the matching and edges outside the matching alternate on L.

We obtain a new perfect matching of G by taking the symmetric difference of M and L. This perfect matching corresponds to a set of arcs in D, all of distinct colors, such that each vertex has exactly one outgoing arc in this set. This set contains a colorful circuit.

Similar combinatorial problems

The problem COLORFUL ARBORESCENCE, encountered in the previous section, corresponds to a standard matroid intersection problem, where the two matroids are partition matroids. In this section we consider other matroid intersection problems, where one of the matroids is a partition matroid, providing matroidal counterparts of the results obtained for colorful linear programming. Proof. If a vertex has a label that appears only once on V (T), we remove it and its antipodal, and work on the boundary of a cross-polytope with a dimension smaller by one. Solving this new problem leads to a solution for the original problem. We repeat this process until each label appears exactly twice. Now, note that the simplices of the boundary of a cross-polytope form the independents of a matroid (it is a partition matroid). Considering the labels as colors, the conclusion follows then from Proposition 2.4.10.

With a similar proof (omitted), we also have the following proposition.

Proposition 2.4.14. Let T be the boundary of the (d + 1)-dimensional cross-polytope and let λ : V (T) → [d + 1] be any labeling. Deciding whether there is a fully-labeled simplex can be done in polynomial time. Moreover, if there is such a fully-labeled simplex, it can be found in polynomial time as well.

A generalization of linear programming and linear complementarity

In this chapter, we present links between colorful linear programming, linear programming, and linear complementarity problems. As a matter of fact, colorful linear programming generalizes both linear programming and the linear complementarity problem defined by Cottle in 1965. A better understanding of colorful linear programming would therefore benefit both of them. Linear programming and the linear complementarity problem are tools of mathematical programming among the most used in industry. Therefore we found it appropriate to dedicate a chapter of this manuscript to their links with colorful linear programming. Section 3.1 presents the links between colorful linear programming and linear programming and gives a common generalization of the two problems. Section 3.2 focuses on the relation between colorful linear programming, the problem FIND ANOTHER COLORFUL SIMPLEX of Section 2.3, and the linear complementarity problem. It gives in particular a colorful interpretation of the complementary pivot algorithm for computing a Nash equilibrium in bimatrix games, due to Lemke and Howson. As in Chapter 2, the inputs of the problems considered in this section are rational numbers, to ease the discussion on complexity.

A generalization of linear programming

Generalization of linear programs: feasibility, optimization

We consider a linear program as follows. In 1997, when they introduced colorful linear programming, Bárány and Onn also proved that the feasibility problem related to colorful linear programming generalizes the feasibility problem related to linear programming. Moreover, the colorful linear programming optimization problem generalizes the bounded linear programming optimization problem. Indeed, consider a bounded linear program, as the one above, and define à ∈ R d ×nd to be the matrix consisting of d copies of A, and c ∈ R nd consisting of d copies of c. Proof. Clearly, the feasibility problem is reducible to the optimization problem. Conversely, we can reduce an optimization problem to the feasibility problem, using binary the problem with µ = µ sup is the optimum.

à = (A, A, . . . , A), c =    c • • • c    .
Remark 3.1.2. The solutions of a colorful linear program are the vertices of the polyhedron corresponding to its non-colorful relaxation. Hence, a colorful linear optimization problem is either infeasible or bounded.

Remark 3.1.3. For linear programming, it is well-known that the optimization problem can be reduced to the feasibility problem. Indeed, if the optimum is finite, then the dual problem also admits a solution with same value, hence combining the primal and the dual problems, we simply have to solve a feasibility problem. Otherwise the value is -∞ if there is a feasible solution and +∞ if not. We were not able to adapt such arguments to colorful linear programming, as the notion of dual itself is not clear for colorful linear programming. Indeed, we do not know a general method that, given any minimization colorful linear program, provides a maximization colorful linear program whose optimal value gives a lower bound on the first problem.

Polyhedral interpretations, almost colorful connectivity

Given a colorful linear program, it is natural to consider its non-colorful relaxation.

As mentioned before, the colorful solutions correspond to particular bases of this relaxation. In this section we try to give a polyhedral interpretation of these solutions as vertices of the polyhedron

P = x ∈ R n | Ax = b, x ≥ 0 ,
when considering the conic version, and the polyhedron

P = x ∈ R n | A 1 • • • 1 x = b 1 , x ≥ 0 ,
when considering the convex version.

In the convex case, the polyhedron P is bounded. In the conic case, the polyhedron is bounded if and only if 0 is not contained in the conic hull of the columns of A. This latter case is actually equivalent to the convex case. Indeed, since the columns of A do not contain 0 in their convex hull, there is a hyperplane H , not containing 0 and intersecting all the half-lines defined by the column vectors of A. Let v i ∈ H be the intersection point of H and the half-line defined by the i th columns of A, for all i ∈ [n]. Then b is in the conic hull of the columns of A if and only if there is a positive combination of b in the convex hull of the v i 's. From now on, considering the convex case simply means that we consider cases with P being a polytope. In other words, an almost colorful solution is a feasible basis intersecting every color but An almost colorful feasible basis B of color i has at most two neighbors which are either colorful or almost colorful of color i . Indeed, there is exactly one color I j , such that |B ∩ I j | = 0. Consider the two variables indexed by I j as entering variables. For each of them, either we obtain another basis, which is either colorful or almost colorful of color i , depending on whether a variable from I i leaves the basis or not, or we have an infinite ray.

x 1 = 0 x 3 = 0 x 2 = 0 x 4 = 0 {2, 4} {1, 2} {1, 3} {3
A colorful feasible basis has at most one neighbor which is either colorful or almost colorful of color i . By the same argument, choosing the variable indexed by I i \ B to be the entering variable either gives another feasible basis, or corresponds to an infinite ray.

Remark 3.1.5. Consider an orientation of R d . A colorful basis B is positively oriented if the column vectors in A B are positively oriented with respect to the order of the colors I 1 , . . . , I d . Otherwise, it is negatively oriented. In the convex case, we can show that the paths in Proposition 3.1.4 have their endpoints of opposite orientation, i.e. the set of colorful bases and almost colorful bases of a fixed color form a collection of cycles and paths between a positively oriented colorful basis and a negatively oriented colorful basis. This result can be shown by slightly adapting the proof of Proposition 3.1.4, using the oriented pivots by Todd [START_REF] Todd | Orientation in complementary pivot algorithms[END_REF]. Furthermore, it shows that the number of positively oriented colorful solutions is equal to the number of negatively oriented solutions in the convex case. It also shows that two solutions of same orientation cannot be connected by an almost colorful path, in which the twice intersected color is fixed.

We end this section with an open question.

Open question. What can be said, in addition to Proposition 3.1.4, about the location of the colorful feasible bases and almost colorful feasible bases of any color on the 1-skeleton of the non-colorful relaxation?

A possible answer to this question would be that the colorful feasible bases and almost colorful bases of any color form a connected component of the 1-skeleton. If this statement were true, it would be sufficient to prove it in the case with all I i 's of size two. Using Proposition 3.1.4 and its oriented extension in the convex case, we note the following. Consider a convex case of colorful linear programming. Define a bipartite graph whose vertex sets are the positively oriented feasible colorful bases on the one hand and the negatively oriented feasible bases on the other hand. For each color i ∈ [d ] and each almost colorful path of color i given by Proposition 3.1.4, we define an edge between the two colorful bases connected by this path and color it with color i . This bipartite graph is d -regular and the coloring of the edges yields a proper edge-coloring.

A generalization of colorful linear programming

The results of this section were obtained in collaboration with Wolfgang Mülzer and Yannik Stein.

In this section, we consider a generalization of colorful linear programming, which is quite natural in regards to the applications of this problem, as the colorful diet programming. Given a partition of the variables, [n] = I 1 ∪ • • • ∪ I k , the aim of colorful linear programming is to find solutions of linear programs with a "various support", via the conditions | supp(x)

∩ I i | ≤ 1 for all i ∈ [k]
. This notion of variety can easily be extended, by replacing the righthandsides in these inequalities by some i ∈ Z + : the constraints become | supp(x)

∩ I i | ≤ i for all i ∈ [k].
This extension was already proposed by Bárány in [START_REF] Bárány | A generalization of Carathéodory's theorem[END_REF] for the colorful Carathéodory theorem, when he stated the following. Proof. For all i ∈ [k], we duplicate i times the matrix

A B i , forming à = (A B 1 , A B 1 , . . . , A B k , A B k ). We now have 1 + • • • + k disjoint feasible bases B (1)
1 , . . . , B Our aim here is to study the algorithmic problems related to the general colorful Carathéodory theorem, as we did for the classical one. Again we consider the problems of finding a solution under the conditions of Theorem 3.1.7 on the one hand and of deciding whether a solution exists on the other hand. Bárány and Onn [START_REF] Bárány | Colourful linear programming and its relatives[END_REF] show that given ε > 0, their algorithm provides a colorful set whose distance to 0 is less than ε in time polynomial in the bit size, in log(1/ε) and in 1/ρ, where ρ > 0 is the radius of a ball contained in d i =1 conv S i . Finding a colorful set ε-close to 0 gives some sort of approximation to colorful linear programming. The colored problems we define in this section can also be seen as approximations of the colorful linear programming problems. Instead of approximating by finding the colorful cone closest to p, we aim for a cone containing p "as colorful as possible".

COLORED LINEAR PROGRAMMING, TFNP version

Input. k sets of points S 1 , . . . , S k ⊆ Q d , a point p ∈ Q d , satisfying p ∈ k i =1 pos(S i ) and k positive integers 1 , . . . , k , such that 1 + • • • + k ≥ d . Output. Find a set T ⊆ k i =1 S i , such that p ∈ pos(T ) and |T ∩ S i | ≤ i for all i ∈ [k].
As for the classical version, the complexity of this problem is unknown. Yet the special case with two colors is solvable in polynomial time.

Proposition 3.1.9. Given two disjoint feasible bases B (1) and B (2) of a linear program and an integer ∈ Z + , we can compute a feasible basis B ⊆ B (1) ∪B (2) , such that |B ∩B 1 | = in polynomial time.

We assume genericity. Before describing the polynomial algorithm, we define c (1) and c (2) to be (generic) vectors in R n such that B (i ) is an optimal basis for the problem min c (i )T x s.t. Ax = b x ≥ 0.

We define then c(t ) to be the vector (1t )c (1) + t c (2) for any t ∈ [0, 1] and consider the linear programs min c(t

) T x s.t. Ax = b x ≥ 0. (3.6)
The following is a key property in the proof of Proposition 3.1.9.

Proposition 3.1.10. There exists a finite number of intervals I 1 , . . . , I s with pairwise disjoint interiors such that s i =1 I i = [0, 1] satisfying the following properties:

• for each i ∈ {1, . . . , s}, the same basis of the linear program (3.6) is optimal for all t ∈ I i .

• for each i ∈ {1, . . . , s}, the linear program (3.6) has a unique optimal basis for all t in the interior of I i .

• for t belonging to two consecutive distinct intervals I i 's, there are exactly two optimal bases differing exactly by one element.

Moreover, we can require that each interval is of length larger than 1/K , where K is some integer with a polynomial number of bits.

Proof. Consider a t such that the reduced costs at optimality are all positive. There is an interval I = [a, b] containing t such that all t in I have the same optimal basis, such that for all t in the interior of I this optimal basis is unique, and such that for t = a or t = b there is exactly one other optimal basis. These a and b are obtained precisely for a t making one of the reduced costs equal to 0. The fact that there is exactly one other optimal basis is a consequence of the generic choice of the c (i ) 's and of the non-degeneracy of the system Ax = b | x ≥ 0 .

We have thus a collection of intervals with disjoint interiors in [0, 1] satisfying the three properties of the statement. Two things remain to be shown. First, that the intervals actually cover [0, 1]. Second, that the length of each interval is bounded from below by 1/K (the fact that there is a finite number of such intervals is then a direct consequence).

Again because of genericity and non-degeneracy, any t not in the interior of one of these intervals has exactly one reduced cost being equal to 0. It is then easy to see that this t is the boundary of some of the intervals. Thus the intervals cover [0, 1].

For such an interval I = [a, b], the numbers a and b are each solution of a linear equation involving only coefficients from the c (i ) 's, from the matrix A, from inverses of its square sub-matrices, and from b. This implies the statement about the size of the intervals.

Proof of Proposition 3.1.9. Let us now describe the algorithm. It is a binary search based algorithm. We repeatedly solve the linear program (3.6) for successive values of t as follows. We start with u 0 = 0 and v 0 = 1. At each iteration k, we have an interval [u k , v k ] such that the optimal basis for t = u k has at least than elements from B (1) and such that the optimal basis for t = v k has at most than elements from B (1) . We solve then the linear program for t = (u k + v k )/2. If the optimal basis associated to this t has at least than elements from B (1) , we define

u k+1 = (u k + v k )/2 and v k+1 = v k . Otherwise, we define u k+1 = u k and v k+1 = (u k + v k )/2.
We explain now why after a polynomial number of iterations we get the desired basis. Note that each iteration can be done in polynomial time.

After a number of iterations bounded from above by log 2 K , either we get [u k , v k ] completely inside an interval I i , and in such a case the corresponding optimal basis is the sought basis, or we get [u k , v k ] belonging to two adjacent intervals, and one of the two corresponding optimal bases is the one we seek.

Consider now the following decision problem.

COLORED LINEAR PROGRAMMING, decision version

Input. k sets of points S 1 , . . . , Since COLORFUL LINEAR PROGRAMMING is NP-complete, so is this problem. We show that it remains NP-complete even when the number of colors is 2. For i ∈ [d -1], we define the vector v i ∈ R d having its i th coordinate equal to 1, its (i + 1)th coordinate (respectively 1st coordinate for i = d -1) equal to -1, and its d th coordinate equal to a i . Similarly, we define vectors w i ∈ R d , and just replace the last coordinate by -a i . Deciding whether there exists a set formed with at most (d -1)/2 vectors v i 's and at most (d -1)/2 vectors w i 's containing 0 in its convex hull, is equivalent to deciding whether there exists a partition as wished.

S k ⊆ Q d , a point b ∈ Q d ,
Indeed, given such a partition, the set

v i | i ∈ I ∪ w i | i ∈ [d -1] \ I contains 0 in its convex hull. Conversely, let S 1 = v i | i ∈ [d -1] and S 2 = w i | i ∈ [d -1] . Given a set T ⊆ S 1 ∪S 2 , positively dependent, such that |T ∩S 1 | ≤ d -1 2 and |T ∩S 2 | ≤ d -1 2 , we define I = i ∈ [d -1] | v i ∈ T ∩S 1 and I = i ∈ [d -1] | w i ∈ T ∩S 2 .
The set T being positively dependent, we have d -1 nonnegative real numbers α 1 , . . . , α d -1 , not all equal to zero, such that i ∈I

α i v i + i ∈I α i w i = 0.
By definition of the v i 's and w i 's, we necessarily have that I and I form a partition of [d -1] and that the α i 's are all equal to some positive real number α. Finally, we obtain

i ∈I a i = i ∉I a i , with |I | = |[d -1] \ I | = d -1 2 .
Note that the proposition gives a complexity result for a case of colored linear programming with points not in general position. We do not know whether the problem remains NP-complete in the case of points in general position.

A generalization of linear complementarity

The linear complementarity problem

In this second section we focus on another important problem in mathematical programming generalized by colorful linear programming: the linear complementarity problem. The problem of finding an equilibrium in a bimatrix game, see Section 2.3.2, is one of the many applications of linear complementarity.

The linear complementarity problem can be formalized as follows.

LINEAR COMPLEMENTARITY PROBLEM (LCP(M , q)) Input. A matrix M ∈ Q d ×d and a vector q ∈ Q d . Task. Decide whether there exists a solution to the system

w -M z = q, (3.7)
w ≥ 0, z ≥ 0, (3.8)
w T z = 0. (3.9)
A solution w z satisfies w ≥ 0 and z ≥ 0. Hence the condition (3.9) implies that for all i ∈ [d ] either w i = 0 or z i = 0. This condition, known as the complementary conditions corresponds to a colorful condition in colorful linear programming, where each color is of size 2.

More formally, the problem LCP(M , q) is equivalent to deciding the feasibility of the following colorful linear program.

(I d , -M )x = q, x ≥ 0, (3.10)
| supp(x) ∩ {i , d + i }| ≤ 1, for all i ∈ [d ].
This formulation corresponds indeed to the formulation of colorful linear programming (1), given in Introduction. Any algorithm solving the conic version of COLORFUL LINEAR PROGRAMMING would hence provide an algorithm for LCP.

Besides, we noted in Section 2.2 that if there are no solutions to the system (I d , -M )x = 0, x ≥ 0 , then the problem is equivalent to a convex case of COLORFUL LINEAR PRO-GRAMMING in dimension d -1. Hence, any algorithm solving the convex version of COLORFUL LINEAR PROGRAMMING would provide an algorithm for LCP when 0 is not contained in the conic hull of the columns of (I d , -M ).

The algorithms we discussed in Chapter 2 generalize ideas of well-known algorithms for LCP, namely the Lemke algorithm and the Lemke-Howson algorithm, which solves BIMATRIX. Our aim in this chapter is to emphasize the links between these algorithms.

The Lemke method

The simplex-like version of Bárány-Onn algorithm, presented in Section 2.1.2, computes a colorful feasible basis under the conditions of the colorful Carathéodory theorem (Theorem 1.2.3). We adapt this algorithm to any colorful linear program with each I i of size two. The adapted Bárány-Onn algorithm works as follows.

Consider a non-degenerate colorful linear program given by The dummy column is chosen such that, one the one hand, it forms a colorful feasible basis with a transversal T ⊆ [n], and on the other hand, if I i is the missing color in T , i.e. such that |T ∩ I i | = 0, at least one of the two variables in I i gives an infinite ray when entering the basis. We then proceed with pivot steps, going from colorful feasible basis to colorful feasible basis, until z 0 leaves the basis or until we reach an infinite ray. What changes in this version of the algorithm from the version given in Section 2.1.2 is the pivot rule. In the original algorithm the entering variable is a variable of the missing color of negative reduce cost. This choice ensures that the algorithm does not cycle. Meanwhile, the termination of the algorithm is ensured by the colorful Carathéodory theorem. In this new case, we are no longer ensured to find a point of the missing color of negative reduced cost. However, since we consider the case where all the colors are of size two, we are still able to define the following pivot rule ensuring that the adapted Bárány-Onn algorithm does not cycle. Any colorful feasible basis containing the dummy variable z 0 has at most two neighbors corresponding to the basis we would obtain by entering one or the other variable of the missing color. As the dummy variable is chosen such that the first colorful feasible basis has only one neighbor, we know, by a classic parity proof argument, that z 0 eventually leaves the basis or we reach an infinite ray.

Ax = b, x ≥ 0, | supp(x) ∩ I i | ≤ 1, for all i ∈ d ,
Note that this algorithm may reach an infinite ray even if there were a colorful feasible solution.

Remark 3.2.1. Unlike the simplex algorithm, this method does not seek entering variables with negative reduced cost. Hence the value of the problem may increase along the pivot steps.

The case of colorful linear programming with all I i 's of size two generalizes (3.10), and in this case the adapted Bárány-Onn algorithm coincides with the Lemke method.

The complementary pivot algorithm, known as the Lemke method, was introduced by Lemke in 1965 [START_REF] Lemke | Bimatrix equilibrium points and mathematical programming[END_REF]. This algorithm tries to compute a solution to LCP(M , q), i.e. a colorful feasible basis of the corresponding colorful linear program (3.10).

First note that, if q ≥ 0, then w = q and z = 0 yield a solution to the problem. Otherwise, we consider the following optimization problem, which corresponds also to a colorful linear program

min x 2d +1 s.t. (I d , -M , -e d )x = q, (3.11)
x ≥ 0,

| supp(x) ∩ {i , d + i }| ≤ 1, for all i ∈ [d ],
where

e d =     1 . . . 1     ∈ R d .
This optimization problem has value 0 if and only if there is a solution to the linear complementarity problem. We assume that (I d , -M , -e d ) is non-degenerate. A classic perturbation argument can be used to tackle the degenerate case.

Consider i 0 such that q i 0 ≤ q i for all i ∈ [d ], and let w = qq i 0 e d . The vector (w, 0, q i 0 ) T is a basic feasible solution of the problem (3.11), corresponding to the basis

B 0 = ([d ] \ {i 0 }) ∪ {2d + 1}.
The Lemke algorithm proceeds with simplex pivots, going from colorful feasible basis to colorful feasible basis, until we reach an optimal colorful basis or an infinite ray.

This corresponds exactly to the adapted Bárány-Onn algorithm, where e d is the dummy variable and [n] \ {i 0 } is the transversal.

If the algorithm returns a solution, then the answer to the decision problem LCP(M , q) is 'yes'. However, it may happen that the answer is 'yes', and yet the algorithm does not return a solution, but reaches an infinite ray instead. There are classes of matrices M for which the algorithm reaches an infinite ray if and only if the problem LCP(M , q) is infeasible, see [START_REF] Murty | Linear Complementarity, Linear and Nonlinear Programming[END_REF] for more details on this subject. As a corollary, the matrices (I , -M ) where M belongs to one of these classes define a class of matrices for which the adapted Bárány-Onn algorithm outputs an infinite ray if and only if the colorful linear program is infeasible. It would be interesting to determine more general such classes of matrices.

When the I i have size larger than two, we can ask whether a similar pivot rule can be designed, leading to an efficient behaviour of the algorithm.

The Lemke-Howson algorithm for BIMATRIX

The pivot algorithm proposed by Meunier and Deza in [START_REF] Meunier | A further generalization of the colourful Carathéodory theorem[END_REF] computes a solution to the problem FIND ANOTHER COLORFUL SIMPLEX. Consider a non-degenerate colorful linear program of the form

Ax = b, x ≥ 0, | supp(x) ∩ I i | ≤ 1 for all i ∈ [d ],
with

|I i | = 2 for all i ∈ [d ],
such that the polyhedron corresponding to the non-colorful relaxation is bounded. Given an initial colorful feasible basis of this colorful linear program, FIND ANOTHER COLORFUL SIMPLEX aims at computing another colorful feasible basis, whose existence is ensured by the Octahedron lemma.

The Meunier-Deza algorithm works as follows. We start with the initial colorful feasible basis, and choose arbitrarily a color I 0 = {i 0 , m + n + i 0 } to be pivot color. One variable of I 0 is not in the basis. We proceed to a pivot step of the simplex algorithm, with this variable entering the basis. If the other variable of I 0 leaves the basis, we are done, otherwise we have reached a first almost colorful feasible basis. We then proceed to pivot steps, going from almost colorful feasible basis to almost colorful feasible basis, until one of the variables in I 0 leaves the basis.

In Section 2.3.2, we showed that this algorithm solves BIMATRIX. To prove this result, we used the formulation of BIMATRIX as a colorful linear program:

I m 0 A 0 0 I n 0 B T x =     1 . . . 1     x ≥ 0, (3.12)
| supp(x) ∩ {i , m + n + i }| ≤ 1, for all i ∈ [m + n].
Note that this formulation coincides with the formulation of a linear complementarity problem, given in (3.10).

The Lemke-Howson algorithm, formalized by Lemke and Howson in 1964, also tackled the problem of computing a Nash equilibrium in a bimatrix game. Their approach was later extended by Lemke, giving birth to the Lemke method. For the special case of BIMATRIX, the Meunier-Deza algorithm coincides with the Lemke-Howson algorithm. The only difference between the two algorithms is the starting point. For the Meunier-Deza algorithm, the polyhedron is bounded and the algorithm starts from a given colorful basis. The Lemke-Howson algorithm, on its part, starts with an almost colorful feasible basis such that only one variable of the missing color can enter the basis, the other giving immediately an infinite ray. It can be shown that for linear complementarity problem arising from BIMATRIX, the Lemke-Howson algorithm never reaches an infinite ray, i.e. there is always a solution, and a solution is always found by the algorithm.

Octahedral systems

Under the conditions of the colorful Carathéodory theorem, there always exists a colorful set containing 0 in its convex hull. As a matter of fact, there are more than one such colorful set. We have seen in Section 1.4.2 that the colorful Carathéodory theorem can be used to provide a bound in the First selection lemma. The arguments providing this bound motivated the following question: how many colorful sets, at least, contain 0 in their convex hulls? An exact bound for the minimal number of such colorful sets has been sought in several papers since 2003 [START_REF] Bárány | Quadratically many colorful simplices[END_REF][START_REF] Deza | Colourful simplicial depth[END_REF][START_REF] Stephen | A quadratic lower bound for colourful simplicial depth[END_REF] and a conjecture was formulated by Deza et al. in 2006 [17]. In this chapter, we study combinatorial objects, known as octahedral systems, suggested by Bárány to investigate this geometric problem. A proof of the colorful simplicial depth conjecture using the octahedral systems is given in the next chapter. Most results of these two chapters were published in [START_REF] Deza | A combinatorial approach to colourful simplicial depth[END_REF][START_REF] Sarrabezolles | The colourful simplicial depth conjecture[END_REF].

Octahedral systems

Definition

Let V 1 , . . . ,V n be n pairwise disjoint finite sets, each of size at least 2. An octahedral system is a set

Ω ⊆ V 1 × • • • × V n satisfying the parity condition: the cardinality of Ω ∩ (X 1 × • • • × X n ) is even if X i ⊆ V i and |X i | = 2 for all i ∈ [n].
We use the terminology of hypergraphs to describe an octahedral system: the sets V i are the classes, the elements in n i =1 V i are the vertices, and the n-tuples in V 1 ו • •×V n are the edges. An edge whose i th component is a vertex x ∈ V i is incident to the vertex x, and conversely. A vertex x incident to no edge is isolated. A class V i is covered if each vertex of V i is incident to at least one edge. Finally, the set of edges incident to x is denoted by δ Ω (x) and the degree of x, denoted by deg Ω (x), refers to |δ Ω (x)|.

An octahedral system

Ω ⊆ V 1 ו • •×V n with |V i | = m i for all i ∈ [n]
is called an (m 1 , . . . , m n )octahedral system. Let ν(m 1 , . . . , m n ) denote the minimum number of edges over all (m 1 , . . . , m n )-octahedral systems without isolated vertices. The minimum number of edges over all (d + 1, . . . , d + 1)-octahedral systems has been considered by Deza et al. [START_REF] Custard | Small octahedral systems[END_REF] who denote this quantity by ν(d ). By a slight abuse of notation, we identify ν(d

) with ν(d + 1, . . . , d + 1 d +1 times ).
Throughout this chapter, given an octahedral system

Ω ⊆ V 1 × • • • × V n , the parity property refers to the evenness of |Ω∩(X 1 ו • •× X n )| if X i ⊆ V i and |X i | = 2 for all i ∈ [n].
In a slightly weaker form, the parity property refers to the following observation: If e = (x 1 , . . . , x n ) is an edge in Ω, and y i a point in V i \ {x i }, for all i ∈ [n], then defining

X i = {x i , y i }, there is an edge distinct from e in Ω∩(X 1 ו • •× X n ). Indeed, |X i | = 2 for all i ∈ [n], hence the number of edges in Ω ∩ (X 1 × • • • × X n ) is even. An octahedral system being a simple hypergraph, there in an edge distinct from e in Ω ∩ (X 1 × • • • × X n ).

Motivation

Let µ(d ) denote the minimal number of colorful sets containing 0 in their convex hulls over all colorful point configurations S 1 , . . . , S d +1 in R d such that 0 ∈ conv(S i ) and

|S i | = d + 1 for all i ∈ [d + 1].
In 2003, Deza et al. [START_REF] Deza | Colourful simplicial depth[END_REF] conjectured that µ(d ) ≥ d 2 + 1. We prove this conjecture with the help of the octahedral systems, see Chapter 5.

Given a colorful point configuration S 1 , . . . , S d +1 , the Octahedron lemma [START_REF] Bárány | Quadratically many colorful simplices[END_REF][START_REF] Deza | Colourful simplicial depth[END_REF] states that, for any S 1 ⊆ S 1 , . . . ,

S d +1 ⊆ S d +1 , with |S 1 | = • • • = |S d +1 | = 2,
the number of colorful simplices generated by d +1 i =1 S i and containing 0 in their convex hulls is even. The hypergraph over V 1 ו • •×V n where V i is identified with S i and whose edges are identified with the colorful simplices containing 0 in their convex hulls is therefore an octahedral system. This is the original motivation for introducing these objects. Furthermore, according to Theorem 1.2.4, given in Chapter 1, if 0 ∈ d +1 i =1 conv(S i ), then each point of the colorful point configuration is in some colorful simplices containing 0 in their convex hulls. Hence, in an octahedral system Ω arising from such a colorful point configuration, each class V i is covered. Therefore, we have ν(d ) ≤ µ(d ).

The combinatorial approach consists in studying ν to provide lower bounds for µ. In this manuscript, we provide a more detailed study of the octahedral systems than the one needed to prove the conjecture. Proof. An umbrella is entirely determined by its color V i and its transversal T . Therefore, if two umbrellas of the same color have an edge in common, they necessarily have the same transversal, which implies that they are equal.

Decomposition

In this section, we describe any octahedral system as a symmetric difference of other octahedral systems. This decomposition will allow us to bound the cardinality of octahedral systems, see Chapter 5.

Consider a nonempty octahedral system

Ω ⊆ V 1 × • • • × V n with |V i | ≥ 2 for all i ∈ [n].
Denote by i 1 the smallest i ∈ [n] such that V i is covered in Ω. Such an i 1 exists according to Lemma 4.1.2. We order the vertices {x 1 , . . . , x m } of V i 1 by increasing degree:

deg Ω (x 1 ) ≤ • • • ≤ deg Ω (x m ).
We define U to be the set of umbrellas of color V i 1 containing an edge of Ω incident to x 1 and set W := U ∈U U . Note that, according to Proposition 4.1.4, W = U ∈U U . Let Ω j be the set of all edges in Ω W incident to x j for all j ∈ [m]. Formally,

U = U | U umbrella of color V i 1 and U ∩ δ Ω (x 1 ) = and Ω j = δ Ω W (x j ).
Note that |U | = deg Ω (x 1 ). In the sequel we refer to (U , Ω 2 , . . . , Ω m ) as a suitable decom-4.2. Decomposition position. Lemma 4.2.1. Let (U , Ω 2 , . . . , Ω m ) be a suitable decomposition and W = U ∈U U . We have (i) Ω j ∩ Ω = , for all j = (they have no edges in common).

(ii) Ω = W Ω 2 • • • Ω m .
(iii) Ω j is an octahedral system, for all j .

(iv) deg Ω (x j ) ≥ max(|U |, |Ω j | -|Ω j ∩ W |) for all j . (v) If V i is not covered in Ω, then V i is neither covered in Ω W nor in any Ω j .
The terminology suitable decomposition is due to item (ii) of Lemma 4.2.1.

Proof. We first prove (i). The i 1 th component of any edge in Ω j is x j . Therefore, Ω j and Ω have no edges in common if j = .

We then prove (ii). There are exactly deg Ω (x 1 ) umbrellas of color V i 1 containing an edge of Ω incident to x 1 . As W is the symmetric difference of these umbrellas, x 1 is isolated in Ω W . Thus, Ω 2 , . . . , Ω m form a partition of the edges in Ω W and

Ω W = Ω 2 • • • Ω m .
Taking the symmetric difference of this equality with W we obtain

Ω = W Ω 2 • • • Ω m .
We now prove (iii). By definition, the Ω j 's are subsets of V 1 × • • • × V n . It remains to prove that they satisfy the parity condition. Consider

X i ⊆ V i with |X i | = 2 for i ∈ [n]. If X i 1 does not contain x j , there are no edges in Ω j induced by X 1 × • • • × X n . If X i 1 contains x j , the edges in Ω j induced by X 1 × • • • × X n are the ones induced by X 1 ו • •× X i 1 -1 ×{x j }× X i 1 +1 ו • •× X n . As x 1 is isolated in Ω W , those edges are exactly the edges in Ω W induced by X 1 × • • • × X i 1 -1 × {x 1 , x j } × X i 1 +1 × • • • × X n .
According to Proposition 4.1.3, W is an octahedral system and Ω W as well, hence there is an even number of edges.

We prove (iv). We have |U | = deg Ω (x 1 ) ≤ deg Ω (x j ) for all j ∈ [m]. Furthermore, by definition of the symmetric difference, we have (

Ω 2 • • • Ω m ) \ W ⊆ Ω. This inclusion becomes (Ω 2 \ W ) • • • (Ω m \ W ) ⊆ Ω.
As two Ω 's share no edges, Ω j \ W ⊆ Ω and thus Ω j \ W ⊆ δ Ω (x j ) for all j ∈ {2, . . . , m}. We obtain

|Ω j | -|Ω j ∩ W | ≤ deg Ω (x j ).
Finally to prove (v) it suffices to prove that a class V i not covered in Ω remains not covered in Ω W . Indeed, if a class is covered in an Ω j , it is also covered in Ω W , as no two Ω 's have an edge in common. Consider V i not covered in Ω. There is a vertex x ∈ V i incident to no edges in Ω. In particular, there are no edges in Ω incident to x 1 and x. Therefore, the umbrellas in U , which are defined by the edges incident to x 1 , contain no edges incident to x. Hence, x is isolated in W = U ∈U U and in Ω. Finally, x remains isolated in Ω W .

Unlike the suitable decomposition of Ω, which is a decomposition over general octahedral systems, the decomposition given in the following lemma is over umbrellas only.

Lemma 4.2.2. Consider an octahedral system

Ω ⊆ V 1 ו • •×V n with |V i | ≥ 2 for all i ∈ [n].
There exists a set of umbrellas D such that Ω = U ∈D U and such that the following implication holds:

V i is the color of some U ∈ D =⇒ V i is covered in Ω.
Proof. The proof proceeds by induction on the number of covered classes in Ω. If no classes are covered, then, according to Lemma 4.1.2, Ω is empty. Suppose now that k ≥ 1 classes are covered and consider a suitable decomposition (U , Ω 2 , . . . , Ω m ) of Ω. Denote by W the symmetric difference W = U ∈U U . According to Proposition 4.1.3, W is an octahedral system, and so is Ω W . There are strictly fewer covered classes in Ω W than in Ω. Indeed, in Ω W , the class V i 1 is no longer covered, since x 1 is isolated, and according to item (v) of Lemma 4.2.1, a class not covered in Ω remains not covered in Ω W . By induction, there exists a set D of umbrellas such that Ω W = U ∈D U , and such that if there is an umbrella of color V i in D , then V i is covered in Ω W . As the umbrellas in D are not of color V i 1 , we have U ∩ D = . Therefore, Ω = ( U ∈U U ) ( U ∈D U ) and the set D = U ∪ D satisfies the statement of the lemma.

Other properties of octahedral systems 4.3.1 Geometric interpretation of the decomposition

Raman Sanyal suggested that the umbrellas are not only a combinatorial tool, but may also have a geometric counterpart. They do indeed, and this counterpart is the following, already seen in Section 1.5 for the third proof of the Octahedron lemma.

T = T ⊆ d +1 i =1 S i | |T | = d , |T ∩ S i | ≤ 1 for all i ∈ [d + 1] .
The convex hulls of the sets in T are (d -1)-simplices. We remove these simplices from R d and obtain a collection of connected components, called the cells, which are open sets in R d . The closure of the cells is R d itself. One cell is unbounded, and all the other cells are bounded. All the points in one cell are contained in exactly the same colorful simplices. Hence, given a cell, we can define the corresponding set of colorful sets containing the cell in their convex hulls. The points in the unbounded cell are contained in the convex hulls of no colorful sets at all. Proof. Considering two adjacent cells and the corresponding sets Ω 1 and Ω 2 of colorful sets, we claim that Ω 1 = Ω 2 U (T ), where T is the transversal corresponding to the face separating the two cells. Consider a colorful set S containing the first cell in its convex hull. If S does not contain T , then while crossing the face we do not leave the convex hull of S. Hence the second cell is also contained in conv(S). Otherwise, S contains T . Consider the point s ∈ S \ T and the two half-spaces defined by aff(T ). The point s lies in the same half-space as the first cell, as it is contained in conv(S). Thus, the second cell is not contained in conv(S). Using this remark, each time the path from C to C crosses a transversal, gives

Ω ∩ Ω = U (T 1 ) • • • U (T r ).
We already noted that the points in the unbounded cell are in the convex hulls of no colorful sets. Hence, the previous proposition applied to the unbounded cell and to the cell containing 0 shows that the set of positively dependent colorful sets is of the form U (T 1 ) • • • U (T r ). This gives another proof that the set of positively dependent colorful sets Ω is an octahedral system.

Further uses of umbrellas and discussions

Given two cells and the corresponding sets of colorful sets Ω 1 and Ω 2 , we define Ω := Ω 1 Ω 2 . Any path from one cell to the other will go through a collection of (d -1)simplices, corresponding to a collection T 1 , . . . , T r of transversals in T , which satisfies Ω = U (T 1 ) • • • U (T r ), according to Proposition 4.3.1. Hence, a cycle, starting from a cell and returning to the same cell, corresponds to a symmetric difference equal to the empty set, which shows that the umbrellas do not form a F 2 -independent family, identifying the sum in F 2 and the symmetric difference.

A natural question is the following. Given two cells, what is the smallest number of cells crossed by a path from one cell to the other? In particular, this would answer the question: can we express the set of positively dependent colorful sets as a symmetric difference of few umbrellas? This is in general not possible. For instance, in the configuration of Figure 4.2, the origin 0 is in (d + 1) d +1 colorful simplices, and hence any path from the unbounded cell to 0 must cross at least (d + 1) d cell faces. Yet, the question remains interesting for specific configurations, such as the ones satisfying the conditions of the colorful Carathéodory theorem. For this particular case, a tight upper bound on the number of colorful simplices containing 0 is not known, and could be tackled via an umbrella approach.

Ω ⊆ V 1 × • • • × V n with |V i | = t for all i ∈ [
n] containing a perfect matching? The second question is to decide whether there is a cell such that the paths from the unbounded cell to this cell correspond to a symmetric difference of umbrellas belonging to this family of octahedral systems.

The realizability problem presented in the next section can also be interpreted in terms of umbrellas.

Realizability

Question 6 of [START_REF] Custard | Small octahedral systems[END_REF] asks whether any octahedral system Proof. We provide an example of a non realizable octahedral system without isolated vertices in Figure 4.3. Suppose by contradiction that this octahedral system can be realized as a colorful point configuration S 1 , S 2 , S 3 . Without loss of generality, we can assume that all the points lie on a circle centered at 0. Take x 3 ∈ S 3 , and consider the line going through x 3 and 0. There are at least two points x 1 and x 1 of S 1 on the same side of . There is a point x 2 ∈ S 2 , respectively x 2 ∈ S 2 , on the other side of the line such that 0 ∈ conv(x 1 , x 2 , x 3 ), respectively 0 ∈ conv(x 1 , x 2 , x 3 ). Assume without loss of generality that x 2 is further away from x 3 than x 2 . Then, conv(x 1 , x 2 , x 3 ) contains 0 as well, contradicting the definition of the octahedral system given in Figure 4.3.

Ω ⊆ V 1 × • • • × V n with n = |V 1 | = . . . = |V n | = d + 1 can
In terms of umbrellas, the realizability problem correspond to two questions. First, consider a realizable octahedral system, and a colorful point configuration realizing it. For any decomposition of this octahedral system into umbrellas, is there a path from the unbounded cell to this cell corresponding to this decomposition? The answer is trivially no, if we do not restrict ourselves to minimal decomposition, in the sense that no sub-sum of the symmetric difference is the empty-set. We do not know the answer, when we add this restriction. Assuming that the answer is yes, the realizability problem would become the following. Given a minimal decomposition, can we define points in Figure 4.3: A non realizable (3, 3, 3)-octahedral system with 9 edges R d and a path from infinity to 0, such that the only (d -1)-colorful simplices crossed by the path are the ones corresponding to the umbrellas of the decomposition? This would allow to reformulate the proof that the octahedral system from Figure 4.3 is non realizable, as follows. First note that this octahedral system is the symmetric difference of the three umbrellas given in Figure 4.4 and that this decomposition is minimal. Let S 1 , . . . , S d +1 in R d be a colorful point configuration. The i -degree of a point x in R d relatively to a colorful point configuration is defined as the number of i -transversals T such that 0 ∈ conv(T ∪ {x}). In addition to the i -degree, we define the i -fan. It is obtained as follows. We remove from R d all (d -1)-dimensional cones of the form We call the collection of the remaining connected components the i -fan relative to the colorful point configuration and denote it F i . Note that a connected component is an open set of R d and that the closure of these components is R d itself. We have that all points in a same connected component in F i have same i -degree.

We can now speak of the i -degree in a connected component. We are in position to prove the following proposition. Note that the degree of a vertex v in a class V i of an octahedral system arising from a colorful point configuration is precisely the i -degree of its geometric counterpart x v .

Proposition 4.3.3. Let Ω ⊆ V 1 ו • •×V d +1 be an octahedral system arising from a generic colorful point configuration S 1 , . . . , S d +1 in R d with |S j | = d +1 for all j ∈ [d +1]. Suppose that a vertex v of d +1 i =1 V i is of degree (d + 1) d , i.
e. all possible edges containing v exist in Ω. Then the degree of every vertex in the same class V i as v is a multiple of d + 1.

Proof. Let v be the vertex as in the statement, and let V i be the class it belongs to. Let x v be the geometric counterpart of v.

Take two distinct connected components K and L of F i that are neighbors. We show that the i -degrees in K and L differ by a multiple of d + 1.

Octahedral systems: computation of bounds

In this chapter, we keep on with the study of octahedral systems introduced in Chapter 4 and more specifically with the study of bounds on their cardinality. The octahedral systems over

V 1 × • • • × V n generalize the colorful point configurations in R n-1
, and this for any sizes of the |V i |'s, as soon as all the colorful sets and 0 are in general position. The colorful simplicial depth conjecture tackled the problem for colorful point configurations satisfying the conditions of the colorful Carathéodory theorem, with

|S i | = d +1 for all i ∈ [d + 1].
In this chapter, we are interested in a more general setup. The chapter is divided into three sections, one for the upper bounds, one for the lower bounds, and a final one explaining how to use the previous results to prove the colorful simplicial depth conjecture.

Upper bounds

The following proposition gives a general upper bound for ν(m 1 , . . . , m n ). Recall that ν(m 1 , . . . , m n ) denotes the minimum number of edges in an (m 1 , . . . , m n )-octahedral system without isolated vertices.

Proposition 5.1.1. Suppose that m 1 ≥ • • • ≥ m n ≥ 2. Then, ν(m 1 , . . . , m n ) ≤ min 0≤c≤k≤n c≤m k+1 k i =1 (m i -2) + 2c + m n (m k+1 -c),
with the convention m n+1 = 1.

Proof. Consider n sets V 1 , . . . ,V n and denote v (i ) 1 , . . . , v (i ) m i the vertices in V i for all i ∈ [n]. For all k ∈ {0, . . . , n} and all c such that 0 ≤ c ≤ min(k, m k+1 ), we construct an octahedral system Ω

(k,c) ⊆ V 1 × • • • × V n satisfying |Ω (k,c) | ≤ k i =1 (m i -2) + 2c + (m k+1 -c)m n .
The construction is illustrated in Figure 5.1. Throughout the construction, we use the following convention. If j ≥ m i , then the vertex denoted by v (i ) j is simply the vertex v (i ) m i .

P 1 and P 2 Q 1 and Q 2 U 1 and U 2 Figure 5.1: Construction of Ω (4,2) ⊆ V 1 × • • • × V 7 with |V 1 | = • • • = |V 7 | = 4
Case (a). We start with the case k = 0 and c = 0. We define m 1 umbrellas of color V n :

U j = {v (1) j } × • • • × {v (n-1) j } × V n for all j ∈ [m 1 ].
The octahedral system defined by Ω (0,0) = j ∈[m 1 ] U j covers all classes and satisfies |Ω (0,0) | = m 1 × m n . Indeed, the U j 's are pairwise disjoint, since they are all of the same color, and each of them contains m n edges.

Upper bounds

Ω (4,2) ⊆ V 1 × • • • × V 7 with |V i | = 4 for all i Case (b). Consider now k ∈ [n -1] and 0 ≤ c ≤ min(k, m k+1
). We first define kc umbrellas:

P i = {v (1) 2 } × • • • × {v (i -1) 2 } × V i × {v (i +1) 1 } × • • • × {v (n) 1 } for all i ∈ [k -c].
The octahedral system defined by

Ω P = i ∈[k-c] P i satisfies |Ω P | = k-c i =1 (m i -2) + 2
. Indeed, two umbrellas P i and P j share an edge if and only if i and j are consecutive numbers, and in this case they share exactly one edge.

Then, we define c umbrellas:

Q i = {v (1) 2 } × • • • × {v (k-c+i -1) 2 } × V k-c+i × {v (k-c+i +1) i } × • • • × {v (n) i } for all i ∈ [c].
The octahedral system defined by

Ω Q = c i =1 Q i satisfies |Ω Q | = c i =1 m k-c+i .
Indeed, the Q i 's form a set of pairwise disjoint umbrellas, since all the edges in Q i are incident to the same vertex v

(k+1) i ∈ V k+1 and v (k+1) i = v (k+1) j for all 1 ≤ i < j ≤ c.
Then, we define m k+1c umbrellas of color V n :

U j = {v (1) c+ j } × • • • × {v (k) c+ j } × {v (k+1) c+ j } × • • • × {v (n-1) c+ j } × V n for all j ∈ [m k+1 -c].
The octahedral system defined by

Ω U = m k+1 -c j =1 U j satisfies |Ω U | = c i =1 m k-c+i .
Indeed, the U j 's form a set of pairwise disjoint umbrellas, since they are of the same color.

Finally, Ω P and Ω Q only share the edge (v (1) 2 , . . . ,

v (k-c) 2 , v (k-c+1) 1 , . . . , v (n) 1 )
. The octahedral system Ω U shares edges neither with Ω P nor with Ω Q . Hence, the octahedral system defined by

Ω (k,c) = ( k-c i =1 P i ) ( c i =1 Q i ) ( m k+1 -c j =1 U j ) satisfies |Ω (k,c) | = k i =1 (m i -2) + 2c + (m k+1 -c)m n . Furthermore, Ω (k,c
) covers every classes. Indeed, the classes V 1 , . . . ,V k as well as the c first vertices of each class V k+1 , . . . ,V n are covered in Ω P Ω Q . The remaining vertices of V k+1 , . . . ,V n are covered in Ω U . We can conclude since Ω P Ω Q and Ω U are disjoint.

Proof. Let D be a set of umbrellas such that there are no umbrellas of color V i in D and Ω = U ∈D U . Denote by y 1 , . . . , y m i the vertices of V i , and by Q j the set of umbrellas in D incident to y j for each j ∈ [m i ]. As D contains no umbrellas of color V i , all the umbrellas in Q j have transversals with i th component equal to y j . Denote by Q j the symmetric difference of the umbrellas in Q j . We have that Q j is an octahedral system, according to Proposition 4.1.3, and that δ Ω (y j ) = Q j , Q j = , and Q j ∩ Q = for all j = . If a vertex is isolated in Ω, then it is also isolated in Q j . In other words, the classes covered in Q j are also classes covered in Ω. Since Q j is not empty and according to Proposition 5.2.1, |Q j | ≥ m. Therefore, we have

|Ω| = m i j =1 deg Ω (y j ) = m i j =1 |Q j | ≥ m i m.
We end this preliminary section with a result proved in [START_REF] Deza | A combinatorial approach to colourful simplicial depth[END_REF].

Proposition 5.2.3. An octahedral system without isolated vertices has at least max

i = j (|V i |+ |V j |) -2 edges.
The special case of this proposition for octahedral systems arising from colorful point configurations S 1 , . . . , S d +1 with |S i | = d + 1 for all i ∈ [d + 1], i.e. µ(d ) ≥ 2d , has been proved in [START_REF] Deza | Colourful simplicial depth[END_REF].

Proof. Assume without loss of generality that |V

1 | ≥ . . . ≥ |V n-1 | ≥ |V n | ≥ 2. Let v * be the vertex minimizing the degree in Ω over V 1 . If deg Ω (v * ) ≥ 2,

Proof of the main result

Our main result provides a lower bound on the cardinality of octahedral systems with all classes of size m and with m not smaller than the number of classes.

Theorem 5.2.5. Let

Ω ⊆ V 1 × • • • × V n be an octahedral system with |V 1 | = • • • = |V n | = m ≥ n ≥ 2. If k ≥ 1 classes among the V i 's are covered, then |Ω| ≥ k(n -2) + 2.
As mentioned in the previous section, the proof of this theorem distinguishes two cases. Proposition 5.2.6 corresponds to the second case. We first prove this proposition. Proposition 5.2.6. Consider an octahedral system Ω ⊆

V 1 × • • • ×V n with |V i | = m for all i ∈ [n] and a suitable decomposition (U , Ω 2 , . . . , Ω m ) of Ω. Consider O ⊆ {Ω 2 , . . . , Ω m } such that for each Ω j ∈ O there is a class V i covered in Ω j and in no other Ω ∈ O . Denote by P ⊆ O the set of umbrellas in O . We have |Ω| ≥ |U |(m -|O |) + Ω j ∈O |Ω j | -|U |(|O | -|P |) -|U | -|P | + 1. Proof. Let W = U ∈U U . The number of edges in Ω is equal to m j =1 deg Ω (x j ). We bound deg Ω (x j ) by |U | for j = 1 and if Ω j ∉ O and by |Ω j | -|Ω j ∩W | otherwise, see (iv) in Lemma 4.2.1. We obtain |Ω| ≥ |U |(m -|O |) + Ω j ∈O |Ω j | -|Ω j ∩ W | .
We introduce a graph G = (V , E ) defined as follows. We use the terminology nodes and links for G in order to avoid confusion with the vertices and edges of Ω. The nodes in V are identified with the umbrellas in U and the Ω j 's in O : V = U ∪ O . There is a link in E between two nodes if the corresponding octahedral systems have an edge in common. The graph G is bipartite: indeed, two umbrellas in U are of the same color V i 1 and, according to Proposition 4.1.4, they do not have an edge in common. According to Lemma 4.2.1, two Ω j 's do not have an edge in common either.

For Ω j in O , we have |Ω j ∩ W | = U ∈U |Ω j ∩U | = deg G (Ω j ), note that here the degree is counted in G. The fact that the umbrellas in U are disjoint proves the first equality. The second equality is deduced from the facts that Ω j has at most one edge in common with each umbrella in U , the one incident to x j , and that Ω j has no neighbors in O . We obtain the following bound

|Ω| ≥ |U |(m -|O |) + Ω j ∈O |Ω j | -deg G (Ω j ) = |U |(m -|O |) + Ω j ∈O |Ω j | -deg G (O \ P ) -deg G (P ).
Again, for the equality, we use the fact that G is bipartite. The number of links in E incident to a node in

O \ P is at most |U |. Hence, deg G (O \ P ) ≤ |U |(|O | -|P |). It
remains to bound deg G (P ). Note that if U is an umbrella in P , it is the only umbrella of its color in P , otherwise it would contradict the property of O . We now prove that there are no cycles induced by P ∪ U in G.

Suppose there is such a cycle C and consider an umbrella U of P in this cycle. Denote its color by V i and its neigbours in C by L and R. As G is simple, L and R are distinct. The umbrellas L and R are both in U , and hence are of color V i 1 and do not have an edge in common. Therefore U ∩ L and U ∩ R do not have an edge in common either, which implies that the i th component of the transversals of L and R are distinct. Note that two umbrellas adjacent in C , both of color distinct from V i , have necessarily transversals with the same i th component. Hence there must be another umbrella of color V i in the path in C between L and R not containing U . This is a contradiction since U is the only umbrella in P of color V i .

The number of links in E incident to P is then at most |U | + |P | -1. This allows us to conclude.

Proof of Theorem 5.2.5.

Let Ω ⊆ V 1 × • • • × V n be an octahedral system with |V 1 | = • • • = |V n | = m ≥ n ≥ 2, and suppose that k ≥ 1 classes V i 1 , . . . ,V i k , with i 1 < • • • < i k , are cov- ered in Ω.
The proof works by induction on k.

If k = 1, then Ω must contain at least m edges for one class to be covered.

Assume now that

k > 1. If |U | ≥ m -1, then, according to item (iv) of Lemma 4.2.1, |Ω| = n j =1 deg Ω (x j ) ≥ n|U | ≥ k(m -2)
+ 2 and we are done. Assume now that |U | ≤ m -2. We consider a suitable decomposition (U , Ω 2 , . . . , Ω m ) of Ω and distinguish two cases.

Case 1: One of the covered classes V i , for i ∈ {i 2 , . . . , i k }, is not covered in any Ω j . Let V i be a covered class in Ω, which is not covered in any Ω j . For each j ∈ {2, . . . , m}, applying Lemma 4.2.2 on Ω j gives a set D j of umbrellas, all of color distinct from V i , such that Ω j = U ∈D j U . We obtain Ω = ( U ∈U U ) ( m j =2 U ∈D j U ), according to item (ii) of Lemma 4.2.1. Thus, we can apply Proposition 5.2.2 which ensures that1

|Ω| ≥ m 2 ≥ k(m -2) + 2.
Case 2: Each covered class V i , for i ∈ {i 2 , . . . , i k }, is covered in at least one of the Ω j .

Choose a set O ⊆ {Ω 2 , . . . , Ω n }, minimal for inclusion, such that each covered class V i , for i ∈ {i 2 , . . . , i k }, is covered in at least one of the Ω j ∈ O . Such set O satisfies the statement of Proposition 5.2.6. Applying this proposition, we obtain

|Ω| ≥ |U |(m -|O |) + Ω j ∈O |Ω j | -|U |(|O | -|P |) -|U | -|P | + 1.
We now bound Ω j ∈O |Ω j |. Let k j be the number of classes covered in Ω j . By minimality of O , there is at least one class covered in each Ω j ∈ O , and according to item (v) of Lemma 4.2.1 we have k j < k, hence 1 ≤ k j < k. By induction, the cardinality of Ω j is at least k j (m -2) + 2. This lower bound is not good enough for the Ω j ∉ P such that k j = 1. We denote by A those Ω j 's. We explain now how to improve the lower bound for Ω j ∈ A . Only one class is covered in Ω j and Ω j ∉ P . According to Lemma 4.2.2, Ω j can be written as a symmetric difference of distinct umbrellas of the same color. According to Proposition 4.1.4, these umbrellas are pairwise disjoint and |Ω j | is equal to m times the number of umbrellas in this decomposition. Since Ω j is not an umbrella itself, otherwise Ω j would have been in P , there are at least two umbrellas in this decomposition. We obtain

Ω j ∈O |Ω j | ≥ Ω j ∈O \A k j (m -2) + 2|O \ A | + 2m|A | = Ω j ∈O k j (m -2) + 2|O | + m|A |. Consequently |Ω| ≥ |U |(m -|O |) + Ω j ∈O k j (m -2) + 2|O | + m|A | -|U |(|O | -|P |) -|U | -|P | + 1. Finally, we have 2|O | -|P | -|A | ≤ Ω j ∈O k j , (5.1) k -1 ≤ Ω j ∈O k j . ( 5.2)
Ineqality (5.1) is obtained by distinguishing the Ω j with k j = 1 from those with k j ≥ 2. Inequality (5.2) results from the fact that each class V i 2 , . . . ,V i k is covered in at least one Ω j in O . Thus,

|Ω| ≥ |U |(m -|O |) + Ω j ∈O k j (m -2) + 2|O | + |U ||A | -|U |(|O | -|P |) -|U | -|P | + 1 ≥ (k -1)(m -2) + 2|O | -|P | + 1 + Ω j ∈O k j -k + |A | + m -2|O | + |P | |U |
where we only used the inequalities m ≥ m -2 ≥ |U | and (5.2). According to (5.1), the expression

Ω j ∈O k j -k + |A | + m -2|O | + |P |
is nonnegative. Moreover, we have already noted that |U | = deg Ω (x 1 ), which is at least 1. Therefore,

|Ω| ≥ (k -1)(m -2) + 2|O | -|P | + 1 + Ω j ∈O k j -k + |A | + m -2|O | + |P |. Using (5.2) again, we obtain |Ω| ≥ k(m -2) + 2.
Remark 5.2.7. The case of equality in Theorem 5.2.5 occurs if and only if Ω can be written as a symmetric difference of k umbrellas of pairwise distinct colors, such that G is a tree, where G is the graph whose vertices are identified with these k umbrellas and whose edges are the pairs of umbrellas with an edge in common. We can easily check that if the latter condition is satisfied, then we have equality. Indeed, in this case we have |Ω| = km -2|E | = k(m -2) + 2. The reverse implication is less direct but can be obtained via a careful yet tedious analysis of the inequalities along the proof of Theorem 5.2.5.

Other bounds

We now present results obtained in collaboration with Antoine Deza [START_REF] Deza | A combinatorial approach to colourful simplicial depth[END_REF], providing lower bounds on the cardinality of octahedral systems with classes of size not larger than the number of classes. We believe that the use of the suitable decomposition may simplify the proofs and provide even stronger results for this case.

The main result is the following.

Lower bounds

Proof. Any edge intersecting X contains X since X induces a complete subgraph in D(Ω), implying deg Ω (X ) ≥ 1. Moreover, we have |X ∩ V i | ≤ 1 for i = 1, . . . , n.

Case (a): deg Ω (X ) ≥ 2. Choose i * such that |X ∩ V i * | = 0. We first note that the degree of each w in V i * \ X is at least k -1.

Indeed, take an edge e containing w and a i * -transversal T disjoint from e and X . Note that e does not contain any vertex of X as underlined in the first sentence of the proof.

Apply the weak form of the parity property to e, T , and the unique vertex x in X ∩ V i * .

There is an edge distinct from e in e ∪T ∪{x}. Note that this edge contains w, otherwise it would contain x and any other vertex in X . It also contains at least one vertex in T . For a fixed e, we can actually choose k -2 disjoint i * -transversals T of that kind and apply the weak form of the parity property to each of them. Thus, there are k -2 distinct edges containing w in addition to e.

Therefore, we have in total at least (k -1) 2 edges, in addition to deg Ω (X ) ≥ 2 edges.

Case (b): deg Ω (X ) = 1. Let e(X ) denote the unique edge containing X . For each i such that |X ∩ V i | = 0, pick a vertex w i in V i \ e(X ). Applying the weak form of the parity property to e(X ), the w i 's, and any colorful selection of u i ∈ V i \ X when i is such that |X ∩ V i | = 0 shows that there is at least one additional edge containing all u i 's. While Lemma 5.2.12 is similar to Lemma 5.2.11, we were not able to find a common generalization. Proof. Choose i * such that X ∩ V i * = . Choose W i * ⊆ V i * \ X of cardinality k -1.

For each vertex w ∈ W i * , choose an edge e(w) containing w. Let v * be the vertex v * minimizing the degree in Ω over V 1 \ X . Since X induces a complete subgraph without outneighbors, there is at least one edge disjoint from X containing v * . We can therefore assume that there is a vertex w * ∈ W i * such that e(w * ) contains v * . Choose W i ⊆ V i for i = i * such that |W i | = k -1 and

w∈W i * e(w) ⊆ W = n i =1 W i .
Case (a): the degree of v * in Ω is at most k -2. For all w ∈ W i * , applying the parity property to e(w), the unique vertex of X ∩ V i * , and k -2 disjoint i * -transversals in W yields (k -1) 2 distinct edges, in a similar way as in Case (a) of the proof of Lemma 5.2.11. Applying the weak form of the parity property to e(w * ), any 1-transversal in W not intersecting the neighborhood of v * in Ω, and each vertex in V 1 \ W 1 gives |V 1 |k + 1 additional edges not intersecting V 2 \ W 2 . In addition, |V 2 |k + 1 edges are needed to cover the vertices of V 2 \W 2 . In total we have at least (k-1) 2 +|V 1 |+|V 2 |-2(k-1) edges. Proof. Let v and v be the two vertices of V 1 having outneighbors in V i * . Let u and u be the two vertices in V i * with (v, u) and (v , u ) forming arcs in D(Ω). Note that according to the basic properties of D(Ω), we have u = u . For each vertex w ∈ V i * , choose an edge e(w) containing w. We can assume that there is a vertex w * ∈ V i * such that e(w * ) contains a vertex v * in V 1 of minimal degree in Ω. We first show that the degree of any vertex in V i * is at least k -1 in the hypergraph induced by W . Pick w ∈ V i * and consider e(w). If v ∈ e(w), take k -2 disjoint i *transversals in W not containing v and not intersecting with e(w). In this case, we necessarily have w = u since v ∉ e(w). Applying the weak form of the parity property to e(w), u , and each of those i * -transversals yields, in addition to e(w), at least k -2 edges containing w. Otherwise, take k -2 disjoint i * -transversals in W not containing v and not intersecting with e(w), and apply the weak form of the the parity property to e(w), u, and each of those i * -transversals. Therefore, in both cases, the degree of w in the hypergraph induced by W is at least k -1.

Then, we add edges not contained in W . If the degree of v * in Ω is at least 2, there are at least 2(|V 1 |k) distinct edges intersecting V 1 \ W 1 . Otherwise, the weak form of the parity property applied to e(w * ), any 1-transversal in W , and each vertex in Similarly, we show that the degree of any vertex in V i * is at least k -1 in the hypergraph induced by W . Pick w ∈ V i * and consider e(w). If v ∈ e(w), take k -2 disjoint i * -transversals in W not containing v and not intersecting with e(w). Applying the weak form of the parity property to e(w), u , and each of those i * -transversals yields, in addition to e(w), at least k -2 edges containing w. Otherwise, take k -2 disjoint i * -transversals in W not containing v and not intersecting with e(w), and apply the weak form of the the parity property to e(w), u, and each of those i * -transversals. Therefore, in both cases, the degree of w in the hypergraph induced by W is at least k -1.

Then, we add edges not contained in W . If the degree of v * in Ω is at least 2, there are at least 2(|V 1 |k) distinct edges intersecting V 1 \ W 1 . Otherwise, the weak form of the parity property applied to e(w * ), any 1-transversal in W , and each vertex in V 1 \W 1 provides |V 1 |-k additional edges not intersecting V 2 \W 2 . Therefore, |V 2 |-k +1 additional edges are needed to cover these vertices of V 2 \ W 2 .

V 1

V n-k+1

V n-z+1 k -1 The following proposition is proved by induction on the cardinality of the V i 's, for octahedral systems of the form illustrated in Figure 5.3. Either the deletion of a vertex results in an octahedral system satisfying the condition of Proposition 5.2.14 and we can apply induction, or we apply Lemma 5.2.12 or Lemma 5.2.13 to bound the number of edges of the system. Lemma 5.2.10 is a key tool to determine if the deletion of a vertex results in an octahedral system satisfying the condition of Proposition 5.2.14. Before proving this proposition, we note that Theorem 5.2.9 can be deduced from this proposition, by setting k = m and z = 0. In other words, we conjecture that the upper bound given in Proposition 5.1.1 is tight.

A more general conjecture

As for the proof of Theorem 5.2.5, the case when Ω can be written as a sum of umbrellas with no umbrellas of color V 1 is settled by Proposition 5.2.2. The proof of the remaining cases seem to need finer inequalities than the one used for Theorem 5.2.5.

Index

  p

Figure 1 :

 1 Figure 1: The Carathéodory theorem in dimension 2

  p

Figure 2 :

 2 Figure 2: The colorful Carathéodory theorem in dimension 2

  p

Figure 3 :

 3 Figure 3: A colorful point configuration in R 3 with 10 colorful tetrahedra containing p

  d and a set I ⊆ [d ], we define x I ∈ R d to be the projection of x on the subspace x ∈ R d | x i = 0 for all i ∉ I . It implies supp(x I ) ⊆ I . A convex set C ⊆ R d is such that for all x, y ∈ C , we have [x, y] ⊆ C . In other words, any convex combination of points of C is in C . The convex hull of a set S, denoted conv(S), is the smallest convex set containing S. If S is finite, S = {s 1 , . . . , s t }, the following equality holds conv

1 .

 1 Definitions and preliminaries with c ∈ R n , A ∈ R d ×n of full rank, and b ∈ R d . A basis is a set B ⊆ [n] of size d such that the matrix A B is nonsingular. The basic solution associated to B is the unique x B ∈ R n such that supp(x B ) ⊆ B and Ax B = b.

  the linear program is non-degenerate, the vertices of P = x ∈ R n | Ax = b, x ≥ 0 are identified with the feasible bases. In this case, two vertices of P are neighbors in the 1-skeleton if the corresponding feasible bases B and B differ by only one: |B ∩ B | = d -1.

1 Figure 1 . 1 :

 111 Figure 1.1: Bárány's proof of the colorful Carathéodory theorem

Figure 1 . 2 :

 12 Figure 1.2: A Sperner labeling in dimension 2

1 . 3 .

 13 Given a polyhedron P = x ∈ R n | Ax = b, x ≥ 0 and a set I ⊆ [n], we define a polyhedron P I := x ∈ P | x i = 0 for all i ∉ I . If A is of full rank, the dimension of P I is at most |I |d , for |I | ≥ d . The faces of P are exactly the P I 's, with I ⊆ [n] (the empty face being considered as one of the faces). Consider now A, b, and disjoint feasible bases B 1 , . . . , B d as in the statement of Theorem 1.2.3. By a standard perturbation argument, we assume that the system Ax = Proofs of the colorful Carathéodory theorem b | x ≥ 0 is non-degenerate. We define P to be the polyhedron P := x ∈ R n |Ax = b, x ≥ 0 . The vertices of P are identified with the feasible bases B ⊆ [n]. Define a labeling λ of the vertices of the polyhedron by λ(B ) := min argmax i ∈[d ] |B ∩ B i | .

Theorem 1 . 4 . 1 (

 141 Tverberg's theorem). Any set of n points in R d with n ≥ (k -1)(d +1)+1 admits a Tverberg k-coloring.

Theorem 1 . 4 . 2 (

 142 First selection lemma). Given a set S of n points in R d in general position, there exists a point p ∈ R d contained in at least c d n d +1 simplices of dimension d formed by points of S, where c d is a constant depending only on the dimension d .

nd

  +1 + O(n d ) simplices.

Theorem 1 . 4 . 3 .

 143 Given a set of points X ⊆ R d in general position with |X| = n, there exists a weak ε-net of size at most O 1 c d ε d +1 . Proof of Theorem 1.4.3. Start with S = and H = X d +1 . At each step, ask whether there is a subset Y ⊆ X such that |Y| ≥ εn and S∩conv(Y) = . If the answer is no, then S is a weak ε-net and return it. Otherwise, consider such a Y. Applying the first selection lemma, there is a point z in the convex hull of at least c d |Y| d +1 simplices formed by points of Y. Let S := S ∪ {z} and H = H \ {T ∈ H | z ∈ conv(T)}. The initial set H is of size n d +1 and at each step, at least c d εn d +1 elements of H are removed from it. Hence, there is at most O 1 c d ε d +1 steps, and in the end, the set S is a weak ε-net of size at most O 1 c d ε d +1 .

Theorem 1 . 5 . 1 (

 151 Octahedron lemma). Consider d + 1 pairs of points S 1 , . . . , S d +1 in R d and a point p ∈ R d , all together in general position. The point p is contained in an even number of colorful simplices.

1. 5 .Figure 1 . 3 :

 513 Figure 1.3: The Octahedron lemma in dimension 2

Theorem 1 . 5 . 1 .

 151 Consider the crosspolytope 3 d +1 in R d +1 , i.e. the polytope whose vertices are e 1 , -e 1 , . . . , e d +1 , -e d +1 , with e i the standard i th unit vector. Define a mapping from 3 d +1 to R d , by mapping e i and -e i to the two points in S i for all i ∈ [d + 1], and extend it affinely, see Figure 1.4 By a basic topological argument, each point of R d has an even number of points in its preimage, except those that are the image of points in the faces of 3 d +1 of dimension d -1. Since the facets of 3 d +1 are exactly mapped to the colorful simplices in R d and since S 1 , . . . , S d +1 and p are in general position, the point p is in an even number of colorful simplices.

Figure 1 . 4 :

 14 Figure 1.4: Affine mapping of the crosspolytope

Theorem 1 . 5 . 1 .

 151 Consider d + 1 pairs of points S 1 , . . . , S d +1 in R d and a point p ∈ R d in general position. For each transversal T ⊆ d +1 i =1 S i , consider the (d -1)-simplex defined by conv(T ). Denote by K the sets of all these simplices. Pick a

  Input. A linear program Ax = b, x ≥ 0 and d disjoint feasible bases B 1 , . . . , B d . Task. Find a feasible basis B such that |B ∩ B i | ≤ 1 for all i ∈ [d ].

  Proof. Define d = d +1 and k = k +2. Let S 1 , . . . , S k in R d be an instance with k = d +q. Embed this instance in R d by adding a d th component equal to 0. Add two sets S k+1

  Input. A linear program Ax = b, x ≥ 0 and a partition of [n] into k subsets I 1 , . . . , I k . Task. Decide whether there is a feasible basis B such that |B ∩ I i | ≤ 1 for all i ∈ [k]. Note that this formulation gives a conic version of the problem more general than COLORFUL LINEAR PROGRAMMING, which corresponds to the specific case with A = A 1 . . . 1 and b = 0 1 .

  Input. A configuration of d + 1 pairs of points S 1 , . . . , S d +1 in Q d and a positively dependent colorful set in this configuration. Task. Find another positively dependent colorful set.

[

  A, I m ]x = (1, . . . , 1) T and x ∈ R n+m + (2.4) and [I n , B T ]x = (1, . . . , 1) T and x ∈ R n+m + .

Proposition 2 . 4 . 4 .

 244 Input. A directed graph D = (V, A), whose arcs are partitioned into color classes C 1 , . . . ,C k . Output. Decide whether there is a circuit using at most one arc from each color class. This problem is the decision counterpart of the polynomial problem presented in Proposition 2.4.1. However, when the conditions of the colorful Carathéodory theorem are not satisfied, we have the following proposition. COLORFUL CIRCUIT is NP-complete.

  min c T x s.t. Ax = b, x ≥ 0, with A ∈ R d ×n of full rank, and b ∈ R d .

Define now the colors to be I 1 =Proposition 3 . 1 . 1 .

 1311 {1, . . . , n}, I 2 = {n + 1, . . . , 2n}, . . . , I d = {n(d -1) + 1, . . . , nd }. A feasible solution of the colorful program Ãx = b, x ≥ 0,| supp(x) ∩ I i | ≤ 1, for all i ∈ [d ],induces a solution of the original linear program with the same cost. Conversely, according to a classical result in linear programming, if the optimum is finite, there is an optimal feasible basic solution, hence there is an optimal feasible solution y of the linear program with | supp(y)| ≤ d . This solution gives a feasible solution ỹ of the colorful linear program with same value c T y = cT ỹ. So far we have only considered only the feasibility problem related to colorful linear programming. We now show the following proposition. The two problems of deciding the feasibility of a colorful linear program and of optimizing a colorful linear program are polynomially reducible one to the other.

0 bFigure 3 . 1 : 2 Figure 3 . 2 :

 031232 Figure 3.1: Reduction of a bounded conic case to a convex case

, 4} PFigure 3 . 3 :Proposition 3 . 1 . 4 .

 4}33314 Figure 3.3: PolyhedronP = x ∈ R 4 | x i v i = b, x ≥ 0 defined in Figure 3.2

Theorem 3 . 1 . 6 (Theorem 3 . 1 . 7 .

 316317 General colorful Carathéodory theorem). Consider k sets of pointsS 1 , . . . , S k ⊆ R d and a point p ∈ R d , such that p ∈ k i =1 pos(S i ), and 1 , . . . , k ∈ Z + satisfying 1 + • • • + k = d . There exists a set T ⊆ k i =1 S i satisfying p ∈ pos(T ) and |T ∩ S i | ≤ i for all i ∈ [d ].The linear programming version of this theorem is the following. Consider a linear program Ax = b, x ≥ 0, with A ∈ R d ×n of full rank and b ∈ R d . Consider k disjoint feasible bases B 1 , . . . , B k of the previous linear program and k integers 1 , . . . , k ∈ Z + such that 1 + • • • + k ≥ d . There is a feasible basis B satisfying |B ∩ B i | ≤ i for all i ∈ [k].

Remark 3 . 1 . 8 .

 318 According to the usual colorful Carathéodory theorem (Theorem 1.2.3), there exists a basis B intersecting each B ( j ) i at most once. This basis yields a basis satisfying the statement of the theorem for the original linear program. Theorem 3.1.7 shows that if there are two disjoint bases B 1 , B 2 of a linear program, then for any 0 ≤ ≤ d there is a basis B ⊆ B 1 ∪B 2 , such that |B ∩B 1 | ≤ and |B ∩ B 2 | ≤ d -. Actually, the result with two colors can be proved just by using the connectivity of the 1-skeleton of the polytope of solutions with support in B 1 ∪ B 2 , see Section 1.1.4. Indeed, the two bases B 1 and B 2 correspond to two vertices of the polytope connected by a path. Two vertices on this path are neighbors if and only if their supports differ only by one. Hence, following this path, we change the size of B ∩ B 2 by at most one at each step, and must therefore visit bases with all values of |B ∩ B 2 | between 0 and d . Nevertheless, such a proof does not work as soon as the number of colors is larger than 3, in which case we need Theorem 3.1.7.

and k nonnegative integers 1 ,

 1 . . . , k . Output. Decide whether there is a set T ⊆ k i =1 S i satisfying b ∈ conv(T ) and |T ∩ S i | ≤ i for all i ∈ {1, . . . , k}.

Proposition 3 . 1 . 11 . 2 . 1

 311121 COLORED LINEAR PROGRAMMING is NP-complete even if k = 2 and 1 = 2 = d -1 Before showing this result, we give an equivalent linear programming formulation of this proposition. Consider a linear program A with A ∈ R (d -1)×n and a partition of [n] into two sets [n] = I 1 ∪ I 2 . Deciding whether there exists a feasible solution x, whose support | supp(x) ∩ I 1 | ≤ d -1 2 and |B ∩ I 2 | ≤ d -1 2 is an NP-complete problem. Proving this statement is equivalent to proving Proposition 3.1.11. Proof. The proof works by a reduction of a version of the problem PARTITION. Consider an instance of partition, i.e. a set of d -1 integers {a 1 , . . . , a d -1 }, with d -1 even. PARTITION aims at deciding whether we can partition [d -1] into two sets I and [d -1] \ I of equal size such that i ∈I a i = i ∉I a i . This problem is NP-complete [21].

  with A being a matrix in R d ×n of full rank, b being a point in R d , and I 1 , . . . , I d ⊆ [n] forming a partition of [n]. As for the algorithm presented in Section 2.1.2, we start by adding a dummy column to the matrix A and the corresponding dummy variable z 0 .

Figure 4 . 1 : 3 Proposition 4 . 1 . 4 .

 413414 Figure 4.1: An umbrella of color V 3

  Consider a colorful point configuration S 1 , . . . , S d +1 ⊆ R d and the origin 0 ∈ R d in general position. Define the set of all transversals

Proposition 4 . 3 . 1 .

 431 Consider two cells C and C , the corresponding sets of colorful simplices Ω and Ω , and a path from C to C , going through cell faces corresponding to transversals T 1 , . . . , T r . We haveΩ Ω = U (T 1 ) • • • U (T r ), where U (T ) denotes the set of all colorful sets containing a transversal T .

  0

Figure 4 . 2 :

 42 Figure 4.2: The complete octahedral system

Figure 4 . 4 :

 44 Figure 4.4: Decomposition of the (3, 3, 3)-octahedral system of Figure 4.3

Figure 4 . 5 :

 45 Figure 4.5: Proof of the non realizability of the (3, 3, 3)-octahedral system of Figure 4.3

Figure 5 . 2 :

 52 Figure 5.2:Ω (4,2) ⊆ V 1 × • • • × V 7 with |V i | = 4 for all i

  then there are at least 2|V 1 | ≥ |V 1 | + |V 2 | -2 edges. Otherwise, deg Ω (v * ) = 1 and we note e(v * ) the unique edge incident to v * . Pick w i in V i \ e(v * ) for all i > 1. Applying the parity property to e(v * ), the points in {w 1 , . . . , w n }, and any w ∈ V 1 \ {v * } yields at least |V 1 | edges not intersecting with V 2 \ {e(v * ) 2 , w 2 }. In addition, |V 2 | -2 edges are needed to cover the vertices in V 2 \ {e(v * ) 2 , w 2 }. In total we have at least |V 1 | + |V 2 | -2 edges. Proposition 5.1.1 combined with Proposition 5.2.3 directly implies Proposition 5.2.4. Proposition 5.2.4. ν(m 1 , m 2 , 2, . . . , 2) = m 1 + m 2 -2 for m 1 , m 2 ≥ 2.

Proposition 5 . 1 . 8 . 5 . 2 . 8 .

 518528 1 combined with Theorem 5.2.5 directly implies Proposition 5.2.Proposition If m ≥ n ≥ 2, then ν(m, . . . , m) = n(m -2) + 2.

  We can actually choose (k -1) |X | distinct colorful selections of u i 's. With e(X ), there are in total (k -1) |X | + 1 edges. If |X | ≥ 3, then (k-1) |X | +1 ≥ (k-1) 2 +2. If |X | = 2, there exists j ≤ 3 such that |X ∩V j | = 0. If |V j | ≥ 3, then at least |V j | -2 ≥ 1 edges are needed to cover the vertices of V j not belonging to these (k -1) |X | + 1 edges. Otherwise, |V j | = 2 and we have j ≥ nz + 1 and k = 3. In this case, we have thus k -1 ≥ z ≥ n -2, i.e. n = 4 and z = 2. Ω is then a (3, 3, 2, 2)-octahedral system and (k -1) |X | + 1 = 5.

Lemma 5 . 2 . 12 .

 5212 Consider a (m 1 , . . . , m n-k , k-z times k, . . . , k , z times k -1, . . . , k -1)-octahedral system Ω ⊆ V 1 × • • • × V n without isolated vertices, with m 1 ≥ • • • ≥ m n-k ≥ k ≥ 3 and 0 ≤ z < k ≤ n. If there is a subset X ⊆ n-z i =1 V i ofcardinality at least 2 inducing in D(Ω) a complete subgraph without outneighbors, then Ω has at least (k -1) 2 + |V 1 | + |V 2 | -2k + 1 edges.

CaseLemma 5 . 2 . 13 .

 5213 (b): the degree of v * in Ω is at least k -1. We have then at least (k -1)(|V 1 |-1)+1 = (k -1) 2 + (k -1)(|V 1 |k) + 1 ≥ (k -1) 2 + |V 1 | + |V 2 | -2k + 1 edges. Consider a (m 1 , . . . , m n-k , k-z times k, . . . , k , z times k -1, . . . , k -1)-octahedral system Ω ⊆ V 1 × • • • × V n without isolated vertices, with m 1 ≥ • • • ≥ m n-k ≥ k ≥ 3 and 0 ≤ z < k ≤ n.If there are at least two vertices of V 1 having outneighbors in D(Ω) in the same V i * with i * > nk + 1, then the octahedral system has at least |V i * |(k -1) + |V 1 | + |V 2 | -2k edges.

Case

  (a):|V i * | = k. Choose W i ⊆ V i such that |W i | = k for i ∈ [nz], |W i | = k -1 for i ∈ {nz + 1, . . ., n}, andw∈V i * e(w) ⊆ W = n i =1 W i .

V 1 \

 1 W 1 provides |V 1 |k additional edges not intersecting V 2 \ W 2 . Therefore, |V 2 |k additional edges are needed to cover these vertices of V 2 \ W 2 .In total, we have at least k(k -1)+ |V 1 | + |V 2 | -2k edges. Case (b): |V i * | = k -1. Choose W i ⊆ V i such that |W i | = k -1 for i ∈ {2, . . . , n, |W 1 | = k,andw∈V i * e(w) ⊆ W =

Figure 5 . 3 :

 53 Figure 5.3: The vertex set of the (m 1 , . .. , m n-k , k, . . . , k, k -1, . . . , k -1)-octahedral system Ω ⊆ V 1 × • • • × V n usedfor the proof of Proposition 5.2.14

Proposition 5 . 2 . 14 . 1 2 k 2 + 1 2 k 1 2 n 2 + 1 2 n 1 2 n 2 + 5 2 n

 5214121212 A (m 1 , . . . , m n-k , k-z times k, . . . , k , z times k -1, . . . , k -1)-octahedral system Ω ⊆ V 1 × • • • × V n without isolated vertices, with m 1 ≥ • • • ≥ m n-k ≥ k ≥ 2 and 0 ≤ z < k ≤ n, has at least -8 + |V 1 | + |V 2 |z edges if k ≤ n -2, -10 + |V 1 |z edges if k = n -1, -11z edges if k = n.

5. 3 .

 3 The colorful simplicial depth conjecture configuration in R d . As explained in Section 4.1.1, the setΩ ⊆ V 1 × • • • × V d +1 , with V i = S i for all i ∈ [d + 1]and whose edges correspond to the colorful sets containing 0 in their convex hulls, is an octahedral system. According to [2, Theorem 2.3.], all the classes are covered in this octahedral system. Applying Theorem 5.2.5 with k = n = d +1 gives the lower bound: µ(d ) ≥ d 2 + 1.

Theorem 5 . 3 .Conjecture 5 . 3 . 2 .(Conjecture 5 . 3 . 3 .

 53532533 1 deals with colorful point configuration satisfying the conditions of the colorful Carathéodory theorem, with all S i of size d + 1. The following conjecture generalizes the one given in Introduction. If it were true, it would generalize this result to colorful point configurations of arbitrary size. Consider a colorful point configuration with |S 1| ≥ • • • ≥ |S d +1 | ≥ 2. Any point p ∈ d +1 i =1 conv(S i ) is contained in the convex hulls of at least |S i | -2) + 2c + |S d +1 | |S k+1 |c , colorful simplices, with the convention |S d +2 | = 1.This combinatorial counterpart of this conjecture is the following. Conjecture 5.3.2 is an immediate corollary of this combinatorial version. Consider an octahedral systemΩ ⊆ V 1 × • • • × V n with |V 1 | ≥ • • • ≥ |V n | ≥ 2. If every class is covered in Ω, then |Ω| ≥ min 0≤c≤k≤d +1 c≤|S k+1 | k i =1 (|V i | -2) + 2c + |V k+1 |c × |V n |,with the convention |V n+1 | = 1.

  Introduction[...] In the early 1950s, I moved to Santa Monica to work for the RAND corporation. My doctor advised me to go on a diet to lose weight. I decided I would model my diet as a linear program and let the computer decide my diet. Some revisions of the earlier model, of course, would be necessary in order to give a greater variety of foods to choose from;[...]

(Dantzig, The diet problem, 1990)

1.2. The Colorful Carathéodory theorem: various formulations 1.2 The Colorful Carathéodory theorem: various formu- lations Given

sets S 1 , . . . , S k

Theorem 1.2.4 (Strong

  Bárány proved that Theorem 1.2.1 is actually a corollary of Theorem 1.2.2. We explain this proof now. Consider a colorful configuration of points S 1 , . . . , S d . By a standard perturbation argument, see Section 1.1.3, we can assume that 0 ∈ int conv(S i ) for all i ∈ [d ]. Consider a point p ∈ R d . Choosing ε ≥ 0 small enough, we have εp ∈ conv(S i ) ⊆ pos(S i ) for all i ∈ [d ]. Applying Theorem 1.2.2, we obtain a colorful set T = {t 1 , . . . , t d } ⊆ colorful Carathéodory theorem). Given d positively dependent sets of points S 1 , . . . , S d in R d , and a point v 0 ∈ R d , there exists a colorful set T such that T ∪ {v 0 } is positively dependent.

	d i =1 S i that contains εp in its conic hull. Hence, there exist α 1 , . . . , α d ≥ 0 such that
	d
	εp =	α i t i .
	i =1
	Dividing by ε + d i =1 α i , we obtain that 0 lies in the convex hull of {t 1 , . . . , t d , -p}. Re-
	placing -p by any point in S d +1 proves Theorem 1.2.1.
	Moreover, it proves that any v ∈ d +1 i =1 S i is part of some positively dependent colorful
	set. We have therefore the following stronger statement.

Theorem 1.2.2 (Colorful Carathéodory theorem, conic version). Given d sets S 1 , . . . , S d in R d , and a vector p in d i =1 pos(S i ), there exists a colorful set T such that p ∈ pos(T ). We give proofs of Theorem 1.2.1 and Theorem 1.2.2 in the next section. Theorem 1.2.2 is slightly more general than Theorem 1.2.1. We prove this statement at the end of the section. Finally, there is a "linear programming formulation" of Theorem 1.2.2. This version is actually strictly equivalent to Theorem 1.2.2 and we mention it mostly to familiarize the reader with the notations of this formulation. Consider the system Ax = b, (1.2) x ≥ 0, with A being a matrix in R d ×n and b being a vector in R d . Theorem 1.2.3 (Colorful Carathéodory theorem, linear programming version). If (1.2) admits d pairwise disjoint feasible bases B 1 , . . . , B d ⊆ [n], then there is a feasible basis B ⊆ [n] such that |B ∩ B i | ≤ 1 for all i ∈ [d ]. Similarly, we could give a linear programming formulation of Theorem 1.2.1, by simply adding a row of ones to A and b.

Table 2 .

 2 1: Average solution time and number of pivots for the simplex-like algorithm

  whose arcs are partitioned into color classes C 1 , . . . ,C k and two vertices s, t ∈ V . Output. Decide whether there exists an oriented path from s to t using at most one arc from each color class. This problem is the decision counterpart of the polynomial problem presented in Proposition 2.4.2. However, when the conditions of the colorful Carathéodory theorem are not satisfied we have the following proposition.

Proposition 2.4.3. COLORFUL PATH is NP-complete, even if the graph is acyclic.

  The vertices in V are identified with the vertices of D and the vertices in [n] are identified with the colors. There is an edge ui ∈ E if there is an arc in δ + (u) ∩C i . The arcs of the Hamiltonian circuit yield a perfect matching M in this bipartite graph.

3.

Hence, this arborescence is different from T . Proposition 2.4.11 ensures that the decisions in Step 3 can be made in polynomial time.

Remark 2.4.6. Proposition 2.4.5 also implies the following result. Given a colorful Hamiltonian s-t path in an acyclic directed graph, we can find another colorful s-t path, not necessarily Hamiltonian, in polynomial time.

The second proposition is the "find another" version of COLORFUL CIRCUIT. Again, the existence in Proposition 2.4.7 is a consequence of the Octahedron lemma. Proposition 2.4.7. Let D = (V, A) be a directed graph with n vertices and 2n arcs, whose arcs are partitioned into n pairs C 1 , . . . ,C n , corresponding to colors. If there exists a colorful Hamiltonian circuit, then there exists another colorful circuit, not necessarily Hamiltonian, and it can be found in polynomial time. Proof. Define a bipartite graph G = (V ∪ [n], E ).

  Given a matroid M whose elements are partitioned into color classes, it can be decided in polynomial time whether there exists a colorful basis.

	Proposition 2.4.11. While colorful linear programming and the problem of finding a colorful base of a
	matroid are not special case one of the other, the problem COLORFUL ARBORESCENCE
	falls in both of them.
	Remark 2.4.12 (Back to Sperner's lemma). Remark 2.3.5 of Section 2.3.2 shows that
	even a very special case of Sperner's lemma already leads to a PPAD-complete prob-
	lem. The matroidal counterpart of the Octahedron lemma implies that the problem
	becomes polynomial when the triangulation is the boundary of the cross-polytope
	3 d +1 , defined in Section 1.5.
	Proposition 2.4.10. Let M be a matroid of rank d with no loops. Assume that the
	elements of M are colored in d colors and that the number of elements colored in each
	color is at least two. If there is a colorful basis, then there is another colorful basis and
	this latter can then be found in polynomial time.
	The proof by Magnanti is based on the matroid intersection algorithm due to Lawler [32].
	The same algorithm shows that the matroidal decision version of COLORFUL LINEAR
	PROGRAMMING, namely deciding whether there is a colorful basis in a matroid whose
	elements are colored, is polynomial.

The next proposition is common knowledge in combinatorics. It is a matroidal version of the colorful Carathéodory theorem (with an additional algorithmic result). Proposition 2.4.8. Let M be a matroid of rank d . Assume that the elements of M are colored in d colors. If there exists a monochromatic basis in each color, then there exists a colorful basis and this latter can be found by a greedy algorithm.

A stronger statement has been conjectured by Rota in 1989

[START_REF] Huang | On the relations of various conjectures on latin squares and straightening coefficients[END_REF]

. Interestingly, this conjecture has a similar flavor with the colored Tverberg conjecture, by Bárány and Larman, mentioned in Section 1.6.1.

Conjecture 2.4.9 (Rota's Conjecture). Consider a matroid of rank n and n disjoint bases B 1 , . . . , B n . There exist n disjoint bases C 1 , . . . ,C n such that

|C i ∩ B j | = 1 for all i , j ∈ [n].

A matroidal version of the Octahedron lemma stated in Section 1.5 also exists. It is due to

Magnanti [36]

. Proposition 2.4.13. Let T be the boundary of the (d + 1)-dimensional cross-polytope and let λ : V (T) → [d +1] be any labeling. Assume given a fully-labeled simplex. Another fully-labeled simplex can be computed in polynomial time.

  arise from a colorful point configuration S 1 , . . . , S d +1 in R d ? That is, are all octahedral systems realizable? We give a negative answer to this question in Proposition 4.3.2. Notice that Proposition 4.3.2 also holds for octahedral systems without isolated vertices. Not all octahedral systems are realizable.

	Proposition 4.3.2.

Here is the only case, where we use the fact that m ≥ n ≥ k

Remerciements

Je tiens à remercier en premier lieu mon directeur de thèse, Frédéric Meunier. Attentif et disponible, c'est un directeur hors pair, un soutien précieux et constant et une source inépuisable d'idées et de pistes de recherche. Je souhaite lui témoigner ma gratitude pour ses nombreux conseils et ses méticuleuses relectures, mais aussi et surtout pour le temps passé à "faire de la recherche", c'était un vrai plaisir. J'adresse mes sincères remerciements à Jesus De Loera et à Victor Chepoi pour avoir accepté d'être rapporteurs de cette thèse. Merci également aux examinateurs qui ont accepté de siéger dans le jury de ma soutenance.

Je souhaite également remercier tous les chercheurs avec qui j'ai collaboré. J'ai une pensée chaleureuse pour Max Klimm et Yann Disser, ainsi que pour Wolfgang Mülzer et Yannik Stein. Je remercie bien sûr tout particulièrement Antoine Deza qui m'a acceuillie à Hamilton et a fait naitre chez moi la fièvre de la programmation linéaire colorée. Enfin je remercie Shmuel Onn, pour son hospitalité et pour nos longues discussions sur les chemins du mont Carmel, qui bien qu'interrompues trop tôt restent parmi mes meilleurs souvenirs dans la recherche. Je souhaite évidemment remercier le Cermics, qui m'a offert les meilleurs conditions de travail que peut espérer un doctorant. Je remercie l'université Paris-Est et en particulier Sylvie Cach, pour sa grande disponibilité et sa bonne humeur communicative. J'adresse enfin mes remerciements à l'équipe du Programme Gaspard Monge pour la recherche Opérationnelle et l'Optimisation, et en particulier à Sandrine Charousset. Vient le tour des amis et de la famille, auxquels j'ajouterais ma marraine la bonne fée Isabelle, perle du Cermics. Merci à vous tous, d'avoir veiller sur moi. Un merci particulier à Mamy, pour son soutien depuis toujours, dans les moments joyeux comme dans les moments difficiles. Merci à Alex, Charly et Camou, à mes collocs Soupa et Maria, au BB, à Paraj et Nina, aux Wild Boars et bien sûr à Emmanuel. Merci à tous Acknowledgements les doctorants : les joueurs de tennis (William et Xavier), les coureurs (Axel, Yannick, Laurents et François), les preneurs de café et autres boissons protéïnées (Houssam, Nahia et Pierre), les gentils organisateurs du séminaire (David et Clément), les anciens (Oussam, Daniel, Thomas, Rafik, Adela, ...) merci pour les bons moments passés ensemble, et meilleurs voeux à ceux dont c'est bientôt le tour.

We assume that the problem has a feasible solution. Releasing the constraint (3.4), the problem becomes a linear program we refer to as the non-colorful relaxation. Since the feasible solutions of the colorful linear program are bases of its non-colorful relaxation, we have a lower bound µ inf for this problem. By basic properties of linear programming, µ inf can be polynomially encoded (Cramer's rule). We also obtain an upper bound µ sup , with any feasible solution of the program. Consider now µ ∈ [µ inf , µ sup ] and the following feasibility problem. Using binary search, we can thus solve the problem. At each step, we consider the problem (3.5) with µ = (µ inf + µ sup )/2. If the problem is feasible, we update µ sup := µ, otherwise we update µ inf := µ. At each step the size of [µ inf , µ sup ] is hence divided by two. Using Cramer's rule again, we know that there is a minimal gap ε, polynomially computable, between two values of c T x with x being a feasible basis of the system {Ax = b, x ≥ 0}. Hence, after log 2 (

) iterations, the feasible basis we obtain for

First properties

The following proposition provides an alternate definition for octahedral systems where the condition "|X

. The proof of this proposition is similar to the proof of Theorem 1.5.2, hence we omit its proof.

Proposition 4.1.1.

has an even number of edges. Proof. Consider an octahedral system

Then there is at least one isolated vertex x i in each V i . Hence, if there were an edge (y 1 , . . . , y n ) in Ω, then the parity condition would not be satisfied for

The symmetric difference of two sets is defined by A B = (A∪B )\(A∩B ). The following proposition, proved in [START_REF] Deza | A combinatorial approach to colourful simplicial depth[END_REF], states that the set of all octahedral systems is stable under the symmetric difference operation.

Proposition 4.1.3. Let Ω and Ω be two octahedral systems over the same vertex set. The set Ω Ω is an octahedral system.

All the terms of the sum are even, which allows to conclude.

We now present a family of specific octahedral systems we call umbrellas. An umbrella U is a set of the form {x (1) (1) , . . . , x (i -1) , x (i +1) , . . . , x (n) ) is its transversal. An umbrella is clearly an octahedral system over V 1 × • • • × V n ; moreover we have the following proposition.

Let X be a subset satisfying constraint (4.1) and such that pos(X ) separates K and L.

In addition to color i , the set X misses exactly one other color, which we denote k. All points of S k are on the same side of the hyperplane containing X and 0, since the convex hull of X ∪ {x v , p} contains the origin for every p in S k . The intersection of all cones of the form pos(X ∪ {-y, p}) is thus a nonempty polyhedron with a nonempty interior. Take a point y of K arbitrarily close to C X . Then, either conv(X ∪ {y, p}) contains the origin for all p ∈ S k , or it contains the origin for none of them. Therefore, the i -degree differs between K and L by the cardinality of S k , i.e. of d + 1. It shows that when going through such a C X , the i -degree changes by a multiple of d + 1.

Since it is possible to go from any connected component to any other using neighbors, we get that the i -degrees in the connected components are all equal modulo d + 1. We show now that i -degree in each connected component of F i is a multiple of d + 1. Take a point x is some other connected component of F i . According to what have been just proved, the i -degree of x and the i -degree of x v differ by a multiple of d + 1. Since the i -degree of x v is a multiple of d + 1, the i -degree of x is a multiple of d + 1 as well.

and the two umbrellas

, which is not a multiple of d + 1. According to Proposition 4.3.3, this octahedral system cannot arise from a colorful configuration of points in general position.

Number of octahedral systems

This section provides an answer to an open question raised in [START_REF] Custard | Small octahedral systems[END_REF] by determining the number of distinct octahedral systems.

We recall that the octahedral systems over V 1 ו • •×V n form a F 2 -vector space, according to Lemma 4.2.1. Additionally, by Lemma 4.2.1, the umbrellas form a generating family of the octahedral systems. Let F i denote the binary vector space F V i 2 and H denote the tensor product

There is a one-to-one mapping between the elements of H and the subsets of

where x i is the unit vector of F i having a 1 at position v i and 0 elsewhere. The decomposition over umbrellas can be translated as follows.

Proposition 4.3.4. The subspace of H generated by the vectors of the form x

2 , forms precisely the set of all octahedral systems. Karasev [29] noted that the set of all colorful simplices in a colorful point configuration forms a d -dimensional co-boundary of the join S 1 * . . . * S d +1 with mod 2 coefficients, see [START_REF] Munkres | Elements of algebraic topology[END_REF] for precise definitions of joins and co-boundaries. With the help of Proposition 4.3.4, we further note that the octahedral systems form precisely the (n -1)co-boundaries of the join V 1 * . . . * V n with mod 2 coefficients. Indeed, the vectors of the form

Proof. We denote by G i the subspace of F i whose vectors have an even number of 1's. Let X be the tensor product G 1 ⊗ . . . ⊗G n . Define now ψ as follows:

By the above identification between H and the hypergraphs and according to the alternate definition of an octahedral system given by Proposition 4.1.1, the subspace ker ψ of H is the set of all octahedral systems on vertex sets V 1 , . . . ,V n . Note that by definition ψ is surjective. Therefore, we have dim ker ψ + dim X * = dim H which implies dim ker ψ = dim Hdim X using the isomorphism between a vector space and its dual. The dimension of H is

. This leads to the desired conclusion.

Two isomorphic octahedral systems, that is, identical up to a permutation of the V i 's, or of the vertices in one of the V i 's, are considered distinct in Theorem 4.3.5, which means that we are counting labeled octahedral systems. A natural question is whether there is a non-labeled version of Theorem 4.3.5, that is whether it is possible to compute, or to bound, the number of non-isomorphic octahedral systems. Answering this question would fully answer Question 7 of [START_REF] Custard | Small octahedral systems[END_REF].

Case (c). Finally, for k = n and c = 1, we define n umbrellas:

The octahedral system defined by Ω (n,1) = n i =1 P i covers every classes and satisfies

Since m n ≥ 2, defining Ω (n,0) := Ω (n,1) gives an octahedral system covering every classes and satisfying

Propositions 5.1.1 can be seen as generalizations of the upper bounds given in [START_REF] Deza | A combinatorial approach to colourful simplicial depth[END_REF], which already generalized µ(d ) ≤ d 2 + 1, proved in [START_REF] Deza | Colourful simplicial depth[END_REF].

Note that when

Lower bounds

Preliminaries

The first bound is an immediate corollary of Lemma

If Ω can be written as a symmetric difference of umbrellas, none of them being of color V i , then |Ω| ≥ m i m.

Theorem 5.2.9. An octahedral system without isolated vertices and with

and where (u, v) is an arc in A if, whenever v is incident to e ∈ Ω, we have u incident to e . In other words, (u, v) is an arc of D(Ω) if any edge incident to v is incident to u as well.

For an arc (u, v) ∈ A, v is an outneighbor of u, and u is an inneighbor of v. The set of all outneighbors of u is denoted by

\ X ; that is, the subset of vertices, not in X , being heads of arcs in A having tail in X . The outneighbors of a set X are the elements of N + D(Ω) (X ). Note that D(Ω) is a transitive directed graph: if (u, v) and (v, w) with w = u are arcs of D(Ω), then (u, w) is an arc of D(Ω). In particular, it implies that there is always a nonempty subset X of vertices without outneighbors inducing a complete subgraph in D(Ω). Moreover, a vertex of D(Ω) cannot have two distinct inneighbors in the same V i . While Lemma 5.2.10 allows induction within octahedral systems, Lemmas 5.2.11, 5.2.12, and 5.2.13 are used in the subsequent sections to bound the number of edges of an octahedral system without isolated vertices.

Indeed, the parity property is clearly satisfied. Lemma 5.2.10. Consider an octahedral system Ω without isolated vertices. Consider

cardinality at least 2 inducing in D(Ω) a complete subgraph, then Ω has at least (k -1) 2 + 2 edges, unless Ω is a (3, 3, 2, 2)octahedral system. Under the same condition on X , a (3, 3, 2, 2)-octahedral system has at least 5 edges.

Proof of Proposition 5.2.14. The proof works by induction on

The three inequalities trivially hold in this case.

Suppose that

We choose a pair (k, z) compatible with Ω. Note that (k, z) is not necessarily unique. If k = 2, Proposition 5.2.3 proves the inequality. We can thus assume that k ≥ 3. We consider the two possible cases for the associated D(Ω).

If there are at least two vertices of V 1 having an outneighbor in the same V i * , with i * > nk + 1, we can apply Lemma 5.2.13. If k ≤ n -2, the inequality follows by a straightforward computation, using that z ≥ 1 when Otherwise, for each i > n -k +1, there is at most one vertex of V 1 having an outneighbor in V i . Since k -1 < |V 1 |, there is a vertex x of V 1 having no outneighbors in n i =n-k+2 V i . Starting from x in D(Ω), we follow outneighbors until we reach a set X inducing a complete subgraph of D(Ω) without outneighbors. Since D(Ω) is transitive, we have

we apply Lemma 5.2.12. Thus, we can assume that |X | = 1.

The subhypergraph Ω of Ω induced by n i =1 V i \ X is an octahedral system without isolated vertices since X is a single vertex without outneighbors in D(Ω), see Lemma 5.2.10. Recall that the vertex in X belongs to n-k+1 i =1 V i . Let (k , z ) be possible parameters associated to Ω determined hereafter. Let i 0 be such that X ⊆ V i 0 . The induction argument is applied to the different values of |V i 0 |. It provides a lower bound on the number of edges in Ω ; adding 1 to this lower bound, we get a lower bound on the number of edges in Ω since there is at least one edge containing X .

, and k = n, we have i 0 = n and (k , z ) = (n -1, 0). We can apply the induction hypothesis and get therefore 1 2 n 2 + 1 2 n -10 + (n -1) edges in Ω , plus at least one containing X . In total, we have 1 2 n 2 + 5 2 n-11-(n-1) edges in Ω, as required.

If |V i 0 | = k, z ≤ k -2, and k = n, we have i 0 = 1. For Ω , the pair (k , z ) = (n, z + 1) provides possible parameters. Note that in this case, the colors must be renumbered to keep them with non-decreasing sizes from 1 to n for Ω . We can then apply the induction hypothesis and get therefore 1 2 n 2 + 5 2 n -11z -1 edges in Ω , plus at least one containing X . In total, we have 1 2 n 2 + 5 2 n -11z edges in Ω, as required.

5.3

The colorful simplicial depth conjecture , and Deza et al. [START_REF] Deza | More colourful simplices[END_REF] showed that µ(d ) ≥ Proof. The inequality µ(d ) ≤ d 2 + 1 is proved in [START_REF] Deza | Colourful simplicial depth[END_REF]. Let S 1 , . . . , S d +1 be a colorful point