Nous montrons la validité du formalisme multifractal pour les mesures aléatoires faiblement Gibbs portées par l’ attracteur associé à une dynamique aléatoire C¹ codée par un sous-shift de type fini aléatoire, et expansive en moyenne. Nous établissons également des loi de type 0-∞ pour les mesures de Hausdorff et de packing généralisées des ensembles de niveau de la dimension locale, et calculons les dimensions de Hausdorff et de packing des ensembles de points en lesquels la dimension inférieure locale et la dimension supérieure locale sont prescrites. Lorsque l’attracteur est un ensemble de Cantor de mesure de Lebesgue nulle, nous montrons la validité du formalisme multifractal pour les mesures discrètes obtenues comme inverses de ces mesures faiblement Gibbs. / We establish the validity of the multifractal formalism for random weak Gibbs measures supported on the attractor associated with a C¹ random dynamics coded by a random subshift of finite type, and expanding in the mean. We also prove a 0-∞ law for the generalized Hausdorff and packing measures of the level sets of the local dimension, and we compute the Hausdorff and packing dimensions of the sets of points at which the lower and upper local dimensions are prescribed. In the case that the attractor is a Cantor set of zero Lebesgue measure, we prove the validity of the multifractal formalism for the discrete measures obtained as inverse of these weak Gibbs measures.

Muitos problemas de otimização em grafos, em especial problemas métricos, são mais fáceis de resolver em árvores. Portanto, uma estratégia para obter um bom algoritmo para certos problemas é obter uma árvore que aproxime o grafo, e utilizar uma solução do problema nessa árvore como uma solução aproximada para o problema no grafo original. Neste trabalho é estudada a técnica de Fakcharoenphol, Rao e Talwar, que mostraram como aproximar uma métrica finita arbitrária com n pontos por uma métrica numa árvore com distorção esperada O(lg n) -- o ótimo assintótico. Essa estratégia resulta em algoritmos de aproximação com boas razões de aproximação, e em algoritmos com bom fator de competitividade para diversos problemas de otimização online e distribuídos. É apresentada especificamente a aplicação da técnica ao problema do emparelhamento mínimo bipartido online, que ilustra como a aproximação de métricas auxilia na resolução de um problema e os cuidados que devem ser tomados nessa aplicação. / Many optimization problems on graphs, especially metric problems, are easier to solve on trees. Therefore, a strategy for obtaining a good algorithm for certain problems is to obtain a tree that approximates the graph, and use a solution of the problem on the tree as an approximate solution for the problem on the original graph. We study the work of Fakcharoenphol, Rao e Talwar, who showed how to approximate an arbitrary finite metric on n points by a tree metric with expected distortion O(lg n), which is asymptotically optimum. This strategy leads to algorithms with good approximation factors, and to competitive algorithms for various optimization problems, some of them online and distributed. Here, we present the application of that technique to the problem of finding a minimum online matching on a bipartite metric graph. This problem illustrates how metric approximation aids in solving a problem, and the care that must be taken when doing such an application.

Muitos problemas de otimização em grafos, em especial problemas métricos, são mais fáceis de resolver em árvores. Portanto, uma estratégia para obter um bom algoritmo para certos problemas é obter uma árvore que aproxime o grafo, e utilizar uma solução do problema nessa árvore como uma solução aproximada para o problema no grafo original. Neste trabalho é estudada a técnica de Fakcharoenphol, Rao e Talwar, que mostraram como aproximar uma métrica finita arbitrária com n pontos por uma métrica numa árvore com distorção esperada O(lg n) -- o ótimo assintótico. Essa estratégia resulta em algoritmos de aproximação com boas razões de aproximação, e em algoritmos com bom fator de competitividade para diversos problemas de otimização online e distribuídos. É apresentada especificamente a aplicação da técnica ao problema do emparelhamento mínimo bipartido online, que ilustra como a aproximação de métricas auxilia na resolução de um problema e os cuidados que devem ser tomados nessa aplicação. / Many optimization problems on graphs, especially metric problems, are easier to solve on trees. Therefore, a strategy for obtaining a good algorithm for certain problems is to obtain a tree that approximates the graph, and use a solution of the problem on the tree as an approximate solution for the problem on the original graph. We study the work of Fakcharoenphol, Rao e Talwar, who showed how to approximate an arbitrary finite metric on n points by a tree metric with expected distortion O(lg n), which is asymptotically optimum. This strategy leads to algorithms with good approximation factors, and to competitive algorithms for various optimization problems, some of them online and distributed. Here, we present the application of that technique to the problem of finding a minimum online matching on a bipartite metric graph. This problem illustrates how metric approximation aids in solving a problem, and the care that must be taken when doing such an application.

