<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)

A relação entre os grupos de tranças de superfícies e os grupos de homotopia das esferas é atualmente um tópico de bastante interesse. Nos últimos anos tem sido feitos avanços consideráveis no estudo desta relação no caso dos grupos de tranças de Artin com n cordas, denotado por Bn, da esfera e do plano projetivo. Nessa tese analisamos com detalhes as interações entre a teoria de tranças e a teoria de homotopia, e mostramos novos resultados que estabelecem conexões entre os grupos de homotopia da 2-esfera S2 e os grupos de tranças sobre qualquer superfície. No andamento deste trabalho, descobrimos uma conexão surpreendente dos grupos de tranças com os grupos cristalográficos e de Bieberbach: para n maior ou igual que 3, o grupo quociente Bn/[Pn, Pn] é um grupo cristalográfico que contém grupos de Bieberbach como subgrupos, onde Pn é o subgrupo de tranças puras de Bn. Com isto obtivemos uma formulação de um Teorema de Auslander e Kuranishi para 2-grupos finitos e exibimos variedades Riemannianas compactas planas que admitem difeomorfismo de Anosov e cujo grupo de holonomia é Z2k . Além disso, durante esta tese, detectamos e, quando possível, corrigimos algumas imprecisões em dois importantes artigos nessa área de estudo, escritos por J. Berrick, F. R. Cohen, Y. L. Wong e J. Wu (Jour. Amer. Math. Soc. - 2006) assim como por J. Y. Li e J.Wu (Proc. London Math. Soc. - 2009). / The relation between surface braid groups and homotopy groups of spheres is currently a subject of great interest. Considerable progress has been made in recent years in the study of these relations in the case of the n-string Artin braid groups, denoted by Bn, the sphere and the projective plane. In this thesis we analyse in detail the interactions between braid theory and homotopy theory, and we present new results that establish connections between the homotopy groups of the 2-sphere S2 and the braid groups of any surface. During the course of this work, we discovered an unexpected connection of braid groups with crystallographic and Bieberbach groups: for n greater or equal than 3, the quotient group Bn/[Pn, Pn] is a crystallographic group that contains Bieberbach groups as subgroups, where Pn is the pure braid subgroup of Bn. This enables us to obtain a formulation of a theorem of Auslander and Kuranishi for finite 2-groups, and to exhibit Riemannian compact flat manifolds that admit Anosov diffeomorphisms and whose holonomy group is Z2k. In addition, during the thesis, we have detected, and where possible, corrected some inaccuracies in two important papers in the area of study, by J. Berrick, F. R. Cohen, Y. L. Wong and J. Wu (Jour. Amer. Math. Soc. - 2006), and by J. Y. Li and J. Wu (Proc. London Math. Soc. - 2009).

A relação entre os grupos de tranças de superfícies e os grupos de homotopia das esferas é atualmente um tópico de bastante interesse. Nos últimos anos tem sido feitos avanços consideráveis no estudo desta relação no caso dos grupos de tranças de Artin com n cordas, denotado por Bn, da esfera e do plano projetivo. Nessa tese analisamos com detalhes as interações entre a teoria de tranças e a teoria de homotopia, e mostramos novos resultados que estabelecem conexões entre os grupos de homotopia da 2-esfera S2 e os grupos de tranças sobre qualquer superfície. No andamento deste trabalho, descobrimos uma conexão surpreendente dos grupos de tranças com os grupos cristalográficos e de Bieberbach: para n maior ou igual que 3, o grupo quociente Bn/[Pn, Pn] é um grupo cristalográfico que contém grupos de Bieberbach como subgrupos, onde Pn é o subgrupo de tranças puras de Bn. Com isto obtivemos uma formulação de um Teorema de Auslander e Kuranishi para 2-grupos finitos e exibimos variedades Riemannianas compactas planas que admitem difeomorfismo de Anosov e cujo grupo de holonomia é Z2k . Além disso, durante esta tese, detectamos e, quando possível, corrigimos algumas imprecisões em dois importantes artigos nessa área de estudo, escritos por J. Berrick, F. R. Cohen, Y. L. Wong e J. Wu (Jour. Amer. Math. Soc. - 2006) assim como por J. Y. Li e J.Wu (Proc. London Math. Soc. - 2009). / The relation between surface braid groups and homotopy groups of spheres is currently a subject of great interest. Considerable progress has been made in recent years in the study of these relations in the case of the n-string Artin braid groups, denoted by Bn, the sphere and the projective plane. In this thesis we analyse in detail the interactions between braid theory and homotopy theory, and we present new results that establish connections between the homotopy groups of the 2-sphere S2 and the braid groups of any surface. During the course of this work, we discovered an unexpected connection of braid groups with crystallographic and Bieberbach groups: for n greater or equal than 3, the quotient group Bn/[Pn, Pn] is a crystallographic group that contains Bieberbach groups as subgroups, where Pn is the pure braid subgroup of Bn. This enables us to obtain a formulation of a theorem of Auslander and Kuranishi for finite 2-groups, and to exhibit Riemannian compact flat manifolds that admit Anosov diffeomorphisms and whose holonomy group is Z2k. In addition, during the thesis, we have detected, and where possible, corrected some inaccuracies in two important papers in the area of study, by J. Berrick, F. R. Cohen, Y. L. Wong and J. Wu (Jour. Amer. Math. Soc. - 2006), and by J. Y. Li and J. Wu (Proc. London Math. Soc. - 2009).

