Dissertations / Theses on the topic 'Espèce combinatoire'

L'objet de cette these est l'etude combinatoire des revetements entre surfaces de riemann et de leurs espaces modulaires : les espaces de hurwitz. Les methodes utilisees sont graphiques : nous utilisons largement le concept de graphe epais. Nous donnons un algorithme de calcul des lacets d'homologie d'un tel graphe. Nous montrons le theoreme d'existence de riemann au niveau des graphes epais. Nous detaillons le processus, du a j. L. Harer et m. Kontsevich, realisant un graphe epais a n faces muni de longueurs d'aretes en une surface de riemann compacte privee de n piqures. Ce processus, bijectif par le theoreme de strebel, mene a une decomposition cellulaire connue et fondamentale des espaces de modules de surfaces de riemann compactes de genre fixe et privees de n piqures. Nous sommes alors en mesure de preciser la variation de la structure complexe en fonction des longueurs d'aretes (ce qui donne la continuite du processus), et de generaliser le processus aux revetements de surfaces de riemann compactes. Cela conduit a la decomposition cellulaire des espaces de hurwitz. Nous etudions un exemple ou l'espace de hurwitz s'identifie a une courbe modulaire. L'etude des revetements cycliques des tores permet de relier l'espace de hurwitz correspondant a des espaces de modules definis par e. Witten dans le cadre d'une conjecture generalisant celle demontree par m. Kontsevich. L'extension des resultats aux compactifications des espaces de modules et de hurwitz s'appuie sur le phenomene de retraction de boucles d'un graphe epais ne bordant pas des faces.

Cette thèse concerne la combinatoire et l'algorithmique des cartes. En utilisant la théorie des espèces de Joyal, on parvient à des résultats énumératifs concernant les cartes non-étiquetées et étiquetées, enracinées ou non, en genre quelconque suivant leur nombre de faces et d'arêtes. Nous relions la combinatoire des cartes à l'asymptotique de la fonction de Airy par un rapprochement inattendu entre la série génératrice du nombre de cartes triangulaires et le développement asymptotique de la fonction de Airy. Nous donnons également un algorithme permettant de dresser une liste exhaustive des cartes triangulaires, en temps amorti constant pour le cas enraciné
This thesis is about combinatoric and algorithmic aspects of maps. Using the species theory of Joyal, we get enumerative results concerning labeled and unlabeled maps both rooted or not, of any genus, by the number of their edges and faces. We relate the combinatorics of maps to the asymptotics of the Airy function by a unexpected matching of the generating series of triangular maps and the asymptotic development of the Airy function.We also give an algorithm able to produce an exhaustive list of triangular maps, in constant amortized time in the rooted case

Le but du travail est de contribuer aux connaissances sur le développement cognitif dans le domaine logico-mathématique et sur l'acquisition par les enfants et les élèves de notions relatives au produit cartésien. Trois champs de problèmes sont étudiés: la combinatoire des dimensions, le repérage avec des coordonnées cartésiennes, les mesures spatiales de surface. Pour analyser dans un même cadre conceptuel spécifique l'évolution des processus dans ces différents domaines l'auteur fait intervenir la notion de dimensionnalité

L'analyse et l'exploitation des préférences interviennent dans de nombreux domaines, comme l'économie, les sciences sociales ou encore la psychologie. Depuis quelques années, c'est l'e-commerce qui s'intéresse au sujet dans un contexte de personnalisation toujours plus poussée. Notre étude s'est portée sur la représentation et l'apprentissage de préférences sur des objets décrits par un ensemble d'attributs. Ces espaces combinatoires sont immenses, ce qui rend impossible en pratique la représentation in extenso d'un ordre de préférences sur leurs objets. C'est pour cette raison que furent construits des langages permettant de représenter de manière compacte des préférences sur ces espaces combinatoires. Notre objectif a été d'étudier plusieurs langages de représentation de préférences et l'apprentissage de préférences. Nous avons développé deux axes de recherche. Le premier axe est l'algorithme DRC, un algorithme d'inférence dans les réseaux bayésiens. Alors que les autres méthodes d'inférence utilisent le réseau bayésien comme unique source d'information, DRC exploite le fait qu'un réseau bayésien est souvent appris à partir d'un ensemble d'objets qui ont été choisis ou observés. Ces exemples sont une source d'information supplémentaire qui peut être utilisée lors de l'inférence. L'algorithme DRC, de ce fait, n'utilise que la structure du réseau bayésien, qui capture des indépendances conditionnelles entre attributs et estime les probabilités conditionnelles directement à partir du jeu de données. DRC est particulièrement adapté à une utilisation dans un contexte où les lois de probabilité évoluent mais où les indépendances conditionnelles ne changent pas. Le second axe de recherche est l'apprentissage de k-LP-trees à partir d'exemples d'objets vendus. Nous avons défini formellement ce problème et introduit un score et une distance adaptés. Nous avons obtenu des résultats théoriques intéressants, notamment un algorithme d'apprentissage de k-LP-trees qui converge avec assez d'exemples vers le modèle cible, un algorithme d'apprentissage de LP-tree linéaire optimal au sens où il minimise notre score, ainsi qu'un résultat sur le nombre d'exemples suffisants pour apprendre un " bon " LP-tree linéaire : il suffit d'avoir un nombre d'exemples qui dépend logarithmiquement du nombre d'attributs du problème. Enfin, une contribution expérimentale évalue différents langages dont nous apprenons des modèles à partir d'historiques de voitures vendues. Les modèles appris sont utilisés pour la recommandation de valeur en configuration interactive de voitures Renault. La configuration interactive est un processus de construction de produit où l'utilisateur choisit successivement une valeur pour chaque attribut. Nous évaluons la précision de la recommandation, c'est-à-dire la proportion des recommandations qui auraient été acceptées, et le temps de recommandation ; de plus, nous examinons les différents paramètres qui peuvent influer sur la qualité de la recommandation. Nos résultats sont concluants : les méthodes que nous avons évaluées, qu'elles proviennent de la littérature ou de nos contributions théoriques, sont bien assez rapides pour être utilisées en ligne et ont une précision très élevée, proche du maximum théorique
The analysis and the exploitation of preferences occur in multiple domains, such as economics, humanities and psychology. E-commerce got interested in the subject a few years ago with the surge of product personalisation. Our study deals with the representation and the learning of preferences on objects described by a set of attributes. These combinatorial spaces are huge, which makes the representation of an ordering in extenso intractable. That's why preference representation languages have been built: they can represent preferences compactly on these huge spaces. In this dissertation, we study preference representation languages and preference learning.Our work focuses on two approaches. Our first approach led us to propose the DRC algorithm for inference in Bayesian networks. While other inference algorithms use the sole Bayesian network as a source of information, DRC makes use of the fact that Bayesian networks are often learnt from a set of examples either chosen or observed. Such examples are a valuable source of information that can be used during the inference. Based on this observation, DRC uses not only the Bayesian network structure that captures the conditional independences between attributes, but also the set of examples, by estimating the probabilities directly from it. DRC is particularly adapted to problems with a dynamic probability distribution but static conditional independences. Our second approach focuses on the learning of k-LP-trees from sold items examples. We formally define the problem and introduce a score and a distance adapted to it. Our theoretical results include a learning algorithm of k-LP-trees with a convergence property, a linear LP-tree algorithm minimising the score we defined and a sample complexity result: a number of examples logarithmic in the number of attributes is enough to learn a "good" linear LP-tree. We finally present an experimental contribution that evaluates different languages whose models are learnt from a car sales history. The models learnt are used to recommend values in interactive configuration of Renault cars. The interactive configuration is a process in which the user chooses a value, one attribute at a time. The recommendation precision (the proportion of recommendations that would have been accepted by the user) and the recommendation time are measured. Besides, the parameters that influence the recommendation quality are investigated. Our results are promising: these methods, described either in the literature or in our contributions, are fast enough for an on-line use and their success rate is high, even close to the theoretical maximum

