Дисертації з теми "Graphes en rubans métriques"

Cette thèse présente quelques contributions à l’étude des fonctions de comptage des graphes en rubans métriques. Un graphe en ruban, aussi connu sous le nom de carte combinatoire, est un plongement cellulaire d’un graphe dans une surface. On peut le représenter via le recollements de polygones ou encore via des factorisations de permutations. Une métrique sur un graphe en rubans est l’attribution d’une longueur strictement positive à chaque arête. Les fonctions de comptage donnent le nombre de graphes en rubans avec une métrique entière et combinatoire fixée (genre de la surface, degré des sommets, nombre de bords) en fonction des périmètres des bords. Notre approche à l’étude de ces fonctions est purement combinatoire et repose sur l’utilisation des bijections et chirurgies pour les graphes en rubans. Dans un premier temps, on montre que ces fonctions sont (quasi-)polynomiales par morceaux, et on précise les régions de (quasi-)polynomialité. Ensuite, on étudie les cas où leur termes de plus haut degré sont de vrais polynômes. Notre intérêt dans ces cas vient du fait que les polynômes correspondants sont utiles pour l’énumération des surfaces à petits carreaux, qui correspondent aux points entiers des strates des surfaces de (demi-)translation (de manière équivalent, states des différentielles sur les surfaces de Riemann). Par conséquent, on peut donner des formules raffinées/alternatives pour les volumes de Masur-Veech des strates. Un exemple connu sont les polynômes de Kontsevich, qui comptent les graphes en rubans métriques trivalents de genre et périmètres des bords fixés. Ils ont été utilisés récemment par Delecroix, Goujard, Zograf et Zorich pour obtenir une formule combinatoire pour les volumes des strates principales des différentielles quadratiques. On se concentre sur les graphes en rubans métriques face-bipartis, qui apparaissent dans l’étude des différentielles Abéliennes. On montre que pour les graphes à un sommet, les termes de plus haut degré des fonctions de comptage sur certains sous-espaces sont des polynômes explicites. En conséquence, on obtient la série génératrice des contributions des surfaces à petits carreaux à n cylindres aux volumes des strates minimales des différentielles Abéliennes, raffinant un résultat précédent de Sauvaget. Ensuite, on présente un résultat de polynomialité similaire pour les deux sous-familles de graphes qui correspondent ou composants connexes de strates minimales de parité spin paire/impaire. Cela donne un raffinement d’une formule pour les différences des volumes correspondants obtenue précédemment par Chen, Möller, Sauvaget et Zagier. Puis on conjecture que le phénomène de polynomialité reste vrai pour les familles de graphes à plusieurs sommets, si chaque graphe est pondéré par le comptage de certains arbres couvrants. On prouve cette conjecture dans le cas planaire. En chemin, on construit des familles d’arbres plans qui correspondent à certaines triangulations de produits de simplexes qui représentent un intérêt du point de vue de la théorie des polytopes. Finalement, on présente une contribution au projet commun avec Duryev et Goujard, où la formule combinatoire de Delecroix, Goujard, Zograf et Zorich est généralisée aux strates des différentielles quadratiques aux singularités impaires. La contribution est une preuve combinatoire de la formule pour les coefficients qui comptent certaines dégénérescences des graphes en ruban métriques non-face-biparti
This thesis presents several contributions to the study of counting functions for metric ribbon graphs. Ribbon graphs, also known as combinatorial maps, are cellular embeddings of graphs in surfaces modulo homeomorphisms. They are combinatorial objects that can be represented as gluings of polygons or factorizations of permutations. Metric on a ribbon graph is an assignment of positive lengths to its edges. The counting functions give the number of integral metric ribbon graphs with fixed combinatorics (genus of the surface, degrees of vertices, number of boundaries) as a function of the perimeters of the boundaries. Our approach to their study is purely combinatorial and relies on bijections and surgeries for ribbon graphs. Firstly, we show that these functions are piecewise (quasi-)polynomials, specifying exactly the regions of (quasi-)polynomiality. We then study the cases when their top-degree terms are honest polynomials. Our interest in such cases comes from the fact that the corresponding polynomials can be used for refined enumeration of square-tiled surfaces, which correspond to integer points in the strata of (half-)translations surfaces (equivalently, strata of differentials on Riemann surfaces). Consequently, one can give refined/alternative formulas for Masur-Veech volumes of strata. One known example are the Kontsevich polynomials, counting trivalent metric ribbon graphs of given genus and perimeters of boundaries. They were recently used by Delecroix, Goujard, Zograf and Zorich to give a combinatorial formula for the volumes of principal strata of quadratic differentials. We concentrate on face-bipartite metric ribbon graphs, which appear in the study of Abelian differentials. We show that in the case of one-vertex graphs the top-degree terms of the counting functions on certain subspaces are in fact (explicit) polynomials. As a consequence, we deduce the generating function for the contributions of n-cylinder square-tiled surfaces to the volumes of minimal strata of Abelian differentials, refining a previous result of Sauvaget. We then present a similar polynomiality result for the two subfamilies of graphs corresponding to even/odd spin connected components of the minimal strata. This also gives a refinement of a formula for the corresponding volume differences previously obtained by Chen, Möller, Sauvaget and Zagier. Next we conjecture that the polynomiality phenomenon holds for families of graphs with several vertices, if each graph is weighted by the count of certain spanning trees. We prove the conjecture in the planar case. In the process, we construct families of plane trees which correspond to certain triangulations of the product of two simlpices, which are interesting from the point of view of the theory of polytopes. Finally, we present a contribution to a joint work with Duryev and Goujard, where the combinatorial formula of Delecroix, Goujard, Zograf and Zorich is generalized to all strata of quadratic differentials with odd singularities. The contribution is a combinatorial proof of the formula for coefficients counting certain degenerations of (non-face-bipartite) metric ribbon graphs

