In this manuscript, we provide foundations of properties of homogeneous polynomials such as the half-plane property, determinantal representability, being weakly determinantal, and having a spectrahedral hyperbolicity cone. One of the motivations for studying those properties comes from the ``generalized Lax conjecture'' stating that every hyperbolicity cone is spectrahedral. The conjecture has particular importance in convex optimization and has curious connections to other areas. We take a combinatorial approach, contemplating the properties on matroids with a particular focus on operations that preserve these properties. We show that the spectrahedral representability of hyperbolicity cones and being weakly determinantal are minor-closed properties. In addition, they are preserved under passing to the faces of the Newton polytopes of homogeneous polynomials. We present a proved-to-be computationally feasible algorithm to test the half-plane property of matroids and another one for testing being weakly determinantal. Using the computer algebra system Macaulay2 and Julia, we implement these algorithms and conduct tests. We classify matroids on at most 8 elements with respect to the half-plane property and provide our test results on matroids with 9 elements. We provide 14 matroids on 8 elements of rank 4, including the Vámos matroid, that are potential candidates for the search of a counterexample for the conjecture.:1 Background 1 1.1 Some Properties of Homogeneous Polynomials . . . . . . . . . . 1 Hyperbolic Polynomials . . . . . . . . . . . . . . . . . . . . . . 1 The Half-Plane Property and Stability . . . . . . . . . . . . . . 8 Determinantal Representability . . . . . . . . . . . . . . . . . . 15 Spectrahedral Representability . . . . . . . . . . . . . . . . . . 19 1.2 Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Some Operations on Matroids . . . . . . . . . . . . . . . . . . . 29 The Half-Plane Property of Matroids . . . . . . . . . . . . . . . 36 2 Some Operations 43 2.1 Determinantal Representability of Matroids . . . . . . . . . . . 43 A Criterion for Determinantal Representability . . . . . . . . . 46 2.2 Spectrahedral Representability of Matroids . . . . . . . . . . . 50 2.3 Matroid Polytopes . . . . . . . . . . . . . . . . . . . . . . . . . 54 Newton Polytopes of Stable Polynomials . . . . . . . . . . . . . 59 3 Testing the Properties: an Algorithm 61 The Half-Plane Property . . . . . . . . . . . . . . . . . . . . . . 61 Being SOS-Rayleigh and Weak Determinantal Representability 65 4 Test Results on Matroids on 8 and 9 Elements 71 4.1 Matroids on 8 Elements . . . . . . . . . . . . . . . . . . . . . . 71 SOS-Rayleigh and Weakly Determinantal Matroids . . . . . . . 76 4.2 Matroids on 9 Elements . . . . . . . . . . . . . . . . . . . . . . 80 5 Conclusion and Future Perspectives 85 5.1 Spectrahedral Matroids . . . . . . . . . . . . . . . . . . . . . . 86 5.2 Non-negative Non-SOS Polynomials . . . . . . . . . . . . . . . 88 5.3 Completing the Classification of Matroids on 9 Elements and More 89 Bibliography 91

Nous nous intéressons dans cette thèse à la problématique de la décision collective. L’objectif est de déterminer une solution de compromis pour des problèmes soumis à de multiples points de vue. Les problèmes considérés sont de nature combinatoire. Plus précisément, il s’agit de la classe des systèmes d’ensembles qui ont une structure de matroïde. La théorie des matroïdes est centrale en optimisation combinatoire, elle a permis d’unifier des structures apparemment séparées comme les arbres et les couplages dans les graphes et elle a engendré des algorithmes efficaces pour résoudre des problèmes d’optimisation non triviaux en temps polynomial. Nous nous intéressons à fournir des algorithmes d’approximation polynomiaux centralisés et décentralisés avec garantie de performance pour déterminer une solution de compromis qui est une base du matroïde. La solution de compromis doit également être équitable pour tous les membres de la collectivité. Nous portons un intérêt particulier au problème de partage équitable de biens indivisibles qui est une thématique importante en choix social computationnel et dont le problème se modélise par les matroïdes. / In this thesis, we are interested in collective decision-making. The objective is to find a tradeoff solution for problems that are evaluated by multiple points of view. We consider problems having a matroid structure. Matroid theory is significant in combinatorial optimization, it helped to unify apparently separated structures like forests and matchings in graphs and it includes efficient algorithms for solving non-trivial optimization problems in polynomial time. We are interested to provide polynomial time centralized and decentralized approximation algorithms for finding a tradeoff solution which is a base of the matroid. The tradeoff solution must also be fair for all the members of the community. We are particularly interested in the issue of the fair division of indivisible goods which is central in computational social choice and that can be modeled by matroids.

<p>This thesis deals with combinatorial and geometric aspects of linear optimization, and consists of two parts.</p> <p>In the first part, we address a conjecture formulated in 2008 and stating that the largest possible average diameter of a bounded cell of a simple hyperplane arrangement of n hyperplanes in dimension d is not greater than the dimension d. The average diameter is the sum of the diameters of each bounded cell divided by the total number of bounded cells, and then we consider the largest possible average diameter over all simple hyperplane arrangements. This quantity can be considered as an indication of the average complexity of simplex methods for linear optimization. Previous results in dimensions 2 and 3 suggested that a specific type of extensions, namely the covering extensions, of the cyclic arrangement might achieve the largest average diameter. We introduce a method for enumerating the covering extensions of an arrangement, and show that covering extensions of the cyclic arrangement are not always among the ones achieving the largest diameter.</p> <p>The software tool we have developed for oriented matroids computation is used to exhibit a counterexample to the hypothesized minimum number of external facets of a simple arrangement of n hyperplanes in dimension d; i.e. facets belonging to exactly one bounded cell of a simple arrangement. We determine the largest possible average diameter, and verify the conjectured upper bound, in dimensions 3 and 4 for arrangements defined by no more than 8 hyperplanes via the associated uniform oriented matroids formulation. In addition, these new results substantiate the hypothesis that the largest average diameter is achieved by an arrangement minimizing the number of external facets.</p> <p>The second part focuses on the colourful simplicial depth, i.e. the number of colourful simplices in a colourful point configuration. This question is closely related to the colourful linear programming problem. We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in R^d is contained in at least (d+1)²/2 simplices with one vertex from each set. This improves the previously established lower bounds for d>=4 due to Barany in 1982, Deza et al in 2006, Barany and Matousek in 2007, and Stephen and Thomas in 2008.</p> <p>We also introduce the notion of octahedral system as a combinatorial generalization of the set of colourful simplices. Configurations of low colourful simplicial depth correspond to systems with small cardinalities. This construction is used to find lower bounds computationally for the minimum colourful simplicial depth of a configuration, and, for a relaxed version of the colourful depth, to provide a simple proof of minimality.</p> / Doctor of Philosophy (PhD)

No description available.