Ce document est le résumé en français de l’article (Lopez 2024) qui est disponible sur arXiv, dont le pdf, des slides de présentation, ainsi que le fichier bibtex associé sont disponibles sur ma page web.

Résumé

Dans cet article, je caractérise les classes de graphes largeur de clique linéaire bornée qui sont des beaux préordres pour l’ordre sous-structure induite en présence de couleurs sur les sommets. De plus, dans le cas où la classe est donnée sous la forme d’une transduction \(\mathsf{MSO}\) depuis des mots finis, je fournis un algorithme pour décider cette propriété. Cette étude s’appuie sur des outils de la théorie des automates, et le schéma de preuve permet de dériver une version faible de la conjecture de Pouzet pour les classes de graphes de largeur de clique linéaire bornée. De manière plus générale, la ligne directrice de cet article est l’idée que les classes de graphes qui sont des beaux préordres pour l’ordre sous-structure induite sont en correspondance avec des classes d’arbres munis de l’ordre de plongement avec trou de Derhowitz and Tzameret (2003). Ceci est démontré pour les classes de graphes de largeur de clique linéaire bornée, et vérifié pour les classes de graphes étudiées par Daligault, Rao, and Thomassé (2010).

Contextualisation

Un préordre \((X, \leq)\) est un beau préordre si toute suite \((x_n)_{n \in \mathbb{N}}\) d’éléments de \(X\) possède une paire croissante \(i < j\) telle que \(x_i \leq x_j\). Par exemple, l’ensemble \(\mathbb{N}\times \mathbb{N}\) est un beau préordre pour l’ordre produit. En théorie des graphes, le résultat fondamental de Robertson and Seymour (2004) montre que l’ensemble des graphes finis est un beau préordre pour l’ordre mineur. Du point de vue de la vérification formelle, les beaux préordres sont au cœur des algorithmes de vérification des systèmes bien structurés (Abdulla et al. 1996).

Les beaux préordres possèdent une riche théorie de clôture : ils sont fermés par produit, somme, et sous-ensemble. En sus, ils sont clos par des constructeurs plus exotiques comme l’ensemble des parties finies, l’ensemble des mots finis, ou l’ensemble des arbres finis (Higman 1952; Kruskal 1972). Ces propriétés rendent l’utilisation des beaux préordres aisée lors de la modélisation de systèmes bien structurés : on peut représenter les états d’un système en combinant différents beaux préordres.

Cependant, et comme étudié dans l’article Lopez (2023), l’ordre placé sur une construction comme « l’ensemble des mots finis sur \((X,\leq)\) » ou « l’ensemble des arbres finis sur \((X,\leq)\) » manque de canonicité, dans le sens où il n’existe pas de préordre le plus fin qui rende ces constructions bien préordonnées. La solution retenue pour a été de considérer les mots finis et les arbres finis comme des constructions inductives, et de proposer une définition systématique d’ordre sur ces constructions inductives.

Une autre solution, qui est celle retenue dans cet article, est de considérer que les ordres sur l’ensemble des arbres finis et des mots finis sont en réalités des ordres de sous structure-induite, lorsque ceux-ci sont vus comme des structures relationnelles finies. En effet, l’ordre sous mot épars de Higman (1952), est en réalité l’ordre de sous-structure induite pour l’ensemble des ordres linéaires coloriés (c’est-à-dire, des mots). De manière similaire, l’ordre de plongement d’arbre de Kruskal (1972) correspond à l’ordre sous-structure induite sur les arbres finis représentés par des structures coloriées utilisant la relation « plus petit ancêtre commun ». Cette présentation est particulièrement naturelle, car ces ordres sont généralement définis en terme de morphismes (voir Haase, Schmitz, and Schnoebelen 2013). Une généralisation de cette présentation se heurte au fait que l’ensemble des graphes finis (une classe de structures très simple) n’est pas un beau préordre pour l’ordre sous-structure induite.

Avant de comprendre quelles classes de structures relationnelles finies donnent lieu à un constructeur de beau préordre pour l’ordre sous-structure induite, il est nécessaire de comprendre dans quel cas des classes de graphes possèdent cette propriété. Ce sujet a déjà été étudié par Ding (1992), où il est montré que les classes de graphes ayant treedepth bornée sont des beaux préordres pour l’ordre sous-structure induite, et ce même avec coloriage. Depuis, la question de la caractérisation des classes de graphes qui sont des beaux préordres pour l’ordre sous-structure induite est restée ouverte, avec des contributions récentes de Daligault, Rao, and Thomassé (2010), ainsi que de Dabrowski, Lozin, and Paulusma (2018) ou Dabrowski, Lozin, and Paulusma (2020).

Il faut bien distinguer différentes approches en fonction de l’intérêt des auteurs et autrices :

