Auswahl der wissenschaftlichen Literatur zum Thema „Graphe ordonné“

Résumé À travers Mark Twain et les Hawai’i, ce texte propose d’analyser les relations entre images littéraires et géographicité. La littérature pourrait bien constituer une puissante machine à fabriquer de la différenciation spatiale, en tant qu’elle convertit l’étendue terrestre en signes, en lieux qui accèdent à la signification par l’imaginaire, lequel peut prendre la forme de l’écriture. Celle-ci ordonne le monde et donne en retour prise pour le transformer. Si Mark Twain a prolongé ainsi certaines images fabriquées par les découvreurs, il en a fourni aussi de nouvelles qui sont venues compliquer le palimpseste mettant en désir les Hawai’i dans l’imaginaire américain. À travers le monde subjectif de l’écrivain et les figures de l’altérité qu’il met en scène, l’utopie hawaiienne peut être lue comme un espace dont l’idéalisation rend possible le développement d’une catharsis.

International audience This paper discusses a surprising relationship between the quantum cohomology of the variety of complete flags and the partially ordered set of Newton polygons associated to an element in the affine Weyl group. One primary key to establishing this connection is the fact that paths in the quantum Bruhat graph, which is a weighted directed graph with vertices indexed by elements in the finite Weyl group, encode saturated chains in the strong Bruhat order on the affine Weyl group. This correspondence is also fundamental in the work of Lam and Shimozono establishing Peterson's isomorphism between the quantum cohomology of the finite flag variety and the homology of the affine Grassmannian. In addition, using some geometry associated to the poset of Newton polygons, one obtains independent proofs for several combinatorial statements about paths in the quantum Bruhat graph and its symmetries, which were originally proved by Postnikov using the tilted Bruhat order. An important geometric application of this work is an inequality which provides a necessary condition for non-emptiness of certain affine Deligne-Lusztig varieties in the affine flag variety. Cet article étudie une relation surprenante entre la cohomologie quantique de la variété de drapeaux complets et l'ensemble partiellement ordonné de polygones de Newton associé à un élément du groupe de Weyl affine. L’élément clé pour établir cette connexion est le fait que les chemins dans le graphe de Bruhat quantique, qui est un graphe orienté pondéré dont les sommets sont indexés par des éléments du groupe de Weyl fini, encodent des chaînes saturées dans l'ordre de Bruhat fort sur le groupe de Weyl affine. Cette correspondance est aussi fondamentale dans les travaux de Lam et Shimonozo qui établissent l'isomorphisme de Peterson entre la cohomologie quantique de la variété de drapeaux finie et l'homologie de la Grassmannienne affine. De plus, en utilisant la géométrie associée à l'ensemble partiellement ordonné des polygones de Newton, on obtient des preuves indépendantes pour plusieurs assertions combinatoires sur les chemins dans le graphe de Bruhat quantiques et les symétries de ce graphe, qui ont été originellement démontrées par Postnikov en utilisant l'ordre de Bruhat incliné. Une application géométrique importante de ce travail est une inégalité qui donne une condition nécessaire pour que certaines variétés de Deligne-Lusztig affines dans la variété de drapeaux affine soient non-vides.

