Letteratura scientifica selezionata sul tema "Graphes généralisés"

Ce travail abordera les inégalités des chances dans l’Ecole algérienne et la politique de soutien à la scolarisation, à partir des données des recensements nationaux de la population et de l’habitat (1966, 1977, 1987, 1998, 2008), les données administratives du ministère de l’Education nationale et l’enquête par grappes à indicateurs multiples MICS-6/2019. La politique de démocratisation et de gratuité de l’enseignement, adoptée par l’Etat depuis l’indépendance, a permis en effet un accès massif à l’éducation pour les deux sexes, mais il ne s’est toujours pas généralisé, avec des disparités régionales avérées notamment le retard observé dans les Hauts Plateaux-Centre et le Grand Sud. Les inégalités sociales et spatiales impactent le parcours scolaire des enfants dans les trois paliers, en particulier le niveau secondaire. La politique sociale de l’éducation cible plus les enfants du primaire du milieu rural et moins les deux autres paliers, notamment en termes de couverture et de spécificité de leurs besoins. Bien que le soutien financier ou matériel vise les enfants pauvres, surtout du palier primaire, ce ne sont pas tous les enfants pauvres qui y ont accès. Les autres catégories en bénéficient également.

Introduction. L’utilisation inappropriée des inhibiteurs de la pompe à protons (IPP) peut être associée à des effets indésirables graves et avoir un impact sur les coûts de santé. La déprescription doit être envisagée lorsqu’une prescription inappropriée d’IPP est identifiée. Les interventions de déprescription sont rarement destinées aux patients. Celles s’adressant uniquement aux prescripteurs ont une efficacité limitée. Objectif. L’objectif de cet essai est d’évaluer l’efficacité d’une intervention multi-facette de déprescription des IPP menée auprès des patients et de leurs médecins généralistes (MG). Méthodes. Il s’agit d’un essai pragmatique, randomisé en grappes, contrôlé, dans la région Pays de la Loire. Les MG et leurs patients adultes à qui plus de 300 doses définies journalières (DDJ) d’IPP ont été délivrées au cours de l’année précédant le début de l’étude seront inclus dans l’étude. Au total, 2 500 MG et 64 500 patients seront répartis aléatoirement entre les bras d’intervention par grappes de cabinet de MG. Trois interventions seront comparées : i) une intervention multi-facette associant a) une brochure d’information sur la déprescription des IPP envoyée aux patients et b) une visite auprès de leurs MG d’un délégué de l’Assurance maladie (DAM) sur la thématique de la déprescription des IPP ; ii) une intervention avec la visite d’un DAM uniquement ; iii) pas d’intervention. Résultats attendus. Le résultat principal sera la déprescription d’IPP, définie comme la proportion de patients ayant obtenu une diminution d’au moins 50 % de la quantité d’IPP qui leur a été délivrée au bout de douze mois par rapport à avant inclusion. Sur la base de précédents essais, nous prévoyons un gain de 10 % de déprescription d’IPP dans le cadre de l’intervention multi-facette par rapport à l’intervention unique auprès des MG et au groupe témoin. L’étude a été financée par l’appel d’offre Resp-IR 2021. Elle a débuté en octobre 2022, pour des résultats préliminaires courant 2024.

International audience In this article, we propose a generalization of the notion of chordal graphs to signed graphs, which is based on the existence of a perfect elimination ordering for a chordal graph. We give a special kind of filtrations of the generalized chordal graphs, and show a characterization of those graphs. Moreover, we also describe a relation between signed graphs and a certain class of multiarrangements of hyperplanes, and show a characterization of free multiarrangements in that class in terms of the generalized chordal graphs, which generalizes a well-known result by Stanley on free hyperplane arrangements. Finally, we give a remark on a relation of our results with a recent conjecture by Athanasiadis on freeness characterization for another class of hyperplane arrangements. Dans cet article, nous proposons une généralisation de la notion des graphes triangulés à graphes signés, qui est basée sur l'existence d'un ordre d'élimination simplicial à un graphe triangulé. Nous donnons un genre spécial de filtrations des graphes triangulés généralisés, et montrons une caractérisation de ces graphes. De plus, nous décrivons aussi une relation entre graphes signés et une certaine classe de multicompositions d'hyperplans, et montrons une caractérisation de multicompositions libres dans cette classe en termes des graphes triangulés généralisés, qui généralise un résultat célèbre de Stanley sur compositions libres d'hyperplans. Finalement, nous donnons une remarque sur une relation de nos résultats avec une conjecture récente d'Athanasiadis sur une caractérisation du freeness d'une autre classe de compositions d'hyperplans.