Les grands réseaux de communication sont partout, des centres de données avec des millions de serveurs jusqu’aux réseaux sociaux avec plusieurs milliards d’utilisateurs.Cette thèse est dédiée à l’étude fine de la complexité de différents problèmes combinatoires sur ces réseaux. Dans la première partie, nous nous intéressons aux propriétés des plongements des réseaux de communication dans les arbres. Ces propriétés aident à mieux comprendre divers aspects du trafic dans les réseaux (tels que la congestion). Plus précisément, nous étudions la complexité du calcul de l’hyperbolicité au sens de Gromov et de paramètres des décompositions arborescentes dans les graphes. Ces paramètres incluent la longueur arborescente (treelength) et l’épaisseur arborescente (treebreadth). Au passage, nous démontrons de nouvelles bornes sur ces paramètres dans de nombreuses classes de graphes, certaines d’entre elles ayant été utilisées dans la conception de réseaux d’interconnexion des centres de données. Le résultat principal dans cette partie est une relation entre longueur et largeur arborescentes (treewidth), qui est un autre paramètre très étudié des graphes. De ce résultat, nous obtenons une vision unifiée de la ressemblance des graphes avec un arbre, ainsi que différentes applications algorithmiques. Nous utilisons dans cette partie divers outils de la théorie des graphes et des techniques récentes de la théorie de la complexité
Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example

Cette thèse concerne l'étude des graphes quantiques, c'est à dire, des systèmes quantiques dans lesquels une particule non relativiste est confinée sur un graphe. Nous proposons une nouvelle voie pour représenter des conditions aux limites, et à l'aide de ce résultat nous résolvons le problème, resté longtemps ouvert, d'approximation par des graphes réguliers de tous les couplages singuliers aux sommets dans un graphe quantique. Nous présentons une construction dans laquelle les arêtes sont disjointes et les paires d'extrémités ainsi obtenues sont raccordés par des arêtes additionnelles de longueur 2d. Chacune de ces arêtes porte un potentiel delta et un potentiel vectoriel . Nous montrons que lorsque d tend vers zéro et les potentiels dépendent convenablement de d, la limite peut produire tout couplage singulier de sommets requis. Ce type de conditions aux limites est utilisé pour examiner les propriétés de diffusion par des sommets singuliers de degré 3. Nous montrons que les couplages entre chaque paire de lignes issues du sommet sont réglables individuellement ce qui pourrait permettre la conception de filtre quantique de type "aiguillage spectral". Nous étudions aussi les opérateurs de Schrödinger sur un graphe infini en forme de chaîne composée de cercles identiques couplés aux points de contact par les interactions. delta Si le graphe est périodique, l'hamiltonien a un spectre de bande. Nous considérons une déformation "courbée" de la chaîne qui consiste en un changement de la position du point de contact entre deux cercles. On montre que cette déformation a pour conséquence la naissance de valeurs propres et analyse leur dépendance par rapport à l"angle de courbature".

Cette thèse concerne l'étude des graphes quantiques, c'est à dire, des systèmes quantiques dans lesquels une particule non relativiste est confinée sur un graphe. Nous proposons une nouvelle voie pour représenter des conditions aux limites, et à l'aide de ce résultat nous résolvons le problème, resté longtemps ouvert, d'approximation par des graphes réguliers de tous les couplages singuliers aux sommets dans un graphe quantique. Nous présentons une construction dans laquelle les arêtes sont disjointes et les paires d'extrémités ainsi obtenues sont raccordés par des arêtes additionnelles de longueur 2d. Chacune de ces arêtes porte un potentiel delta et un potentiel vectoriel. Nous montrons que lorsque d tend vers zéro et les potentiels dépendent convenablement de d, la limite peut produire tout couplage singulier de sommets requis. Ce type de conditions aux limites est utilisé pour examiner les propriétés de diffusion par des sommets singuliers de degré 3. Nous montrons que les couplages entre chaque paire de lignes issues du sommet sont réglables individuellement ce qui pourrait permettre la conception de filtre quantique de type "aiguillage spectral". Nous étudions aussi les opérateurs de Schrödinger sur un graphe infini en forme de chaîne composée de cercles identiques couplés aux points de contact par les interactions. Delta Si le graphe est périodique, l'hamiltonien a un spectre de bande. Nous considérons une déformation "courbée" de la chaîne qui consiste en un changement de la position du point de contact entre deux cercles. On montre que cette déformation a pour conséquence la naissance de valeurs propres et analyse leur dépendance par rapport à l"angle de courbature"
This thesis is devoted to investigation of quantum graphs, in other words, quantum systems in which a nonrelativistic particle is confined to a graph. We propose a new way to represent the boundary conditions, and with the help of this result we solve the longstanding open problemof approximating by regular graphs all singular vertex couplings in quantum graph vertices. We present a construction in which the edges are disjunct and the pairs of the so obtained endpoints are joined by additional connecting edges of lengths 2d. Each connecting edge carries a delta potential and a vector potential. It is shown that when the lengths 2d of the connecting edges shrink to zero and the added potentials properly depend on d, the limit can yield any requested singular vertex coupling. This type of boundary conditions is used to examine scattering properties of singular vertices of degrees 2 and 3. We show thar the couplings between each pair of the outgoing edges are individually tunable, which could enable the design of quantum spectral junctions filters. We also study Schrödinger operators on an infinite quantum graph of a chain form which consists of identical rings connected at the touching points by delta-couplings. If the graph is periodic, the Hamiltonian has a band spectrum. We consid a "bending" deformation of the chain consisting in changing the position of the point of contact between two rings. We show that this deformation gives rive to eigenvalues and analyze their dependence on the "bending angle"

