Cette thèse porte sur la rapidité du temps de mélange de chaînes de Markov sur des graphes. La contribution principale concerne les graphes avec des dynamiques locales sur les arêtes, la topologie du graphe évoluant au fur et à mesure que les arêtes glissent les unes le long des autres. Nous proposons une classification des différents modèles existants de graphes dynamiques, tout en illustrant l’importance des transitions le long d’une structure mouvante pour améliorer la vitesse de convergence. Cette étude est complétée par la preuve, pour l’une de ces dynamiques, d’un temps de mélange rapide. Nous définissons notamment l’expansion partielle d’un graphe. Celle-ci permet de suivre l’avancement de la dynamique, partant d’un état de faible expansion, jusqu’à obtention d’une bonne expansion à l’équilibre. La fin de cette thèse porte sur une amélioration de l’algorithme de simulation parfaite de Propp et Wilson. Nous introduisant un oracle pour les transitions, inspiré de l’échantillonnage préférentiel, qui permet de réduire la complexité de l’algorithme. Nous fournissons une preuve de correction, ainsi qu’une étude de l’impact de cette méthode sur la vitesse d’échantillonnage d’ensembles indépendants pour certains graphes. / This thesis focuses on the rapid mixing of graph-related Markov chains. The main contribution concerns graphs with local edge dynamics, in which the topology of a graph evolves as edges slide along one another. We propose a classification of existing models of dynamic graphs, and illustrate how evolving along a changing structure improves the convergence rate. This is complemented by a proof of the rapid mixing time for one such dynamic. As part of this proof, we introduce the partial expansion of a graph. This notion allows us to track the progression of the dynamic, from a state with poor expansion to good expansion at equilibrium. The end of the thesis proposes an improvement of the Propp and Wilson perfect sampling technique. We introduce oracle sampling, a method inspired by importance sampling that reduces the overall complexity of the Propp and Wilson algorithm. We provide a proof of correctness, and study the performance of this method when sampling independent sets from certain graphs.

Dans cette thèse, nous étudions des problèmes différents de coloration maximale dans les graphes sommet-colorés. Nous nous concentrons sur la recherche des structures avec le nombre maximal possible de couleurs par des algorithmes en temps polynomial, nous donnons aussi la preuve des problèmes NP-difficiles pour des graphes spécifiques. En particulier, nous étudions d’abord le problème de l’appariement coloré maximum. Nous montrons que ce problème peut être résolu efficacement en temps polynomial. En plus, nous considérons également une version spécifique de ce problème, à savoir l’appariement tropical, qui consiste à trouver un appariement contenant toutes les couleurs du graphe original. De même, un algorithme de temps polynomial est également fourni pour le problème de l’appariement tropical avec la cardinalité minimale et le problème de l’appariement tropical maximum avec la cardinalité minimale. Ensuite, nous étudions le problème des chemins colorés maximum. Il existe deux versions pour ce problème: le problème de plus court chemin tropical, c’est-à-dire de trouver un chemin tropical avec le poids total minimum et le problème de plus longue chemin coloré, à savoir, trouver un chemin avec un nombre maximum possible de couleurs. Nous montrons que les deux versions de ce problème sont NP-difficile pour un graphe orienté acyclique, graphes de cactus et graphes d'intervalles où le problème de plus long chemin est facile. De plus, nous fournissons également un algorithme de paramètre fixe pour le premier dans les graphes généraux et plusieurs algorithmes de temps polynomiaux pour le second dans les graphes spécifiques, y compris les graphes des chaîne bipartites, graphes de seuil, arborescences, graphes des blocs et graphes d'intervalles appropriés. Ensuite, nous considérons le problème des cycles colorés maximum. Nous montrons d'abord que le problème est NP-difficile même pour des graphes simples tels que des graphes divisés, des graphes bi-connecteurs et des graphes d'intervalles. Nous fournissons ensuite des algorithmes de temps polynomial pour les classes de graphes de seuil et graphes des chaîne bipartites et graphes d'intervalles appropriés. Plus tard, nous étudions le problème des cliques colorées maximum. Nous montrons tout d’abord que le problème est NP-difficile même pour plusieurs cas où le problème de clique maximum est facile, comme des graphes complémentaires des graphes de permutation bipartite, des graphes complémentaires de graphes convexes bipartites et des graphes de disques unitaires, et aussi pour des graphes sommet-colorées appropriés. Ensuite, nous proposons un algorithme paramétré XP et des algorithmes de temps polynomial pour les classes de graphes complémentaires de graphes en chaîne bipartites, des graphes multipartites complets et des graphes complémentaires de graphes cycles. Enfin, nous nous concentrons sur le problème des stables (ensembles indépendants) colorés maximum. Nous montrons d’abord que le problème est NP-difficile même dans certains cas où le problème de stable maximum est facile, tels que les co-graphes et les graphes des P₅-gratuit. Ensuite, nous fournissons des algorithmes de temps polynomial pour les graphes de grappes, et les arbres. / In this thesis, we study different maximum colorful problems in vertex-colored graphs. We focus on finding structures with the possible maximum number of colors by efficient polynomial-time algorithms, or prove these problems as NP-hard for specific graphs. In particular, we first study the maximum colorful matching problem. We show that this problem can be efficiently solved in polynomial time. Moreover, we also consider a specific version of this problem, namely tropical matching, that is to find a matching containing all colors of the original graph, if any. Similarly, a polynomial time algorithm is also provided for the problem of tropical matching with the minimum cardinality and the problem of maximal tropical matching with the minimum cardinality. Then, we study the maximum colorful paths problem. There are two versions for this problem: the shortest tropical path problem, i.e., finding a tropical path with the minimum total weight, and the maximum colorful path problem, i.e., finding a path with the maximum number of colors possible. We show that both versions of this problem are NP-hard for directed acyclic graphs, cactus graphs and interval graphs where the longest path problem is easy. Moreover, we also provide a fixed parameter algorithm for the former in general graphs and several polynomial time algorithms for the latter in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs. Next we consider the maximum colorful cycles problem. We first show that the problem is NP-hard even for simple graphs such as split graphs, biconnected graphs, interval graphs. Then we provide polynomial-time algorithms for classes of threshold graphs and bipartite chain graphs and proper interval graphs. Later, we study the maximum colorful cliques problem. We first show that the problem is NP-hard even for several cases where the maximum clique problem is easy, such as complement graphs of bipartite permutation graphs, complement graphs of bipartite convex graphs, and unit disk graphs, and also for properly vertex-colored graphs. Next, we propose a XP parameterized algorithm and polynomial-time algorithms for classes of complement graphs of bipartite chain graphs, complete multipartite graphs and complement graphs of cycle graphs. Finally, we focus on the maximum colorful independent set problem. We first prove that the problem is NP-hard even for some cases where the maximum independent set problem is easy, such as cographs and P₅-free graphs. Next, we provide polynomial time algorithms for cluster graphs and trees.