International audience We study the class of functions on the set of (generalized) Young diagrams arising as the number of embeddings of bipartite graphs. We give a criterion for checking when such a function is a polynomial function on Young diagrams (in the sense of Kerov and Olshanski) in terms of combinatorial properties of the corresponding bipartite graphs. Our method involves development of a differential calculus of functions on the set of generalized Young diagrams. Nous étudions la classe des fonctions sur l'ensemble des diagrammes de Young (généralisés) qui sont définies comme des nombres d'injections de graphes bipartites. Nous donnons un critère pour savoir si une telle fonction est une fonctions polynomiale sur les diagrammes de Young (au sens de Kerov et Olshanski) utilisant les propriétés combinatoires des graphes bipartites correspondants. Notre méthode repose sur le développement d'un calcul différentiel sur les fonctions sur les diagrammes de Young généralisés.

International audience The $n$-dimensional associahedron is a polytope whose vertices correspond to triangulations of a convex $(n + 3)$-gon and whose edges are flips between them. It was recently shown that the diameter of this polytope is $2n - 4$ as soon as $n > 9$. We study the diameters of the graphs of relevant generalizations of the associahedron: on the one hand the generalized associahedra arising from cluster algebras, and on the other hand the graph associahedra and nestohedra. Related to the diameter, we investigate the non-leaving-face property for these polytopes, which asserts that every geodesic connecting two vertices in the graph of the polytope stays in the minimal face containing both. L’associaèdre de dimension $n$ est un polytope dont les sommets correspondent aux triangulations d’un $(n + 3)$-gone convexe et dont les arêtes sont les échanges entre ces triangulations. Il a été récemment démontré que le diamètre de ce polytope est $2n - 4$ dès que $n > 9$. Nous étudions les diamètres des graphes de certaines généralisations de l’associaèdre : d’une part les associaèdres généralisés provenant des algèbres amassées, et d’autre part les associaèdres de graphes et les nestoèdres. En lien avec le diamètre, nous étudions si toutes les géodésiques entre deux sommets de ces polytopes restent dans la plus petite face les contenant.

International audience We generalize the theory of critical groups from graphs to simplicial complexes. Specifically, given a simplicial complex, we define a family of abelian groups in terms of combinatorial Laplacian operators, generalizing the construction of the critical group of a graph. We show how to realize these critical groups explicitly as cokernels of reduced Laplacians, and prove that they are finite, with orders given by weighted enumerators of simplicial spanning trees. We describe how the critical groups of a complex represent flow along its faces, and sketch another potential interpretation as analogues of Chow groups. Nous généralisons la théorie des groupes critiques des graphes aux complexes simpliciaux. Plus précisément, pour un complexe simplicial, nous définissons une famille de groupes abéliens en termes d'opérateurs de Laplace combinatoires, qui généralise la construction du groupe critique d'un graphe. Nous montrons comment réaliser ces groupes critiques explicitement comme conoyaux des opérateurs de Laplace réduits combinatoires, et montrons qu'ils sont finis. Leurs ordres sont obtenus en comptant (avec des poids) des arbres simpliciaux couvrants. Nous décrivons comment les groupes critiques d'un complexe représentent le flux le long de ses faces, et esquissons une autre interprétation potentielle comme analogues des groupes de Chow.

International audience We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph $G$ and its directed line graph $\mathcal{L} G$. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when $G$ is regular of degree $k$, we show that the sandpile group of $G$ is isomorphic to the quotient of the sandpile group of $\mathcal{L} G$ by its $k$-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs. Nous généralisons un théorème de Knuth qui relie les arbres couvrants dirigés d'un graphe orienté $G$ au graphe adjoint orienté $\mathcal{L} G$. On peut associer à tout graphe orienté un groupe abélien appelé groupe du tas de sable, et dont l'ordre est le nombre d'arbres couvrants dirigés enracinés en un sommet fixé. Lorsque $G$ est régulier de degré $k$, nous montrons que le groupe du tas de sable de $G$ est isomorphe au quotient du groupe du tas de sable de $\mathcal{L} G$ par son sous-groupe de $k$-torsion. Comme corollaire, nous déterminons les groupes de tas de sable de deux familles de graphes étudiées en informatique: les graphes de de Bruijn et les graphes de Kautz.