We present a uniform construction of tensor products of one-column Kirillov–Reshetikhin (KR) crystals in all untwisted affine types, which uses a generalization of the Lakshmibai–Seshadri paths (in the theory of the Littelmann path model). This generalization is based on the graph on parabolic cosets of a Weyl group known as the parabolic quantum Bruhat graph. A related model is the so-called quantum alcove model. The proof is based on two lifts of the parabolic quantum Bruhat graph: to the Bruhat order on the affine Weyl group and to Littelmann's poset on level-zero weights. Our construction leads to a simple calculation of the energy function. It also implies the equality between a Macdonald polynomial specialized at $t=0$ and the graded character of a tensor product of KR modules. Nous présentons une construction uniforme pour les produits tensoriels des cristaux de Kirillov–Reshetikhin de type colonne, pour tous les types affines symétriques, qui utilise une généralisation des chemins de Lakshmibai–Seshadri (dans la théorie des chemins de Littelmann). Cette généralisation est basée sur un graphe sur les classes paraboliques d’un groupe de Weyl appelé le graphe de Bruhat parabolique quantique. Un modèle lié est le modèle des alcôves quantiques. La preuve est basée sur deux relèvements du graphe de Bruhat parabolique quantique : dansl’ordre de Bruhat affine et dans un ensemble ordonné des poids de niveau zéro. Notre construction donne une formule simple pour la fonction d’énergie. Elle donne aussi l’égalité d’un polynôme de Macdonald spécialisé à $t=0$ avec le caractère gradué d’un produit tensoriel des modules de Kirillov–Reshetikhin.

International audience The Bruhat order gives a poset structure to any Coxeter group. The ideal of elements in this poset having boolean principal order ideals forms a simplicial poset. This simplicial poset defines the boolean complex for the group. In a Coxeter system of rank n, we show that the boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of these spheres is the boolean number, which can be computed inductively from the unlabeled Coxeter system, thus defining a graph invariant. For certain families of graphs, the boolean numbers have intriguing combinatorial properties. This work involves joint efforts with Claesson, Kitaev, and Ragnarsson. \par L'ordre de Bruhat munit tout groupe de Coxeter d'une structure de poset. L'idéal composé des éléments de ce poset engendrant des idéaux principaux ordonnés booléens, forme un poset simplicial. Ce poset simplicial définit le complexe booléen pour le groupe. Dans un système de Coxeter de rang n, nous montrons que le complexe booléen est homotopiquement équivalent à un bouquet de sphères de dimension (n-1). Le nombre de ces sphères est le nombre booléen, qui peut être calculé inductivement à partir du système de Coxeter non-étiquetté; définissant ainsi un invariant de graphe. Pour certaines familles de graphes, les nombres booléens satisfont des propriétés combinatoires intriguantes. Ce travail est une collaboration entre Claesson, Kitaev, et Ragnarsson.

International audience We show that maximal 0-1-fillings of moon polynomials, with restricted chain lengths, can be identified with certain rc-graphs, also known as pipe dreams. In particular, this exhibits a connection between maximal 0-1-fillings of Ferrers shapes and Schubert polynomials. Moreover, it entails a bijective proof showing that the number of maximal fillings of a stack polyomino $S$ with no north-east chains longer than $k$ depends only on $k$ and the multiset of column heights of $S$. Our main contribution is a slightly stronger theorem, which in turn leads us to conjecture that the poset of rc-graphs with covering relation given by generalised chute moves is in fact a lattice. Nous démontrons que les remplissages maximaux avec 0 et 1 des polyominos $L$-convexes, avec longueurs de chaînes restreintes, peuvent être identifiés avec certains $\textit{rc-graphes}$, également connus sous le nom de $\textit{pipe dreams}$. En particulier, ceci montre un lien entre ces remplissages d'un diagramme de Ferrers et les polynômes de Schubert. On en déduit en outre une preuve bijective du fait que le nombre de remplissages maximaux d'un $\textit{stack polyomino}$ $S$, avec longueurs de chaînes bornées par un entier $k$, dépend seulement de $k$ et du multi-ensemble des tailles des colonnes de $S$. Notre contribution principale est un énoncé un peu plus fort, qui nous mène à conjecturer que l'ensemble ordonné (poset) des $\textit{rc-graphes}$ est en fait un treillis.