Un des rôles des SIG 3D est d'intégrer et de mettre en cohérence des données issues de producteurs de données variés tout en respectant les choix faits en fonction des besoins des utilisateurs, en termes de géométrie et de topologie. Les SIG 3D actuels utilisent généralement une modélisation géométrique et topologique unique qui facilite, entre autres, les requêtes comme celles calculées à partir des modéles topologiques tels que le parcours de proche en proche des primitives géométriques d'un objet ou de ses voisins. En contrepartie, cette homogénéisation entraîne une perte des spécificités des modèles, de lourds calculs de conversion et ne corrige pas, sans une aide extérieure, les problèmes inhérents à l'acquisition et à la modélisation. Cette thèse propose un modèle d'analyse pour les SIG 3D permettant d'opérer des requêtes sur un objet (analyse intra-objet), quel que soit le choix technique de l'utilisateur, ou sur un ensemble d'objets (analyse inter-objets), même s'ils ne sont pas parfaitement cohérents. A partir de principes issus de la cristallographie, ce modèle, nommé Cristage, analyse les symétries de chaque objet pour décrire sa structure, c'est-à-dire la manière dont les primitives sont agencées entre elles. Complémentaire des modèles topologiques, cette première abstraction donne une vision globale de l'objet, ce qui facilite certaines requêtes comme l'extraction du toit d'une cavité ou la simplification géométrique d'un bâtiment 3D. L'analyse des différents éléments de symétrie (plans, axes et centre) offre une seconde abstraction : la maille. Considérée en cristallographie comme l'enveloppe du plus petit parallélépipède conservant les propriétés géométriques, elle est utilisée comme une boîte englobante adaptée à la forme de l'objet. Elle permet, en particulier, la mise en relation logique des objets géographiques, quelle que soit leur dimension. A l'aide des mailles, deux graphes sont calculés. Le premier, qualifié de graphe d'incidence, décrit les relations entre objets et facilite le parcours entre eux. Le second, appelé graphe temporel, dessine, pour un objet, l'évolution de ses relations avec son environnement / This work proposes a model for analysis based on 3D GIS. The proposed approach allows queries to be made on one object (intra-object analysis) or a set of objects (inter-objects analysis) even if the geometrical coherence between objects is not perfect. From crystallographic principles, this model analyses the symmetric features of each object to describe its structure i.e. the way which geometric primitives are arranged together. This first abstraction, the structure, gives a global overview of the object. A second abstraction, the lattice unit, is obtained through the analysis of symmetric elements. It is used like a 3D Bounding Box adapted to the object shape. It allows relationships of geographical objects whatever their geometric dimension. With the help of lattice units, two graphs are computed to describe relationships between objects and to draw, for one object, the evolution of its relationship with its own environment