En ce moment même, d'énormes quantités de données sont générées, collectées et analysées. Dans de nombreux cas, ces données sont échantillonnées sur des objets à la structure géométrique particulière. De tels objets apparaissent fréquemment dans notre vie quotidienne. Utiliser ce genre de données pour inférer la structure géométrique de tels objets est souvent ardue. Cette tâche est rendue plus difficile encore si les objets sous-jacents sont abstraits ou encore de grande dimension. Dans cette thèse, nous nous intéressons à deux problèmes concernant l'analyse géométrique de données. Dans un premier temps, nous nous penchons sur l'inférence de la métrique de structures filamentaires. En supposant que ces structures sont des espaces métriques proches d'un graphe métrique nous proposons une méthode, combinant les graphes de Reeb et l'algorithme Mapper, pour approximer la structure filamentaire via un graphe de Reeb. Notre méthode peut de plus être facilement implémentée et permet de visualiser simplement le résultat. Nous nous concentrons ensuite sur le problème de la comparaison de formes. Nous étudions un ensemble de méthodes récentes et prometteuses pour la comparaison de formes qui utilisent la notion de carte fonctionnelles. Nos résultats théoriques montrent que ces approches sont stables et peuvent être utilisées dans un contexte plus général que la comparaison de formes comme la comparaison de variétés Riemanniennes de grande dimension. Enfin, en nous basant sur notre analyse théorique, nous proposons une généralisation des cartes fonctionnelles aux nuages de points. Bien que cette généralisation ne bénéficie par des garanties théoriques, elle permet d'étendre le champ d'application des méthodes basées sur les cartes fonctionnelles. / Massive amounts of data are being generated, collected and processed all the time. A considerable portion of them are sampled from objects with geometric structures. Such objects can be tangible and ubiquitous in our daily life. Inferring the geometric information from such data, however, is not always an obvious task. Moreover, it’s not a rare case that the underlying objects are abstract and of high dimension, where the data inference is more challenging. This thesis studies two problems on geometric data analysis. The first one concerns metric reconstruction for filamentary structures. We in general consider a filamentary structure as a metric space being close to an underlying metric graph, which is not necessarily embedded in some Euclidean spaces. Particularly, by combining the Reeb graph and the Mapper algorithm, we propose a variant of the Reeb graph, which not only faithfully approximates the metric of the filamentary structure but also allows for efficient implementation and convenient visualization of the result. Then we focus on the problem of shape comparison. In this part, we study the stability properties of some recent and promising approaches for shape comparison, which are based on the notion of functional maps. Our results show that these approaches are stable in theory and potential for being used in more general setting such as comparing high-dimensional Riemannian manifolds. Lastly, we propose a pipeline for implementing the functional-maps-based frameworks under our stability analysis on unorganised point cloud data. Though our pipeline is experimental, it undoubtedly extends the range of applications of these frameworks.

No description available.