1. Montrer qu’une classe de graphe est un constructeurs de beaux préordres, c’est-à-dire, que pour tout beau préordre \((X, \leq)\), l’ensemble des graphes coloriés par \(X\) est un beau préordre pour l’ordre sous-structure induite, où \(X\) est vu comme un ensemble de couleurs ordonnées. On dit alors que la classe est un constructeur de beau préordre.
2. Montrer qu’une classe de graphes est un beau préordonnée pour l’ordre sous-structure induite, pour tout nombre arbitrairement grand mais fini de couleurs. On dit alors que la classe est un beau préordre avec étiquettes.
3. Montrer qu’une classe de graphes est un beau préordonnée pour l’ordre sous-structure induite, avec un nombre fini de couleurs fixé (au moins \(2\) couleurs). On dit alors que la classe est un k-beau préordre, où \(k\) est le nombre de de couleurs utilisées.
4. Montrer qu’une classe de graphes est un beau préordonnée pour l’ordre sous-structure induite, sans aucune notion de coloriage.

Dans cet article, on s’intéressera principalement à la propriété (1), mais la littérature est plutôt concernée par les propriétés (3) et (4). Notons que (1) implique (2), qui implique (3), qui implique (4). On peut démontrer que l’implication (3) \(\implies\) (4) est stricte, mais il a été conjecturé par Pouzet (1972) que l’implication \((2) \implies (3)\) est en réalité une équivalence. Je conjecture que l’implication \((1) \implies (2)\) est également une une équivalence.

Jusqu’à présent, la notion de largeur de clique n’a pas été utilisée dans ce résumé, et son apparition dans cet article est motivée par les travaux de Daligault, Rao, and Thomassé (2010), qui ont étudié certaines classes de graphes de largeur de clique bornée et caractérisé lesquelles sont des beaux préordres pour l’ordre sous-structure induite avec couleurs (propriété 2). En plus de fournir un cadre théorique agréable dans lequel travailler, les auteurs conjecturent qu’une classe de graphes héréditaire¹¹ et qui est un \(2\)-beau préordre (propriété 3) a toujours une largeur de clique bornée (Daligault, Rao, and Thomassé 2010, Conjecture 5). Originellement, la notion de largeur de clique bornée a été introduite par Courcelle (Courcelle 1991, 1994; Courcelle, Engelfriet, and Rozenberg 1993) afin de généraliser les langages réguliers aux classes de graphes, et fournit un cadre théorique agréable pour représenter de telles classes.

Contributions de l’article

Dans cet article, je caractérise les classes de graphes largeur de clique linéaire bornée qui sont des beaux préordres pour l’ordre sous-structure induite en présence d’un nombre arbitraire couleurs (propriété 2). Cette caractérisation est incomparable à celle de (Daligault, Rao, and Thomassé 2010) car je me limite à la largeur de clique linéaire, alors que (Daligault, Rao, and Thomassé 2010) se limite à des classes spécifiques ayant une largeur de clique bornée.

De plus, je fournis un algorithme pour décider si une classe de graphes donnée sous la forme d’une transduction \(\mathsf{MSO}\) depuis des mots finis est un beau préordre pour l’ordre sous-structure induite. Cet algorithme, basé sur des outils de la théorie des automates peut se généraliser pour expliquer de manière purement algébrique les résultats ad-hoc de Daligault, Rao, and Thomassé (2010). Enfin, je démontre que l’équivalence \((1) \iff (2)\) est vraie pour les classes de graphes de largeur de clique linéaire bornée.

Au cœur de ces résultats se trouve le théorème de factorisation de Simon (1990), qui permet de remplacer les formules \(\mathsf{MSO}\) par des arbres colorés de profondeur finie. Ce théorème permet de réduire une classe de graphes de largeur de clique linéaire bornée qui est un beau préordre à une classe de mots imbriqués de profondeur finie, qui est elle-même un beau préordre pour l’ordre de Higman (1952) « imbriqué ». Cette caractérisation, en plus de révéler une structure arborescente sous-jacente pour les classes de graphes ayant une largeur de clique linéaire bornée, fait apparaître comme naturel l’ordre de plongement avec trou de Derhowitz and Tzameret (2003) : dans le cas des mots finis, cet ordre est précisément l’ordre de Higman emboité.

Cette découverte mène a la conjecture suivante : une classe de graphes héréditaire et qui est un constructeur de beau préordre pour l’ordre sous-structure induite est en correspondance avec une classe d’arbres munie de l’ordre de “plongement avec trou” (potentiellement imbriqué) de Derhowitz and Tzameret (2003), ce qui fait le lien avec l’étude précédemment mentionnée sur les constructions inductives (Lopez 2023), ce préordre étant lui-même obtenu inductivement (Derhowitz and Tzameret 2003; Freund 2020). J’ai démontré cette conjecture pour les classes de graphes étudiées par Daligault, Rao, and Thomassé (2010).

Conclusion

Cet article démontre que l’hypothèse de largeur de clique bornée fournit un cadre théorique propice à l’étude des classes de graphes finis qui sont des beaux préordres pour l’ordre sous-structure induite, cela sans réduire la généralité du propos selon (Daligault, Rao, and Thomassé 2010, Conjecture 5). De plus, il renforce les conjectures selon lesquelles les propriétés (1), (2) et (3) sont équivalentes. Enfin, il ouvre la voie à l’étude plus générale des structures relationnelles finies, et fait le lien entre les beaux préordres obtenus en coloriant des structures finies et ceux obtenus via des constructions inductives.

Références