Ce travail concerne l'etude des systemes lineaires generalises par l'approche bond graph. La modelisation de ces systemes avec choix particulier des vecteurs d'etat ne permet pas de les considerer comme des systemes reguliers surtout lorsqu'ils presentent des impulsions a l'instant initial et a tout instant ulterieur lorsque l'entree n'est pas suffisamment derivable. Une modelisation de ces systemes par bond graph est proposee. Ensuite, une interpretation graphique des elements de chaque matrice composant le modele d'etat generalise est donnee en terme de chemins causaux et de leur gain. Le calcul formel des coefficients du polynome caracteristique generalise a partir du modele bond graph comportant certains elements en causalite derivee, est donne. Ces coefficients peuvent etre ensuite a la base d'une methode de placement de poles formel par retour d'etat statique a partir du modele bond graph. La determination de la matrice de transfert est terminee par le calcul formel des differents numerateurs de cette matrice directement sur le modele bond graph. Le rang bond graph est une propriete interessante dans l'analyse structurelle par l'approche bond graph. Son calcul pour les systemes lineaires generalises est apparu alors comme une extension du resultat enonce pour les systemes reguliers modelises par bond graph. Pour la commandabilite en etat et l'observabilite structurelles, nous avons propose des procedures graphiques permettant de verifier la r- commandabilite et la r- observabilite du systeme generalise associe au modele bond graph
Nous avons egalement interprete graphiquement des criteres algebriques associes au sous systeme rapide dans la forme de rosenbrock du systeme generalise initial. La caracteristique principale d'un systeme generalise est ses modes impulsionnels s'ils existent. La modelisation des systemes generalises par bond graph ne permet pas de les faire apparaitre d'un point de vue structurel mais ceci est possible d'un point de vue formel. Une procedure graphique permettant de determiner formellement le nombre de modes impulsionnels que le systeme generalise peut exhiber a ete proposee. La modelisation par bond graph des systemes a commutation a permis de caracteriser leur modes impulsionnels. Nous avons interprete le nombre de ces modes a l'aide des chemins causaux apparus apres commutation entre element commutant et element i ou c statiquement dependant. Aussi, nous avons propose une interpretation graphique basee sur la notion de chemins causaux et de rang bond graph pour l'etude de la i- commandabilite et de la i- observabilite du systeme a commutation modelise par bond graph

Cette these est constituee par trois parties: (i), (ii) et (iii): i) on generalise le theoreme des bases de burnside a la classe des groupes matroidaux. On precise la structure des groupes matroidaux a sous-groupe de frattini trivial. On montre que les p-groupes dedoubles s'obtiennent canoniquement par extension d'un p-groupe possedant un systeme generateur x et un automorphisme qui inverse tout element de x; ii) on etudie l'influence des ordres des elements d'un groupe fini sur sa structure. On calcule le diametre du graphe de commutativite de plusieurs groupes. On decrit completement les groupes nilpotents et les groupes infinis possedant une fonction de steiner; iii) on classifie les graphes geodetiques de diametre 2. On etudie les graphes f-geodetiques (ou le nombre des geodesiques reliant deux sommets est une fonction donnee, dependant de la distance entre eux). On montre qu'un graphe f-geodetique biparti est regulier si et seulement si il est distance-regulier

De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels
Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems

De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels
Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems

Cette thèse s'inscrit dans le cadre de l'analyse statistique de données en grande dimension. Nous avons en effet aujourd'hui accès à un nombre toujours plus important d'information. L'enjeu majeur repose alors sur notre capacité à explorer de vastes quantités de données et à en inférer notamment les structures de dépendance. L'objet de cette thèse est d'étudier et d'apporter des garanties théoriques à certaines méthodes d'estimation de structures de dépendance de données en grande dimension.La première partie de la thèse est consacrée à l'étude de modèles parcimonieux et aux méthodes de type Lasso. Après avoir présenté les résultats importants sur ce sujet dans le chapitre 1, nous généralisons le cas gaussien à des modèles exponentiels généraux. La contribution majeure à cette partie est présentée dans le chapitre 2 et consiste en l'établissement d'inégalités oracles pour une procédure Group Lasso appliquée aux modèles linéaires généralisés. Ces résultats montrent les bonnes performances de cet estimateur sous certaines conditions sur le modèle et sont illustrés dans le cas du modèle Poissonien. Dans la deuxième partie de la thèse, nous revenons au modèle de régression linéaire, toujours en grande dimension mais l'hypothèse de parcimonie est cette fois remplacée par l'existence d'une structure de faible dimension sous-jacente aux données. Nous nous penchons dans cette partie plus particulièrement sur la méthode PLS qui cherche à trouver une décomposition optimale des prédicteurs étant donné un vecteur réponse. Nous rappelons les fondements de la méthode dans le chapitre 3. La contribution majeure à cette partie consiste en l'établissement pour la PLS d'une expression analytique explicite de la structure de dépendance liant les prédicteurs à la réponse. Les deux chapitres suivants illustrent la puissance de cette formule aux travers de nouveaux résultats théoriques sur la PLS . Dans une troisième et dernière partie, nous nous intéressons à la modélisation de structures au travers de graphes et plus particulièrement à la détection de communautés. Après avoir dressé un état de l'art du sujet, nous portons notre attention sur une méthode en particulier connue sous le nom de spectral clustering et qui permet de partitionner les noeuds d'un graphe en se basant sur une matrice de similarité. Nous proposons dans cette thèse une adaptation de cette méthode basée sur l'utilisation d'une pénalité de type l1. Nous illustrons notre méthode sur des simulations
This thesis falls within the context of high-dimensional data analysis. Nowadays we have access to an increasing amount of information. The major challenge relies on our ability to explore a huge amount of data and to infer their dependency structures.The purpose of this thesis is to study and provide theoretical guarantees to some specific methods that aim at estimating dependency structures for high-dimensional data. The first part of the thesis is devoted to the study of sparse models through Lasso-type methods. In Chapter 1, we present the main results on this topic and then we generalize the Gaussian case to any distribution from the exponential family. The major contribution to this field is presented in Chapter 2 and consists in oracle inequalities for a Group Lasso procedure applied to generalized linear models. These results show that this estimator achieves good performances under some specific conditions on the model. We illustrate this part by considering the case of the Poisson model. The second part concerns linear regression in high dimension but the sparsity assumptions is replaced by a low dimensional structure underlying the data. We focus in particular on the PLS method that attempts to find an optimal decomposition of the predictors given a response. We recall the main idea in Chapter 3. The major contribution to this part consists in a new explicit analytical expression of the dependency structure that links the predictors to the response. The next two chapters illustrate the power of this formula by emphasising new theoretical results for PLS. The third and last part is dedicated to graphs modelling and especially to community detection. After presenting the main trends on this topic, we draw our attention to Spectral Clustering that allows to cluster nodes of a graph with respect to a similarity matrix. In this thesis, we suggest an alternative to this method by considering a $l_1$ penalty. We illustrate this method through simulations