In this thesis I study metric aspects of finite nearly simple groups. Its four distinct chapters deal with four different questions. In the first chapter, I give a full description of the normal subgroup lattice of any algebraic ultraproduct of universal finite quasisimple groups. In the second, I investigate approximation questions for arbitrary abstract and topological groups by families of finite groups with conjugacy-invariant norms. In the third chapter, I prove that the map induced by any non-trivial word on the metric ultraproduct of classical groups of Lie type of unbounded rank is always surjective using cohomological and algebraic methods. In the last chapter, it is proved that (simple) metric ultraproducts of finite classical groups of Lie type of unbounded rank with different field sizes are always non-isomorphic. Also, if the field sizes are equal, two such ultraproducts can only be isomorphic if the Lie types are equal or one Lie type is orthogonal and the other symplectic.:Introduction 0 Notation, basic definitions, and facts 0.1 Group theory 0.2 Some ring and field theory 0.3 Ultraproducts and norms 1 The normal subgroup lattice of an algebraic ultraproduct 1.1 Introduction 1.2 Auxiliary geometric results 1.3 Relative bounded normal generation in universal finite quasisimple groups 1.4 The lattice of normal subgroups 2 Metric approximation of groups by finite groups 2.1 Introduction 2.2 Preliminaries 2.2.1 On C-approximable abstract groups 2.2.2 On C-approximable topological groups 2.3 On Sol-approximable groups 2.4 On Fin-approximable groups 2.5 On the approximability of Lie groups 3 Word maps are surjective on metric ultraproducts 3.1 Introduction 3.2 Symmetric groups 3.2.1 Power words 3.2.2 The cycle structure of elements from PSL_2(q) 3.2.3 Effective surjectivity of word maps over finite fields 3.2.4 Proof of Theorem 3.1 3.3 Unitary groups 3.3.1 Proof of Theorem 3.3 3.3.2 Further implications 3.3.3 Concluding remarks 3.4 Finite groups of Lie type 3.4.1 The linear case 3.4.2 The case of quasisimple groups of Lie type stabilizing a form 3.4.3 An alternative way of proving Theorem 3.1 using wreath products 4 Isomorphism questions for metric ultraproducts 4.1 Introduction 4.2 Description of conjugacy classes in S_U, GL_U(q), and PGL_U(q) 4.3 Characterization of torsion elements in S_U , GL_U(q), and PGL_U(q) 4.4 Faithful action of S_U and PGL_U(q) 4.5 Centralizers in S_U , GL_U(q), Sp_U(q), GO_U(q), and GU_U(q) 4.6 Centralizers in PGL_U(q), PSp_U(q), PGO_U(q), and PGU_U(q) 4.7 Double centralizers of torsion elements 4.7.1 The case S_U 4.7.2 The case PGL_U(q), PSp_U(q), PGO_U(q), and PGU_U(q) 4.8 Distinction of metric ultraproducts 4.8.1 Computation of e_G(o) when gcd{o,p}=gcd{o,|Z|}=1 4.8.2 Proof of Theorem 4.1 Index of Symbols Index Bibliography / In dieser Doktorarbeit studiere ich metrische Aspekte von endlichen fast-einfachen Gruppen. Ihre vier Kapitel beschäftigen sich mit vier unterschiedlichen Themenfeldern. Im ersten Kapitel gebe ich eine vollständige Beschreibung des Normalteilerverbandes eines algebraischen Ultraproduktes von universellen endlichen quasieinfachen Gruppen. Im zweiten beschäftige ich mich mit Approximationsfragen für beliebige abstrakte und topologische Gruppen durch Familien von endlichen Gruppen, auf denen eine konjugationsinvariante Norm erklärt ist. Im dritten Kapitel beweise ich, dass die Abbildung auf einem metrischen Ultraprodukt von klassischen Gruppen vom Lie-Typ von unbeschränktem Rang, die von einem beliebigen nicht-trivialen Wort induziert wird, immer surjektiv ist. Dabei verwende ich sowohl kohomologische als auch algebraische Methoden. Im letzten Kapitel beweise ich, dass (einfache) metrische Ultraprodukte von klassischen endlichen Gruppen vom Lie-Typ von unbeschränktem Rang mit unterschiedlicher Körpergröße immer nicht-isomorph sind. Ist die Körpergröße gleich, so können zwei solche Gruppen nur dann isomorph sein, falls sie auch denselben Lie-Typ haben, oder eine vom orthogonalen Typ und die andere vom symplektischen ist.:Introduction 0 Notation, basic definitions, and facts 0.1 Group theory 0.2 Some ring and field theory 0.3 Ultraproducts and norms 1 The normal subgroup lattice of an algebraic ultraproduct 1.1 Introduction 1.2 Auxiliary geometric results 1.3 Relative bounded normal generation in universal finite quasisimple groups 1.4 The lattice of normal subgroups 2 Metric approximation of groups by finite groups 2.1 Introduction 2.2 Preliminaries 2.2.1 On C-approximable abstract groups 2.2.2 On C-approximable topological groups 2.3 On Sol-approximable groups 2.4 On Fin-approximable groups 2.5 On the approximability of Lie groups 3 Word maps are surjective on metric ultraproducts 3.1 Introduction 3.2 Symmetric groups 3.2.1 Power words 3.2.2 The cycle structure of elements from PSL_2(q) 3.2.3 Effective surjectivity of word maps over finite fields 3.2.4 Proof of Theorem 3.1 3.3 Unitary groups 3.3.1 Proof of Theorem 3.3 3.3.2 Further implications 3.3.3 Concluding remarks 3.4 Finite groups of Lie type 3.4.1 The linear case 3.4.2 The case of quasisimple groups of Lie type stabilizing a form 3.4.3 An alternative way of proving Theorem 3.1 using wreath products 4 Isomorphism questions for metric ultraproducts 4.1 Introduction 4.2 Description of conjugacy classes in S_U, GL_U(q), and PGL_U(q) 4.3 Characterization of torsion elements in S_U , GL_U(q), and PGL_U(q) 4.4 Faithful action of S_U and PGL_U(q) 4.5 Centralizers in S_U , GL_U(q), Sp_U(q), GO_U(q), and GU_U(q) 4.6 Centralizers in PGL_U(q), PSp_U(q), PGO_U(q), and PGU_U(q) 4.7 Double centralizers of torsion elements 4.7.1 The case S_U 4.7.2 The case PGL_U(q), PSp_U(q), PGO_U(q), and PGU_U(q) 4.8 Distinction of metric ultraproducts 4.8.1 Computation of e_G(o) when gcd{o,p}=gcd{o,|Z|}=1 4.8.2 Proof of Theorem 4.1 Index of Symbols Index Bibliography