L'objet de cette thèse est d'étudier la géométrie des immeubles à angles droits. Ces espaces, définis par J. Tits sont des espaces singuliers qui peuvent être vus comme des généralisations des arbres en dimension supérieure. La thèse est divisée en deux parties. Dans la première partie, nous décrivons comment la notion de résidus parallèles permet de comprendre l'action d'un groupe sur un immeuble. En corollaire nous retrouvons que dans un groupe de Coxeter et dans un produit graphé les intersections de sous-groupes paraboliques sont paraboliques. Dans la seconde partie, nous abordons la structure quasi-conforme du bord des immeubles hyperboliques à angles droits. En particulier, nous trouvons des exemples d'immeubles de dimension 3 et 4 dont le bord vérifie la propriété combinatoire de Loewner. Cette propriété est une version faible de la propriété de Loewner. Cette partie est motivée par le fait que, depuis G.D. Mostow, la structure quasi-conforme au bord a mené à plusieurs résultats de rigidités dans les espaces hyperboliques. Dans le cas des immeubles de dimension 2, M. Bourdon et H. Pajot ont prouvé la rigidité des quasi-isométries en utilisant la propriété de Loewner au bord
The object of this thesis is to study the geometry of right-angled buildings. These spaces, defined by J. Tits, are singular spaces that can be seen as trees of higher dimension. The thesis is divided in two parts. In the first part, we describe how the notion of parallel residues allows to understand the action of a group on the building. As a corollary we recover that in Coxeter groups and in graph products intersections of parabolic subgroups are parabolic. In the second part, we discuss the quasiconformal structure of boundaries of right-angled hyperbolic buildings thanks to combinatorial tools. In particular, we exhibit some examples of buildings of dimension 3 and 4 whose boundary satisfy the combinatorial Loewner property. This property is a weak version of the Loewner property. This part is motivated by the fact that the quasiconformal structure of the boundary led to many results of rigidity in hyperbolic spaces since G.D. Mostow. In the case of buildings of dimension 2, many works have been done by M. Bourdon and H. Pajot. In particular, the Loewner property on the boundary permitted them to prove the quasi-isometry rigidity for some buildings of dimension 2

Nous etudions les espaces d'ordres abstraits. D'abord, nous faisons une etude algebrique, en definissant sur le groupe associe a ces espaces, une relation d'equivalence qui satisfait un nombre fini d'axiomes formules dans un langage de premier ordre. Nous appelons cette structure groupe special. Nous prouvons alors qu'il existe une dualite entre la categorie des espaces d'ordres abstraits et la categorie des groupes speciaux reduits (avec une definition convenable de morphismes pour ces categories). Cette dualite permet, par exemple, de caracteriser un des axiomes (le moins clair) de la definition d'espace d'ordres abstrait, d'utiliser les techniques de la theorie de modeles pour l'etude de ces espaces et, plus generalement, de donner un nouveau point de vue pour la theorie algebrique reduite des formes quadratiques. Ensuite, nous nous interessons aux aspects geometriques des espaces d'ordres abstraits (en utilisant des techniques de la theorie des matroides). En effet, nous demontrons que les espaces d'ordres abstraits sont munis d'une structure de geometrie combinatoire binaire et bipartite (les circuits sont tous de cardinalite paire). En utilisant ces resultats, nous donnons un lemme technique (lemme technique a), qui classifie certaines geometries combinatoires finies qui representent des espaces d'ordres abstraits. Ce cercle d'idees permet d'obtenir des nouveaux resultats, ainsi que d'ameliorer, preciser et eclaircir le corpus deja connu de la theorie des espaces d'ordres abstraits

Le dual topologique de l'espace des séries en un nombre quelconque, éventuellement infini, de variables non commutatives avec un corps topologique séparé de coefficients, pour la topologie produit, n'est autre que l'espace des polynômes. Il en résulte de façon immédiate que les endomorphismes continus sur les séries sont exactement les matrices infinies mais finies en ligne. Les matrices triangulaires infinies, puisque formant une algèbre de Fréchet, disposent quant à elles d'un calcul intégral et différentiel, que nous développons dans un cadre assez général, et qui permet d'établir une correspondance exponentielle-logarithme de type Lie. Nous déployons ces outils sur l'algèbre de Weyl (à deux générateurs) réalisée fidèlement comme une algèbre d'opérateurs agissant continûment sur l'espace des séries formelles (en une variable). Puis nous démontrons que chaque endomorphisme d'un espace vectoriel de dimension infinie dénombrable peut s'obtenir explicitement sous la forme de la somme d'une famille sommable en des opérateurs plus élémentaires, les opérateurs d'échelle (généralisation de l'algèbre de Weyl), précisant de la sorte le théorème de densité de Jacobson. Par dualité (topologique) un résultat similaire concernant les opérateurs continus sur un espace de combinaisons linéaires infinies tombent presque gratuitement. Par ailleurs nous développons la notion d'algèbre (contractée) large d'un monoïde à zéro (obtenue par complétion de l'algèbre contractée) qui nous permet de calculer de nouvelles formules d'inversion de Möbius ainsi que des séries de Hilbert.

Garantir la fiabilité des systèmes informatiques exige des moyens de vérification rigoureux. Le model checking est une technique de vérification dont l’intérêt majeur est l’automatisation, et donc la facilité d’utilisation pour les ingénieurs. La récente attribution du prix Turing aux créateurs de cette technique atteste de sa viabilité. Le model checking explore exhaustivement les modèles analysés. Cela amène un problème majeur : l’explosion combinatoire liée aux espaces d'états des grands systèmes. Depuis plus de vingt ans, de nombreuses solutions ont été proposées pour repousser cette limite de taille afin d’être capable de traiter des espace d’états toujours plus grands dont les tailles peuvent atteindre très rapidement les 10^400 éléments. Les travaux présentés ici proposent deux types de solutions pour traiter plus efficacement de plus grands espaces d’états. La première s'appuie sur les ressources de calcul parallèle des machines multi-processeurs,omniprésentes aujourd’hui, et des grappes de calcul. La deuxième propose de traiter plus efficacement les diagrammes de décision en automatisant la technique dite de saturation, dont l’efficacité empiriquement montrée est très difficile à atteindre manuellement.