Submitted by Livia Mello (liviacmello@yahoo.com.br) on 2016-10-05T14:40:49Z No. of bitstreams: 1 DissCHFP.pdf: 1216039 bytes, checksum: e21e062b0283d2bfe6ec436442e824a5 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:23:38Z (GMT) No. of bitstreams: 1 DissCHFP.pdf: 1216039 bytes, checksum: e21e062b0283d2bfe6ec436442e824a5 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:23:43Z (GMT) No. of bitstreams: 1 DissCHFP.pdf: 1216039 bytes, checksum: e21e062b0283d2bfe6ec436442e824a5 (MD5) / Made available in DSpace on 2016-10-20T19:23:50Z (GMT). No. of bitstreams: 1 DissCHFP.pdf: 1216039 bytes, checksum: e21e062b0283d2bfe6ec436442e824a5 (MD5) Previous issue date: 2016-02-25 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / In this work, we will use topological methods in combinatorics and geometry to present a proof of the topological Tverberg theorem and a result about many Tverberg partitions. / O objetivo principal desta dissertação consiste em desenvolver um estudo detalhado de métodos topológicos em combinatória e geometria visando apresentar uma prova da versão topológica do teorema de Tverberg e de um teorema sobre a quantidade de partições de Tverberg. / FAPESP: 2015/01264-7

No description available.

Inspired by Happel's question, whether the exchange graph and the simplicial complex of tilting modules over a quiver algebra are independent from the multiplicities of multiple arrows in the quiver, we study quantitative aspects of Fomin and Zelevinsky's quiver mutation rule. Our results turn out to be very useful in the mutation-infinite case for understanding combinatorial structures as the cluster exchange graph or the simplicial complex of tilting modules, which are governed by quiver mutation. Using a class of quivers we call forks we can show that any such quiver yields a tree in the exchange graph. This allows us to provide a good global description of the exchange graphs of arbitrary mutation-infinite quivers. In particular we show that the exchange graph of an acyclic quiver is a tree if (and in fact only if) any two vertices are connected by at least two arrows. Furthermore we give classification results for the simplicial complexes and thereby obtain a partial positive answer to Happel's question. Another consequence of our findings is a confirmation of Unger's conjecture about the infinite number of components of the tilting exchange graph in all but finitely many cases. Finally we generalise and conceptualise our results by introducing what we call "polynomial quivers", stating several conjectures about "polynomial quiver mutation", and giving proofs in special cases.

Dans [PRID], Pridham a montré que tout n-champs d'Artin M admet une présentation en tant que schéma simplicial X. → M, telle que le schéma simplicial X satisfait à certaines propriétés notées par G.Pn,k de [GROTH]. Dans la présentation (…→ X2 → X1 → X0 → M), le schéma X1 représente une carte pour X0 x MX0. Donc, la lissité de X0 → M est équivalente à la lissité des deux projections ә0,ә1 : X1 → X0. Ce sont les deux premières parties de la condition de Grothendieck-Pridham, notées G.P1,0 et G.P1,1. Dans [BENZ12] nous avons introduit un n-champ d'Artin M des éléments de Maurer-Cartan d'une dg-catégorie. On a construit une carte, et on a déjà fait la preuve des premières conditions de lissité explicitement. Pour tout n et tout 0 ≤ k ≤ n Pridham considère un schéma noté MatchΛkn(X) avec un morphisme Xn → MatchΛkn(X). On construira explicitement le schéma simplicial de Grothendieck-Pridham X, on montrera la lissité formelle de cette carte précédente, ainsi que M est un n-champ géométrique. / In [PRID], Pridham has shown that any Artin n-stack M has a presentation as a simplicial scheme X. → M such that the simplicial scheme X satisfies certain properties denoted G.Pn,k of [GROTH]. In the presentation (…→ X2 → X1 → X0 → M), the scheme X1 represents a chart for X0 x MX0. Thus, the smoothness of X0 → M is equivalent to the smoothness of the two projections ә0,ә1 : X1 → X0. These are the first two parts of the Grothendieck-Pridham condition, denoted G.P1,0 and G.P1,1. In [BENZ12] we introduced an Artin n-stack M of Maurer-Cartan elements of a dg-category. We constructed a chart, and have already proven the first smoothness conditions explicitly. For any n and any 0 ≤ k ≤ n Pridham considers a scheme denoted MatchΛkn(X) with a morphism Xn → MatchΛkn(X). We will construct explicitly the Grothendieck-Pridham simplicial scheme and show the smoothness of the preceding map, therefore M is a geometric n-stack.