Le thème central de cette thèse est l'étude d'espaces métriques aléatoires dont la structure est apparentée à celle d'un arbre. On étudie d'abord une façon aléatoire de recoller une suite d'espaces métriques itérativement, en attachant à chaque étape de la procédure un nouveau bloc sur la structure construite jusque là. Sous certaines conditions sur les blocs que l'on agglomère, on calcule la dimension de Hausdorff de la structure obtenue et son expression est surprenante ! On s'intéresse ensuite à certaines propriétés asymptotiques (degrés, hauteur, profil) de deux modèles d'arbres discrets construits récursivement, les arbres récursifs pondérés et les arbres à attachement préférentiel affine à poids initiaux. Les premiers encodent la structure discrète sous-jacente aux recollements des blocs dans la construction précédente, et les seconds ont un rôle similaire pour des modèles de graphes discrets construits de façon analogues. On exploite cette connexion afin de montrer des résultats de limites d'échelle pour certains modèles de graphes discrets vers des espaces métriques continus construits par recollement itératif. Enfin, dans un travail en collaboration avec Christina Goldschmidt et Bénédicte Haas, on prouve des résultats concernant la composante alpha-stable à surplus fixé. Cet espace métrique aléatoire apparaît comme la limite d'échelle des grandes composantes connexes de modèles de configuration critique à queue lourde. L'objets obtenu est presque un arbre à l'exception d'un nombre fini de cycles dont nous étudions la structure
The subject of this thesis is the study of some random metric spaces with a tree-like structure. We first study a construction in which we glue a sequence of metric spaces onto each other in a sequential manner. Under some conditions on the spaces that we aggregate, we compute the Hausdorff dimension of the obtained structure and it has a surprising expression ! We then investigate some asymptotic properties (degrees, height,profile) of two models of growing discrete trees, the weighted recursive trees and the preferential attachment trees with additive fitnesses. The former encodes the underlying discrete structure in the construction described above and the latter have a similar interpretation for some models of discrete growing graphs. We make use of this connection in order to prove scaling limit results for these random discrete graphs towards continuous metric space constructed by a gluing procedure. Last, in a joint work with Christina Goldschmidt and Bénédicte Haas, we investigate the behaviour of the alpha­stable component with fixed surplus. This random metric space appears as the scaling limit of large connected components of the configuration model with heavy-tailed degrees. This abject is almost a tree except for a finite number of cycles. We compute the distribution of the cyclic structure and give a description of the whole space as trees glued along this structure

Cette these presente un point de vue categorique des systemes de transitions et illustre sa pertinence par des applications en theorie des graphes. Ce point de vue consiste, d'apres m. Pouzet et i. Rosenberg a considerer un systeme de transitions comme une sorte d'espace metrique; la distance entre deux etats etant, non pas un nombre, mais le langage accepte par l'automate constitue du systeme de transitions et de ces deux etats comme etats initiaux et finaux. Par exemple, voyant un graphe comme un systeme de transitions sur l'alphabet a deux lettres a et b muni de l'involution echangeant a et b, on retrouve la distance zigzag introduite par quilliot en 1983 pour les graphes. Si on ordonne les langages par l'ordre inverse de l'inclusion, alors les morphismes de systeme de transitions deviennent des applications contractantes; ainsi les idees issues de l'abondante etude des contractions d'espaces metriques peuvent etre appliquees aux systemes de transitions. Considerant des systemes de transitions involutifs nous decrivons les langages acceptes; notre description utilise un ordre sous les mots qui peut se definir a partir d'une regle de reecriture possedant la propriete de church-rosser. Nous en tirons une caracterisation des retractes absolus parmi ces systemes, semblable a celle obtenue par aronszajn et panichpakdi en 1956 pour les espaces metrique. Comme application nous obtenons, en collaboration avec h. -j. Bandelt et m. Pouzet, que la classe des graphes antisymetriques est la plus large classe de graphes ayant les retractes de produits de zigzags (reflexifs et antisymetriques) comme retractes absolus

Ce travail se situe dans le domaine de l'optimisation combinatoire. Nous étudions plus particulièrement des caractérisations d'objets pour lesquels des problèmes, qui dans le cas général sont NP-complets, deviennent polynomiaux. Nous traitons d'abord le problème de la faisabilité d'un multiflot, qui possède des applications trés importantes en recherche opérationnelle. C'est à dire, étant donnée la spécification du problème, avec le réseau, les capacités et les demandes, on veut démontrer l'existence ou la non-existence d'une solution. Une façon d'aborder ce problème est de donner des conditions nécessaires et suffisantes pour l'existence d'un multiflot, comme celle connue par condition de coupe. Nous présentons la condition (CC, K_5, F_7), qui généralise la condition de coupe et "raffine" une autre condition existante, la (CC3). La structure du problème de multiflot nous permet aussi de regarder un problème étroitement associé, celui du "packing" de métriques. Nous traitons le cas des packing entiers et demi-entiers, quand la famille de métriques comprend les métriques CC3 et les métriques K_5 et F_7. Nous caractérisons la classe de graphes, et plus généralement de matroïdes, ou l'on peut trouver des packings entiers et demi-entiers, sous quelques hypothèses additionnelles. Puis nous nous intéressons aux propriétés générales des graphes h- et t-parfaits, et au problème de coloration associé. Les résultats que nous présentons donnent des bornes pour leur nombres chromatiques, et des classes qui satisfont une conjecture de Shepherd. Enfin nous présentons la hiérarchie des graphes étudiés, qui est obtenu grâce à des outils comme les graphes faiblement bipartis, les clutters binaires et les matrices à composantes 0,1. Nous clôturons ce mémoire en précisant quelques directions de recherche qui pourront donner suite à ce travail, aussi bien sur le sujet de la faisabilité des problèmes de multiflot, que sur la coloration des graphes h- et t-parfaits.

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes
This Ph. D. Manuscript is built around the notion of graph embedding. An embedding of a graph G is an application mapping the vertices of G to elements of another structure, and preserving some properties of G. There are two types of embeddings. The combinatorial embeddings map the vertices of a graph G to the vertices of a graph H. The usual property that is preserved is the adjacency between vertices. In this thesis, we consider the isometric embeddings, preserving in addition the distances between vertices. We give some structural characterizations for families of graphs isometrically embeddable in hypercubes or Hamming graphs. The topological embeddings aim at drawing a graph G on some surface. Vertices are mapped to distinct points of the surface and the edges are represented by continuous curves linking these points. Is it possible to draw a graph G so that the edges do not cross eachother ? If not, what is the minimum number of crossings of a drawing of G ? We deal with these questions on different surfaces, or in relation with some graph operations as direct product or zip product

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes.

Cette these a pour but de montrer la pertinence du concept d'enveloppe injective dans la description des varietes de retractes absolus. Etant donne un systeme de transition m:=(q,t) sur un alphabet a, la distance entre deux etats x, y est le langage accepte par l'automate a:=(mx,y ayant x pour etat initial et y pour etat final. Nous supposons l'alphabet ordonne et muni d'une involution preservant l'ordre et nous considerons des systemes de transitions qui sont reflexifs et involutifs. Lorsque a est forme de deux lettres a,b et a=b, ces systemes sont ceux associes aux graphes reflexifs non necessairement symetrques et la distance zig-zag introduite par a. Quilliot en 1983. On peut voir les systemes de transitions reflexifs et involutifs comme des espaces metriques dont la distance prend ses valeurs dans l'algebre de heyting constituee des sections finales de a* muni de l'ordre de higman. De meme que, comme l'a montre j. Isbell, les espaces metriques ordinaires ont une enveloppe injective, chaque espace metrique a valeurs dans cette algebre de heyting a egalement une enveloppe injective; en outre celle-ci est un systeme de transition reflexif et involutif. Si dans le cas des espaces ordinaires, l'enveloppe injective d'un espace a deux elements est le segment qui joint ces deux elements, dans notre cas, meme sur l'alphabet a deux lettres, la structure de l'enveloppe injective peut etre tres compliquee. Or ces enveloppes injectives jouent un role important. Elles permettent de construire toutes les enveloppes injectives et ainsi determinent la variete ar#t formee des systemes de transitions qui sont retractes de toutes leurs extensions isometriques, systemes que nous appelons retractes absolus. Elles interviennent egalement dans la description des sous-varietes. Nous inspirant du schema de classification propose par d. Duffus et i. Rival, nous appelons representation d'un espace metrique e sur notre algebre de heyting toute famille (e#i) d'espaces metriques telle que e est retracte du produit e#i et chaque e#i est retracte de e. Nous disons qu'un espace metrique e est irreductible si pour toute representation (e#i) de e, l'espace e est retracte d'un certain e#i. L'espace e est indecomposable (resp. Finiment indecomposable) si pour toute famille (resp. Finie) (e#i) d'espaces metriques, e retracte du produit e#i implique qu'il est retracte de l'un des facteurs. Nous montrons que les irreductibles sont des enveloppes injectives d'espaces a deux elements. Avec une hypothese de finitude sur l'alphabet a, nous montrons que tout retracte absolu a une representation par des irreductibles. Nous montrons egalement que les sous-varietes de ar#t sont en nombre continupotent des que l'alphabet a au moins deux lettres. Pour une section finale f de a*, notons s#f l'enveloppe injective de l'espace a deux elements (x,y) tel que d(x,y)=f. Nous montrons que e est indecomposable (resp. Finiment indecomposable) si et seulement si il est de la forme s#f avec f completement irreductible (resp. Irreductible) dans l'algebre de heyting. Le premier cas revient a dire que f est de la forme a*u ou u est un mot, le second que f=a*j ou j est un ideal de a. Nous decrivons les systemes de transitions associes aux elements completement irreductibles de l'algebre de heyting et nous montrons qu'ils engendrent la variete des retractes absolus. Comme sous produit nous obtenons une description de la variete des graphes reflexifs non necessairement symetriques, semblable a celle obtenue par r. Nowakowski et i. Rival, et independamment par a. Quilliot, dans le cas symetrique. La description des finiment indecomposables fait appel a une description des ideaux de mots sur un alphabet ordonne. Nous montrons que tout ideal de mots est un produit fini d'ideaux de mots sur un alphabet ordonne. Nous montrons que tout ideal de mots est un produit fini d'ideaux de la forme j union le mot vide avec j ideal de a ou de la forme i* avec i section initiale de a si et seulement si l'alphabet est belordonne. Ce resultat avait ete obtenu par p. Jullien 4 dans le cas ou l'alphabet est une antichaine finie

Il s'agit d'une contribution dans le domaine de la géométrie métrique du plan projectif complexe CP2 et de la variété de Grassmann réelle des plans dans R6. On s'intéresse à l'étude de tous les p-uplets, p ≥ 3, de droites équiangulaires dans C3 et des p-uplets de plans équi-isoclins dans R6. Sachant que 9 est le nombre maximum de droites équiangulaires que l'on peut construire dans C3, on décrit une méthode qui permet de construire tous les p-uplets de droites équiangulaires pour tout pϵ[3,9]. En particulier, on construit dans C3 cinq classes de congruence de quadruplets de droites équiangulaires dont une dépend d'un paramètre réel ɣ que l'on étend à une famille infinie de sextuplets de droites équiangulaires dépendant du même paramètre réel ɣ. En outre, on donne les angles pour lesquels nos sextuplets s'étendent au-delà et jusqu'aux 9-uplets. On sait qu'il existe un p-uplet, p≥3, de plans équi-isoclins engendrant Rr, r≥4, de paramètre c, 0
This work contributes to the field of metric geometry of the complex projective plane CP2 and the real Grassmannian manifold of the planes in R6. More specifically, we study all p-tuples, p ≥ 3, of equiangular lines in C3 or equidistant points in CP2, and p-tuples of equi-isoclinic planes in R6. Knowing that 9 is the maximum number of equiangular lines that can be constructed in C3, we develop a method to obtain all p-tuples of equiangular lines for all p ϵ [3,9]. In particular, we construct in C3 five congruence classes of quadruples of equiangular lines, one of which depends on a real parameter ɣ, which we extend to an infinite family of sextuples of equiangular lines depending on the same real parameter ɣ. In addition, we give the angles for which our sextuples extend beyond and up to 9-tuples. We know that there exists a p-tuple, p ≥ 3, of equi-isoclinic planes generating Rr, r ≥ 4, with parameter c, 0< c <1, if and only if there exists a square symmetric matrix, called Seidel matrix, of p × p square blocks of order 2, whose diagonal blocks are all zero and the others are orthogonal matrices in O(2) and whose smallest eigenvalue is equal to - 1/c and has multiplicity 2p-r. In this thesis, we investigate the case r=6 and we also show that we can explicitly determine the spectrum of all Seidel matrices of order 2p, p ≥ 3 whose off-diagonal blocks are in {R0, S0} where R0 and S0 are respectively the zero-angle rotation and the zero-angle symmetry. We thus show an unexpected link between some p-tuples of equi-isoclinic planes in Rr and simple graphs of order p

Le problème du médian est un des problèmes les plus étudiés en théorie des espaces métriques. Nous l'étudions dans les graphes médians d'un point de vue algorithmique. Nous présentons un algorithme linéaire basé sur un calcul rapide des classes de parallélisme des arêtes (les Thêta-classes) via un parcours en largeur particulier (LexBFS). Nous donnons également un algorithme linéaire pour le problème du médian dans les l1-complexes cubiques des graphes médians et dans les structures d'évènements.Ensuite, nous présentons une caractérisation des graphes aux médians connexes dans la p-ième puissance Gp du graphe et donnons une méthode polynomiale pour vérifier si un graphe est un graphe aux médians Gp-connexes, étendant un résultat de Bandelt et Chepoi (cas p=1). Nous utilisons cette caractérisation pour montrer que certaines classes de graphes sont G2-connexes, comme les graphes de Helly bipartis et les graphes pontés. Nous travaillons également sur l'aspect axiomatique en étudiant l'ABC-problème, qui consiste à déterminer les graphes (nommés ABC-graphes) dans lesquels la fonction médian est l'unique fonction consensus respectant trois axiomes simples (A) Anonymat, (B) Intervalle (Betweeness) et (C) Cohérence. Nous montrons que les graphes modulaires aux médians G2-connexes sont des ABC-graphes et définissons de nouveaux axiomes pour caractériser la fonction médian dans d'autres classes de graphes, comme les graphes aux médians connexes. Nous prouvons également que les graphes respectant la propriété d'appariement (qui sont des ABC-graphes) est une sous-classe propre des graphes de Helly bipartis et étudions la complexité de la reconnaissance de ces graphes
The median problem is one of the most investigated problem in metric graph theory. We will start by studying this problem in median graphs. We present a linear time algorithm based on the majority rule which characterize the median in median graphs and on a fast computation of the parallelism classes of the edges (the \Theta-classes) via LexBFS which is a particular breadth first search algorithm.We also provide linear time algorithms to compute the median set in the l_1-cube complexes of median graphs and in event structures. Then, we provide a characterization of the graphs with connected medians in the pth power of the graph and provide a polynomial method to check if a graph is a G^p-connected median graph, extending a result of Bandelt and Chepoi (case p=1). We use this characterization to prove that some important graph classes in metric graph theory have G2-connected medians, such as bipartite Helly graphs and bridged graphs. We will also studied the axiomatic aspect of the median function by investigating the ABC-problem, which determine the graphs (named ABC-graphs) in which the median function is the only consensus function verifying three simples axioms (A) Anonymat, (B) Betweeness and (C) Consistency. We show that modular graphs with G2-connected medians are ABC-graphs and define new axioms allowing us to characterize the median function on some graph classes. For example the graphs with connected medians (including Helly graphs). We also show that a known class of ABC-graphs (graphs satisfying the pairing property) is a proper subclass of bipartite Helly graphs and we investigate their recognition

Nous étudions les propriétés métriques locales des ensembles de niveau des applicationshorizontalement différentiables entre des groupes de Carnot, c'est-à-dire différentiable par rapport à la structure sous-riemannienne intrinsèque.Nous considérons des applications dont la différentielle horizontale est surjective,et notre étude peut être vue comme une généralisation du théorème des fonctions implicites pour les groupes de Carnot.Tout d'abord, nous présentons deux notions de tangence dans les groupes de Carnot:la première basée sur la condition de platitude au sens de Reifenberg et la deuxième issue de l'analyse convexe classique.Nous montrons que dans les deux cas, l'espace tangent à un ensemble de niveau coïncide avec le noyau de la différentielle horizontale.Nous montrons que cette condition de tangence caractérise en fait les ensembles de niveaudits ‘co-abéliens', c'est-à-dire ceux pour lesquels l'espace d'arrivée est abélien, et qu'une telle caractérisation n'est pas vraie en général.Ce résultat sur les espaces tangents a plusieurs conséquences remarquables.La plus importante est que la dimension de Hausdorff des ensembles de niveau est celle à laquelle l'on s'attend.Nous montrons également la connectivité locale des ensembles de niveau, et le fait que les ensembles de niveau de dimension 1 sont topologiquement des arcs simples.Pour les ensembles de niveau de dimension 1 nous trouvons une formule de l'aire qui permet d'exprimer la mesure de Hausdorff en termes d'intégrales de Stieltjes généralisées.Ensuite, nous menons une étude approfondie du cas particulier des ensembles de niveau dans les groupes d'Heisenberg.Nous montrons que les ensembles de niveau sont topologiquement équivalents à leurs espaces tangents.Il s'avère que la mesure de Hausdorff des ensembles de niveau de codimension élevée est souvent irrégulière, étant, par exemple, localement nulle ou infinie.Nous présentons une condition simple de régularité supplémentaire pour une application pour assurer la régularité au sens d'Ahlfors des ses ensembles de niveau.Parmi d'autres résultats, nous obtenons une nouvelle caractérisation généraledes graphes Lipschitziens associés à une décomposition en produit semi-direct d'un groupe de Carnot.Nous traitons, en particulier, le cas des groupes de Carnot dont le nombre de stratesest plus grand que $2$.Cette caractérisation nous permet de déduire une nouvelle caractérisation des ensemblesde niveau co-abéliens qui admettent une représentation en tant que graphe
Metric properties of level sets of differentiable maps on Carnot groupsAbstract.We investigate the local metric properties of level sets of mappings defined between Carnot groups that are horizontally differentiable, i.e.with respect to the intrinsic sub-Riemannian structure. We focus on level sets of mapping having a surjective differential,thus, our study can be seen as an extension of implicit function theorem for Carnot groups.First, we present two notions of tangency in Carnot groups: one based on Reifenberg's flatness condition and another coming from classical convex analysis.We show that for both notions, the tangents to level sets coincide with the kernels of horizontal differentials.Furthermore, we show that this kind of tangency characterizes the level sets called ``co-abelian'', i.e.for which the target space is abelian andthat such a characterization may fail in general.This tangency result has several remarkable consequences.The most important one is that the Hausdorff dimension of the level sets is the expected one. We also show the local connectivity of level sets and, the fact that level sets of dimension one are topologically simple arcs.Again for dimension one level set, we find an area formula that enables us to compute the Hausdorff measurein terms of generalized Stieltjes integrals.Next, we study deeply a particular case of level sets in Heisenberg groups. We show that the level sets in this case are topologically equivalent to their tangents.It turns out that the Hausdorff measure of high-codimensional level sets behaves wildly, for instance, it may be zero or infinite.We provide a simple sufficient extra regularity condition on mappings that insures Ahlfors regularity of level sets.Among other results, we obtain a new general characterization of Lipschitz graphs associated witha semi-direct splitting of a Carnot group of arbitrary step.We use this characterization to derive a new characterization of co-ablian level sets that can be represented as graphs

Dans cette thèse, nous étudions l'interpolation réelle des espaces de Sobolev et ses applications. Le manuscrit est constitué de deux parties. Dans la première partie, nous démontrons au premier chapitre que les espaces de Sobolev non homogènes W^1_p (resp. homogènes ) sur les variétés Riemanniennes complètes vérifiant la propriété de doublement et une inégalité de Poincaré forment une échelle d'interpolation réelle pour un intervalle de valeurs de p. Nous étendons ce résultat à d'autres cadres géométriques. Dans un deuxième court chapitre, nous comparons différents espaces de Sobolev sur le cone Euclidien et nous regardons le lien de ces espaces avec l'interpolation. Nous montrons sur cet exemple que l'hypothèse de Poincaré n'est pas une condition nécessaire pour pouvoir interpoler les espaces de Sobolev. Dans le dernier chapitre de cette partie, nous définissons les espaces de Sobolev non homog'nes W^1_p,V (resp. homogènes ) associés à un potentiel positif V sur une variété Riemannienne. Nous démontrons que si la variété véifie la propriété de doublement et une inégalité de Poincaré et si de plus V est dans une classe de Holder inverse, ces espaces forment aussi une échelle d'interpolation réelle pour un intervalle de valeurs de p. Nous étendons ce résultat aux cas des groupes de Lie. Dans la deuxième partie, dans un premier chapitre en collaboration avec E. Russ, nous étudions sur un graphe vérifiant la propriété de doublement et une inégalité de Poincaré, la Lp bornitude de la transformée de Riesz pour p > 2 et son inégalité inverse pour p < 2. Pour notre but, nous démontrons aussi des résultats d'interpolation des espaces de Sobolev et des inégalités de Littlewood-Paley. Dans le deuxième chapitre, nous démontrons en utilisant notre résultat d'interpolation, des inégalités de Gagliardo-Nirenberg sur les variétés Riemanniennes complètes vérifiant le doublement, des inégalités de Poincaré et pseudo-Poincaré. Ce résultat s'applique aussi dans le cadre des groupes de Lie et des graphes.

La propriété de résilience a tout d'abord commencé à être étudiée dans les domaines de l'écologie et de la psychologie avant d'intéresser chercheurs en économie, anthropologie, infrastructure civile et plus récemment en informatique et technologies de l'information. La résilience concerne originellement la survie et l'adaptation d'une population à des changements mais il en va différemment dans le cas d'infrastructures pour lesquelles la survie peut ne pas être considérée comme un objectif final mais davantage comme un moyen d'atteindre un autre but : fournir des biens ou des services. La protection de ces infrastructures reste tout de même indispensable et a longtemps été accomplie uniquement en respect des paradigmes que sont la sûreté et la sûreté de fonctionnement. Cependant, ces approches nécessitent une connaissance détaillée des événements redoutés qui peuvent affecter les systèmes. Or plusieurs événements tels que l'accident de la centrale nucléaire de Fukushima ou des cyber-attaques comme StuxNet et BlackEnergy ont mis en avant plusieurs faiblesses de ces paradigmes. Des recherches sont donc menées sur la résilience des systèmes afin de parer à ces faiblesses. Les travaux présentés dans cette thèse proposent un nouveau modèle permettant d’évaluer la résilience d’un système en n’ayant à détailler que les composants qui qui le composent ainsi que leurs interactions alors que les précédents modèles d’évaluation se concentraient sur la description des menaces et de leurs impacts sur le système
The property of resilience began to be studied in the fields of ecology and psychology before becoming of interest to researchers in economics, anthropology, civil infrastructure and more recently in computer science and information technology. Resilience is originally concerned with the survival and adaptation of a population to changes, but the case of infrastructures is different as survival may not be considered as an end goal but rather as a mean to another end: providing goods or services. Nevertheless, the protection of such infrastructures remains necessary and has long been accomplished in accordance with the paradigms of safety and dependability. However, these approaches require a detailed knowledge of the feared events that may affect the systems. Several events such as the accident at the Fukushima nuclear power plant or cyber-attacks such as StuxNet and BlackEnergy have highlighted several weaknesses in these paradigms.Research is therefore being conducted on the resilience of systems to address these weaknesses. The work presented in this thesis proposes a new model for assessing the resilience of a system by only having to detail its components and their relationships, whereas previous evaluation models focused on describing the threats and their impacts on the system

On montre, en utilisant des arguments relativement élémentaires, que les prolongements quasi-isométriques de l'espace euclidien "En" dans lui-même sont quasi-surjectifs, et que toute quasi-isométrie de "T x En" dans lui-même (où T est un arbre métrique localement fini) induit une quasi-isométrie de T. On généralise ensuite ces résultats au cas où "En" est remplacé par une variété ouverte "PL" munie d'une métrique uniformément contractile. Enfin, on obtient des résultats concernant les quasi-isométries de certains autres espaces métriques homéomorphes à "T x En", ce qui inclut le cas des groupes de Baumslag-Solitar.

Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets
A distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs

Le développement d'infrastructures linéaires de transport conduit, à toutes les échelles, à une artificialisation du territoire et au morcellement du milieu naturel. La fragmentation du paysage est un processus spatial qui s'accompagne d'une diminution progressive de la connectivité entre les différents éléments nécessaires au bon déroulement des processus écologiques. Ainsi, le maintien d'un bon niveau de connectivité entre les habitats naturels, s'il est compatible avec les activités humaines, est devenu un enjeu majeur pour la préservation de la biodiversité. En mobilisant des méthodes empruntées à la théorie des graphes et à l'écologie du paysage, la thèse cherche à démontrer l'intérêt de la modélisation des réseaux écologiques par les graphes paysagers, dans l'analyse des impacts des infrastructures à l'échelle régionale. Cette démarche, fondée sur la modélisation, a permis de démontrer l'influence du réseau écologique du chevreuil dans la localisation des collisions entre les individus de cette espèce et les véhicules empruntant le réseau de la DIR est en Franche-Comté. Le travail a également permis de proposer un cadre méthodologique pour localiser l'impact potentiel de la branche est de la LGV Rhin-Rhône sur la distribution d'une espèce, et estimer la distance de perturbation de cette infrastructure. Enfin, deux démarches sont proposées pour évaluer quantitativement et hiérarchiser des aménagements afin d'éviter ou d'atténuer ces impacts. Les résultats montrent la pertinence de l'intégration des réseaux écologiques dans les études d'impacts des infrastructures de transport.

Dans cette thèse nous étudions les transformées de Riesz et les espaces de Hardy associés à un opérateur sur un espace métrique mesuré. Ces deux sujets sont en lien avec des estimations du noyau de la chaleur associé à cet opérateur. Dans les Chapitres 1, 2 et 4, on étudie les transformées quasi de Riesz sur les variétés riemannienne et sur les graphes. Dans le Chapitre 1, on prouve que les quasi transformées de Riesz sont bornées dans Lp pour 1

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

Cette thèse est consacrée à l'étude de quelques propriétés mathématiques de deux modèles de population : le processus Fleming-Viot généralisé d'une part et le processus de branchement d'autre part. Dans les deux cas, la population est composée d'une infinité d'individus, chacun étant caractérisé par un type génétique. Au cours du temps les fréquences asymptotiques de ces types évoluent de façon aléatoire au travers d'événements de reproduction où un individu tiré aléatoirement donne naissance à une descendance portant le même type génétique. Mathématiquement ces deux modèles sont décrits par des processus aléatoires à valeurs mesures. Afin de donner un sens à la généalogie de la population sous-jacente, plusieurs approches ont été proposées au cours des quinze dernières années. La contribution principale de cette thèse consiste en l'unification de deux constructions : la représentation lookdown définie par Peter Donnelly et Thomas Kurtz en 1999 et les flots stochastiques de ponts (ou de subordinateurs) introduits au début des années 2000 par Jean Bertoin et Jean-François Le Gall. Cette unification nécessite l'introduction d'objets nouveaux (les Eves, les flots stochastiques de partitions) et repose sur une étude fine des comportements asymptotiques des deux modèles mentionnés précédemment. En particulier, nous définissons la propriété d'Eve comme suit : si la fréquence asymptotique d'un type génétique tend vers $1$ lorsque $t$ devient grand alors la population descend asymptotiquement d'un seul individu au temps initial, appelé l'Eve de la population. Dans le cas des processus de branchement nous obtenons une condition nécessaire et suffisante sur le paramètre du modèle (aussi appelé mécanisme de branchement) qui assure que cette propriété d'Eve est vérifiée. Nous obtenons également une classification complète de tous les autres comportements possibles. Dans le cas des processus Fleming-Viot généralisés, nous obtenons une classification partielle des comportements possibles en fonction du paramètre du modèle. Enfin, lorsque la propriété d'Eve est vérifiée, nous construisons de façon trajectorielle la représentation lookdown à partir d'un flot stochastique de ponts (ou de subordinateurs). Nous présentons également une étude complète du processus de branchement explosif conditionné à la non-explosion et faisons apparaître une famille infinie de mesures quasi-stationnaires pour ce processus. Finalement nous nous intéressons au processus des longueurs du coalescent de Kingman dynamique et présentons une construction alternative à celle de Pfaffelhuber, Wakolbinger et Weisshaupt.

La Science des réseaux est apparue comme un domaine d'étude fondamental pour modéliser un grand nombre de systèmes synthétiques ou du monde réel.La découverte du graphe petit monde et du graphe sans échelle dans ces réseaux a révolutionné la façon d'étudier, d'analyser, de modéliser et de traiter ces réseaux. Dans cette thèse, nous nous intéressons à l'étude des réseaux ayant ces propriétés et souvent qualifiés de réseaux complexes.A notre avis, les recherches menées dans ce domaine peuvent être regroupées en quatre catégories: l'analyse, la structure, le processus/organisation et la visualisation.Nous abordons des problèmes relatifs à chacune de ces catégories tout au long de cette thèse. (...)
Network science has emerged as a fundamental field of study to model many physicaland real world systems around us. The discovery of small world and scale free propertiesof these real world networks has revolutionized the way we study, analyze, model andprocess these networks. In this thesis, we are interested in the study of networks havingthese properties often termed as complex networks. In our opinion, research conducted inthis field can be grouped into four categories, Analysis, Structure, Processes-Organizationand Visualization. We address problems pertaining to each of these categories throughoutthis thesis. (...)

La Science des Réseaux est apparue comme un domaine d'étude fondamental pour modéliser un grand nombre de systèmes synthetiques ou du monde réel. La découverte du graphe petit monde et du graphe sans échelle dans ces réseaux a révolutionné la façon d'étudier, d'analyser, de modéliser et de traiter ces réseaux. Dans cette thèse, nous nous intéressons à l'étude des réseaux ayant ces propriétés et souvent qualifiés de réseaux complexes. À notre avis, les recherches menées dans ce domaine peuvent être regroupées en quatre catégories: l'analyse, la structure, le processus/organisation et la visualisation. Nous abordons des problèmes relatifs à chacune de ces catégories tout au long de cette thèse. Les premiers chapitres introduisent l'état de l'art nécessaire aux lecteurs. Les chapitres 3,4,5,6 et 7 abordent chacun un problème spécifique auquel nous proposons une solution. Dans le chapitre 3, nous présentons une méthode de visualisation analytique pour analyser les réseaux complexes. En s'appuyant sur cette méthode, nous introduisons une nouvelle métrique pour déterminer la présence de sommets largement connectés. Nous détaillons dans le chapitre 4 un ensemble de modèles pour générer des réseaux artificiels ayant les propriétés petit monde et sans échelle. Nous proposons un nouveau modèle générant des réseaux de ce type et qui contiennent, de plus, des structures communautaires. En extension des résultats d'analyse obtenus au chapitre 3, nous introduisons un algorithme de clustering agglomératif dans le chapitre 5. Dans le chapitre 6, nous abordons la question de la visualisation de ces réseaux complexes grâce à un système qui combine simplification et clustering avec des algorithmes de mise en page dédiée. Nous abordons enfin dans le chapitre 7 la question de l'évaluation de la qualité des clusters pour les réseaux complexes qui n'ont pas de sommets largement connectés. Nous concluons chaque chapitre par des perspectives de recherches dédiées. Enfin, nous résumons nos résultats et concluons cette thèse en proposant quelques futurs axes de recherches basés sur nos découvertes.

Le paysage constitue à la fois un cadre de vie pour les populations humaines et un support du cycle de vie des espèces animales. Les modifications du paysage induites par les dynamiques d’occupation du sol se répercutent sur ces deux dimensions, l’une esthétique et l’autre écologique. Ces logiques étant généralement étudiées dans des champs disciplinaires différents, peu de recherches ont porté sur la manière dont elles s’articulent selon les modifications des structures paysagères.Ce travail cherche donc à modéliser de manière rétrospective la coévolution spatiale des fonctions esthétique et écologique du paysage à partir de métriques spatiales basées sur des données d’occupation du sol. Il se focalise sur les changements intervenus dans les franges urbaines de deux agglomérations françaises (Besançon et Paris) durant les 30 dernières années.La démarche adoptée a d’abord visé à modéliser, à partir des données d’occupation du sol, (1)les préférences paysagères d’un ensemble d’individus et (2) la connectivité écologique pour un ensemble d’espèces animales. En mobilisant de manière complémentaire des analyses statistiques multivariées et des analyses spatiales, le cœur du travail a ensuite consisté à étudier comment ces deux fonctions ont évolué de manière convergente ou divergente au cours du temps. Les résultats donnent de nouveaux éléments de compréhension des relations entre esthétique et écologie du paysage et amènent à s’interroger sur l’intérêt de la modélisation spatiale pour une gestion du paysage conciliant la préservation du cadre de vie des habitants et la conservation de la biodiversité
Landscape is both a backdrop to the lives of human populations and a medium for the life cycle of animal species. Landscape changes induced by land-use and land-cover dynamics affect both these dimensions, the one aesthetic, and the other ecological. Because these rationales areusually studied within different disciplines, little research has been done into how the two clashor combine as and when landscape structures change. This work seeks therefore to model the spatial co-evolution of the aesthetic and ecological functions of landscape retrospectively usingspatial metrics based on land-cover data. It focuses on changes in the urban fringes of two French cities (Paris and Besançon) over the last 30 years. The approach attempts first to use land-cover data to model (1) the landscape preferences of a set of individuals and (2) the ecological connectivity of a set of animal species. Drawing on both multivariate statistical analysis and spatial analysis, the core of this work consists in investigating how the two functions have evolved in convergent or divergent ways over time. The results provide fresh insight into the relationship between landscape aesthetics and landscape ecology and raise questions about the value of spatial modelling for a landscape management approach that endeavours to reconcile the preservation of residents’ living environments and the conservationof biodiversity

Au cours de ce travail, nous nous intéressons aux limites d'échelle de deux classes de cartes. Dans un premier temps, nous regardons les quadrangulations biparties de genre strictement positif g fixé et, dans un second temps, les quadrangulations planaires à bord dont la longueur du bord est de l'ordre de la racine carrée du nombre de faces. Nous voyons ces objets comme des espaces métriques, en munissant leurs ensembles de sommets de la distance de graphe, convenablement renormalisée. Nous montrons qu'une carte prise uniformément parmi les cartes ayant n faces dans l'une de ces deux classes tend en loi, au moins à extraction près, vers un espace métrique limite aléatoire lorsque n tend vers l'infini. Cette convergence s'entend au sens de la topologie de Gromov--Hausdorff. On dispose de plus des informations suivantes sur l'espace limite que l'on obtient. Dans le premier cas, c'est presque sûrement un espace de dimension de Hausdorff 4 homéomorphe à la surface de genre g. Dans le second cas, c'est presque sûrement un espace de dimension 4 avec une frontière de dimension 2, homéomorphe au disque unité de R^2. Nous montrons en outre que, dans le second cas, si la longueur du bord est un petit~o de la racine carrée du nombre de faces, on obtient la même limite que pour les quadrangulations sans bord, c'est-à-dire la carte brownienne, et l'extraction n'est plus requise.

Les travaux de ma thèse s'articulent en trois parties distinctes.Dans la première partie j'étudie les mesures de Malliavin-Shavguldize sur les difféomorphismes du cercle et de l'intervalle. Il s'agit de mesures de type " Haar " pour ces groupes de dimension infinie : elles furent introduites il a une vingtaine d'années pour permettre une étude de leur théorie des représentations. Un premier chapitre est dédié à recueillir les résultats présents dans la littérature et et les représenter dans une forme plus étendue, avec un regard particulier sur les propriétés de quasi-invariance de ces mesures. Ensuite j'étudie de problèmes de nature plus dynamique : quelle est la dynamique qu'on doit s'attendre d'un difféomorphisme choisi uniformément par rapport à une mesure de Malliavin-Shavguldize ? Je démontre en particulier qu'il y a une forte présence des difféomorphismes de type Morse-Smale.La partie suivante vient de mon premier travail publié, obtenu en collaboration avec Andrés Navas. Inspirés d'un théorème récent de Avila et Kocsard sur l'unicité des distributions invariantes par un difféomorphisme lisse minimal du cercle, nous analysons le même problème en régularité faible, avec des argument plus géométriques.La dernière partie est constituée des résultats récemment obtenus avec Mikhail Khristoforov et Victor Kleptsyn. Nous abordons les problèmes reliés à la gravité quantique de Liouville en étudiant des espaces auto-similaires qui sont la limite de graphes finis. Nous démontrons qu'il est possible de trouver des distances aléatoires non-triviales sur ces espaces qui sont compatibles avec la structure auto-similaire.