$\textit{Adinkras}$ are graphical tools created for the study of supersymmetry representations. Besides having inherent interest for physicists, the study of adinkras has already shown connections with coding theory and Clifford algebras. Furthermore, adinkras offer many natural and accessible mathematical problems of combinatorial nature. We present the foundations for a mathematical audience, make new connections to other fields (homological algebra, poset theory, and polytopes), and solve some of these problems. Original results include the enumeration of all hypercube adinkras through dimension 5, the enumeration of odd dashings of adinkras for any dimension, and a connection between rankings and the chromatic polynomial for certain graphs. Les $\textit{adinkras}$ sont des dessins qui sont utilisés pour étudier les représentations des théories supersymétriques. Outre leur intérêt en physique, les adinkras sont aussi utiles en connexion avec la théorie des codes et les algèbres de Clifford. De plus, les adinkras offrent beaucoup de problèmes de nature combinatoire qui sont à la fois naturels et accessibles. Nous présentons une introduction pour une audience de mathématiciens, présentons de nouvelles connexions avec d’autres domaines (algèbres homologiques, ensembles partiellement ordonnés, polytopes), et résolvons certains problèmes. Parmi les résultats nouveaux, nous énumérons les adinkras de l’hypercube de dimension inférieure ou égale à 5, nous énumérons les $\textit{odd dashings}$ en toute dimension, et établissons une relation entre les $\textit{rankings}$ et le polynôme chromatique pour certains graphes.

International audience The structure of zero and nonzero minors in the Grassmannian leads to rich combinatorics of matroids. In this paper, we investigate an even richer structure of possible equalities and inequalities between the minors in the positive Grassmannian. It was previously shown that arrangements of equal minors of largest value are in bijection with the simplices in a certain triangulation of the hypersimplex that was studied by Stanley, Sturmfels, Lam and Postnikov. Here we investigate the entire set of arrangements and its relations with this triangulation. First, we show that second largest minors correspond to the facets of the simplices. We then introduce the notion of cubical distance on the dual graph of the triangulation, and study its relations with the arrangement of t-th largest minors. Finally, we show that arrangements of largest minors induce a structure of partially ordered sets on the entire collection of minors. We use the Lam and Postnikov circuit triangulation of the hypersimplex to describe a 2-dimensional grid structure of this poset. La structure des mineurs nuls et non nuls dans la Grassmannienne amène à une combinatoire très riche dematroïdes. Dans cet article, nous examinons la structure encore plus riche des égalités et inégalités possibles entreles mineurs de la Grassmannienne positive. Il a été montré précédemment que les arrangements de mineurs égauxde valeur maximale sont en bijection avec les simplexes d’une certaine triangulation de l’hypersimplexe étudiée parStanley, Sturmfels, Lam et Postnikov. Nous examinons ici l’ensemble total des arrangements et ses relations aveccette triangulation. Tout d’abord, nous montrons que les deuxièmes plus grands mineurs correspondent aux facettesdes simplexes. Nous introduisons ensuite la notion de distance cubique sur le graphe dual de la triangulation, et nousétudions ses relations avec l’arrangement des t-ièmes plus grands mineurs. Enfin, nous montrons que les arrangementsde mineurs maximaux induisent une structure d’ensemble partiellement ordonn´e sur la collection totale des mineurs.Nous utilisons la triangulation-circuit de Lam et Postnikov de l’hypersimplexe pour décrire une structure de réseau2-dimensionnel sur ce poset.

On introduit une nouvelle structure algébrique qui formalise bien les problèmes de reconstruction, assortie d'une conjecture qui permettrait de traiter directement des symétries. Le cadre fournit par cette étude permet de plus d'engendrer des relations qui ont lieu entre les nombres de sous-structures, et d'une certaine façon, la conjecture formulée affirme qu'on les obtient toutes. De plus, la généralisation des résultats précédemment obtenus pour la reconstruction permet de chercher 'a en apprécier les limites en recherchant des cas où ces relations sont optimales. Ainsi, on montre que les théorèmes de V.Müller et de L.Lovasz sont les meilleurs possibles en exhibant des cas limites. Cette généralisation aux algèbres d'invariants, déjà effectuée par P.J.Cameron et V.B.Mnukhin, permet de placer les problèmes de reconstruction en tenaille entre d'une part des relations (fournies) que l'on veut exploiter, et des exemples qui établissent l'optimalité du résultat. Ainsi, sans aucune donnée sur le groupe, le résultat de L.Lovasz est le meilleur possible, et si l'on considère l'ordre du groupe, le résultat de V.Müller est le meilleur possible.