La quantité de données disponibles n'a jamais été aussi grande. Se poser les bonnes questions, c'est-à-dire des questions qui soient à la fois pertinentes et dont la réponse est accessible est difficile. L'analyse topologique de données tente de contourner le problème en ne posant pas une question trop précise mais en recherchant une structure sous-jacente aux données. Une telle structure est intéressante en soi mais elle peut également guider le questionnement de l'analyste et le diriger vers des questions pertinentes. Un des outils les plus utilisés dans ce domaine est l'homologie persistante. Analysant les données à toutes les échelles simultanément, la persistance permet d'éviter le choix d'une échelle particulière. De plus, ses propriétés de stabilité fournissent une manière naturelle pour passer de données discrètes à des objets continus. Cependant, l'homologie persistante se heurte à deux obstacles. Sa construction se heurte généralement à une trop large taille des structures de données pour le travail en grandes dimensions et sa robustesse ne s'étend pas au bruit aberrant, c'est-à-dire à la présence de points non corrélés avec la structure sous-jacente.Dans cette thèse, je pars de ces deux constatations et m'applique tout d'abord à rendre le calcul de l'homologie persistante robuste au bruit aberrant par l'utilisation de la distance à la mesure. Utilisant une approximation du calcul de l'homologie persistante pour la distance à la mesure, je fournis un algorithme complet permettant d'utiliser l'homologie persistante pour l'analyse topologique de données de petite dimension intrinsèque mais pouvant être plongées dans des espaces de grande dimension. Précédemment, l'homologie persistante a également été utilisée pour analyser des champs scalaires. Ici encore, le problème du bruit aberrant limitait son utilisation et je propose une méthode dérivée de l'utilisation de la distance à la mesure afin d'obtenir une robustesse au bruit aberrant. Cela passe par l'introduction de nouvelles conditions de bruit et l'utilisation d'un nouvel opérateur de régression. Ces deux objets font l'objet d'une étude spécifique. Le travail réalisé au cours de cette thèse permet maintenant d'utiliser l'homologie persistante dans des cas d'applications réelles en grandes dimensions, que ce soit pour l'inférence topologique ou l'analyse de champs scalaires. / Massive amounts of data are now available for study. Asking questions that are both relevant and possible to answer is a difficult task. One can look for something different than the answer to a precise question. Topological data analysis looks for structure in point cloud data, which can be informative by itself but can also provide directions for further questioning. A common challenge faced in this area is the choice of the right scale at which to process the data.One widely used tool in this domain is persistent homology. By processing the data at all scales, it does not rely on a particular choice of scale. Moreover, its stability properties provide a natural way to go from discrete data to an underlying continuous structure. Finally, it can be combined with other tools, like the distance to a measure, which allows to handle noise that are unbounded. The main caveat of this approach is its high complexity.In this thesis, we will introduce topological data analysis and persistent homology, then show how to use approximation to reduce the computational complexity. We provide an approximation scheme to the distance to a measure and a sparsifying method of weighted Vietoris-Rips complexes in order to approximate persistence diagrams with practical complexity. We detail the specific properties of these constructions.Persistent homology was previously shown to be of use for scalar field analysis. We provide a way to combine it with the distance to a measure in order to handle a wider class of noise, especially data with unbounded errors. Finally, we discuss interesting opportunities opened by these results to study data where parts are missing or erroneous.

Inspired by Happel's question, whether the exchange graph and the simplicial complex of tilting modules over a quiver algebra are independent from the multiplicities of multiple arrows in the quiver, we study quantitative aspects of Fomin and Zelevinsky's quiver mutation rule. Our results turn out to be very useful in the mutation-infinite case for understanding combinatorial structures as the cluster exchange graph or the simplicial complex of tilting modules, which are governed by quiver mutation. Using a class of quivers we call forks we can show that any such quiver yields a tree in the exchange graph. This allows us to provide a good global description of the exchange graphs of arbitrary mutation-infinite quivers. In particular we show that the exchange graph of an acyclic quiver is a tree if (and in fact only if) any two vertices are connected by at least two arrows. Furthermore we give classification results for the simplicial complexes and thereby obtain a partial positive answer to Happel's question. Another consequence of our findings is a confirmation of Unger's conjecture about the infinite number of components of the tilting exchange graph in all but finitely many cases. Finally we generalise and conceptualise our results by introducing what we call "polynomial quivers", stating several conjectures about "polynomial quiver mutation", and giving proofs in special cases.