L'objectif de notre travail est de déterminer des algorithmes qui facilitent la résolution de jeux combinatoires par des calculs informatiques. En premier lieu, nous expliquons comment l'implémentation du nimber permet d'accélérer le calcul de jeux impartiaux en version normale. Puis, nous proposons des raffinements ou des généralisations d'algorithmes de parcours des arbres de jeu, en particulier le PN-search, tout en discutant de l'intérêt de l'intervention humaine lors de l'exécution de ces algorithmes. Enfin, nous présentons des algorithmes de vérification, dont le but initial était de s'assurer de la validité de nos calculs, mais qui permettent également d'obtenir des arbres solutions de taille réduite. Ces techniques sont appliquées à l'étude de deux jeux : le Sprouts, où les joueurs relient des points par des lignes, et le Dots-and-boxes, dont le but est de compléter le maximum de boîtes en plaçant des arêtes. Le Sprouts est un jeu combinatoire impartial, dont la nature topologique rend difficile la représentation informatique. Nous explicitons une telle représentation, avant d'étudier une généralisation où le jeu se déroule sur des surfaces compactes. Le Dots-and-boxes est un jeu partisan, et nous détaillons diverses simplifications théoriques qui nous ont permis d'obtenir informatiquement des résultats nouveaux sur ce jeu.

Cette thèse est consacrée à l’étude combinatoire, algébrique et homologique des hyperarbres et des partitions semi-pointées. Nous étudions plus précisément des structures algébriques et homologiques construites à partir des hyperarbres, puis des partitions semi-pointées.Après un bref rappel des notions utilisées, nous utilisons la théorie des espèces de structure afin de déterminer l’action du groupe symétrique sur l’homologie du poset des hyperarbres. Cette action s’identifie à l’action du groupe symétrique liée à la structure anti-cyclique de l’opérade PreLie. Nous raffinons ensuite nos calculs sur une graduation de l’homologie, appelée homologie de Whitney. Cette étude motive l'introduction de la notion d’hyperarbre aux arêtes décorées par une espèce. Une bijection des hyperarbres décorés avec des arbres en boîtes et des partitions décorées permet d’obtenir une formule close pour leur cardinal, à l’aide d’un codage de Prüfer. Nous adaptons ensuite les méthodes de calcul de caractères sur les algèbres de Hopf d’incidence, introduites par W. Schmitt dans le cas de familles de posets bornés, à des familles de posets non bornés vérifiant certaines propriétés. Nous appliquons ensuite cette adaptation aux posets des hyperarbres. Enfin, au cours de notre étude une généralisation des posets des partitions et des posets des partitions pointées apparaît : les poset des partitions semi-pointées. Nous montrons que ces posets sont aussi Cohen-Macaulay, avant de déterminer à l’aide de la théorie des espèces une formule close pour la dimension de l’unique groupe d’homologie non trivial de ces posets
This thesis is dedicated to the combinatorial, algebraic and homological study of hypertrees and semi-pointed partitions. More precisely, we study algebraic and homological structures built from hypertrees and semi-pointed partitions. After recalling briefly the notions needed, we use the theory of species of structures to compute the action of the symmetric group on the homology of the hypertree posets. This action is the same as the action of the symmetric group linked with the anticyclic structure of the PreLie operad. We refine our computations on a grading of the homology : Whitney homology. This study is a motivation for the introduction of the notion of edge-decorated hypertrees. A one-to-one correspondence of decorated hypertrees with box trees and decorated partitions enables us to compute a close formula for the cardinality of decorated hypertrees, thanks to a Prüfer code. Moreover, we adapt computation methods of characters on incidence Hopf algebras, introduced by W. Schmitt for families of bounded posets, to families of unbounded posets satisfying some additional properties, called triangle and diamond posets. We apply these results to the hypertree posets. Finally, we unveil a new family of posets : the semi-pointed partition posets, which generalize both partition posets and pointed partition posets. We show the Cohen-Macaulayness of these posets and obtain, thanks to species theory, a closed formula for the dimension of its unique homology group, which extend the ones established for partition posets and pointed partition posets

Ce travail de thèse porte sur la dynamique du flot linéaire des surfaces de translation et de sa renormalisation par le flot de Teichmüller introduite par H. Masur et W. Veech en 1982. Une version combinatoire de cette renormalisation, l'induction de Rauzy sur les échanges d'intervalles, fût introduite auparavant par G. Rauzy en 1979. D'une part, nous faisons une étude combinatoire des classes de Rauzy qui forment une partition de l'ensemble des permutations irréductibles et interviennent dans l'algorithme d'induction de Rauzy. Nous donnons une formule pour la cardinalité de chaque classe. D'autre part, nous étudions un modèle de billard infini $\ZZ^2$-périodique dans le plan appelé le \og vent dans les arbres \fg introduit dans une version stochastique par P.~et T. Ehrenfest en 1912 et par J. Hardy et J. Weber en 1980 dans la version périodique. Nous construisons une famille de directions pour lesquelles le flot du billard est divergent donnant ainsi des exemples de $\ZZ^2$-cocycles divergents au-dessus d'échanges d'intervalles. De plus, nous démontrons que le taux polynomial de diffusion générique est $2/3$ autrement dit que la distance maximale atteinte par une particule au temps $t$ est de l'ordre de $t^{2/3}$.

L'objet de cette thèse est l'étude des liens existant entre la combinatoire de l'écriture d'un nombre réel en base entière ou sous la forme d'une fraction continue et le caractère algébrique ou transcendant de ce nombre réel (une conjecture de Borel prévoit que tout irrationnel algébrique est un nombre absolument normal: ses écritures en bases entières ont la même propriété que celle d'une suite aléatoire de chiffres).

Nous avons exploré plusieurs aspects théoriques et expérimentaux de l'optimisation combinatoire. Premièrement, nous avons défini une notion de structure permettant de s'échapper du résultat du théorème du No Free Lunch. Deuxièmement nous avons formalisé la symétrie de l'espace de recherche des problèmes de partitionnements. A l'aide de cette formalisation, nous pûmes concevoir des outils travaillant efficacement sur cette espace. Plus précisément nous avons développé un test d'égalité, une mesure de distance et un nouvel opérateur de Cross over. Nous avons utilisé ces résultats pour classifier les benchmarks classique de la coloration de graphe. Pour finir, nous avons développe pour ce problème une métaheuristique parallèle qui équilibre l'intensification et la diversification pendant la recherche.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004.
N° d'ordre (Lille 1) : 3467. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. 9 p.

La production d’Etienne-Martin souffre toujours d’une méconnaissance certaine. Les nombreux ouvrages et études qui lui ont été consacrés n’ont pas suffi à ce que le sculpteur obtienne la juste place qui lui revient dans l’Histoire de l’Art, et l’œuvre se dérobe encore à la compréhension. Trois facteurs principaux sont en cause : la difficulté à comprendre la nature et la fonction de la forme biographique dans son travail sculptural, graphique et manuscrit ; à appréhender l’Abécédaire, système conceptuel qu’il a créé au début des années 1960 ; à déterminer le rôle de l’ésotérisme et de la spiritualité dans sa production. Afin d’éclairer ces problématiques, nous nous fonderons sur l’étude conjointe de ses œuvres, de sa bibliothèque, et des milliers de feuillets manuscrits inédits qu’il a consacrés au récit de son enfance, à ses créations et surtout à l’Abécédaire. Ce travail sera mis en perspective avec des sources secondaires dans une orientation transversale et pluridisciplinaire. Il met en évidence le langage profondément synthétique de l’artiste qui est parvenu, au travers de l’expression de sa mythologie individuelle, à créer un œuvre dans laquelle chaque sculpture n’est pas une entité isolée, mais, au contraire, trouve sa place au sein d’une structure dotée d’un principe combinatoire à même d’engendrer de nouvelles créations. De par ses caractéristiques conceptuelles et formelles, ainsi que par les questions qu’il soulève, cet œuvre mémoriel fait pleinement écho aux recherches menées par ses contemporains
Etienne-Martin's production remains relatively unknown to this day. The several studies and publications dedicated to it have not been sufficient for the sculptor to be given the place he deserves in Art History, and the understanding of his work still is evasive. This can be explained by three main causes: the nature and the function of the artist’s biography in relation to his sculptural, graphical and written work is hard to grasp; the Abécédaire, Etienne-Martin’s own conceptual system built in the 60s is still puzzling; and the roles of esoterism and spirituality in his work are still unclear. In an effort to address these issues, we will rely on the examination of his work, of his library as well as that of thousands of unpublished pages in which he tells the story of his childhood, of his creations and mostly of the Abécédaire. Through the use of secondary sources, this study will be put into perspective, both in a transversal and multidisciplinary way. It sheds light on the deeply synthetic language of the artist. Thanks to the expression of his own individual mythology, Etienne-Martin has succeeded in creating a work in which each sculpture is not simply a distinct entity. On the contrary, it finds its place inside a structure endowed with a combinatorial principle and able to forge new creations. Owing to its conceptual and formal characteristics, as well as to the questions it raises, this memorial work resonates deeply with the research of his contemporaries

