MSc (Mathematics) / Department of Mathematics and Applied Mathematics / See the attached abstract below

Les données de classement, c.à. d. des listes ordonnées d'objets, apparaissent naturellement dans une grande variété de situations, notamment lorsque les données proviennent d’activités humaines (bulletins de vote d'élections, enquêtes d'opinion, résultats de compétitions) ou dans des applications modernes du traitement de données (moteurs de recherche, systèmes de recommendation). La conception d'algorithmes d'apprentissage automatique, adaptés à ces données, est donc cruciale. Cependant, en raison de l’absence de structure vectorielle de l’espace des classements et de sa cardinalité explosive lorsque le nombre d'objets augmente, la plupart des méthodes classiques issues des statistiques et de l’analyse multivariée ne peuvent être appliquées directement. Par conséquent, la grande majorité de la littérature repose sur des modèles paramétriques. Dans cette thèse, nous proposons une théorie et des méthodes non paramétriques pour traiter les données de classement. Notre analyse repose fortement sur deux astuces principales. La première est l’utilisation poussée de la distance du tau de Kendall, qui décompose les classements en comparaisons par paires. Cela nous permet d'analyser les distributions sur les classements à travers leurs marginales par paires et à travers une hypothèse spécifique appelée transitivité, qui empêche les cycles dans les préférences de se produire. La seconde est l'utilisation des fonctions de représentation adaptées aux données de classements, envoyant ces dernières dans un espace vectoriel. Trois problèmes différents, non supervisés et supervisés, ont été abordés dans ce contexte: l'agrégation de classement, la réduction de dimensionnalité et la prévision de classements avec variables explicatives.La première partie de cette thèse se concentre sur le problème de l'agrégation de classements, dont l'objectif est de résumer un ensemble de données de classement par un classement consensus. Parmi les méthodes existantes pour ce problème, la méthode d'agrégation de Kemeny se démarque. Ses solutions vérifient de nombreuses propriétés souhaitables, mais peuvent être NP-difficiles à calculer. Dans cette thèse, nous avons étudié la complexité de ce problème de deux manières. Premièrement, nous avons proposé une méthode pour borner la distance du tau de Kendall entre tout candidat pour le consensus (généralement le résultat d'une procédure efficace) et un consensus de Kemeny, sur tout ensemble de données. Nous avons ensuite inscrit le problème d'agrégation de classements dans un cadre statistique rigoureux en le reformulant en termes de distributions sur les classements, et en évaluant la capacité de généralisation de consensus de Kemeny empiriques.La deuxième partie de cette théorie est consacrée à des problèmes d'apprentissage automatique, qui se révèlent être étroitement liés à l'agrégation de classement. Le premier est la réduction de la dimensionnalité pour les données de classement, pour lequel nous proposons une approche de transport optimal, pour approximer une distribution sur les classements par une distribution montrant un certain type de parcimonie. Le second est le problème de la prévision des classements avec variables explicatives, pour lesquelles nous avons étudié plusieurs méthodes. Notre première proposition est d’adapter des méthodes constantes par morceaux à ce problème, qui partitionnent l'espace des variables explicatives en régions et assignent à chaque région un label (un consensus). Notre deuxième proposition est une approche de prédiction structurée, reposant sur des fonctions de représentations, aux avantages théoriques et computationnels, pour les données de classements. / Ranking data, i.e., ordered list of items, naturally appears in a wide variety of situations, especially when the data comes from human activities (ballots in political elections, survey answers, competition results) or in modern applications of data processing (search engines, recommendation systems). The design of machine-learning algorithms, tailored for these data, is thus crucial. However, due to the absence of any vectorial structure of the space of rankings, and its explosive cardinality when the number of items increases, most of the classical methods from statistics and multivariate analysis cannot be applied in a direct manner. Hence, a vast majority of the literature rely on parametric models. In this thesis, we propose a non-parametric theory and methods for ranking data. Our analysis heavily relies on two main tricks. The first one is the extensive use of the Kendall’s tau distance, which decomposes rankings into pairwise comparisons. This enables us to analyze distributions over rankings through their pairwise marginals and through a specific assumption called transitivity, which prevents cycles in the preferences from happening. The second one is the extensive use of embeddings tailored to ranking data, mapping rankings to a vector space. Three different problems, unsupervised and supervised, have been addressed in this context: ranking aggregation, dimensionality reduction and predicting rankings with features.The first part of this thesis focuses on the ranking aggregation problem, where the goal is to summarize a dataset of rankings by a consensus ranking. Among the many ways to state this problem stands out the Kemeny aggregation method, whose solutions have been shown to satisfy many desirable properties, but can be NP-hard to compute. In this work, we have investigated the hardness of this problem in two ways. Firstly, we proposed a method to upper bound the Kendall’s tau distance between any consensus candidate (typically the output of a tractable procedure) and a Kemeny consensus, on any dataset. Then, we have casted the ranking aggregation problem in a rigorous statistical framework, reformulating it in terms of ranking distributions, and assessed the generalization ability of empirical Kemeny consensus.The second part of this thesis is dedicated to machine learning problems which are shown to be closely related to ranking aggregation. The first one is dimensionality reduction for ranking data, for which we propose a mass-transportation approach to approximate any distribution on rankings by a distribution exhibiting a specific type of sparsity. The second one is the problem of predicting rankings with features, for which we investigated several methods. Our first proposal is to adapt piecewise constant methods to this problem, partitioning the feature space into regions and locally assigning as final label (a consensus ranking) to each region. Our second proposal is a structured prediction approach, relying on embedding maps for ranking data enjoying theoretical and computational advantages.

En 2010 Chung, Graham et Knuth ont démontré une remarquable identité symétrique sur les nombres eulériens et posé le problème de trouver un q-analogue de leur identité. En utilisant les q-polynômes eulériens introduits par Shareshian-Wachs, nous avons pu obtenir une telle q-identité. La preuve bijective que nous avons imaginée, nous a permis ensuite de démontrer d'autres q-identités symétriques, en utilisant un modèle combinatoire dû à Foata-Han. Entre temps, Hyatt a introduit les fonctions quasisymétriques eulériennes colorées afin d'étudier la distribution conjointe du nombre d'excédances et de l'indice majeur sur les permutations colorées. En appliquant le Decrease Value Theorem de Foata-Han, nous donnons d'abord une nouvelle preuve de sa formule principale sur la fonction génératrice des fonctions quasisymétriques eulériennes colorées, puis généralisons certaines identités eulériennes symétriques, en les exprimant comme des identités sur les fonctions quasisymétriques eulériennes colorées. D'autre part, en prolongeant les travaux récents de Savage-Visontai et Bec-raun, nous considérons plusieurs q-polynômes de descente des mots signés. Leurs fonctions génératrices factorielles et multivariées sont explicitement calculées. Par ailleurs, nous montrons que certains de ces polynômes n'ont que des zéros réels. Enfin, nous étudions la fonction génératrice diagonale des nombres de Jacobi Stirling de deuxième espèce, en généralisant des résultats analogues pour les nombres de Stirling et Legendre-Stirling de deuxième espèce. Il s'avère que cette fonction génératrice est une série rationnelle dont le numérateur est un polynôme à coefficients entiers positifs. En appliquant la théorie des P-partitions de Stanley nous trouvons des interprétations combinatoires de ces coefficients / In 2010 Chung-Graham-Knuth proved an interesting symmetric identity for the Eulerian numbers and asked for a q-analog version. Using the q-Eulerian polynomials introduced by Shareshian-Wachs we find such a q-identity. Moreover, we provide a bijective proof that we further generalize to prove other symmetric qidentities using a combinatorial model due to Foata-Han. Meanwhile, Hyatt has introduced the colored Eulerian quasisymmetric functions to study the joint distribution of the excedance number and major index on colored permutations. Using the Decrease Value Theorem of Foata-Han we give a new proof of his main generating function formula for the colored Eulerian quasisymmetric functions. Furthermore, certain symmetric q-Eulerian identities are generalized and expressed as identities involving the colored Eulerian quasisymmetric functions. Next, generalizing the recent works of Savage-Visontai and Beck-Braun we investigate some q-descent polynomials of general signed multipermutations. The factorial and multivariate generating functions for these q-descent polynomials are obtained and the real rootedness results of some of these polynomials are given. Finally, we study the diagonal generating function of the Jacobi-Stirling numbers of the second kind by generalizing the analogous results for the Stirling and Legendre-Stirling numbers of the second kind. It turns out that the generating function is a rational function, whose numerator is a polynomial with nonnegative integral coefficients. By applying Stanley’s theory of P-partitions we find combinatorial interpretations of those coefficients

No description available.

Les volcans bouclier basaltiques se déforment sous leur propre poids, tout particulièrement en période d'éruption. À Hawaii, cette déformation co-éruptive est en majeure partie expliquée par un plan de décollement à la base des édifices, dont le glissement serait associé à la force de poussée des intrusions dans les «rift zones» (i.e. concentration de dykes subverticaux dans les zones de faiblesse de l'édifice). Cependant, cette explication n'est pas valable pour beaucoup d'autres volcans basaltiques, où l'existence d'un décollement est peu probable. Nous avons profité de l'incision intense du Piton des Neiges (La Réunion) par l'érosion pour observer la structure interne d'un volcan basaltique, et comprendre, par le terrain et la modélisation numérique, comment la déformation d'un tel édifice s'articule avec son activité magmatique. Notre étude structurale révèle que trois populations d'intrusions perpendiculaires (deux subverticales et une subhorizontale) coexistent, et que les principales zones de faiblesses sont des «sill zones» (i.e. concentrations d'intrusions subhorizontales), Parallèlement, notre étude des déformations, essentiellement cassantes, révèle que deux extensions perpendiculaires dominent dans l'édifice, avec l'apparition de régimes localement décrochants et même compressifs à proximité des sill zones. Les directions de déformations et les directions d'intrusions sont compatibles et coïncident aussi avec la direction d'écoulement des grandes avalanches de débris qui ont affectée le Piton des Neiges au cours de son histoire. À partir de ces données de terrain, nous proposons un modèle de déformation du Piton des Neiges où les intrusions dans l'édifice génèrent des cycles de permutations de contraintes. Le stade ultime de chaque cycle serait la mise en place de sills en régime compressif. En testant numériquement l'effet de telles injections sur la déformation d'un édifice, nous montrons que les sills peuvent être un facteur majeur d'instabilité, capable de conduire à des déstabilisations de flanc telles que les avalanches observées. Notre modèle conceptuel, déduit du terrain et quantifié par la modélisation, constitue ainsi une alternative au modèle de déformation hawaiien, applicable sur des édifices tels que le Piton de la Fournaise (La Réunion), Tenerife (Canaries) et Fernandina (Galapagos). Notre étude démontre enfin l'intérêt essentiel d'étudier les systèmes anciens pour mieux comprendre les volcans actifs. / Basaltic shield volcanoes deform under their own weight, especially during eruptive periods. In Hawaii, this co-eruptive deformation is mainly explained by slip events on a basal decollement plane, related to the forceful intrusion of magma into “rift zones”(i.e. high concentration of subvertical dikes in weakness areas). However, this explanation is not valid on many other basaltic shields where the existence of basal decollements is unlikely. We used the deep incision of Piton des Neiges volcano (La Réunion) to observe the internalstructure of a basaltic shield.By coupling a field work and a numerical study, we aimed at understand how deformation interacts with magmatic activity on such an edifice. Our structural study reveals that three populations of perpendicular intrusions coexist and that the main weakness areas are “sill zones” (i.e. high concentration of low-­dipping intrusions). In parallel, our study of brittle deformation structures shows that two perpendicular extensional stress fields dominate in the edifice and that strike-­slip and compressional regimes appear near sill zones. The directions of deformation are compatible with the orientations of intrusions and are also consistent with the directions of emplacement of large debris avalanches, which occurred on Piton des Neiges during its evolution. From these field data, we propose a deformation model of Piton des Neiges volcano where magma intrusion in the edifice generates cycles of stress permutations. The ultimate stage of each cycle consists in sill intrusion under a compressional regime. The numerical simulations, testing the influence of such injections on edifice deformation, reveal that sills can be major instability factors, capable of triggering large flank collapses. Our conceptual model, inferred from field work and quantified by numerical models, thus constitutes an alternative to the Hawaiian model of deformation, applicable on edifices like Piton de la Fournaise (La Réunion), Tenerife (Canary) or Fernandina (Galapagos). Our study finally demonstrates the essential interest of studying old eroded systems to understand active volcanoes.

Cette thèse se divise en 2 grandes parties indépendantes ; la première traitant des nombres de Jacobi-Stirling, la seconde abordant les nombres d’Entringer. La première partie introduit les nombres de Jacobi-Stirling de seconde et de première espèce comme coefficients algébriques dans des relations polynomiales. Nous donnons des interprétations combinatoires de ces nombres, en termes de partitions d’ensembles et de quasi-permutations pour les nombres de seconde espèce, et en termes de permutations pour les nombres de première espèce. Nous étudions également les fonctions génératrices diagonales de ces familles de nombres, ainsi qu’une de leur généralisation sur le modèle des r-nombres de Stirling. La seconde partie introduit les nombres d’Entringer à l’aide de leur interprétation en termes de permutations alternantes. Nous étudions les différentes formules de récurrence vérifiées par ces nombres et généralisons ces résultats à l’aide d’un q-analogue utilisant la statistique d’inversion. Nous verrons également que ces résultats peuvent être étendus à des permutations de forme donnée quelconque. Enfin, nous définissons la notion de famille d’Entringer, et établissons des bijections entre certaines de ces familles. En particulier, nous établissons une bijection reliant les permutations alternantes de premier terme fixé, aux arbres binaires croissants dont l’extrémité du chemin minimal est fixée. / This thesis is constructed in two main independant parts ; the first one dealing with the numbers of Jacobi-Stirling, the second one tackling the numbers of Entringer. The first part introduces the numbers of Jacobi-Stirling of the second kind and of the first kind, as algebraic coefficients in some polynomial relations. We give some combinatorial interpretations of these numbers, in terms of set partitions and quasi-permutations for the numbers of the second kind, and in terms of permutations for the numbers of the first kind. We also study the diagonal generating functions of these sequences of numbers, and one of their generalization based on the model of r-Stirling numbers. The second part introduces the numbers of Entringer with their interpretation in terms of alternating permutations. We study the different recurrences formulas satisfied by these numbers, and refine these results with a q-analogue using the inversion statistic. We also note that these results can be extend to permutations with any fixed shape. Finally, we define the notion of Entringer family, and provide bijections between some of these families. In particular, we establish a bijection between the alternating permutations with fixed given value, and the binary increasing trees such that the end-point of the minimal path is fixed.

Cette thèse porte sur des classes d’objets combinatoires, qui modélisent des données en bio-informatique. Nous étudions notamment deux méthodes de mutation des gènes à l’intérieur du génome : la duplication et l’inversion. Nous étudions d’une part le problème de la duplication-miroir complète avec perte aléatoire en termes de permutations à motifs exclus. Nous démontrons que la classe de permutations obtenue avec cette méthode après p duplications à partir de l’identité est la classe de permutations qui évite les permutations alternées de longueur 2p + 1. Nous énumérons également le nombre de duplications nécessaires et suffisantes pour obtenir une permutation quelconque de longueur n à partir de l’identité. Nous proposons également deux algorithmes efficaces permettant de reconstituer deux chemins différents entre l’identité et une permutation déterminée. Nous donnons enfin des résultats connexes sur d’autres classes proches. La restriction de la relation d’ordre < induite par le code de Gray réfléchi à l’ensemble des compositions et des compositions bornées induit de nouveaux codes de Gray pour ces ensembles. La relation d’ordre < restreinte à l’ensemble des compositions bornées d’un intervalle fournit encore un code de Gray. L’ensemble des ncompositions bornées d’un intervalle généralise simultanément l’ensemble produit et l’ensemble des compositions d’un entier et donc la relation < définit de façon unifiée tous ces codes de Gray. Nous réexprimons les codes de Gray de Walsh et Knuth pour les compositions (bornées) d’un entier à l’aide d’une unique relation d’ordre. Alors, le code de Gray deWalsh pour des classes de compositions et de permutations devient une sous-liste de celui de Knuth, lequel est à son tour une sous-liste du code de Gray réfléchi. / This thesis considers classes of combinatorial objects that model data in bioinformatics. We have studied two methods of mutation of genes within the genome : duplication and inversion. At first,we study the problem of the whole mirror duplication-random lossmodel in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this method after p duplications from the identity is the class of permutations avoiding alternating permutations of length 2p + 1.We also enumerate the number of duplications that are necessary and sufficient to obtain any permutation of length n from the identity. We also suggest two efficient algorithms to reconstruct two different paths between the identity and a specified permutation. Finally,we give related results on other classes nearby. The restriction of the order relation < induced by the reflected Gray code for the sets of compositions and bounded compositions gives new Gray codes for these sets. The order relation < restricted to the set of bounded compositions of an interval also yields a Gray code. The set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so < puts under a single roof all theseGray codes.We re-expressWalsh’s and Knuth’sGray codes for (bounded) compositions of an integer in terms of a unique order relation, and so Walsh’s Gray code becomes a sublist of Knuth’s code, which in turn is a sublist of the Reflected Gray Code.

No description available.

Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the dt t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds on the minimum size k = k(n) of a covering array. Most definitive results are for t = 2, 3, 4.

Šajā darbā mēs pētam kombinatoriskās kartes, kas tiek kodētas kā permutāciju pāri, pielietojot ģeometrisku ideju, ka stūri starp šķautnēm grafam, kas izvietots uz virsmas, ir elementi, uz kuriem permutācijas darbojas.<br />Ģeometriskās kombinatoriskās kartes kā arī parciālās kartes tiek aplūkotas, ciklu pārklājumu teorija, kas dod objektus, kas atbilst cikliem grafā, tiek attīstīta. Tiek atrastas dažas permutāciju formulas, kas rēķina grafu teorētiskos pielietojumos aktuālus karšu raksturlielumus. Visa darba ideja ir meklēt noderīgus pielietojumus: atrast permutāciju izteiksmēs rēķināmus raksturlielumus, kuriem atbilst grafu teorētiski raksturlielumi.<br />Datorprograma, kas rēķina permutāciju formulas un no attīstītās teorijas iegūtos algoritmus, ir izveidota.