Dans ce travail, nous donnons un cadre général de surfaces riemanniennes qui dégénèrent sur des graphes métriques que nous appelons surfaces décomposables en cylindres et en jonctions. Les surfaces décomposables en cylindres et en jonctions dépendent d’un paramètre t qui traduit le mécanisme d’écrasement sur le graphe. Quand le paramètre t tend vers 0, les circonférences des cylindres tendent vers 0 et leurs longueurs restent fixes. On obtient ainsi les arêtes du graphe limite. Les jonctions, elles, sont écrasées dans toutes les directions et donc dégénèrent sur les sommets du graphe limite. Nous étudions alors le comportement asymptotique du spectre de ces variétés lors de cette déformation. Nous adoptons les points de vue de la convergence des valeurs propres ordonnées et de celle des branches analytiques. Ces deux approches sont fondamentalement différentes. Le cas des valeurs propres ordonnées est assez classique et nous retrouvons la convergence vers le spectre du graphe limite. L’étude des branches analytiques est plus original. Nous montrons la convergence et donnons une caractérisation des limites possibles. Ces résultats s’appliquent dans le cas des surfaces de translations qui possèdent une direction complètement périodique
In this work, we give a general framework of Riemannian surfaces that can degenerate on metric graphs and that we call surfaces made from cylinders and connecting pieces. The latter depend on a parameter t that describes the degeneration. When t goes to 0, the waists of the cylinders go to 0 but their lengths stay fixed. We thus obtain the edges of the limiting graph. The connecting pieces are squeezed in all directions and degenerate on the vertices of the limiting graph. We then study the asymptotic behaviour of the spectrum of these surfaces when t varies from two different points of view, considering the spectrum either as a sequence of ordered eigenvalues or as a collection of analytic eigenbranches. In the case of ordered eigenvalues, we recover a rather classical statement, and prove that the spectrum converges to the spectrum of the limiting object. The study of the analytic eigenbranches is more original. We prove that any such eigenbranch converges and we give a characterisation of the possible limits. These results apply to translation surfaces on which there is a completely periodic direction

Dans cette thèse, nous étudions les régularités dans les graphes et les représentations succinctes des graphes. Une régularité, ou structure, est un terme générique qui désigne un ensemble de sommets du graphe ayant certaines propriétés. Parmi les régularités les plus connues, nous pouvons citer les cliques, les sous-graphes denses, les communautés, les modules et les splits. Une représentation succincte d'un graphe est une façon de le décrire qui est plus efficace que de simplement lister les différentes arêtes du graphe. Chercher des régularités permet d'obtenir des représentations succinctes. Ainsi, dans un premier temps, nous avons développé un algorithme de compression de graphe qui cherche différentes régularités du graphe, en sélectionne une partie et partitionne le graphe en fonction des structures sélectionnées. Cet algorithme donne une description succincte du graphe qui est meilleure que certains algorithmes de référence.Dans un deuxième temps, nous avons créé nos propres structures, de sorte qu'elles soient adaptées à la compression et qu'elles soient assez facile à chercher. Pour ce faire, nous sommes partis d'une structure connue, le split, et nous l'avons généralisée en créant le r-split, où r est un paramètre entier fixé. Nous avons alors montré que l'ensemble des r-splits d'un graphe a une cohérence globale, dans le sens où seul un nombre polynomial d'entre eux suffit à décrire l'intégralité des r-splits du graphe. Cela généralise une propriété bien connue des splits, pour lesquels seul un nombre linéaire d'entre eux suffit à retrouver tous les autres. Nous avons également montré que les r-splits peuvent se calculer en temps polynomial en utilisant des algorithmes d'optimisation de fonctions sous-modulaires.Dans un troisième temps, nous nous sommes intéressés à la recherche de structures particulières : les motifs dans les graphes ordonnés. Un graphe ordonné est un graphe dans lequel les sommets sont ordonnés de 1 à n. Un motif est un sous-graphe ordonné partiel, dans le sens où chaque paire de sommets peut être reliée soit par une arête, soit par une non-arête, soit par ni l'une ni l'autre. Le but est de fixer un motif P et de construire un algorithme capable de détecter si P est dans n'importe quel graphe ordonné donné en paramètre. Ce problème est polynomial en la taille du graphe via une recherche exhaustive. Cependant, est-il possible de faire mieux ? Nous avons montré que oui : la plupart des motifs à trois sommets peuvent être détectés en temps linéaire là où une recherche exhaustive nécessite un temps cubique. Concernant les motifs plus grands, nous avons exhibé des classes de motifs qui peuvent être détectés en temps sous-cubique : les motifs planaires extérieurs. En ajoutant des contraintes supplémentaires, nous avons exhibé une classe de motifs qui peuvent être détectée en temps linéaire : il s'agit des motifs planaires extérieurs sans cycle et sans non-arête
In this thesis, we investigate regularities in graphs and succinct representations of graphs.A regularity, or structure, is a generic term that refers to a set of vertices in a graph with certain properties.Among the most well-known regularities, we can mention cliques, dense subgraphs, communities, modules, and splits.A succinct representation of a graph is a way of describing it that is more efficient than simply listing the different edges of the graph.Searching for regularities enables obtaining succinct representations.Thus, in a first step, we developed a graph compression algorithm that searches for different graph regularities, selects a portion of them, and partitions the graph based on the selected structures.This algorithm provides a succinct description of the graph that is better than some benchmark algorithms.In a second step, we created our own structures, so they are suitable for compression and are easy enough to search for.To do this, we started from a known structure, the split, and generalized it to create the r-split, where r is a fixed integer parameter.We then showed that the set of r-splits of a graph has a global coherence, in the sense that only a polynomial number of them is sufficient to describe all r-splits of the graph.This generalizes a well-known property of splits, for which only a linear number of them is sufficient to recover all the others.We also demonstrated that r-splits can be computed in polynomial time using submodular function optimization algorithms.In a third step, we focused on searching for particular regularities: patterns in ordered graphs.An ordered graph is a graph in which the vertices are ordered from 1 to n.A pattern is a partial ordered subgraph, in the sense that each pair of vertices can be connected either by an edge, a non-edge, or neither.The goal is to fix a pattern P and build an algorithm capable of detecting if P is in any ordered graph given as an input.This problem is polynomial in the size of the graph via exhaustive search.However, is it possible to do better?We were able to show that yes: most three-vertex patterns can be detected in linear time while exhaustive search requires cubic time.Regarding larger patterns, we exhibited classes of patterns that can be detected in subcubic time: outerplanar patterns.By adding additional constraints, we exhibited a class of patterns that can be detected in linear time: these are outerplanar patterns without cycles and non-edges

The thesis focuses on two open problems on finite partially ordered sets: the structure of order polytopes and the approximation of the number of linear extensions of a poset by mean of graph entropy. The polytopes considered here are the linear ordering polytope, the semiorder polytope, the interval order polytope, the partial order polytope and also a generalisation of the linear ordering polytope: the linear extension polytope of a fixed poset P. Various results on the structure of theses polytopes are proved in the first part of the thesis. In the second part of the thesis, we improve the existing bounds linking the entropy of the incomparability graph of the poset P and its number of linear extension.
Le but de la thèse est d'étudier deux problèmes ouverts sur les ensembles ordonnés finis: la structure des polytopes d'ordre et l'approximation du nombre d'extensions linéaires d'un ordre partiel au moyen de la notion d'entropie de graphe. Les polytopes considérés sont le polytope des ordres totaux, le polytope des semiordres, le polytope des ordres d'intervalles, le polytope des ordres partiels, ainsi qu'une généralisation du polytope des ordres totaux: le polytope des extensions linéaires d'un ensemble ordonné fixé P. Des résultats sur la structure de ces polytopes sont présentés dans la première partie de la thèse. Dans la deuxième partie de la thèse, nous améliorons les bornes existantes liant l'entropie du graphe d'incomparabilité d'un ordre partiel et son nombre d'extensions linéaires.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished

Cette thèse présente un calcul des séquents pour la logique linéaire enrichie d'un connecteur non commutatif et autodual "précède" situé entre le "par" et le "tenseur". Il est défini pour des séquents dont les formules sont orientées par un ordre partiel. Un calcul de réseaux de démonstration quotientant ce calcul des séquents est défini en termes de graphes orientés. Ce calcul est doté d'une sémantique dénotationnelle dans les espaces cohérents, préservée par élimination des coupures, un processus convergent et confluent. Des résultats combinatoires nécessaires sur les ordres partiels et sur la structure des graphes de démonstrations sont établies ainsi que quelques propriétés du calcul commutatif avec la règle MIX.

Cette thèse porte sur l'utilisation des outils théoriques de l'informatique pour améliorer les algorithmes dans la pratique, en particulier ceux qui traitent des données sous forme de graphes. Un graphe représente des éléments (nœuds) et leurs interactions (arêtes). L'informatique théorique a conçu des algorithmes pour des graphes arbitraires, tels que la recherche des chemins les plus courts ou l'identification des nœuds interconnectés. Cependant, les réseaux réels ont des propriétés spécifiques qui sont inconnues à l'avance en raison des situations du monde réel dont ils sont issus. Ils peuvent être très volumineux, ce qui pose un problème pour les traiter en un temps raisonnable. Pour aider à concevoir des algorithmes qui passent à l'échelle sur de gros graphes, nous nous concentrons sur la technique qui consiste à réordonner les nœuds selon un ordre spécifique qui dépend des propriétés locales ou globales du graphe. Nous classifions les différents mécanismes et méthodes qui ont été utilisés pour concevoir des ordres dans divers domaines d'application. Ensuite, nous présentons trois contributions qui utilisent l'ordre des nœuds pour rendre les algorithmes plus efficaces. Tout d'abord, nous reproduisons un article qui conçoit un ordre pour rendre les systèmes de cache plus efficaces, ce qui accélère différents algorithmes de graphes. Deuxièmement, nous créons de nouveaux ordres qui réduisent le nombre d'opérations dans un algorithme existant pour lister les triangles. Troisièmement, nous utilisons des algorithmes simples avec des ordres appropriés pour limiter la taille d'une couverture minimale par les sommets sur une instance spécifique de graphe, ce qui nous permet de certifier la qualité des résultats obtenus par des valeurs approchées. Ces résultats insistent sur les questions de passage à l'échelle, les mesures de temps, les fondements mathématiques et la validation par l'expérience. Enfin, nous présentons une collaboration sur l'analyse des réseaux qui consiste à décrire la mobilité des chercheurs et chercheuses dans l'espace de la connaissance
This thesis focuses on using theoretical tools of computer science to improve algorithms in practice, specifically algorithms that process data in the form of graphs. A graph represents elements (nodes) and their interactions (edges). Computer scientists have designed theoretical algorithms for arbitrary graphs, such as finding shortest paths or identifying inter-connected nodes. However, real-world networks have specific properties that are unknown in advance due to the situations from which they arise. They can be very large, which presents a challenge for processing them in reasonable time. To help design scalable algorithms for real-world networks, we focus on the technique of node ordering, which consists in processing the nodes in a specific order that depends on local or global properties of the network. We provide a review on the different mechanisms and methods that have been used to design orderings across various application domains. Then, we present three contributions that use node orderings to make algorithms more efficient. First, we replicate a paper that designs an ordering to make cache systems more effective, which accelerates different graph algorithms. Second, we create new orderings that diminish the number of operations in an existing algorithm for triangle listing. Third, we use greedy algorithms with certain orderings to bound the size of a minimum vertex cover on a specific instance, which allows us to certify the quality of approximate values. These findings insist on scalability issues, time measurements, mathematical grounding and validation by experiments. Finally, we present a collaboration on network analysis that consists in describing the mobility of researchers within the space of knowledge