La coloration des graphes est un sujet central en théorie des graphes, et divers concepts de coloration ont été étudiés dans la littérature. Cette thèse étudie certains de ces concepts de coloration et les problèmes associés. Il s'agit notamment de la coloration des graphes signés généralisés, du nombre de choix fractionnels forts des graphes, du nombre de coloration généralisé des graphes, de la largeur gémellaire des graphes, de la discordance (combinatoire) des systèmes d'ensembles définissables et des classes de graphes chi_p-bornées. Un graphe signé est une paire (G, sigma), où G est un graphe et sigma: E(G) to {+,-} est une signature. Un graphe signé généralisé est également une paire (G, sigma), où la signature sigma attribue à chaque arête e une permutation sigma(e) dans un ensemble S comme son signe. Dans une coloration d'un graphe signé ou d'un graphe signé généralisé (G, sigma), le signe sigma(e) détermine les paires de couleurs qui doivent être évitées en tant que couleurs des sommets terminaux de e. Une question naturelle motivée par le théorème des quatre couleurs est de savoir pour quels sous-ensembles S de S_4, tout graphe planaire est S-4-colorable. Cette question a maintenant une réponse complète: seul S={id} posséde cette propriété, ce qui signifie que le théorème des quatre couleurs est strict au sens de la coloration généralisée des graphes signés. Ce résulat a été établi par une séquence de six articles, par différents groupes d'auteurs. L'une des contributions de cette thése est le résultat établi dans l'un de ces articles, à savoir que que de nombreux ensembles S n'ont pas la propriété désirée. La thèse considère également des questions similaires pour les graphes planaires sans triangle, ce qui peut être considéré comme une exploration de l'étanchéité du théorème de Grötzsch. Notre résultat montre que pour tout sous-ensemble S de S_3, si S n'est pas conjugué à un sous-ensemble de {id, (12)}, alors il existe un graphe planaire sans triangle qui n'est pas S-3-colorable. Une autre tentative pour renforcer le théorème de Grötzsch est de considérer le nombre de choix fractionnaire fort des graphes planaires sans triangle. Il a été prouvé par Voigt qu'il existe des graphes planaires sans triangle qui ne sont pas 3-choissables. Cette thèse prouve que le supremum du nombre de choix fractionnel fort des graphes planaires sans triangle est au moins 3+1/17. Un sujet important de la théorie structurelle des graphes est l'étude de la complexité structurelle des graphes. Quelques concepts et invariants de graphes sont largement étudiés dans la littérature. Récemment, le concept de largeur gémellaire a été introduit. Dans cette thèse, nous prouvons qu'un graphe G sans sous graphe K_{s,s} et de largeur gémellaire d a ses nombres de coloration forts (faibles) r bornés supérieurement par une fonction exponentielle en r et que nous pouvons construire des graphes réalisant une telle dépendance en r. L'une des deux notions centrales de la théorie structurelle des classes de graphes éparses est celle de classes d'expansion bornée. La discordance combinatoire est un sujet important. Elle mesure les irrégularités inévitables des systèmes d'ensembles et la difficulté intrinsèque de leur approximation. Dans cette thèse, nous donnons une nouvelle caractérisation des classes d'expansion bornée en termes de discordance de système définissables. La notion de chi-boundedness est un sujet central en théorie des graphes chromatiques. Dans cette thèse, les classes chi-bornées sont étudiées ici dans le contexte des colorations stellaires et, plus généralement, des chi_p-colorations. Considéré dans le cadre général de l'édute des classes éparses, il conduit à des extensions naturelles de la notion de classe d'expansion bornée. Nous résolvons ici deux conjectures liées à la limitation du nombre chromatique stellaire (i.e. chi_2). Nous donnons des caractérisations structurelles des classes (fortement et faiblement) chi_p-bornée
Graph coloring is a central topic in graph theory, and various coloring concepts have been studied in the literature. This thesis studies some of the coloring concepts and related problems. These include coloring of generalized signed graphs, strong fractional choice number of graphs, generalized coloring number of graphs, twin-width of graphs, (combinatorial) discrepancy of definable set systems and chi_p-bounded classes of graphs. A signed graph is a pair (G, sigma), where G is a graph and sigma: E(G) to {+,-} is a signature. A generalized signed graph is also a pair (G, sigma), where the signature sigma assigns to each edge e a permutation sigma(e) in a set S as its sign. In a coloring of a signed graph or a generalized signed graph (G, sigma), the sign sigma(e) determines the pairs of colors that need to be avoided as the colors of the end vertices of e. Let S_k be the set of all permutations of [k]. A natural question motivated by the four color theorem is for which subsets S of S_4, every planar graph is S-4-colorable. This question is now completely answered: only S={id} has this property, which means that the four color theorem is tight in the sense of generalized signed graph coloring. This answer is obtained in a sequence of six papers, by different groups of authors. The contribution of this thesis is the results in one of the papers, which shows that many sets S do not have the desired property. The thesis also considers similar questions for triangle-free planar graphs, which can be viewed as exploring the tightness of Grötzsch Theorem. Our result shows that for any subset S of S_3, if S is not conjugate to a subset of {id, (12)}, then there exists a triangle-free planar graph which is not S-3-colorable. Another attempt to strengthen Grötzsch Theorem is to consider multiple list coloring of triangle-free planar graphs. It was proved by Voigt that there are triangle-free planar graphs that are not 3-choosable. This thesis strengthens Voigt's result by considering the strong fractional choice number of graphs and proves that the supremum of the strong fractional choice number of triangle-free planar graphs is at least 3+1/17. One important subject in structural graph theory is to study the structural complexity of graphs or classes of graphs and a few concepts and graph invariants are studied extensively in the literature. These include treewidth of graphs, generalized coloring number, etc. Recently, the concept of twin-width was introduced by Bonnet, Kim, Thomassé and Watrigant. In this thesis, we study the relation between twin-width and generalized coloring number. We prove that a graph $G$ with no K_{s,s}-subgraph and twin-width d has strong(weak) r-coloring numbers bounded by an exponential function of r and that we can construct graphs achieving such a dependency in r. One of the two central notions in structural theory of classes of sparse graphs is the classes with bounded expansion. These classes have strong algorithmic and structural properties and enjoy numerous characterizations and applications. Combinatorial discrepancy is a significant subject in its own right. It measures the inevitable irregularities of set systems and the inherent difficulty to approximate them. In this thesis, we give a new characterization of bounded expansion classes in terms of discrepancy of definable set systems. The notion of chi-boundedness is a central topic in chromatic graph theory. This thesis studies chi-bounded classes in the context of star colorings and, more generally, chi_p-colorings, say chi_s-bounded and (strongly and weakly) chi_p-bounded classes. This fits to a general scheme of sparsity and leads to natural extensions of the notion of bounded expansion class. Here we solve two conjectures related to star coloring ({i.e.} chi_2) boundedness and give structural characterizations of strongly chi_p-bounded classes and weakly chi_p-bounded classes

Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits

Les modèles d'appariements aléatoires représentent de nombreux systèmes stochastiques concrets dans lesquels des éléments de différentes classes sont appariés selon des règles de compatibilités spécifiées. Par exemple, on peut citer les systèmes dédiés à l'allocation d'organes, les sites de recherche d'emplois, de logements, etc. De tels modèles sont toujours associés à un triptyque d'éléments : un graphe connexe, dit de compatibilités, dont les sommets représentent les classes des éléments pouvant entrer dans le systèmeet dont chaque arête relie deux classes compatibles, une politique d'appariements permettant de décider, en cas d'incertitude, quels appariements vont s'effectuer à l'intérieur du système, et un taux d'arrivées selon lequel les éléments entrent en son sein. Dans cette thèse, nous considérons des graphes généralisés, c'est-à-dire que l'on autorise l'appariement de deux éléments de la même classe, et nous étendons donc à ce cadre certains résultats déjà connus dans le cas de graphes simples. La stabilité d'un système régi par un modèle d'appariements est une propriété très importante. En effet, elle assure que les admissions au sein du système étudié sont contrôlées de sorte que les éléments ne restent pas bloqués à l'intérieur et que leur nombre n'augmente pas indéfiniment. Il est donc essentiel que le taux d'arrivées des éléments permette au système d'être stable. Dans ce manuscrit, nous caractérisons de manière algébrique cette zone de stabilité pour certains modèles d'appariements (généraux, généraux avec abandons, bipartis, bipartis étendus) ou de files d'attente, dites skill-based. Par ailleurs, nous démontrons que la politique d'appariements dite First Come, First Matched (FCFM) possède la propriété d'être maximale (généralisée), c'est-à-dire que la zone de stabilité du modèle d'appariements général associé à un graphe de compatibilités et à une politique quelconque est toujours incluse dans celle associée à ce même graphe et à FCFM. Notons que cette dernière coïncide alors avec un ensemble de mesures défini par des conditions purement algébriques. Dans ce cas, la question de l'étude des mesures permettant la stabilité des systèmes régis par un modèle d'appariements revient donc à celle, plus élémentaire, de la caractérisation d'un ensemble déterministe. Nous donnons alors un moyen de construction (simple) des mesures appartenant à celui-ci, ce qui peut s'avérer très utile pour calibrer le contrôle d'accès au système. En effet, la vérification algorithmique qu'une mesure quelconque vérifie ces conditions algébriques nécessite un nombre d'opérations polynomial en le nombre de sommets du graphe, et devient donc très coûteuse à mesure que ce cardinal augmente. Nous explicitons également, sous une forme produit, l'expression de la loi stationnaire de l'évolution temporelle du contenu d'un système stable régi par un modèle d'appariements général et sous la politique FCFM, permettant, notamment, de calculer explicitement des caractéristiques à l'équilibre de systèmes concrets et d'estimer leurs performances en temps long. On peut ainsi, par exemple, calculer la taille moyenne à l'équilibre d'une liste d'attente dans le cadre de dons croisés de reins, ou encore, estimer le temps moyen d'attente sur une interface pair-à-pair ou un site de rencontres.Enfin, les taux d'appariements associés à un modèle d'appariements (général ou biparti étendu) stable sont étudiés. Ils sont définis comme étant les fréquences asymptotiques des appariements réalisés et fournissent un critère de performance des systèmes régis par de tels modèles d'appariements, de même que les propriétés de politique-insensibilité et d'équité de ces taux, qui sont également discutées
Stochastic matching models represent many concrete stochastic systems in which elements of different classes are matched according to specified compatibility rules. For example, we can cite systems dedicated to organs allocation, job search sites, housing allocation programs, etc. Such models are typically associated to a triplet of elements: a connected graph, called compatibility graph, whose vertices represent the classes of elements that can enter the system and whose edges connect two compatible classes, amatching policy which decides the matches to be concretely executed, in case of multiple choices, and an arrival rate according to which the elements enter within it. In this thesis, we consider generalized graphs, meaning that we allow the matching of two elements of the same class, and we therefore extend to this framework some results already known in the case of simple graphs.The stability of a system governed by a matching model is a very important property. It ensures that the admissions within the system under study, are regulated, so that the elements do not accumulate in the system in the long run. It is therefore essential that the arrival rate of the elements allows the system to be stable. In this manuscript, we characterize, algebraically, this stability region for some matching models (general, general with reneging, bipartite, extended bipartite) or skill-based queueing systems.Moreover, we demonstrate that the matching policy called First Come, First Matched (FCFM) has the property of being (generalized) maximal, meaning that the stability region of the general matching model associated with a compatibility graph and with any policy is always included in the one associated with this same graph and ruled by FCFM. Note that this latter then coincides with a set of measures defined by purely algebraic conditions. In this case, the study of stability of the matching model at hand boils down to the more elementary question of characterizing of a deterministic set of measures. We then givea (simple) way to construct the measures belonging to the latter set. This turns out to be very useful for admission control, as checking the algebraic conditions requires a number of operations which is polynomial in the number of vertices of the considered compatibility graph, and therefore becomes very expensive as the number of vertices grows large.We also give, in a product form, the expression of the stationary distribution of the number-in-system process of a stable system governed by a general matching model and under the FCFM policy, allowing, in particular, to explicitly calculate characteristics at equilibrium of concrete systems and to estimate their long-time performance. We can thus, for example, calculate the size average at equilibrium of a waiting list in the case of cross-donation of kidneys, or even, estimate the average waiting time on a peer-to-peerinterface or on a dating website.Finally, the matching rates associated with a stable matching model (general or extended bipartite) are studied. They are defined as the asymptotic frequencies of the executed respective matchings, and provide an insightful performance criterion for the corresponding matching systems, as well as the policy-insensitivity and fairness properties of the matching rates, which are also discussed