Le modèle à deux matrices a été introduit pour étudier le modèle d'Ising sur surface aléatoire. Depuis, le lien entre les modèles de matrices et la combinatoire de surfaces discrétisées s'est beaucoup développé Cette thèse a pour propos d'approfondir ces liens et de les étendre au delà des modèles de matrices en suivant l'évolution de mes travaux de recherche. Tout d'abord, je m'attache à définir rigoureusement le modèle à deux matrices hermitiennes formel donnant accès aux fonctions génératrices de surfaces discrétisées portant une structure de spin. Je montre alors comment calculer, par des méthodes de g'eométrie algébrique, tous les termes du développement topologique des observables comme formes différentielles définies sur une courbe algébrique associée au modèle: la courbe spectrale. Dans un second temps, je montre comment, imitant la construction du modèle à deux matrices, on peut définir de telles formes différentielles sur n'importe quelle courbe algébrique possédant de nombreuses propriétés d'invariance sous les déformations de la courbe algébrique considérée. En particulier, on peut montrer que si cette courbe est la courbe spectrale d'un modèle de matrices, ces invariants reconstituent les termes des développements topologiques des observables du modèle. Finalement,

je montre que pour un choix particulier des paramètres, ces objets peuvent être rendus invariants modulaires et sont solutions des équations d'anomalie holomorphe de la théorie de Kodaira-Spencer donnant un nouvel élément vers la preuve de la conjecture de Dijkgraaf-Vafa.

Ce mémoire est consacré à mes travaux sur la dynamique conforme dans les espaces métriques. Il est constitué de deux parties, la première concernant les groupes hyperboliques, et la seconde l'itération de revêtements ramifiés dans des espaces topologiques. Ces deux parties sont reliées par le dictionnaire de D. Sullivan. On a choisi d'orienter l'exposition en prenant la conjecture de J.W. Cannon comme fil d'Ariane.

Nous cherchons dans cette thèse à calculer les stratégies gagnantes de jeux combinatoires avec un programme informatique. Nous montrons comment les découpages qui apparaissent au sein de certains jeux impartiaux peuvent être utilisés pour accélérer les calculs. Nous détaillons en particulier l'utilisation du concept d'arbre canonique réduit dans les calculs en version misère. Ces méthodes ont été appliquées avec succès au calcul de deux jeux impartiaux en apparence très différents : le Sprouts, où les joueurs relient des points par des lignes, et le Cram, qui consiste à remplir un plateau avec des dominos. Nous exposons ensuite une méthode originale de suivi des calculs de jeux, avec des interactions en temps réel par l'opérateur humain. Enfin, nous décrivons l'architecture du programme modulaire qui nous a permis de réaliser de nombreux calculs différents au sein d'un cadre commun, et qui pourrait être étendu à l'avenir à d'autres jeux ou algorithmes.

Daniel Kan associe a tout ensemble simplicial réduit x un fibre principal contractile de base x et de fibre un groupe simplicial libre, note gx. Un concept généralisé de prisme nous permet de considérer ce groupe comme sous-quotient canonique d'un modèle simplicial de l'espace de lacets de x, et de munir l'espace total du fibre d'une contraction combinatoire évoquant l'idée topologique de contraction des chemins. Est ainsi établie une correspondance biunivoque explicite entre les représentants algébriques des classes d'homotopie de Gx et certains représentants géométriques des classes d'homotopie de x. En utilisant les propriétés homotopiques du commutant de Gx nous obtenons enfin une version effective du théorème de Hurewicz comportant entre autres la construction algorithmique de sphères combinatoires a partir de certains cycles homologique

Dans cette thèse on étudie les liens entre les récurrences topologique et géométrique et les volumes de Masur-Veech des espaces des modules des différentielles quadratiques et Abéliennes. On a choisi de s'intéresser aux graphes en rubans car ils peuvent être utilisé pour calculer les volumes de Masur-Veech. Dans le cas des graphes trivalents on propose une formule de récurrence géométrique, qui a été donnée indépendamment dans "On the Kontsevich geometry of the combinatorial Teichmüller space". On étudie ensuite les graphes en rubans orientés, dans ce cas on propose une décomposition des graphes que l'on a choisi d'appeler "La décomposition acyclique''. Cette décomposition permet de décomposer un graphe en ruban général en une famille de graphes à un sommet. En utilisant ce théorème on peut maintenant calculer les volumes des espaces des modules. On relie ensuite la décomposition acyclique aux opérateurs de "cut and join''. A la fin du mémoire on étudie les dégénérescences de graphes en rubans et on montre que les volumes des espaces des modules admettent un prolongement par continuité
In this thesis we study the relations between topological and geometric recursions and Masur Veech volumes of moduli spaces of quadratic and Abelian differentials. We chose to study ribbon graphs because they can be used to compute these volumes. In the case of trivalent ribbon graphs we give a geometric recursion formula that was also independently found in "On the Kontsevich geometry of the combinatorial Teichmüller space". We also study oriented ribbon graphs, in this case we found decomposition of graphs that we call "The acyclic decomposition''. This decomposition allow to decompose general oriented ribbon graphs into graphs with only one vertex. Using this we are able to compute volumes of their moduli spaces. We relate the acyclic decomposition to cut and joins operators. At the end of the memoir we study degenerations of ribbon graphs and show that volumes of moduli spaces of oriented ribbon graphs admit continuous extensions

Nous nous intéressons dans cette thèse aux modèles de représentation de maillages multirésolution. Un tel maillage décrit la décomposition cellulaire d'un objet à des niveau de résolution ou de détail différents. De nombreuses applications en modélisation ou traitement de la géométrie prennent appui sur ce type de représentation. Les modèles existants sont le plus souvent conçus en visant une application particulière et sont donc généralement limités à un contexte particulier (quadtrees de triangles ou de quadrangles, maillages progressifs, arbres binaires de sommets). Nous proposons dans cette thèse une extension multirésolution des cartes combinatoires. La généricité du modèle des cartes multirésolution permet son utilisation aussi bien dans le cadre d'une construction des maillages multirésolution par raffinement d'un maillage initial grossier ou par simplification d'un maillage initial fin. Nous illustrons cette flexibilité au sein d'outils de manipulation de surfaces de subdivision multirésolution utilisant des algorithmes de raffinement variés ainsi que de maillages progressifs. Nous démontrons que dans les deux cas notre modèle apporte également des gains en efficacité concernant le parcours des maillages intermédiaires et les requêtes de voisinage au sein de ces maillages. De plus, ces gains en souplesse et en efficacité sont obtenus en maintenant des besoins en mémoire comparables à ceux des structures existantes.