Nous definissons les ordres de contiguite comme possedant une extension lineaire pour laquelle chaque ensemble de successeurs directs apparait comme un intervalle. Nous etudions cette nouvelle classe d'ordres dont la reconnaissance est lineaire, ainsi que certaines restrictions. Cette classe contient en particulier les ordres d'intervalles et les ordres sans n, ce qui entraine la np-completude de la dimension et du nombre de sauts. Nous montrons que le calcul du nombre d'extensions lineaires de contiguite est p-complet. Concernant les ordres de contiguite de hauteur un, nous prouvons que la dimension est un probleme polynomial. Nous etablissons egalement l'invariance de comparabilite de l'appartenance a la classe des ordres de double contiguite ainsi que la np-completude de la dimension pour les ordres de forte contiguite

Les structures arborescentes (arbres) sont largement étudiées en informatique. Les données semi-structurées en sont un récent champ d'application : il est admis que les arbres ordonnés d'arité non bornée sont un bon modèle pour ces données. Dans certains cas il est intéressant de considérer des arbres non ordonnés. Des formalismes logiques (logiques) sont utilisés pour décrire des requêtes ou vérifier des propriétés sur des données semi-structurées. Il est important d'identifier des logiques représentant un compromis entre expressivité et praticabilité des algorithmes. Des critères pertinents sont la satisfiabilité et la complexité du model checking de la logique. Nous étudions une logique spatiale, LS, qui est à la base d'un langage de requètes pour données semi-structurées modélisées par des arbres non ordonnés. La logique LS est très expressive, incluant des opérateurs spatiaux pour décrire localement la structure d'un arbre, un opérateur de point fixe et permettant de quantifier sur des étiquettes et sur des arbres. Nous établissons des résultats sur la satisfiabilité et la complexité du model checking pour différents fragments de LS. Nous identifions deux fragments syntaxiques de LS à satisfiabilité décidable, montrons que ces fragments sont équivalents aux logiques MSO et PMSO respectivement, et introduisons des classes d'automates d'arbres qui capturent ces deux fragments. Nous montrons que la complexité du mode! checking de LS est dans PSPACE-complet. Si seule la taille de l'arbre est prise en compte, la complexité du model checking va de linéaire à PSP ACE-complet pour les différents fragments de la logique.

La notion d'intervalle dans un graphe, traduit de façon naturelle la notion du segment dans les espaces euclidiens. Par analogie, un ensemble C de sommets est convexe si pour tout couple x, y de sommets de C, l'intervalle entre x et y est inclu dans C. En utilisant la convexité géodésique, Djokovic a caractérisé les graphes isométriquement plongeable dans l'hypercube. Une vingtaine d'années plus tard, Mulder a caractérisé les graphes médians comme des graphes isométriquement plongeable dans l'hypercube et qui sont fermés pour l'opération médian. La comprehension du lien apparent entre ces deux résultats, nous a permis de trouver une nouvelle caractérisation, d'inspiration géométrique, des graphes médians. Cette caractérisation nous a permis à reconnaître les graphes médians qui sont des produits d'arbres ou de chemins. Nous avons donné une caractérisation de ces produits par mineurs convexes exclus. Un autre groupe de résultats concerne des graphes définis naturellement à partir des polyminos. En cherchant le nombre minimum de sommets qui engendrent convexement un tel graphe G, nous avons trouvé que ce nombre est égal au nombre maximum de sommets de degré un d'un arbre obtenu à partir de G par la contraction d'arêtes bien choisies