Les définitions actuelles des infrastructures de sécurité (française, européenne, G-20) sont inadaptées à la réalité des attaques observées ou potentielles. Il en est de même des attaques elles-mêmes et en conséquence le terme « cyberattaque » réduit considérablement le champ conceptuel et opérationnel de celui qui est en charge de la protection et de la défense. La quasi-totalité des approches se réduit à identifier le champ strictement technique informatique (systèmes, réseaux) et à oublier d’autres dimensions propres au renseignement. Ainsi les principales méthodologies d’identification et de gestion du risque (EBIOS ou méthodologies similaires) considèrent une définition particulièrement restrictive, statique et locale de la notion d’infrastructure critique. La modélisation elle-même des attaquants et des attaques est extrêmement réduite. La principale erreur est de restreindre les approches techniques et les angles d’attaque d’un attaquant au seul champ informatique. Les angles « cyber » peuvent ne pas exister ou représenter un volet limitée dans un scenario global d’attaque. En outre, l’approche classique néglige le volet opérationnel gouvernant la préparation et la conduite de la manœuvre dans une attaque. Les modélisations par arbres d’attaques sont également très limitées du fait d’une restriction au seul champ cyber (systèmes et réseaux).Il est alors nécessaire de concevoir une définition très élargie, laquelle doit être dictée par la vision de l'attaquant et non celle du défenseur. Cette thèse vise à développer de nouveaux modèles d'infrastructure de sécurité basés sur la théorie des graphes et a modéliser de manière très élargie le concept d’attaque, incluant ou non un champ cyber. Cette représentation déjà utilisée pour décrire la topologie des infrastructures critiques sera enrichie pour appréhender de manière exhaustive l'environnement avec lesquelles elles interagissent. Les interdépendances avec d’autres entités (personnes, autres infrastructures critiques…) sont un élément clef dans la construction de scenarii d’attaques sophistiquées. Cette représentation enrichie doit aboutir à des nouveaux modèles d'attaquants, plus réalistes et mettant en œuvre des composants externes de l'infrastructure mais appartenant à son environnement proche. L'objectif majeur est la recherche de chemins optimaux dans un scénario d'attaque défini par l'objectif de l'adversaire. Cette approche globale, apporte une définition plus fine (et donc plus réaliste) de la sécurité comme étant le coût le plus faible du chemin d'attaque pris sur l'ensemble des adversaires réalistes (polynomiaux, i.e. agissant en temps fini).Le programme de recherche est structuré en cinq étapes. Les deux premières étapes visent à définir les modèles et les objets représentant les infrastructures de sécurité ainsi que les attaquants auxquelles elles sont confrontées. La troisième étape consiste en la définition d'une méthodologie générique pour évaluer la sécurité d'une infrastructure de sécurité. Cette étape doit aboutir à la conception d'heuristiques de recherche de vulnérabilités. Afin de valider les modèles et la méthodologie proposés, le programme de thèse prévoit le développement d'un démonstrateur recherche sous la forme d'une plate-forme d'évaluation. Enfin, la dernière étape consistera à l'évaluation d'un système existant à partir de la plate-forme en mettant en œuvre la méthodologie proposée. L'objectif de cette dernière étape est de valider les modèles et la méthodologie et d'en proposer une amélioration si nécessaire
The current definitions of a critical infrastructure are not adapted to the actual attacks which are observed these days. The problem is the same for the definition of an attack and therefore, the term « cyber attack » tends to reduce the conceptual and operational field of the person in charge of the security. Most of the approaches are reduced to identify the technical and IT domain only, and they forget the others domains specific to the intelligence. Then, the main methodologies to identify and to manage risk (EBIOS or some similar methodologies) take into account a definition of a critical infrastructure which is restrictive, static and local. The model of attacker and attack is also extremely narrowed as the technical approaches and the angles of attack of an attacker tend to be restricted to the IT domain only, even if the « cyber » angles may not exist or may only be a small part of an attack scenario.Therefore, it is necessary to have a new definition of a critical infrastructure, more complete and made according to the attacker point of view. Indeed, critical infrastructures can be protected by assessing the threats and vulnerability. This thesis aims to develop new models of infrastructure and attack accurately, models which will based on graph theory, with or without the cyber part. This graph-based representation is already used a lot to describe infrastructure, it will be enriched in order to have a more exhaustive view of an infrastructure environment. The dependencies with other entities (people, others critical infrastructures, etc.) have to be taken into account in order to obtain pertinent attack scenarios. This enriched representation must lead to new models of attackers, more realistic and implementing external components of the infrastructure which belong to its immediate environment. The main objective is the research of optimal paths or other mathematical structures which can be translated into attack scenarios. This global approach provides a finer (and therefore more realistic) definition of security as the lowest cost of the attack path.The research program is structured in five stages. The first two steps are aimed at defining the models and objects representing the security infrastructures as well as the attackers they are confronted with. The major difficulty encountered in developing a relevant infrastructure model is its ability to describe. Indeed, the more the model is rich, the more it can describe the infrastructure and the adversaries that attack it. The counterpart of developing a relevant model is its exponential characteristic. In these security models, we therefore expect that the problem of finding the vulnerabilities of a security infrastructure is equivalent to difficult problems, i.e. NP-hard or even NP-complete. The locks to be lifted will therefore consist in the design of heuristics to answer these problems in finite time with an ``acceptable" response. The third step is to define a generic methodology for assessing the safety of a security infrastructure. In order to validate the proposed models and methodology, the thesis program provides for the development of a research demonstrator in the form of an evaluation platform. Finally, the last step will be to evaluate an existing system from the platform by implementing the proposed methodology. The objective of this last step is to validate the models and the methodology and to propose an improvement if necessary