Cette th{è}se traite des propri{é}t{é}s des syst{è}mes dynamiques associ{é}s aux pavages du plan
euclidien $\R^2$ et du demi-plan hyperbolique \H. Un pavage de $\R^2$ ou de \H, code une action
d'un groupe d'isom{é}tries (soit le groupe des translations du plan, soit le groupe des
transformations affines) sur un espace m{é}trique compact $\Omega$ de sorte que les propri{é}t{é}s de
cette action sont reli{é}es avec les propri{é}t{é}s combinatoires du pavage. Les actions obtenues par
cette mani{è}re ont des comportements tr{è}s vari{é}s. Pour certains cas, comme par exemple pour le
pavage de Penrose, cette action est libre et minimale. Ceci donne {à} l'espace $\Omega$ une structure
de lamination particuli{è}re appell{é}e {\it sol{é}no{\"\i}de}. Localement, cet espace est le produit d'un
ensemble de Cantor par un ouvert du plan euclidien (resp. hyperbolique). Dans cette th{è}se, nous
{é}tudions principalement le comportement statistique des orbites de telles actions. Pour cela nous
caract{é}risons les mesures finies invariantes pour ces actions ainsi que les mesures harmoniques des
sol{é}no{\"\i}des associ{é}s. Il apparait des diff{é}rences fondamentales dans les techniques utilis{é}es entre
le cas euclidien et le cas hyperbolique. Nous donnons de plus, pour tout entier $r\geq 1$ des
exemples explicites de pavages du demi-plan hyperbolique dont le syst{è}me dynamique associ{é} est une
action libre et minimale poss{é}dant $r$ mesures finies invariantes et ergodiques.

Non communiqué
Rauzy-type dynamics are group (or monoid) actions on a collection of combinatorial objects. The first and best known example concerns an action on permutations, associated to interval exchange transformations (IET) for the Poincaré map on compact orientable translation surfaces. The equivalence classes on the objects inducedby the group action are related to components of the moduli spaces of Abelian differentials with prescribed singularities, and, in two variants of the problem, have been classified by Kontsevich and Zorich, and by Boissy, through methods involving both combinatorics, algebraic geometry, topology and dynamical systems. In the first half of this thesis, we provide a purely combinatorial proof of both classification theorems. Our proof can be interpreted geometrically and the over archingidea is close to that of Kontsevich and Zorich, although the techniques arerather different. Not all Rauzy-type dynamics have a geometrical correspondence however, and some parts of this first proof do not seem to generalize well.In the second half of the thesis we develop a new method, that we call the labelling method. This second method is not completely disjoint from the first one, but it the new crucial ingredient of considering a sort of ‘monodromy’ for the dynamics, in away that we now sketch. Many statements in this thesis are proven by induction. It is conceivable to prove, by induction, a classification theorem for unlabelled objects. However, as the labelling method will show, it is easier to prove two statements in parallel within the same induction, the one on the unlabelled objects, and an apparently much harder one, on the monodromy of the labelled objects. Although the final result is stronger than the initial aim, by virtue of the stronger inductive hypothesis, the method may work more easily.This second approach extends to several other Rauzy-type dynamics. Our firststep is to apply the labelling method to derive a second proof of the classificationtheorem for the Rauzy dynamics. Then we apply it to the study of two other Rauzy-type dynamics (one of which is strictly related to the Rauzy dynamics on non-orientable surfaces), and finally we inventory a surprisingly high number of Rauzy-type dynamics for which the labelling

Cette thèse se situe dans les domaines de la combinatoire, de la théorie des ordres et de la théorie descriptive. La première contribution concerne la théorie des bons quasi-ordres (wqo) et des meilleurs quasi-ordres (bqo). Le résultat principal est la preuve d'une conjecture, énoncée par Pouzet en 1978 dans sa thèse d'état, qui établit que tout wqo dont l'ensemble des idéaux non principaux ordonnés par inclusion forme un bqo est alors lui-même un bqo. La preuve repose sur de nouveaux résultats, qui allient la combinatoire et la topologie, au sujet des fonctions d'un front vers un espace métrique compact. La seconde contribution de cette thèse traite de la complexité topologique dans le cadre des espaces To à base dénombrable. Dans le cas de l'espace de Baire, le quasi-ordre de Wadge est un wqo sur les sous-ensembles Boréliens qui a suscité énormément d'intérêt. Cependant cette relation de réduction par fonctions continues s'avère bien moins satisfaisante pour d'autres espaces d'importance tels que la droite réelle, comme l'ont fait notamment remarquer Hertling, Schlicht et Ikegami. Nous proposons de conserver la continuité et d'affaiblir la notion de fonction pour celle de relation. Pour ce faire, nous utilisons la notion de représentation admissible étudiée en « Type-2 theory of effectivity » initiée par Weihrauch. Nous introduisons alors le quasi-ordre de réduction par relations relativement continues et montrons que celui-ci à la fois raffine les hiérarchies classiques de complexité topologique et forme un wqo sur les sous-ensembles Boréliens de chaque espace quasi-Polonais
This thesis deals with combinatorics, order theory and descriptive set theory. The first contribution is to the theory of well-quasi-orders (wqo) and better-quasi-orders (bqo). The main result is the proof of a conjecture made by Maurice Pouzet in 1978 his thèse d'état which states that any wqo whose ideal completion remainder is bqo is actually bqo. Our proof relies on new results with both a combinatorial and a topological flavour concerning maps from a front into a compact metric space. The second contribution is of a more applied nature and deals with topological spaces. We define a quasi-order on the subsets of every second countable To topological space in a way that generalises the Wadge quasi-order on the Baire space, while extending its nice properties to virtually all these topological spaces. The Wadge quasi-order of reducibility by continuous functions is wqo on Borel subsets of the Baire space, this quasi-order is however far less satisfactory for other important topological spaces such as the real line, as Hertling, Ikegami and Schlicht notably observed. Some authors have therefore studied reducibility with respect to some classes of discontinuous functions to remedy this situation. We propose instead to keep continuity but to weaken the notion of function to that of relation. Using the notion of admissible representation studied in Type-2 theory of effectivity, we define the quasi-order of reducibility by relatively continuous relations. We show that this quasi-order both refines the classical hierarchies of complexity and is wqo on the Borel subsets of virtually every second countable To space - including every (quasi-)Polish space

Dans ce document, nous nous intéressons à la modélisation de l'image par le biais de la théorie des hypergraphes. Notre contribution est essentiellement axée sur la détermination des propriétés issues de
cette théorie et sur l'analyse de leur adéquation avec des problématiques de l'image et particulièrement la détection de contours et la suppression de bruit.

Dans un premier temps, nous étudions la représentation par hypergraphes de voisinage spatiocolorimétrique de l'image. Trois représentations sont présentées incorporant des propriétés globales, locales, des mesures de similarité et des mesures de dissimilarité.

Ensuite, on utilise les propriétés des hypergraphes engendrées par la représentation afin de définir des modèles structurels de bruit et de contour. Ceci nous permet ainsi de déduire des algorithmes de suppression de bruit et d'extraction de contours sur des images
à niveaux de gris et couleur. Les performances des approches proposées sont comparées aux solutions classiquement utilisées.
Enfin, la représentation par hypergraphe de voisinage
spatiocolorimétrique s'est avérée efficace pour
le traitement des images bas niveaux.

Le but de cette thèse est l'étude de la fibre de Milnor associée à un complémentaire d'arrangement d'hyperplans. Il est montré par un exemple que cette variété n'est pas toujours formelle, ou même 1-formelle. La formalité est une propriété introduite dans les années 1970 dans le cadre de la théorie de l'homotopie rationnelle. Des avancées récentes ont identifié cette propriété comme critère particulièrement fin pour établir un lien entre variétés caractéristiques et variétés de résonance, associées à l'espace étudié. Ces deux types de variétés sont des invariants dont les définitions présentent beaucoup de points communs, mais dans des espaces différents. Un lien très fort - la variété de résonance est le cône tangent à l'origine de la variété caractéristique correspondante - avait été établi sous diverses hypothèses, que l'introduction de la 1-formalité permet d'élargir. C'est en montrant que pour l'exemple décrit dans cette thèse, ce lien n'existe pas, que l'on prouve que la variété considérée n'est pas formelle.

Cette étude vise à unifier dans une même approche les descriptions données par une sémantique cognitive et les représentations associées, et étudiées par une sémantique formelle. La sémantique cognitive a pour but d’associer des schèmes aux significations des unités analysées. La sémantique formelle consiste à étudier les modes de représentation de ces schèmes et les relations avec les observables. Notre étude s’appuie et s’insère dans le modèle général développé à l’université Paris-Sorbonne dans le groupe LaLIC (Langages, Logiques, Informatique et Cognition), il s’agit d’utiliser le modèle de la GAC (Grammaire Applicative et Cognitive) et de la GRACE (GRammaire Applicative Cognitive et Enonciative) ; ces deux modèles font appel d’une part à la topologie et d’autre part à la logique combinatoire en vue d’un traitement automatique de la signification. Nous avons choisi d’étudier le problème des prépositions et plus spécialement des trois prépositions : dans, sous et à du français et de leur équivalents en arabe ; cela nous à conduit à rechercher des invariants associés à ces trois prépositions ou relateurs, la préposition dans renvoie à l’intériorité d’un lieu, qu’il soit spatial, temporel, spatio-temporel, notionnel ou d’activité ; la préposition sous renvoie à un lieu déterminé ou engendré par un autre lieu dont on prend la fermeture ; quand à la préposition à renvoie à la fermeture d’un lieu. Le lieu est un lieu cognitif abstrait, suffisamment général qui, selon le contexte peut prendre des valeurs plus particulières
This study aims to unify in a single approach the descriptions given by cognitive semantics and associated representations, studied by formal semantics. Cognitive semantics consists to associate the meanings of the analyzed with schemes. Formal semantics consists in studying the modes of representation of these schemes and the relations to the observables. Our study is based on the general model developed at the Paris-Sorbonne University in the LaLIC group, using the GAC model (Applicative and Cognitive Grammar) and GRACE (GRammar Applicative Cognitive and Enunciative), these two models use the one hand to the topology and on the other hand to the combinatory logic in order to an automatic processing of meanings. We have chosen to study the problem of the three prepositions: dans, sous and à of French and their equivalences in Arabic, this leads us to search for invariants associated with these three prepositions or relators, the preposition dans refers to the interiority of a place, be it spatial, temporal, spatial-temporal, notional or activity and the preposition sous refers to a specific place or generated by another place whose closing is taken. The preposition à refers to the closing of a place, here the place is cognitive or abstract place, sufficiently general that according to the context can take more particular values

Cette thèse s'inscrit dans le cadre de l'optimisation d'agencement, une étape importante dans la conception de systèmes multidisciplinaires complexes tels que les véhicules aérospatiaux. Les problèmes d'agencement optimal (OLP) consistent à trouver la meilleure disposition d'un ensemble de composants dans un système ou un espace, afin d'atteindre certains objectifs (réduction des coûts, amélioration des performances, etc.) tout en satisfaisant diverses contraintes (géométriques, fonctionnelles, etc.). Le traitement des OLP est encore un défi aujourd'hui, tant en termes de formulation que de résolution. En effet, les OLP sont souvent très contraints et impliquent de nombreuses variables de décision (continues, discrètes, catégorielles), qui peuvent être fixes ou conditionnelles. Les variables conditionnelles sont utiles pour définir différents choix de conception qui doivent être faits en même temps que l'optimisation de l'agencement des composants. Ainsi, la résolution des OLP nécessite l'utilisation d'algorithmes d'optimisation avancés combinant différentes catégories de méthodes, comme par exemple les métaheuristiques et l'optimisation bayésienne.L'objectif global de la thèse est d'étudier les OLP, leur formulation dans différents contextes, leur résolution à l'aide de diverses méthodes d'optimisation et hybridations, ainsi que la validation de ces méthodes dans le cadre de la conception de véhicules aérospatiaux. Les contributions de la thèse sont organisées en deux parties correspondant à deux types d'OLP. Dans la première (respectivement deuxième) partie, la liste de composants à agencer est fixe (resp. variable), impliquant des OLP à espace de recherche fixe ou FSS-OLP, (resp. des OLP à espace de recherche conditionnel ou CSS-OLP). Dans les deux cas, le système/l'espace dans lequel les composants sont agencés est considéré comme mono ou multi-contenant.Dans la première partie, une étude des FSS-OLP est proposée, incluant leurs formulations génériques, leurs applications et méthodes de résolution, avec un focus particulier sur les méthodes quasi-physiques et les métaheuristiques. Basés sur un système de force virtuelle (VF), les algorithmes quasi-physiques simulent les lois de la dynamique et traitent efficacement les problèmes fortement contraints. Une variante (nommée CSO-VF) de de ces algorithmes est développée afin de résoudre les FSS-OLP à un seul contenant. Dans CSO-VF, la position et l'orientation des composants évoluent grâce au VF. Pour traiter les systèmes multi-contenants, CSO-VF est hybridé à un algorithme génétique (GA) dans un algorithme à deux étages qui affecte les composants aux contenants puis optimise leur disposition dans chacun des contenants. Ces deux algorithmes sont évalués grâce à des problèmes d'agencement de satellites.Dans la deuxième partie, une étude des CSS-OLP est proposée avec la même approche que dans la première partie. Les variables conditionnelles engendrent des OLP plus complexes. Par exemple, dans le contexte de la conception aérospatiale, une quantité donnée de carburant peut être incluse dans le système, soit dans un grand réservoir, soit dans deux plus petits. Par conséquent, le nombre de composants à positionner n'est pas le même dans les deux cas et le nombre de variables de conception et de contraintes varie donc au cours du processus d'optimisation. Deux approches ont été développées pour traiter les CSS-OLP à un seul contenant : la première est un GA modifié pour introduire des variables cachées dans les chromosomes. La seconde est une approche bi-niveaux combinant optimisation bayésienne et l'algorithme CSO-VF. L'optimisation bayésienne sélectionne les composants et CSO-VF optimise leur agencement. Cette dernière approche a été hybridée avec un GA dans un algorithme tri-niveaux afin de traiter les CSS-OLP multi-contenants. Enfin, tous les algorithmes sont évalués et comparés grâce à des problèmes d'agencement de satellites
This thesis falls within the scope of layout optimization, which is an important stage in the design of complex multidisciplinary engineering systems such as aerospace vehicles. Optimal layout problems (OLPs) involve finding the best arrangement of a set of components within a single- or multi-container system or space to meet specific objectives (cost reduction, performance enhancement, etc.) while satisfying various constraints (geometrical, functional, etc.). Dealing with OLPs is challenging both in terms of their formulation and their efficient and effective resolution. Actually, OLPs are often highly constrained and involve many mixed decision variables (continuous, discrete/categorial) which may be fixed or conditional. Conditional variables are highly useful to define different design choices when the set of components to be arranged is variable and dynamic. Consequently, their resolution requires the use of advanced optimization algorithms combining different classes of (mixed-variable) methods including metaheuristics and Bayesian optimization.The overall objective of the thesis is to investigate OLPs, their formulation in different contexts, their resolution using various optimization methods and their hybridization, and their validation within the framework of aerospace vehicle design. The contributions of the thesis are organized in two parts corresponding to two types of OLPs. In the first (resp. second) part, the set of components to be arranged is fixed (variable or conditional) involving fixed search space OLPs or FSS-OLPs (resp. conditional search space OLPs or CSS-OLPs). In both cases, the system/space in which the components are arranged is considered single- or multi-container.In the first part, a survey of constrained mixed-variable FSS-OLPs is proposed including their generic formulations, applications and resolution methods with a particular focus on quasi-physical methods and population-based metaheuristics. Based on a virtual force system (VF) quasi-physical algorithms emulate the principle of physical laws in system dynamics and deal efficiently with highly constrained problems. A variant (namely CSO-VF) of these algorithms is devised for solving single-container FSS-OLPs. In CSO-VF, the positions and orientations of the components are evolved using VF. To deal with multi-container systems, CSO-VF is combined with a Genetic Algorithm (GA) in a two-stage algorithm that assigns the components to the containers and optimizes their layout. These single- and multi-container algorithms are assessed considering satellite module FSS-OLPs that are representative benchmarks.In the second part, a survey of constrained mixed-variable CSS-OLPs is proposed in the same way than in the first part. Conditional variables involve more complex OLPs. Actually, for instance, in the context of aerospace concept design, a given amount of fuel could be included in a container in either one large tank or two smaller ones. Therefore, as the number of components to position is not the same in both cases the number of design variables as well as constraint functions vary during the optimization process. To deal with single-container CSS-OLPs, two approaches have been investigated: the first one is a GA revisited considering hidden variables, leading to variable-geometry OLPs (in objective and constraint functions). The second approach is a two-stage surrogate guided-CSO-VF algorithm combining Bayesian Optimization with CSO-VF. Bayesian Optimization selects the components with are considered by CSO-VF for layout optimization. This latter approach has been extended with a GA in a three-stage algorithm to tackle multi-container CSS-OLPs. Finally, all the algorithms are evaluated and compared based on their application to CSS variants of satellite module OLPs

In this thesis we deal with combinatorial and geometric properties of arc complexes and triangulation graphs, and we will provide some applications to the study of the mapping class group and to the Teichmüller theory of a bordered surface. The thesis is divided into two parts. In the former we deal with the problem of combinatorial rigidity of arc complexes. In the latter we study some large-scale properties of the arc complex and the 1-skeleton of its dual, the so-called ideal triangulation graph.

Cette thèse est consacrée à l'étude des représentations modulaires des algèbres d'Ariki-Koike, et des liens avec la théorie des cristaux et des bases canoniques de Kashiwara via le théorème de catégorification d'Ariki. Dans un premier temps, on étudie, grâce à des outils combinatoires, les matrices de décomposition de ces algèbres en généralisant les travaux de Geck et Jacon. On classifie entièrement les cas d'existence et de non-existence d'ensembles basiques, en construisant explicitement ces ensembles lorsqu'ils existent. On explicite ensuite les isomorphismes de cristaux pour les représentations de Fock de l'algèbre affine quantique de type A affine. On construit alors un isomorphisme particulier, dit canonique, qui permet entre autres une caractérisation non-récursive de n'importe quelle composante connexe du cristal. On souligne également les liens avec la combinatoire des mots sous-jacente à la structure cristalline des espaces de Fock, en décrivant notamment un analogue de la correspondance de Robinson-Schensted-Knuth pour le type A affine.

In this thesis we deal with combinatorial and geometric properties of arc complexes and triangulation graphs, and we will provide some applications to the study of the mapping class group and to the Teichmüller theory of a bordered surface. The thesis is divided into two parts. In the former we deal with the problem of combinatorial rigidity of arc complexes. In the latter we study some large-scale properties of the arc complex and the 1-skeleton of its dual, the so-called ideal triangulation graph.

Cette thèse est composée de deux parties : l’une traite des propriétés combinatoires de mots infinis et l’autre des problèmes de colorations des graphes.La première partie du manuscrit concerne les structures régulières dans les mots apériodiques infinis, à savoir les sous-séquences arithmétiques et les premiers retours complets.Nous étudions la fonction qui donne la longueur maximale d’une sous-séquence arithmétique monochromatique (une progression arithmétique) en fonction de la différence commune d pour une famille de mots morphiques uniformes, qui inclut le mot de Thue-Morse. Nous obtenons la limite supérieure explicite du taux de croissance de la fonction et des emplacements des progressions arithmétiques de longueurs maximales et de différences d. Pour étudier des sous-séquences arithmétiques périodiques dans des mots infinis, nous définissons la notion d'indice arithmétique et obtenons des bornes supérieures et inférieures sur le taux de croissance de la fonction donnant l’indice arithmétique dans la même famille de mots.Dans la même veine, une autre question concerne l’étude de deux nouvelles fonctions de complexité de mots infinis basées sur les notions de mots ouverts et fermés. Nous dérivons des formules explicites pour les fonctions de complexité ouverte et fermée pour un mot d'Arnoux-Rauzy sur un alphabet de cardinalité finie.La seconde partie de la thèse traite des colorations parfaites (des partitions équitables) de graphes infinis de degré borné. Nous étudions les graphes de Caley de groupes additifs infinis avec un ensemble de générateurs fixé. Nous considérons le cas où l'ensemble des générateurs est composé d'entiers de l'intervalle [-n, n], et le cas où les générateurs sont des entiers impairs de [-2n-1, 2n+1], où n est un entier positif. Pour les deux familles de graphes, nous obtenons une caractérisation complète des colorations parfaites à deux couleurs
The content of the thesis is comprised of two parts: one deals with combinatorial properties of infinite words and the other with graph coloring problems.The first main part of the manuscript concerns regular structures in infinite aperiodic words, such as arithmetic subsequences and complete first returns.We study the function that outputs the maximal length of a monochromatic arithmetic subsequence (an arithmetic progression) as a function of the common difference d for a family of uniform morphic words, which includes the Thue-Morse word. We obtain the explicit upper bound on the rate of growth of the function and locations of arithmetic progressions of maximal lengths and difference d. To study periodic arithmetic subsequences in infinite words we define the notion of an arithmetic index and obtain upper and lower bounds on the rate of growth of the function of arithmetic index in the same family of words.Another topic in this direction involves the study of two new complexity functions of infinite words based on the notions of open and closed words. We derive explicit formulae for the open and closed complexity functions for an Arnoux-Rauzy word over an alphabet of finite cardinality.The second main part of the thesis deals with perfect colorings (a.k.a. equitable partitions) of infinite graphs of bounded degree. We study Caley graphs of infinite additive groups with a prescribed set of generators. We consider the case when the set of generators is composed of integers from the interval [-n,n], and the case when the generators are odd integers from [-2n-1,2n+1], where n is a positive integer. For both families of graphs, we obtain a complete characterization of perfect 2-colorings

Cette thèse est une contribution au domaine des cubulations de groupes hyperboliques au sens de Gromov. Nous nous intéressons au cas particulier des groupes fondamentaux de variétés hyperboliques réelles compactes. La philosophie inspirée dans ce domaine par les travaux de M. Sageev est que si un groupe hyperbolique possède suffisamment de sous-groupes de codimension 1 quasi-convexes, alors il agit géométriquement sur un complexe cubique CAT(0) de dimension finie. Nous démontrons un critère précis de cubulation pour les groupes fondamentaux de variétés hyperboliques compactes, à l'aide de constructions d'espaces à murs quasi-isométriques à l'espace hyperbolique réel. Nous nous restreignons par la suite au cas particulier de la dimension 3 et plus particulièrement aux 3-variétés hyperboliques compactes virtuellement fibrées sur le cercle. Nous exploitons alors une construction de surfaces immergées incompressibles dites coupées-croisées due à D. Cooper, D. Long et A. Reid dans une telle 3-variété M pour fabriquer des sous-groupes de surface de son groupe fondamental~G. En raffinant des arguments de J. Masters et en exploitant la structure de l'application de Cannon-Thurston, nous parvenons à construire des sous-groupes de surfaces quasi-convexes de G en quantité suffisante pour que leurs ensembles limites permettent de séparer toutes les paires de points distincts du bord du revêtement universel de M. En conséquence de cette construction, G agit géométriquement sur un complexe cubique CAT(0) de dimension finie. D. Wise soulève alors la question de savoir si ce groupe G peut agir géométriquement et également virtuellement co-spécialement (au sens de F. Haglund et D. Wise) sur un complexe cubique CAT(0). Une réponse positive résoudrait les conjectures selon lesquelles G est large et le premier nombre de Betti virtuel de M est infini. Nous faisons remarquer que pour obtenir une réponse positive à cette question, il suffit de trouver une surface coupée-croisée virtuellement plongée dans un revêtement fini fibré sur le cercle de M. Nous concluons en présentant des conditions algébriques, puis géométriques et cohomologiques suffisantes pour qu'une surface coupée-croisée donnée soit virtuellement plongée.

Ce mémoire porte sur la théorie des espèces introduite par André Joyal en 1981. Développée systématiquement par Bergeron, Labelle et Leroux au LaCIM, la théorie donne une élégante présentation de la théorie des séries formelles et possède des applications dans plusieurs disciplines allant de la combinatoire énumérative à la physique statistique. Une opération importante de la théorie consiste en l'opération de dérivation pour laquelle Labelle et Lamathe ont introduit en 2009 une généralisation de l'opérateur différentiel standard D en donnant une interprétation combinatoire à Ω(X,D)F(X), où Ω(X,T) et F(X) sont des espèces à deux et une sortes d'éléments respectivement. Yeh a montré que de tels opérateurs peuvent être décomposés de façon unique en sommes de produits d'opérateurs plus simples appelés opérateurs différentiels combinatoires atomiques. Dans leur article, Labelle et Lamathe ont présenté une liste des premiers opérateurs différentiels atomiques. Dans ce mémoire, nous apportons une contribution originale à la théorie des espèces. En particulier, nous explicitons plusieurs notions de cette théorie en fournissant notamment une preuve détaillée d'un théorème, dû à Labelle et Lamathe, permettant de calculer l'application d'un opérateur moléculaire sur une espèce donnée. Ensuite, nous donnons deux algorithmes permettant de déterminer si un opérateur différentiel moléculaire donné est atomique. Nous étendons ensuite la liste des opérateurs différentiels donnée dans (Labelle et Lamathe, 2009). Les résultats de ce travail furent présentés à la conférence GASCom 2012 qui eut lieu à l'université de Bordeaux du 25 au 27 juin 2012. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : opérateurs différentiels combinatoires, opérateurs moléculaires, opérateurs atomiques, espèces de structures.

Ce travail traite principalement de l'énumération d'extensions de structures combinatoires classiques appelées chemins de Dyck et fonctions de stationnement. Ces structures, très étudiées en raison de leur rôle fondamental dans de multiples contextes combinatoires, sont aussi étroitement liées à la théorie de la représentation, à la théorie des fonctions symétriques et à la géométrie algébrique, entre autres. En particulier, elles sont liées à l'étude combinatoire des espaces coinvariants diagonaux DRk,n, introduits par Garsia et Haiman, qui sont des représentations du groupe symétrique Gn sur des espaces de polynômes en k jeux de n variables. Dans le cas bivarié, il a été conjecturé que les séries de Hilbert des espaces coinvariants diagonaux « augmentés » DRm2,n et de leur sous-représentation signe DRm2,nɛ sont respectivement égales à une somme de statistiques sur les fonctions de m-stationnement et sur les chemins de m-Dyck. Il existe également une conjecture plus générale pour la série de Frobenius de ces espaces qui s'appelle la conjecture « shuffle » (Haglund et al., 2005). Dans le cas trivarié, Haiman a conjecturé en 1994 les dimensions suivantes : dim(DR3,nɛ) = 2/n(n+1) (4n+1 n-1) et dim(DR3,n) = 2n (n+1)n-2. D'autre part, en 2006, Chapoton a démontré que les intervalles dans le treillis de Tamari sont comptés par 2/n(n+1) (4n+1 n-1). Motivé par ses travaux sur le cas trivarié et par les deux conjectures précédentes, Bergeron a introduit le treillis de m-Tamari et étendu certaines questions concernant les chemins de m-Dyck et les fonctions de m-stationnement pour rendre compte du cas trivarié. Il a conjecturé que : dim(DRm3,nɛ) = m+1/n(mn+1) ((m+1)2n+m n-1), que : dim(DRm3,n) = (m+1)n(mn+1)n-2, et que ces deux cardinalités comptent respectivement les intervalles et les intervalles de stationnement du treillis de m-Tamari. Dans cette thèse, nous démontrons une généralisation commune de ces deux conjectures énumératives que nous avons énoncée avec Bergeron. Plus précisément, avec Mireille Bousquet-Mélou et Guillaume Chapuy, nous avons démontré que la série de Frobenius d'une certaine représentation combinatoire sur les intervalles de stationnement du treillis de m-Tamari est donnée par : Ʃ λ=(λ1,…,λl)˫n (mn+1)l-2 II 1≤i≤l ((m+1)λi λi) Pλ/Zλ. Cette démonstration équivaut à résoudre un nouveau type d'équations différentielles à variable catalytique. Toujours avec Bergeron, nous avons conjecturé que le produit tensoriel de cette représentation combinatoire et de la représentation signe ɛ est isomorphe à DRm3,n. Nous avons également formulé une généralisation de la conjecture « shuffle » en proposant une formule combinatoire explicite pour la série de Frobenius graduée de DRm3,n. Ceci renforce notre hypothèse que l'étude des intervalles du treillis de m-Tamari est bel et bien en lien avec l'étude des espaces DRm3,n. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : combinatoire algébrique, combinatoire énumérative, représentations du groupe symétrique, fonctions génératrices, statistiques.