Cette thèse traite de problèmes liés à la théorie des limitesd'objets combinatoires, une récente théorie qui a permis de tisserdes liens entre différents domaines tels que la combinatoire,l'analyse, la géométrie ou la théorie de la probabilité.Cette thèse applique des méthode venant de cette théorie à des problèmesde combinatoire extrémale.Dans un premier chapitre, je développe une théorie des limites d'objetsappelés emph{types d'ordre}, un objets qui encode des configurationsd'ensembles de points du plan. Le type d'ordre d'un ensemble de pointssuffit à caractériser de nombreuses propriétés essentielles de cet ensemblede point comme, par exemple, son enveloppe convexe.Je montre qu'une limite de type d'ordre peut être représentée par un objetanalogue à un graphon à valeurs O ou 1.Je fais ensuite le lien entre limites de type d'ordre et la distributionnaturelle de limite de type d'ordre obtenue par l’échantillonnage de pointsdu plan suivant une certaine probabilité.De cette manière, toute probabilité sur le plan engendre une limite de typed'ordre. Je montre d'une part que cette correspondance n'est pas surjective-c'est à dire qu'il existe des limites de type d'ordre ne venant pas de probabilitédu plan- et j'étudie d'autre part son injectivité.Je montre que si le support d'une mesure de probabilité est assez gros, par exemple siil contient une boule ouvert, alors la limite que cette mesure engendre suffit à caractériser cette mesure à une transformation projective près.Un second chapitre traite de test de propriété.Un testeur de propriété est un algorithme aléatoire permettant de séparerles objets ayant une certaine propriété des objet à distance au moins εde l'avoir, au sens de la distance d'édition.Ce domaine donne des algorithmes extrêmement rapides, et en particulierdes algorithmes dont la complexité ne dépends pas de la taille de l'entréemais seulement du paramètre de précision ε.Un résultat fondamental de cet domaine pour les graphes montré par Alonet Shapira est le suivant : toute classe de graphe héréditaire possède un teltesteur.Cette thèse contribue à la question suivante :Quelles classes de graphes possède un testeur dont la complexité est unpolynôme en 1/ε ?Je montre qu'en particulier la classe des graphes d'intervales possède un teltesteur.La théorie des algèbres de drapeaux est un outil étroitement lié aux limites degraphes denses qui donne une méthode pour démontrer des bornes sur certainsparamètres combinatoires à l'aide d'un ordinateur.Dans un troisième chapitre, je présente un programme écrit durant ma thèsequi implémente cette méthode.Ce programme fonctionne comme une bibliothèque pour calculer dans les algèbresde drapeaux, manipuler des inégalités sur les drapeaux ou encoder des problèmesd'optimisations par une instance de programme semi-défini positif qui peutensuite être résolu par un solveur externe.Ce programme est en particulier utilisé pour obtenir un nouvelle borne pour le cas triangulaire de la conjecture de Caccetta-Häggkvist. / This thesis is focused on problems related to the theory of combinatorial limits.This theory opened links between different fields such asanalysis, combinatorics, geometry and probability theory.In this thesis, we apply ideas coming from this framework toproblems in extremal combinatorics.In a first chapter we develop a theory of limits for emph{order types},a geometrical object that encodes configuration of a set of points in theplane by the mean of the orientations of their triangles.The order type of a point set suffices to determine many of its properties,such as for instance the boundary of its convex hull.We show that the limit of a converging sequence of order typescan be represented by random-free object analogous to a graphon.Further, we link this notion to the natural distributions of order typesarising from the sampling of random points from some probability measureof the plane.We observe that in this mean, every probability measure gives rise to a limitof order types.We show that this map from probability measure on the plane to limit oforder type is not surjective.Concerning its injectivity,we prove that if a measure has large enough support, for instance if its supportcontains an open ball, the limit of order types the measure generatessuffices to essentially determine this measure.A second chapter is focused on property testing.A tester is a randomized algorithm for distinguishing between objects satisfyinga property from those that are at some distance at least εfrom having itby means of the edition distance.This gives very efficient algorithms, and in particular algorithms whosecomplexity does not depend on the size of the input but only on the parameter ε.For graphs, it has been shown by Alon and Shapira that every hereditary propertyhas such a tester.We contribute to the following question :which classes of graphs have a one-sided property tester with a number of queries that is a polynomial in 1/ε ?We give a proof that the class of interval graphs has such a tester.The theory of flag algebras is a framework introduced by Razborovclosely related to dense limit of graphs, that gives a way to systematicallyderive bounds for parameters in extremal combinatorics.In a third chapter we present a program developed during my Phd.that implements this method.This program works as a library that can compute flag algebras,manipulate inequalities on densities and encode the optimization of some parameterin a semi-definite positive instance that can be given to a dedicated solverto obtain a bound on this parameter.This program is in particular used to obtain a new bound forthe triangle case of the Caccetta-Häggkvist conjecture.

Une classe de graphes est close par mineurs si, pour tout graphe dans la classe et tout mineur de ce graphe, le mineur est ́egalement dans la classe. Par un fameux th ́eor`eme de Robertson et Seymour, nous savons que car- act ́eriser une telle classe peut ˆetre fait `a l’aide d’un nombre fini de mineurs exclus minimaux. Ceux-ci sont des graphes qui n’appartiennent pas `a la classe et qui sont minimaux dans le sens des mineurs pour cette propri ́et ́e.Dans cette thèse, nous étudions trois problèmes à propos de classes de graphes closes par mineurs. Les deux premiers sont reliés à la caractérisation de certaines classes de graphes, alors que le troisième étudie une relation de “packing-covering” dans des graphes excluant un mineur.Pour le premier problème, nous étudions des plongements isométriques de graphes dont les arêtes sont pondérées dans des espaces métriques. Principalement, nous nous intêressons aux espaces ell_2 et ell_∞. E ́tant donné un graphe pondéré, un plongement isométrique associe à chaque sommet du graphe un vecteur dans l’autre espace de sorte que pour chaque arête du graphe le poids de celle-ci est égal à la distance entre les vecteurs correspondant à ses sommets. Nous disons qu’une fonction de poids sur les arêtes est une fonction de distances réalisable s’il existe un tel plongement. Le paramètre f_p(G) détermine la dimension k minimale d’un espace ell_p telle que toute fonction de distances réalisable de G peut être plongée dans ell_p^k. Ce paramètre est monotone dans le sens des mineurs. Nous caractérisons les graphes tels que f_p(G) a une grande valeur en termes de mineurs inévitables pour p = 2 et p = ∞. Une famille de graphes donne des mineurs inévitables pour un invariant monotone pour les mineurs, si ces graphes “expliquent” pourquoi l’invariant est grand.Le deuxième problème étudie les mineurs exclus minimaux pour la classe de graphes avec φ(G) borné par une constante k, où φ(G) est un paramètre lié au dominant des coupes d’un graphe G. Ce polyèdre contient tous les points qui, composante par composante, sont plus grands ou égaux à une combination convexe des vecteurs d’incidence de coupes dans G. Le paramètre φ(G) est égal au membre de droite maximum d’une description linéaire du dominant des coupes de G en forme entière minimale. Nous étudions les mineurs exclus minimaux pour la propriété φ(G) <= 4 et montrons une nouvelle borne sur φ(G) en termes du “vertex cover number”.Le dernier problème est d’un autre type. Nous étudions une relation de “packing-covering” dans les classes de graphes excluant un mineur. Étant donné un graphe G, une boule de centre v et de rayon r est l’ensemble de tous les sommets de G qui sont à distance au plus r de v. Pour un graphe G et une collection de boules donnés nous pouvons définir un hypergraphe H dont les sommets sont ceux de G et les arêtes correspondent aux boules de la collection. Il est bien connu que dans l’hypergraphe H, le “transversal number” τ(H) vaut au moins le “packing number” ν(H). Nous montrons une borne supérieure sur ν(H) qui est linéaire en τ(H), résolvant ainsi un problème ouvert de Chepoi, Estellon et Vaxès. / A class of graphs is closed under taking minors if for each graph in the class and each minor of this graph, the minor is also in the class. By a famous result of Robertson and Seymour, we know that characterizing such a class can be done by identifying a finite set of minimal excluded minors, that is, graphs which do not belong to the class and are minor-minimal for this property.In this thesis, we study three problems in minor-closed classes of graphs. The first two are related to the characterization of some graph classes, while the third one studies a packing-covering relation for graphs excluding a minor.In the first problem, we study isometric embeddings of edge-weighted graphs into metric spaces. In particular, we consider ell_2- and ell_∞-spaces. Given a weighted graph, an isometric embedding maps the vertices of this graph to vectors such that for each edge of the graph the weight of the edge equals the distance between the vectors representing its ends. We say that a weight function on the edges of the graph is a realizable distance function if such an embedding exists. The minor-monotone parameter f_p(G) determines the minimum dimension k of an ell_p-space such that any realizable distance function of G is realizable in ell_p^k. We characterize graphs with large f_p(G) value in terms of unavoidable minors for p = 2 and p = ∞. Roughly speaking, a family of graphs gives unavoidable minors for a minor-monotone parameter if these graphs “explain” why the parameter is high.The second problem studies the minimal excluded minors of the class of graphs such that φ(G) is bounded by some constant k, where φ(G) is a parameter related to the cut dominant of a graph G. This unbounded polyhedron contains all points that are componentwise larger than or equal to a convex combination of incidence vectors of cuts in G. The parameter φ(G) is equal to the maximum right-hand side of a facet-defining inequality of the cut dominant of G in minimum integer form. We study minimal excluded graphs for the property φ(G) <= 4 and provide also a new bound of φ(G) in terms of the vertex cover number.The last problem has a different flavor as it studies a packing-covering relation in classes of graphs excluding a minor. Given a graph G, a ball of center v and radius r is the set of all vertices in G that are at distance at most r from v. Given a graph and a collection of balls, we can define a hypergraph H such that its vertices are the vertices of G and its edges correspond to the balls in the collection. It is well-known that, in the hypergraph H, the transversal number τ(H) is at least the packing number ν(H). We show that we can bound τ(H) from above by a linear function of ν(H) for every graphs G and ball collections H if the graph G excludes a minor, solving an open problem by Chepoi, Estellon et Vaxès. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse a pour thème la coloration de diverses classes de graphes épars. Shearer montra en 1983 [She83] que le ratio d'indépendance des graphes sans triangle de degré maximal d est au moins (1-o(1))ln d/d, et 13 ans plus tard Johansson [Joh96] démontra que le nombre chromatique de ces graphes est au plus O(d/ln d) quand d tend vers l'infini. Ce dernier résultat fut récemment amélioré par Molloy [Mol19], qui montra que la borne (1+o(1))d/ln d est valide quand d tend vers l'infini.Tandis que le résultat de Molloy s'exprime à l'aide d'un paramètre global, le degré maximal du graphe, nous montrons qu'il est possible de l'étendre à la coloration locale. Il s'agit de la coloration par liste, où la taille de la liste associée à chaque sommet ne dépend que de son degré. Avec une méthode différente se basant sur les propriétés de la distribution hard-core sur les ensembles indépendants d'un graphe, nous obtenons un résultat similaire pour la coloration fractionnaire locale, avec des hypothèses plus faibles. Nous démontrons également un résultat concernant la coloration fractionnaire locale des graphes où chaque sommet est contenu dans un nombre borné de triangles, et une borne principalement optimale sur le taux d'occupation — la taille moyenne des ensembles indépendants — de ces graphes. Nous considérons également les graphes de maille 7, et prouvons des résultats similaires qui améliorent les bornes précédemment connues quand le degré maximal du graphe est au plus 10^7. Finalement, pour les graphes d-réguliers où d vaut 3, 4, ou 5, de maille g variant entre 6 et 12, nous démontrons de nouvelles bornes inférieures sur le ratio d'indépendance.Le Chapitre 2 est dédié à la coloration à distance t d'un graphe, qui généralise la notion de coloration forte des arêtes. Nous cherchons à étendre le théorème de Johansson à la coloration à distance t, par l'exclusion de certains cycles. Le résultat de Johansson s'obtient par exclusion des triangles, ou des cycles de taille k pour n'importe quelle valeur de k. Nous montrons que l'exclusion des cycles de taille 2k, pour n'importe quel k>t, a un effet similaire sur le nombre chromatique à distance t, et sur l'indice chromatique à distance t+1. En outre, quand t est impair, une conclusion similaire peut se faire pour le nombre chromatique à distance t par l'exclusion des cycles de d'une taille impaire fixée valant au moins 3t. Nous étudions l'optimalité de ces résultats à l'aide de constructions de nature combinatoire, algébrique, et probabiliste.Dans le Chapitre 3, nous nous intéressons à la densité bipartie induite des graphes sans triangle, un paramètre relaxant celui de la coloration fractionnaire. Motivés par une conjecture de Esperet, Kang, et Thomassé [EKT19], qui prétend que la densité bipartie induite de graphes sans triangle de degré moyen d est au moins de l'ordre de ln d, nous démontrons cette conjecture quand d est suffisamment grand en termes du nombre de sommets n, à savoir d est au moins de l'ordre de (n ln n)^(1/2). Ce résultat ne pourrait être amélioré que par une valeur de l'ordre de ln n, ce que nous montrons à l'aide d'une construction reposant sur le processus sans triangle. Nos travaux se ramènent à un problème intéressant, celui de déterminer le nombre chromatique fractionnaire maximal d'un graphe épars à n sommets. Nous prouvons des bornes supérieures non triviales pour les graphes sans triangle, et pour les graphes dont chaque sommet appartient à un nombre borné de triangles.Cette thèse est reliée aux nombres de Ramsey. À ce jour, le meilleur encadrement connu sur R(3,t) nous est donné par le résultat de Shearer, et par une analyse récente du processus sans triangle [BoKe13+,FGM13+], ce qui donne(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Beaucoup de nos résultats ne pourraient être améliorés à moins d'améliorer par la même occasion (1), ce qui constituerait une révolution dans la théorie de Ramsey quantitative. / This thesis focuses on generalisations of the colouring problem in various classes of sparse graphs.Triangle-free graphs of maximum degree d are known to have independence ratio at least (1-o(1))ln d/d by a result of Shearer [She83], and chromatic number at most O(d/ln d) by a result of Johansson [Joh96], as d grows to infinity. This was recently improved by Molloy, who showed that the chromatic number of triangle-free graphs of maximum degree d is at most (1+o(1))d/ln d as d grows to infinity.While Molloy's result is expressed with a global parameter, the maximum degree of the graph, we first show that it is possible to extend it to local colourings. Those are list colourings where the size of the list associated to a given vertex depends only on the degree of that vertex. With a different method relying on the properties of the hard-core distribution on the independent sets of a graph, we obtain a similar result for local fractional colourings, with weaker assumptions. We also provide an analogous result concerning local fractional colourings of graphs where each vertex is contained in a bounded number of triangles, and a sharp bound for the occupancy fraction — the average size of an independent set — of those graphs. In another direction, we also consider graphs of girth 7, and prove related results which improve on the previously known bounds when the maximum degree does not exceed 10^7. Finally, for d-regular graphs with d in the set {3,4,5}, of girth g varying between 6 and 12, we provide new lower bounds on the independence ratio.The second chapter is dedicated to distance colourings of graphs, a generalisation of strong edge-colourings. Extending the theme of the first chapter, we investigate minimal sparsity conditions in order to obtain Johansson-like results for distance colourings. While Johansson's result follows from the exclusion of triangles — or actually of cycles of any fixed length — we show that excluding cycles of length 2k, provided that k>t, has a similar effect for the distance-t chromatic number and the distance-(t+1) chromatic index. When t is odd, the same holds for the distance-t chromatic number by excluding cycles of fixed odd length at least 3t. We investigate the asymptotic sharpness of our results with constructions of combinatorial, algebraic, and probabilistic natures.In the third chapter, we are interested in the bipartite induced density of triangle-free graphs, a parameter which conceptually lies between the independence ratio and the fractional chromatic number. Motivated by a conjecture of Esperet, Kang, and Thomassé [EKT19], which states that the bipartite induced density of a triangle-free graph of average degree d should be at least of the order of ln d, we prove that the conjecture holds for when d is large enough in terms of the number of vertices n, namely d is at least of the order of (n ln n)^(1/2). Our result is shown to be sharp up to term of the order of ln n, with a construction relying on the triangle-free process. Our work on the bipartite induced density raises an interesting related problem, which aims at determining the maximum possible fractional chromatic number of sparse graph where the only known parameter is the number of vertices. We prove non trivial upper bounds for triangle-free graphs, and graphs where each vertex belongs to a bounded number of triangles.All the content of this thesis is a collection of specialisations of the off-diagonal Ramsey theory. To this date, the best-known bounds on the off-diagonal Ramsey number R(3,t) come from the aforementioned result of Shearer for the upper-bound, and a recent analysis of the triangle-free process [BoKe13+,FGM13+] for the lower bound, giving(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Many of our results are best possible barring an improvement of (1), which would be a breakthrough in off-diagonal Ramsey theory.

De nos jours, les interactions ont une part prépondérante dans notre vie. Ces interactions peuvent représenter la diffusion de rumeurs, de maladies, etc. Comprendre comment ces interactions affectent notre vie est important. Une façon naturelle de faire est d'utiliser la théorie des graphes. Néanmoins, comme le montrent certaines études, l'aspect temporel ne doit pas être négligé. Dans ce travail, nous nous sommes concentrés sur la détection d'individus importants dans ces graphes en utilisant des métriques de centralité qui prennent en compte l'aspect temporel. Nous avons proposé un protocole de comparaison qui compare les différentes mesures de centralité existantes. Nous l'avons appliqué sur plusieurs graphes, ce qui nous a donné un aperçu de la façon dont les différentes métriques agissent. Ensuite, nous avons observé le besoin de calcul élevé de ces métriques de centralité. Dès lors, nous avons introduit une méthode qui réduit ce besoin. Finalement, nous avons introduit une nouvelle mesure de centralité, appelée ego-betweenness centrality. / Nowadays, interactions are a huge part of our daily life. These interactions can represent the diffusion of rumors, diseases, etc. Understanding how these interactions affect our life is quite important. A natural way to do so is using graph theory. However, this is not straightforward as studies show the temporal aspect, in other words, the order of interactions, should be taken into account. In this work, we concentrated on detecting the important individuals in these graphs using centrality metrics that take into account the temporal aspect. We proposed a comparison protocol that compares the different centrality metrics that exist. We applied it on several networks, which gave us insight on how the different metrics react. Secondly, we observed the high computational need of these centrality metrics. Therefore, we introduced a method to reduce this need. And finally, we introduced a novel centrality metric that we call ego-betweenness centrality.

La richesse de la programmation par contraintes repose sur la très large variété des algorithmes qu’elle utilise en puisant dans les grands domaines de l’Intelligence Artificielle, de la Programmation Logique et de la Recherche Opérationnelle. Cependant, cette richesse, qui offre aux spécialistes une palette quasi-illimitée de configurations possibles pour attaquer des problèmes combinatoires, devient une frein à la diffusion plus large du paradigme, car les outils actuels sont très loin d’une boîte noire, et leur utilisation suppose une bonne connaissance du domaine, notamment en ce qui concerne leur paramétrage. Dans cette thèse, nous proposons d’analyser le comportement des contraintes de cardinalité avec des modèles probabilistes et des outils de dénombrement, pour paramétrer automatiquement les solveurs de contraintes : heuristiques de choix de variables et de choix de valeurs et stratégies de recherche. / The main asset of constraint programming is its wide variety of algorithms that comes from the major areas of artificial intelligence, logic programming and operational research. It offers specialists a limitless range of possible configurations to tackle combinatorial problems, but it becomes an obstacle to the wider diffusion of the paradigm. The current tools are very far from being used as a black-box tool, and it assumes a good knowledge of the field, in particular regarding the parametrization of solvers.In this thesis, we propose to analyze the behavior of cardinality constraints with probabilistic models and counting tools, to automatically parameterize constraint solvers: heuristics of choice of variables and choice of values and search strategies.

L'utilisation croissante des réseaux sociaux et de capteurs génère une grande quantité de données qui peuvent être représentées sous forme de graphiques complexes. Il y a de nombreuses tâches allant de l'analyse de l'information à la prédiction et à la récupération que l'on peut imaginer sur ces données où la relation entre les noeuds de graphes devrait être informative. Dans cette thèse, nous avons proposé différents modèles pour trois tâches différentes: - Classification des noeuds graphiques - Prévisions de séries temporelles relationnelles - Filtrage collaboratif. Tous les modèles proposés utilisent le cadre d'apprentissage de la représentation dans sa variante déterministe ou gaussienne. Dans un premier temps, nous avons proposé deux algorithmes pour la tâche de marquage de graphe hétérogène, l'un utilisant des représentations déterministes et l'autre des représentations gaussiennes. Contrairement à d'autres modèles de pointe, notre solution est capable d'apprendre les poids de bord lors de l'apprentissage simultané des représentations et des classificateurs. Deuxièmement, nous avons proposé un algorithme pour la prévision des séries chronologiques relationnelles où les observations sont non seulement corrélées à l'intérieur de chaque série, mais aussi entre les différentes séries. Nous utilisons des représentations gaussiennes dans cette contribution. C'était l'occasion de voir de quelle manière l'utilisation de représentations gaussiennes au lieu de représentations déterministes était profitable. Enfin, nous appliquons l'approche d'apprentissage de la représentation gaussienne à la tâche de filtrage collaboratif. Ceci est un travail préliminaire pour voir si les propriétés des représentations gaussiennes trouvées sur les deux tâches précédentes ont également été vérifiées pour le classement. L'objectif de ce travail était de généraliser ensuite l'approche à des données plus relationnelles et pas seulement des graphes bipartis entre les utilisateurs et les items. / The increasing use of social and sensor networks generates a large quantity of data that can be represented as complex graphs. There are many tasks from information analysis, to prediction and retrieval one can imagine on those data where relation between graph nodes should be informative. In this thesis, we proposed different models for three different tasks: - Graph node classification - Relational time series forecasting - Collaborative filtering. All the proposed models use the representation learning framework in its deterministic or Gaussian variant. First, we proposed two algorithms for the heterogeneous graph labeling task, one using deterministic representations and the other one Gaussian representations. Contrary to other state of the art models, our solution is able to learn edge weights when learning simultaneously the representations and the classifiers. Second, we proposed an algorithm for relational time series forecasting where the observations are not only correlated inside each series, but also across the different series. We use Gaussian representations in this contribution. This was an opportunity to see in which way using Gaussian representations instead of deterministic ones was profitable. At last, we apply the Gaussian representation learning approach to the collaborative filtering task. This is a preliminary work to see if the properties of Gaussian representations found on the two previous tasks were also verified for the ranking one. The goal of this work was to then generalize the approach to more relational data and not only bipartite graphs between users and items.

Cette thèse présente une méthode de segmentation de modèles 3D en parties significatives ou fonctionnelles. La segmentation s’effectue par "transfert" d’une segmentation exemple : la segmentation d’un modèle est calculée en transférant les segments d’une segmentation exemple d’un objet appartenant à la même classe de modèles 3D. Pour ce faire, nous avons adapté et étendu la méthode de segmentation par les marches aléatoires et transformé notre problème en un problème de localisation et mise en correspondance de faces germes. Notre méthode comporte quatre étapes fondamentales : la mise en correspondance entre le modèle exemple et le modèle cible, la localisation automatique de germes sur le modèle cible pour initialiser les régions, le calcul des segments du modèle cible et l’amélioration de leurs frontières. En constatant que les critères de similarité diffèrent selon que les objets sont de type rigide (chaises, avions,…) ou de type articulé (humains, quadrupèdes,…), nous décomposons notre approche en deux. La première dédiée aux objets rigides, où la mise en correspondance est basée sur le calcul des transformations rigides afin d’aligner au mieux les parties significatives des deux objets comparés. La deuxième dédiée aux modèles articulés, où la mise en correspondance des parties fonctionnelles, présentant des variations de poses plus importantes, est basée sur des squelettes calculés via des diagrammes de Reeb. Nous montrons à travers des évaluations qualitatives et quantitatives que notre méthode obtient des résultats meilleurs que les techniques de segmentation individuelle et comparables aux techniques de co-segmentation avec un temps de calcul nettement inférieur. / In this dissertation, we present a new method to segment 3D models into their functional parts. The segmentation is performed by a transfer approach: a semantic-oriented segmentation of an object is calculated using a pre-segmented example model from the same class (chairs, humans, etc.). To this end, we adapted and extended the random walk segmentation method which allowed us to transform our problem into a problem of locating and matching seed faces. Our method consists of four fundamental steps: establishing correspondences between the example and the target model, localizing seeds to initialize regions in the target model, computing the segments and refining their boundaries in the target model. We decomposed our approach in two, taking into account similarity criteria which differ regarding the object type (rigid vs. articulated). The first approach is dedicated to rigid objects (chairs, airplanes, etc.), where the matching is based on rigid transformations to determine the best alignment between the functional parts of the compared objects. The second one focused on articulated objects (humans, quadrupeds, etc.), where coarse topological shape attributes are used in a skeleton-based approach to cover larger pose variations when computing correspondences between functional parts. We show through qualitative and quantitative evaluations that our method improves upon individual segmentation techniques and obtains results that are close to the co-segmentation techniques results with an important calculation time reduction.