Cette dissertation se divise en deux parties, distinctes mais connexes, qui sont le reflet de la cotutelle. Nous étudions et résolvons des problèmes concernant d'une part la combinatoire des mots dans un contexte abélien et d'autre part des problèmes de couverture dans des graphes. Chaque question fait l'objet d'un chapitre. En combinatoire des mots, le premier problème considéré s'intéresse à la régularité des suites au sens défini par Allouche et Shallit. Nous montrons qu'une suite qui satisfait une certaine propriété de symétrie est 2-régulière. Ensuite, nous appliquons ce théorème pour montrer que les fonctions de complexité 2-abélienne du mot de Thue--Morse ainsi que du mot appelé ''period-doubling'' sont 2-régulières. Les calculs et arguments développés dans ces démonstrations s'inscrivent dans un schéma plus général que nous espérons pouvoir utiliser à nouveau pour prouver d'autres résultats de régularité. Le deuxième problème poursuit le développement de la notion de mot de retour abélien introduite par Puzynina et Zamboni. Nous obtenons une caractérisation des mots sturmiens avec un intercepte non nul en termes du cardinal (fini ou non) de l'ensemble des mots de retour abélien par rapport à tous les préfixes. Nous décrivons cet ensemble pour Fibonacci ainsi que pour Thue--Morse (bien que cela ne soit pas un mot sturmien). Nous étudions la relation existante entre la complexité abélienne et le cardinal de cet ensemble. En théorie des graphes, le premier problème considéré traite des codes identifiants dans les graphes. Ces codes ont été introduits par Karpovsky, Chakrabarty et Levitin pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Le rapport entre la taille optimale d'un code identifiant et la taille optimale du relâchement fractionnaire d'un code identifiant est comprise entre 1 et 2 ln(|V|)+1 où V est l'ensemble des sommets du graphe. Nous nous concentrons sur les graphes sommet-transitifs, car nous pouvons y calculer précisément la solution fractionnaire. Nous exhibons des familles infinies, appelées quadrangles généralisés, de graphes sommet-transitifs pour lesquelles les solutions entière et fractionnaire sont de l'ordre |V|^k avec k dans {1/4, 1/3, 2/5}. Le second problème concerne les (r,a,b)-codes couvrants de la grille infinie déjà étudiés par Axenovich et Puzynina. Nous introduisons la notion de 2-coloriages constants de graphes pondérés et nous les étudions dans le cas de quatre cycles pondérés particuliers. Nous présentons une méthode permettant de lier ces 2-coloriages aux codes couvrants. Enfin, nous déterminons les valeurs exactes des constantes a et b de tout (r,a,b)-code couvrant de la grille infinie avec |a-b|>4. Il s'agit d'une extension d'un théorème d'Axenovich
This dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results. The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue-Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set. In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^k with k in {1/4,1/3,2/5}. The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich