# Sur certaines structures complémentaires de structures connues

Daniel Parrochia

► To cite this version:

Daniel Parrochia. Sur certaines structures complémentaires de structures connues. 2020. hal-03088356

HAL Id: hal-03088356

https://hal.science/hal-03088356v1

Preprint submitted on 26 Dec 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Sur certaines structures complémentaires de structures connues

Daniel Parrochia

Université Jean Moulin - Lyon 3 (France)

**Résumé.** Dans cet article, nous commençons par étudier la structure des graphes complémentaires de certains graphes et leurs matrices d'adjacence associées. Puis, nous définissons différentes relations d'ordre (strict, large, fort ou faible) et étudions les structures complémentaires susceptibles d'être associées à certains ordres, pré-ordres ou ordres partiels, via leurs graphes d'incomparabilité. Nous accordons une attention particulière aux chaînes et aux treillis, notamment aux treillis booléens. L'idée générale est de donner un sens concret à des structures qui n'apparaissent généralement qu'en blanc ou en creux et se trouvent rarement explicitées. En les rapprochant, nous révélons non pas exactement des figures de la discontinuité ou du désordre, mais plutôt un ensemble de structures et d'ordres alternatifs aux organisa-tions et ordonnancements habituels. Au-delà de la mathématique, nous en tirons, in fine, quelques conséquences philosophiques. Comme on ne s'est intéressé jusqu'ici en sciences humaines qu'aux structures pleines et directes, c'est en fait une immense et systématique extension du structuralisme que nous proposons. En appendice, nous appliquons ces considérations au cas de la théologie négative.

**Mots-clés.** Graphes, graphes complémentaires, ordres partiels, treillis, treillis booléens, graphes d'incomparabilité, théologie négative.

**Abstract** In this article, we start by studying the structure of the complementary graphs of certain graphs and their associated adjacency matrices. Then, we define different order relations (strict, large, strong or weak) and study the complementary structures likely to be associated with certain orders, preorders or partial orders, via their incomparability graphs. We pay special attention to chains and lattices,
especially Boolean lattices. The general idea is to give concrete meaning to struc-
tures which generally only appear in white or hollow and are rarely explained. By
bringing them together, we reveal not exactly figures of disorder, but rather a set of
alternative structures and orders to the usual organizations and orderings. Beyond
mathematics, we ultimately draw some philosophical consequences. As we have so
far only been interested in the human sciences in full and direct structures, it is in
fact an immense and systematic extension of structuralism that we are proposing. In
the appendix, we apply these considerations to the case of negative theology.

**Key words.** Graphs, complementary graphs, partial orders, lattices, Boolean lattices, incomparability graphs, negative theology.

# 1 Introduction

L'ordre et le désordre, on le sait, ont non seulement des degrés, ils ont en fait une
existence relative. Le philosophe Henri Bergson avait déjà noté cette propriété par-
ticulière de ces deux notions. Selon lui, «le désordre est simplement l'ordre que nous
ne cherchons pas. Vous ne pouvez pas supprimer un ordre, même par la pensée, sans
en faire surgir un autre» (voir [Bergson 38], 108). Sans doute Bergson donnait-il au
mot «ordre» un sens très large, proche de celui d'«organisation». Partant de ce que
la théorie des graphes peut en traduire, nous nous restreindrons progressivement
au sens du mot «ordre» que les mathématiciens connaissent et qui s'emploie en ré-
férence avec les relations du même nom. Mais, cette précision étant apportée, force
est de reconnaître que les mathématiciens, d'une certaine manière, sont bergsoniens :
l'existence d'une certaine relation R entre les éléments d'un ensemble non vide E, qui
correspond à un début d'organisation sur E qu'on peut décrire en traçant son graphe
G, fait immédiatement surgir la possibilité de l'organisation complémentaire $G' = \bar{G}$
– autrement dit le graphe correspondant à la relation $R' = \bar{R}$ existant aussi nécessai-
rement entre les éléments de E, même si ce n'est pas celle à laquelle on s'intéresse de
prime abord. De plus, comme on le découvrira, ce qui se révèle ici au plan des graphes
peut être transposé à d'autres structures plus spécifiques, notamment les structures
d'ordre au sens restreint de la «théorie des ordres» : chaines, ensembles partiellement
ordonnés (ou posets), treillis, matroïdes... Nous nous proposons ici d'étudier chaque
fois les formes complémentaires de celles qui sont données au départ et de décrire
également en précision leur structure. Comme l'action de connaître ne consiste qu'à
définir des appartenances, effectuer des regroupements, modifier des découpages ou
trouver de nouvelles ressources, il semble que l'on ne puisse guère échapper aux structures. En même temps, nous savons que définir une entité par son complémentaire (une antistructure) a été aussi une quête de l'humanité (c'était, notamment, l'un des buts de la théologie négative). Nous terminerons donc par des considérations plus philosophiques sur cette question.

## 2 Rappels sur les graphes

**Définition 2.1** (graphe, multigraphe, p-graphe). Un graphe $G(X, U)$, ensemble de sommets et d'arcs qui les relient (voir [Berge 70], 3), est le couple constitué :

1. Par un ensemble $X = \{x_1, x_2, ..., x_n\}$ où les $x_i$ sont des «sommets»;

2. Par une famille $U = \{u_1, u_2, ..., u_m\}$ où les $u_j$ sont des éléments du produit cartésien :

$$X \times X = \{(x, y) \mid x \in X, y \in Y\}.$$

Quand deux sommets sont reliés par plus d'une arête, on parle de *multigraphe* et, plus précisément, si $(x, y)$ apparaît $p$ fois dans $G$, alors $G(X, U)$ est un *p*-graphe.

**Définition 2.2.** Un multigraphe $G(X, U)$ est un *graphe simple* si :

1. Il n'a pas de boucle;

2. Entre 2 sommets, il n'y a jamais plus d'un arc pour les relier.

Parmi les graphes, certains présentent quelques régularités : par exemple, le même «degré», c'est-à-dire le même nombre d'arêtes ou d'arcs afférents à chaque sommet. On les appelle des graphes «réguliers». D'autres ne sont pas ainsi et enveloppent déjà du désordre en eux-mêmes : ils sont «irréguliers», voire «hautement irréguliers» et sont l'objet, aujourd'hui de nombreuses études et de beaucoup de conjectures (voir par exemple [Chartland 16], 1-16). Nous laisserons ici de côté cette question pour nous pencher sur celle de la complémentarité (l'organisation qui n'apparaît en principe qu'en creux dans la présentation du graphe et se trouve, du coup, souvent négligée<fnref n="1" />).

<footnote n="1">1. Nous avons dû constater que certains livres pourtant réputés comme des «bibles» en théorie des graphes, consacraient fort peu de lignes à ces questions, et notamment aux graphes de comparabilité et d'incomparabilité dont les propriétés sont souvent laissées à prouver au lecteur (voir [Diestel 06], 127, 136 et 242).</footnote>
**Définition 2.3** (Graphe complémentaire d'un graphe simple). (Voir [Gondran 79], 4) Etant donné un graphe simple $G = [X, U]$, le graphe complémentaire de $G = [X, \bar{U}]$ a le même ensemble de sommets que $G$ et comme arcs, les arcs complémentaires de ceux de $U$. On a :

$$ (i, j) \in U \Rightarrow (i, j) \notin \bar{U}; $$

$$ (i, j) \notin U \Rightarrow (i, j) \in \bar{U}; $$

La Fig. 1 montre un graphe simple $G$ et son graphe complémentaire $\bar{G}$.

<figure><img src="image_2.png" /><figcaption>FIGURE 1 – Graphe $G$ et son complémentaire $\bar{G}$</figcaption></figure>

Comme on peut le constater le graphe complémentaire du graphe $G$ (connexe) n'est pas lui-même connexe. Cependant, d'une façon générale, si le complémentaire d'un graphe non connexe est bien connexe, la converse n'est pas vraie.

**Définition 2.4** (matrice d'adjacence ou matrice d'incidence sommets-sommets). La matrice d'incidence sommets-sommets (ou matrice d'adjacence) d'un graphe est une matrice $M_{i,j}(i = 1, ..., n; j = 1, ..., n)$ à coefficients 0 ou 1, où chaque ligne correspond à un sommet de $G$, où chaque colonne correspond à un sommet de $G$ et où :

$$ M_{ij} = \begin{cases} 1 & \text{si et seulement si } (i, j) \in U; \\ 0 & \text{sinon.} \end{cases} $$

Connaissant le nombre d'arcs de $G[X, U]$, il est facile de calculer le nombre d'arcs de son graphe complémentaire.
**Théorème 2.1.** Si $|X| = n$, $|\overline{U}| = \binom{n}{2} - |U|$.

*Démonstration.* Le nombre total des combinaisons possibles de 2 éléments pris parmi $n$ est $\binom{n}{2}$. Il suffit de lui soustraire le cardinal $|U|$ de l'ensemble des arcs de $G[X, U]$ pour obtenir le cardinal de $\overline{U}$ puisque $|U| + |\overline{U}| = \binom{n}{2}$. $\square$

**Théorème 2.2** (Matrice du complémentaire d'un graphe simple). La matrice du complémentaire d'un graphe simple $G$ s'obtient comme la différence entre la complémentaire $M_c$ de la matrice du graphe $G$ et la matrice unité $I_n$ si $G$ a $n$ sommets.

*Démonstration.* Considérons la matrice $M_c$ complémentaire de la matrice d'adjacence $M$ d'un graphe $G$. C'est nécessairement celle d'un graphe à boucles car les zéros de la diagonale de $M$ ont été remplacés par des uns, ce qui signifie que $a$ est en relation avec lui-même, $b$ en relation avec lui-même, etc. Si nous voulons obtenir comme complément de $G$ un graphe $\overline{G}$ simple sans boucles, il nous faut trouver une matrice $M'$ avec une diagonale nulle. En d'autres termes, il faut soustraire des 1 aux 1 sur la diagonale de $M$ et, pour cela, il faut poser :

$$M' = M_c - I_n,$$

où $I_n$ est la matrice identité à $n$ lignes et $n$ colonnes, dont les termes diagonaux sont tous égaux à 1 et les termes non-diagonaux égaux à 0. $\square$

**Définition 2.5** (graphe autocomplémenté). Un graphe auto-complémenté $G$ est un graphe dont le graphe complémentaire $\overline{G}$ présente une structure identique à celle de $G$ (à la permutation près des labels (lettres ou nombres) désignant les sommets<fnref n="2" />).

On vérifie que les graphes de la Fig. 2, d'ordre inférieur à 10, sont des graphes autocomplémentés.

**Définition 2.6** (cycle d'un graphe). Dans un graphe $G(X, U)$, un cycle est une séquence d'arcs

$$\mu = (u_1, u_2, \dots, u_q)$$

telle que :

1. Tout arc $u_k$ (avec $1 < k < q$) est relié par une de ses extrémités au précédent $u_{k-1}$ et par l'autre extrémité au suivant $u_{k+1}$. En d'autres termes, c'est une «chaîne» (suite d'arêtes consécutives en théorie des graphes);

<footnote n="2">2. Il va de soi que, dans un tel cas, le graphe complémentaire possédant la même structure que le graphe initial, passer au complémentaire n'apporte guère d'informations nouvelles.</footnote>
<figure><img src="image_3.png" /><figcaption>FIGURE 2 – Graphes auto-complémentés</figcaption></figure>

2. La séquence n'utilise pas deux fois le même arc;

3. Le sommet initial et le sommet terminal de la chaîne coïncident.

# 3 Arbre, complémentaire d'un arbre et co-arbre

**Définition 3.1.** Un arbre est un graphe connexe sans cycle (voir [Berge 70], 22-50; [Gondran 79], 103-128).

Les propriétés suivantes sont une simple reformulation de la définition :

- Un arbre est un graphe dans lequel tout couple de points $x$ et $y$ sont reliés par une chaîne unique.

- Un arbre est un graphe connexe où le nombre d'arêtes est égal au nombre de points diminués de 1.
— Un arbre est un graphe sans cycle où le nombre d'arêtes est égal au nombre de points diminués de 1.

— Un arbre est un graphe connexe où la suppression d'une seule arête quelconque le rend non connexe.

— Un arbre est un graphe sans cycle où l'adjonction d'une nouvelle arête reliant 2 sommets non-adjacents crée un cycle et un seul.

Un arbre étant un graphe, il est facile de trouver le graphe complémentaire d'un arbre donné, lequel, généralement, n'est pas un arbre, comme on peut le voir sur l'exemple de la Fig. 3, obtenue à partir de l'examen de la matrice complémentaire de la matrice de l'arbre $\mathcal{A}$.

<figure><img src="image_4.png" /><figcaption>FIGURE 3 – L'arbre $\mathcal{A}$ et son complémentaire $\overline{\mathcal{A}}$</figcaption></figure>

On ne confondra pas *arbre complémentaire* et *coarbre*.

**Définition 3.2** (coarbre). Soit $G = [X, U]$ un graphe connexe. On dit que le graphe partiel $H = [X, V]$ est un *coarbre* de $G$ si et seulement si le graphe partiel $\overline{H} = [X, U - V]$ est un arbre de $G$.

Un coarbre peut être lui-même un arbre, comme le montre la Fig. 4.

# 4 Relation d'ordre, ensemble ordonné

**Définition 4.1.** (Relation d'ordre - voir [Kaufmann 78], 5-7) Une relation interne binaire $\leq$ sur un ensemble $E$ est une relation d'ordre si pour tous $x, y$ et $z$ éléments de $E$, on a :

1. $x \leq x$ (réflexivité);
<figure><img src="image_5.png" /><figcaption>FIGURE 4 – Arbre et coarbre dans un graphe</figcaption></figure>

$$2. (x \le y \text{ et } y \le x) \Rightarrow x = y \text{ (antisymétrie)};$$

$$3. (x \le y \text{ et } y \le z) \Rightarrow x \le z \text{ (transitivité).}$$

Une telle relation est parfois nommée «ordre large». Si on remplace $\le$ par $<$, alors la relation devient une relation d'«ordre strict». En ce cas, elle est irréflexive. Elle se lit « x est plus petit que y », ou « y est supérieur à x » et on a :

$$x < y \text{ si et seulement si } x \le y \text{ et } x \ne y.$$

On notera que certaines relations d'ordre sont des relations *totales*, c'est-à-dire que deux éléments de $E$ sont toujours *comparables*, autrement dit, pour tous $x, y$ de $E$ :

$$x \le y \text{ ou } y \le x.$$

On dit alors que $\le$ est une relation d'«ordre total», et que l'ensemble $E$ est *totale-ment ordonné* par cette relation.

**Définition 4.2** (Ensemble ordonné - voir [Harzheim 05]). Un ensemble ordonné est un ensemble muni d'une relation d'ordre.

**Définition 4.3** (Chaîne). En théorie des ordres, on appelle «chaîne» un ensemble totalement ordonné, c'est-à-dire tel que, étant donné deux éléments $x$ et $y$ de cet ensemble, l'une au moins des deux relations suivantes est vraie :

$$x \le y \text{ ou } y \le x.$$

Si un ensemble ordonné est fini, il peut être représenté graphiquement sous la forme d'un *diagramme de Hasse*, de façon similaire à la représentation habituelle d'un
graphe sur papier, ce qui peut permettre de travailler plus aisément sur lui. S'il est infini, on peut dessiner une partie de son diagramme de Hasse.

**Définition 4.4** (préordre). On appelle «préordre» une relation réflexive et transitive. Une relation de préordre n'est pas une relation d'ordre en général car il manque la propriété d'antisymétrie. Mais tout quotient d'un préordre par la relation d'équivalence associée est un ordre.

**Définition 4.5** (ordre strict). Une relation d'ordre strict sur un ensemble non vide n'est pas non plus, *stricto sensu*, une relation d'ordre car elle n'est pas réflexive. Mais si $<^-$ est un ordre strict sur $E$, la relation « $x <^-$ y ou $x =^-$ y » est un ordre sur $E$.

**Définition 4.6** (ordre cyclique). Une relation d'ordre cyclique est une relation ternaire $R$ invariante par permutation circulaire. On a :

$$R(x, y, z) = R(y, z, x) \text{ avec les propriétés :}$$

$$\text{— } R(x, y, z) = \neg R(z, y, x) \text{ (asymétrie)};$$

$$\text{— } R(x, y, z) \text{ et } R(x, z, u) = R(x, y, u) \text{ (transitivité)};$$

Une relation d'ordre cyclique n'est pas une relation d'ordre car c'est une relation ternaire. Mais les relations binaires obtenues en fixant l'un de ses trois arguments sont des relations d'ordre strict.

**Définition 4.7** (Ordre partiel - ensemble partiellement ordonné (poset)). Une relation d'ordre sur $E$ est dite «partielle» si elle n'est pas totale, et $E$ est alors un *ensemble partiellement ordonné* (ou *poset*). À tout poset pourra être associé un graphe de comparabilité (correspondant à la relation d'ordre sur le poset) et un graphe d'incomparabilité (correspondant à la relation complémentaire). On montre que ces graphes ont des propriétés particulière, comme le fait d'être des graphes «parfaits» (voir [Berge 84]): on trouvera une définition de la «perfection» d'un graphe dans la section 6, déf. 6.5).

**Définition 4.8** (arbre enraciné ou arborescence). Un arbre enraciné (ou arborescence) est un graphe orienté acyclique possédant une racine $r$ (c'est-à-dire un point tel que tout autre sommet du graphe puisse être atteint par un chemin issu de $r$). Un arbre enraciné peut naturellement être associé à une relation d'ordre partiel notée $\leq^3$.

<footnote n="3">3. On peut toutefois le définir différemment : par exemple, G. Kurepa ([Kurepa 35]) a introduit</footnote>
**Définition 4.9** (Plus grand élément et élément maximal). Dans un ensemble ordonné $(E, \leq)$, un élément $x$ d'une partie $A \subset E$ est le plus grand élément ou maximum de $A$, si :

$$ \forall y \in A, x > y. $$

Dans un ensemble ordonné, il n'existe pas forcément de plus grand élément. En revanche, si $E$ est fini, il contiendra (au moins) un élément $a$ dit maximal, autrement dit, tel que :

$$ a \in E \text{ et } \forall x \in E, a \leq x \Rightarrow x = a. $$

Si $E$ est un ensemble inductif infini, le lemme de Zorn garantit encore l'existence d'un élément maximal.

**Définition 4.10** (Négation – ou complémentaire – d'une relation d'ordre). La négation d'une relation binaire $R$ définie sur un ensemble $E$ est la relation associée au graphe complémentaire de la relation $R$ dans $E \times E$. On la note généralement $\mathcal{R}$. Dit autrement, deux éléments sont en relation par $\mathcal{R}$ si et seulement s'ils ne le sont pas par $R$.

Dire qu'un ordre est total, c'est dire que sa négation est l'ordre strict inverse. C'est-à-dire qu'il y a équivalence pour un ordre $\leq$ entre :

$$ \text{---} \leq \text{est total;} $$

$$ \text{---} x \not\leq y \iff y < x. $$

En revanche, dès qu'il existe deux éléments distincts non comparables par un ordre, la négation de la relation ne peut être un ordre (strict ou large), car elle n'est pas antisymétrique. La négation d'un ordre non total n'est donc jamais un ordre.

**Définition 4.11** (Bon ordre. Ensemble bien ordonné). Un ensemble ordonné est dit *bien ordonné* si tout sous-ensemble non vide de cet ensemble possède un plus petit élément.

**Définition 4.12** (Treillis). (voir [Blyth 05]) Un ensemble est appelé *treillis* s'il est ordonné et si tout couple d'éléments possède une même borne supérieure et une même borne inférieure.

<footnote>une relation dite «de ramification», somme logique d'une relation d'incomparabilité $||$ (reliant les éléments collatéraux) et une relation de descendance directe $\sim$ reliant les nœuds «pères» aux nœuds «fils». Elle vaut aussi pour un arbre infini. Sur la structure associée à un arbre défini de cette manière, voir [Parrochia 13], 122-123).</footnote>
**Définition 4.13** (hypergraphe). Soit $X = \{x_1, x_2, ..., x_n\}$ un ensemble fini, et $\mathcal{E} = (E_i | i \in I)$ une famille de partie de $X$. On dira que $\mathcal{E}$ constitue un hypergraphe sur $X$ si l'on a :

$$E_i \neq \emptyset, \\ \bigcup_{i \in I} E_i = X.$$

**Définition 4.14** (matroïde). Il existe plusieurs définitions des matroïdes. En termes d'indépendance, on dira qu'un *matroïde* fini $M$ est une paire $(E, \mathcal{I})$, où $E$ est un ensemble fini (appelé ensemble de base) et $\mathcal{I}$ est une famille de $E$ (appelés ensembles indépendants) avec les propriétés suivantes :

1. L'ensemble vide est indépendant, c'est-à-dire $\emptyset \in \mathcal{I}$. Alternativement, au moins un sous-ensemble de $E$ est indépendant, c'est-à-dire $\mathcal{I} \neq \emptyset$.

2. Chaque sous-ensemble d'un ensemble indépendant est indépendant, c'est-à-dire pour chaque $A' \subseteq A \subseteq E$, si $A \in \mathcal{I}$ alors $A' \in \mathcal{I}$. Ceci est parfois appelé la *propriété d'hérédité*.

3. Enfin, si $A$ et $B$ sont deux ensembles indépendants (c'est-à-dire que chaque ensemble est indépendant) et $A$ a plus d'éléments que $B$, alors il existe $x \in A \setminus B$ tel que $B \cup \{x\}$ soit dans $\mathcal{I}$. Ceci est parfois appelé la *propriété d'augmentation* ou la *propriété d'échange* de l'ensemble indépendant.

On notera qu'à tout matroïde $M(E, \mathcal{I})$ on peut associer un hypergraphe $H(E, \mathcal{I})$ ayant $E$ comme ensemble de sommets et dont les arêtes sont les éléments de $\mathcal{I}$ (autres que $\emptyset$).

Les deux premières propriétés définissent une structure combinatoire connue sous le nom de *système d'indépendance* (ou *complexe simplicial abstrait*).

**Définition 4.15** (complexe simplicial). Plus précisément, un complexe simplicial abstrait est la donnée d'un ensemble $V$ (dont les éléments sont appelés sommets) et d'un ensemble $\Sigma$ de parties finies non vides (les *faces*) de $V$ qui soit stable par sous-parties non vides. Autrement dit, toute partie non vide d'une face est aussi une face. Il est en général requis que tout sommet appartienne à un nombre fini non nul de faces.

Les faces de cardinal 2 sont aussi appelées *arêtes* en référence au vocabulaire de la théorie des graphes. Par analogie, pour tout entier $n$, une face de dimension $n$ (dite
aussi $n$-face) est une face de cardinal $n + 1$. Si la dimension des faces est bornée, la dimension d'un complexe simplicial est la dimension maximale des faces. Dans le cas contraire, cette dimension est infinie. La notion de « complexe simplicial » généralise donc à la fois les notions d'ensemble, de graphe, d'hypergraphe et de matroïde.

- Un complexe simplicial de dimension 0 est simplement un ensemble sans structure additionnelle.

- Un complexe simplicial de dimension 1 est un graphe.

- Un complexe simplicial de dimension 2 est un espace triangulé.

Plus généralement, en toute dimension, on appelle triangulation d'un espace topologique un homéomorphisme entre cet espace et un complexe simplicial. Bien sur, tout espace topologique n'est pas «triangulable».

**Définition 4.16 (Ordre et Complexe simplicial).** Une classe importante de complexes simpliciaux provient d'ensembles ordonnés finis. On définit le complexe d'ordre $D(S)$ d'un ensemble ordonné fini $S$ comme étant l'ensemble des chaînes de $S$. Le complexe d'ordre est trivialement un complexe simplicial.

Cette définition suppose quelques considérations topologiques. En mathématiques, la topologie associée à un poset $(S, \leq)$ est la topologie d'Alexandrov (les ensembles ouverts sont des ensembles supérieurs) sur le poset des chaînes finies de $(S, \leq)$, ordonnées par inclusion.

Soit $V$ un ensemble de sommets. Un complexe simplicial abstrait $\Delta$ est un ensemble d'ensembles finis de sommets, appelés faces $\sigma \subseteq V$, tels que

$$ \forall \rho \forall \sigma : \rho \subseteq \sigma \in \Delta \Rightarrow \rho \in \Delta. $$

Étant donné un complexe simplicial $\Delta$ défini comme ci-dessus, on définit une topologie (ensemble de points) sur $\delta$ en demandant qu'un sous-ensemble $\Gamma \subseteq \Delta$ soit fermé si et seulement si $\Gamma$ est un complexe simplicial, c'est à dire :

$$ \forall \rho \forall \sigma : \rho \subseteq \sigma \in \Gamma \Rightarrow \rho \in \Gamma. $$

C'est la topologie d'Alexandrov sur le poset des faces de $\Delta$ (voir [Wachs 04]).

Le complexe d'ordre associé à un poset $(S, \leq)$ a l'ensemble $S$ comme sommets et les chaînes finies de $(S, \leq)$ comme faces. La topologie associée à un poset $(S, \leq)$ est alors la topologie d'Alexandrov sur le complexe d'ordre associé à $(S, \leq)$.
Le complexe d'ordre d'un poset étant l'ensemble des chaînes, il est facile de voir que son complémentaire sera l'ensemble des antichaînes.

Il existe des représentations booléennes des posets, treillis, complexes simpliciaux et matroïdes (voir [Rhodes 15]). Toutefois, nous ne nous servirons pas de ce formalisme car la définition de la matrice booléenne d'un treillis $M(T) = m_{x,a}$ avec :

$$m_{x,a} = \begin{cases} 0 & \text{si } x \ge a; \\ 1 & \text{sinon,} \end{cases}$$

ne permet pas de passer au complémentaire 4. En revanche, ce formalisme permet de trouver directement le nombre d'arêtes du graphe de comparabilité d'un poset (il suffit de compter, dans la matrice obtenue, le nombre de zéros qui ne sont pas sur la diagonale (pour plus de précisions, voir [Parrochia 20])). De là, on obtient très facilement le nombre d'arêtes du graphe d'incomparabilité. En effet, soit $|E|$ le nombre d'arêtes du graphe de comparabilité d'un poset P. Le nombre N d'arêtes de son graphe d'incomparabilité est :

$$N = \binom{n}{2} - |E|.$$

# 5 Ordres faibles (stricts et larges)

En mathématiques, en particulier en théorie des ordres, un *ordre faible* est une formalisation de la notion intuitive de classement d'un ensemble, dont certains membres peuvent être liés les uns aux autres. Les ordres faibles sont une généralisation des ensembles totalement ordonnés (classements sans égalité) et sont à leur tour généralisés par les préordres et les ensembles partiellement ordonnés.

Il existe plusieurs manières équivalentes de formaliser les ordres faibles : ils peuvent être axiomatisés comme des ordres faibles stricts (ensembles partiellement ordonnés dans lesquels l'incomparabilité est une relation transitive), comme des pré-ordres totaux (relations binaires transitives dans lesquelles au moins une des deux relations possibles existe entre chaque paire d'éléments), ou comme des partitions ordonnées

<footnote n="4">4. L'exemple suivant suffira à le montrer : Soit $T = \{0, a, b, 1\}$ avec $0 \le a, b \le 1$. Comme on n'a pas $a \ge b$ puisque $a$ et $b$ sont incomparables, $m_{ab} = m_{ba} = 1$. Mais en passant à la matrice $M_c$ complémentaire de $M$, nous obtenons nécessairement $m_{ab} = m_{ba} = 0$, ce qui signifie qu'on a à la fois $a \ge b$ et $b \ge a$. Mais ceci entraîne $a = b$, ce qui est faux.</footnote>
(partitions des éléments en sous-ensembles disjoints, avec un ordre total sur les sous-ensembles). Dans de nombreux cas, une autre représentation appelée *arrangement préférentiel* et basée sur une fonction d'utilité est également possible.

L'arrivée d'une course (de chevaux, de cyclistes, d'athlètes...), les sondages d'opinion, l'ordonnancement des points du plan euclidien par leur distance à l'origine peuvent donner naissance à des ordres faibles.

**Définition 5.1.** On appelle *ordre faible* sur un ensemble $S$ qui est un ordre partiel strict (c'est-à-dire, muni d'une relation transitive qui est irréflexive ou, de manière équivalente, qui est asymétrique), un ordre dans lequel la relation «ni $a < b$ ni $b < a$» est transitive. Par conséquent, un ordre faible strict a les propriétés suivantes :

— Pour tout $x$ dans $S$, on n'a pas $x < x$ (irréflexivité);

— Pour tout $x, y$ dans $S$, si $x < y$ alors on n'a pas $y < x$ (asymétrie);

— Pour tout $x, y, z$ dans $S$, si $x < y$ et $y < z$ alors $x < z$ (transitivité);

— Pour tout $x, y, z$ dans $S$, si $x$ est incomparable avec $y$ (ni $x < y$ ni $y < x$ ne tiennent), et $y$ est incomparable avec $z$, alors $x$ est incomparable avec $z$ (transitivité de l'incomparabilité). La relation d'incomparabilité est parfois notée $||$.

Cette liste de propriétés est quelque peu redondante, en ce que l'asymétrie implique une irréflexivité, et en ce que l'irréflexivité et la transitivité impliquent ensemble l'asymétrie.

Définie comme ci-dessus, la relation d'incomparabilité est une relation d'équivalence : elle est transitive ; de plus, on a aussi la symétrie : $x \parallel y$ ssi $y \parallel x$) et même la réflexivité ($x \parallel x$ puisque $x < x$ ne tient pas). Ses classes d'équivalence partitionnent donc les éléments de $S$. Elles sont, de plus, totalement ordonnées par $<$. Inversement, tout ordre total sur une partition de $S$ donne lieu à un ordre faible strict dans lequel $x < y$ si et seulement s'il existe des ensembles $A$ et $B$ dans la partition, avec $x$ dans $A$, $y$ dans $B$ et $A < B$ dans l'ordre total.

Tous les ordres partiels n'obéissent pas à la loi transitive de l'incomparabilité. Par exemple, considérons l'ordre partiel dans l'ensemble $E = \{a, b, c\}$ défini par la relation $b < c$. Les paires $a, b$ et $a, c$ sont incomparables mais $b$ et $c$ sont liés, donc l'incomparabilité ne forme pas une relation d'équivalence et cet exemple n'est pas un ordre faible strict.

Les ordres faibles stricts sont très étroitement liés aux préordres totaux ou aux ordres
faibles (non stricts), et les mêmes concepts mathématiques qui peuvent être modélisés avec des ordres faibles stricts peuvent être modélisés aussi bien avec les préordres totaux. Un préordre total est un préordre qui est également une relation connexe, c'est-à-dire qu'aucune paire d'éléments n'est incomparable. Un préordre total $\leqslant$ satisfait les propriétés suivantes :

— Pour tout $x, y$ et $z$, si $x \leqslant y$ et $y \leqslant z$, alors $x \leqslant z$ (transitivité);

— Pour tout $x, y, x \leqslant y$ ou $y \leqslant x$ (connexité);

— Donc, pour tout $x, x \leqslant x$ (réflexivité).

Un ordre total est un pré-ordre total qui est antisymétrique, autrement dit, qui est aussi un ordre partiel. Les préordre totaux sont parfois également appelées «relations de préférence»<fnref n="5" />.

**Passage au complémentaire** On notera que le complément d'un ordre faible strict est un pré-ordre total, et vice versa, mais il semble plus naturel de relier les ordres faibles stricts et les préordres totaux d'une manière qui préserve plutôt qu'inverse l'ordre des éléments. On prend donc généralement l'inverse du complément. Autrement dit, pour un ordre faible strict $<$, on introduit un préordre total $\leqslant$ en définissant $x \leqslant y$ chaque fois qu'on n'a pas $y < x$. Dans l'autre sens, pour définir un ordre faible strict à partir d'un préordre total $\leqslant$, on posera $x < y$ chaque fois qu'on n'aura pas $y \leqslant x$.

Dans tout pré-ordre, il y a une relation d'équivalence correspondante où deux éléments $x$ et $y$ sont définis comme équivalents si $x \leqslant y$ et $y \leqslant x$. Dans le cas d'un préordre total, l'ordre partiel correspondant sur l'ensemble des classes d'équivalence est un ordre total. Deux éléments sont équivalents dans un préordre total si et seule-

<footnote n="5">5. Dans la vie quotidienne, on fait toujours des choix et tout se résout souvent par l'établissement de préordres totaux. Certains philosophes (par exemple Leibniz) ont d'ailleurs douté que les individus, psychologiquement, pussent se trouver dans des situations d'indifférence, autrement dit qu'il existât autre chose que des préordres totaux. Ainsi ce philosophe contestait-il la situation de l'âne de Buridan hésitant entre un seau d'avoine et un seau d'eau. Comme on sait, ce paradoxe attribué à Jean Buridan (1292-1363) n'apparaît dans aucune de ses œuvres, mais Aristote (Traité Du Ciel (295b 32) évoque un homme devant choisir entre de l'eau et de la nourriture. En réalité, beaucoup d'éléments du monde s'avèrent souvent incomparables, et les spécialistes de marketing jouent volontiers avec cette difficulté d'établir des comparaisons, pour mieux dissimuler la supériorité objective d'un produit concurrent. Nous ne tranchons pas sur le fond mais soulignons seulement que, si des relations de comparabilité existent, alors, nécessairement, des relations d'incomparabilité existent aussi, ne serait-ce que comme le négatif des précédentes.</footnote>
ment s'ils sont incomparables dans l'ordre faible strict correspondant.

**Définition 5.2** (Partitions ordonnées). Une partition d'un ensemble $S$ est une famille de sous-ensembles disjoints non vides de $S$ qui ont $S$ comme union. Une partition, associée à un ordre total sur les ensembles de la partition, donne une structure de partition ordonnée.

Une partition ordonnée d'un ensemble fini peut être écrite comme une suite finie d'ensembles de la partition : par exemple, les trois partitions ordonnées de l'ensemble $S = \{a, b\}$ sont :

$$ \{a\}, \{b\}; \quad \{b\}, \{a\} \text{ et } \{a, b\}. $$

Dans un ordre faible strict, les classes d'équivalence d'incomparabilité donnent une partition d'ensemble, dans laquelle les ensembles héritent d'un ordre total de leurs éléments, donnant lieu à une partition ordonnée. Dans l'autre sens, toute partition ordonnée donne lieu à un ordre faible strict dans lequel deux éléments sont incomparables lorsqu'ils appartiennent au même ensemble dans la partition, et héritent sinon de l'ordre des ensembles qui les contiennent.

On peut encore noter qu'on peut énumérer tous les ordres faibles sur un ensemble fini. On sait également que les semi-ordres généralisent les ordres faibles stricts, mais n'assument pas la transitivité de l'incomparabilité.

# 6 Graphes associés à un ensemble partiellement ordonné

**Définition 6.1.** Soit $P$ un ensemble partiellement ordonné, muni de la relation $<$, réflexive, antisymétrique, transitive. On dit que deux éléments $x$ et $y$ de $P$ sont comparables si $x < y$ ou $y < x$ (on peut aussi remplacer $<$ par la relation d'ordre large $\le$). Dans le cas contraire, c'est-à-dire lorsque deux éléments de $P$ sont incomparables, on a entre eux, comme précédemment, la relation $||$ dite «relation d'incomparabilité», réflexive, symétrique et transitive.

Quand $P$ est un ensemble partiellement ordonné (poset), on peut ainsi associer à $P$ deux graphes. L'un est appelé *graphe de comparabilité* de $P$ et l'autre *graphe d'incomparabilité* de $P$. Ces deux graphes ont les éléments de $P$ comme ensemble de
sommets. Dans le graphe de comparabilité, les éléments distincts $x$ et $y$ de $P$ sont adjacents lorsqu'ils sont comparables dans $P$. De même, $x$ et $y$ sont adjacents dans le graphe d'incomparabilité lorsqu'ils sont incomparables dans $P$. Nous allons nous intéresser plus précisément à ce dernier cas. Avant cela, introduisons les définitions suivantes :

**Définition 6.2** (coloration d'un graphe). La coloration des sommets (resp. des arêtes) d'un graphe $G = (X, U)$ correspond à l'affectation d'une couleur à chacun de ses sommets (resp. arêtes) de telle sorte que deux sommets (resp. arêtes) adjacents ne soient pas porteurs de la même couleur.

**Définition 6.3** (nombre chromatique d'un graphe). Un graphe est dit $p$-chromatique si ses sommets admettent une coloration en $p$ couleurs. On appelle nombre chromatique $\gamma(G)$ (resp. indice chromatique $q(G)$) le nombre minimum de couleurs distinctes nécessaires pour effectuer une coloration des sommets (resp. des arêtes) du graphe $G$.

**Définition 6.4** (clique dans un graphe). Soit $G = (X, U)$ un graphe. Un sous-ensemble de sommets $C \subset X$ de $G$ tel que deux sommets quelconques de $C$ soient reliés par une arête est nommé une clique.

**Définition 6.5** (graphe parfait). Soient $\gamma(G)$ le nombre chromatique d'un graphe $G$ et $\omega(G)$ le nombre maximum de sommets d'une clique. On dira qu'un graphe $G$ est $\gamma$-parfait si on a l'égalité :

$$ \gamma(G_A) = \omega(G_A) $$

pour tout sous-ensemble $A$ de sommets de $G$.

**Définition 6.6** (graphe de cordes ou string graph). Un graphe est dit «de cordes» (string graph en anglais) s'il est isomorphe au graphe de croisement d'un ensemble de cordes d'un cercle.

En 1950, Dilworth (voir [Dilworth 50]) a pu prouver que les graphes d'incomparabilité étaient des graphes parfaits, donc que le nombre chromatique d'un graphe d'incomparabilité est égal à son nombre de cliques (un résultat analogue pour les graphes de comparabilité avait précédemment été prouvé par Erdös et Szekeres (voir [Erdös 35])). En 1967, Gallai (voir [Galvin 94]) a donné une caractérisation des graphes d'incomparabilité en termes de sous-graphes induits interdits minimaux. On sait aussi que les graphes d'incomparabilité peuvent être reconnus dans un
temps polynomial (voir [Golumbic 80]). En 1983, Golumbic, Rotem et Urrutia (voir [Golumbic 83] et Lov'asz (voir [Lov'asz 83])) ont prouvé que tout graphe d'incomparabilité était également un graphe de cordes (string graph) (sur tout cela, voir [Fox 12]).

On trouvera dans la Fig. 5 un exemple de poset (A), son graphe de comparabilité (B) et son graphe d'incomparabilité (C).

<figure><img src="image_6.png" /><figcaption>FIGURE 5 – Poset, graphe de comparabilité, graphe d'incomparabilité</figcaption></figure>

# 7 Chaînes et antichaînes

**Définition 7.1 (chaîne-antichaîne).** Soit $S$ un ensemble partiellement ordonné (poset). Rappelons qu'une *chaîne* est un sous-ensemble totalement ordonné de $S$ ; une *antichaîne* est un sous-ensemble de $S$ dans lequel deux éléments distincts sont incomparables.

**Définition 7.2 (chaîne-antichaîne maximale).** Une chaîne (resp. une antichaîne) maximale est une chaîne (resp. une antichaîne) qui n'est pas un sous-ensemble propre d'une autre chaîne (resp. antichaîne). Alternativement, une chaîne $C$ est maximale dans un poset $(S, \le)$ si aucun élément de $S - C$ n'est comparable à un élément de $C$ ; une antichaîne $A$ est maximale si aucun élément de $S - A$ n'est incomparable à un élément de $A$.

Une autre définition de la longueur d'une chaîne consiste à dire qu'elle est simplement de la plus grande taille possible dans un poset.
**Définition 7.3.** Une chaîne (resp. une antichaîne) maximale est celle qui est de la plus grande taille possible. La taille de la chaîne la plus longue est connue sous le nom de *hauteur* d'un poset. La taille de la plus grande antichaîne est connue sous le nom de *largeur* d'un poset.

**Théorème 7.1.** Une chaîne maximale dans un poset fini non vide $S$ doit contenir un élément maximal (et aussi un élément minimal) de $S$.

**Théorème 7.2.** *L'ensemble des éléments maximaux d'un poset fini $S$ est une antichaîne maximale ; de même, l'ensemble des éléments minimaux d'un poset fini $S$ est une antichaîne maximale.*

**Théorème 7.3** (voir [Dilworth 50], [Galvin 94]). *Si $A$ est une plus grande antichaîne dans un poset fini $(S, \leq)$, alors il y a une partition de $S$ en chaînes $C_1 \cup C_2 \cup \dots C_n$ telle que $n = |A|$. De plus, chaque $C_i$ contient exactement un élément de $A$, et il n'y a pas de partition de $S$ en moins de $n$ chaînes.*

L'article original de Dilworth (voir aussi [Fulkerson 56]) couvre en fait le cas infini, du moins un cas infini très spécifique : un poset de largeur finie $k$, même s'il n'est pas lui-même fini, peut être partitionné en $k$ chaînes (éventuellement infinies).

Erdös a posé la question de savoir si le théorème de Dilworth est vrai pour des posets de largeur infinie : c'est-à-dire que si $(S, \leq)$ n'a pas de largeur finie, y a-t-il nécessairement une antichaîne dont les éléments peuvent être mis en correspondance biunivoque avec les chaînes dans une partition en chaînes de $S$ ? Étonnamment, la réponse est «non».

Le théorème de Dilworth se généralise en dimension infinie (voir [Perles 63]).

**Théorème 7.4** (Dual du théorème de Dilworth - voir [Mirsky 79]). *Si $C$ est une plus grande chaîne dans un poset fini $(S, \leq)$, alors il y a une partition de $S$ en antichaînes $A_1 \cup A_2 \cup \dots A_n$ tel que $n = |C|$. De plus, chaque $A_i$ contient exactement un élément de $C$, et il n'y a pas de partition de $S$ en moins de $n$ antichaînes.*

**Théorème 7.5** (Fraïssé - voir [Fraïssé 00]). *L'ensemble des antichaînes est un poset.*

Soit $X$ un poset ; nous définissons le poset des antichaînes noté $A(X)$ comme étant constitué de toutes les antichaînes de $X$, ordonnées par inclusion inverse. $A(X)$ pos-
sède un plus grand élément, à savoir l'antichaine vide denotée $\theta$, et (avec l'axiome de choix) des éléments minimaux, à savoir les antichaînes maximales de $X$ par rapport à l'inclusion.

$A(X)$ est bien fondé si $X$ est absolument libre.

Étant donné un poset $X$ finiment libre, on appelle «épaisseur» de $X$, notée $\text{Thick}(X)$ la hauteur de l'ensemble vide dans $A(X)$.

Il est clair que l'épaisseur est de 0 si et seulement si $X$ est l'ensemble vide ; l'épaisseur est de 1 si et seulement si $X$ est une chaîne non vide.

Étant donné un poset $X$ d'épaisseur $\alpha$ et un élément $u \in |X|$, alors la restriction de $X$ aux éléments $\ge u$ a une épaisseur $\le \alpha$ ; idem pour la restriction aux éléments $\le u$. L'égalité se produit souvent : pour le voir, il suffit de partager une chaîne non vide $C$ (épaisseur 1) entre l'intervalle initial $\le u$ et l'intervalle final $\ge u \pmod{C}$.

Étant donné un poset $X$ et un élément $u \in |X|$, le singleton $\{u\}$ constitue une antichaîne de $X$ ; de plus la hauteur $\text{Ht}(u)$ dans $X$ est inférieure à $\text{Ht}(X)$ ; plus précisément $\text{Ht}(X) = \text{Sup}(\text{Ht}(u) + 1)$ pour tous les éléments $u \in |X|$.

Soit $X_u$ le poset de $X$ restreint aux éléments $u$ tels que $u \pmod{X}$. Alors $\text{Thick}(X_u) < \text{Ht}(\{u\})$ dans $A(X)$, d'où $\text{Thick}(X_u) < \text{Ht}(\theta)$ dans $A(X)$ donc $\text{Thick}(X_u) < \text{Thick}(X)$.

**Théorème 7.6.** Le graphe d'incomparabilité d'une *n*-chaîne (chaîne contenant *n* éléments) est le graphe vide (null graph) $N_n$ (ou graphe sans arêtes).

*Démonstration.* Nous savons que les éléments d'une chaîne sont comparables, autrement dit, dans le graphe d'incomparabilité, aucune arête de la chaîne n'est adjacente à une autre. En conséquence, le graphe d'incomparabilité d'une chaîne est le graphe nul à $n$ sommets noté $N_n$ si la chaîne possède $n$ éléments. $\square$

Il est clair qu'une *n*-chaîne a pour graphe d'incomparabilité le graphe vide $N_n$, pour $n \ge 2$, lequel peut être conçu comme une *n*-antichaîne. En revanche, le graphe vide $N_n$ n'est pas nécessairement le graphe d'incomparabilité d'une *n*-chaîne.
# 8 Cas des treillis

Comme on l'a vu (Déf. 4.10), un treillis est un ensemble partiellement ordonné (po-set) dans lequel tout élément possède une même borne supérieure (plus petit des majorants) et une même borne inférieure (plus grand des minorants). La Fig. 6 en donne un exemple caractéristique.

<figure><img src="image_7.png" /><figcaption>FIGURE 6 – Un exemple de treillis</figcaption></figure>

La matrice d'adjacence $M(T)$ du diagramme de Hasse correspondant au treillis de la Fig. 6 est donnée dans la Table 1.

<table><caption>TABLE 1 – Matrice d'adjacence de $T$</caption><thead><tr><th></th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><th>a</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><th>b</th><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><th>c</th><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><th>d</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>e</th><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>f</th><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr></tbody></table>

La matrice $M_c(T)$, complémentaire de la précédente apparaît dans la Table 2.

La Fig. 7 montre le graphe complémentaire (A) et le graphe d'incomparabilité (B) du treillis $T$. Comme on peut le voir, le graphe d'incomparabilité de $T$ comprend 6 sommets et seulement 3 arêtes.

La table 3 donne la matrice $M'(T)$ du graphe d'incomparabilité de $T$ :
$$
M_c(T) =
\begin{array}{c|cccccc}
 & a & b & c & d & e & f \\
\hline
a & 0 & 0 & 0 & 1 & 1 & 1 \\
b & 0 & 0 & 1 & 0 & 1 & 1 \\
c & 0 & 1 & 0 & 0 & 0 & 1 \\
d & 1 & 0 & 0 & 0 & 1 & 0 \\
e & 1 & 1 & 0 & 1 & 0 & 0 \\
f & 1 & 1 & 1 & 0 & 0 & 0
\end{array}
$$

<figure><img src="image_8.png" /><figcaption>FIGURE 7 – Graphe complémentaire (A) et graphe d’incomparabilité (B) du diagramme de Hasse du treillis T</figcaption></figure>

Deux treillis non isomorphes peuvent avoir le même graphe d'incomparabilité (voir Fig. 8).

Comme le remarquent Wasadikar et Survase (voir [Wasadikar 12], il existe de nombreux articles qui relient la théorie des treillis et la théorie des graphes. Filipov (voir [Filipov 80]) aura sans doute été l'un des premiers à étudier les graphes de comparabilité d'ensembles partiellement ordonnés en définissant la contiguïté entre deux éléments d'un poset par la relation de comparabilité : a et b sont adjacents si $a \le b$ ou $b \le a$. Dans le même ordre d'idées, Duffus et Rival (voir [Duffus 77]) définissent le graphe de recouvrement d'un poset par la relation de recouvrement : a et b sont adjacents si $a \prec b$ ou $b \prec a$. Les articles de Gadenova (voir [Gadenova 80]), Bollobas et Rival (voir [Bollobas 79]) parlent des propriétés des graphes de recouvrement dérivés de treillis. Dans [Nimborkar 10], Nimbhorkar, Wasadikar et Pawar ont introduit des graphes sur un treillis $L$ avec $0$, en définissant la contiguïté de deux éléments $x, y \in L$ par la relation : $x \wedge y = 0$. Plus récemment, Bostjan Bresar et.al. (voir [Bresar 08]) ont eux-mêmes introduit des graphes de recouvrement qui sont des graphes d'incomparabilité de posets. Ils ont en particulier défini un graphe dans lequel l'ensemble
$$ M(T) = \begin{array}{c|cccc} & b & c & d & e \\ \hline b & 0 & 1 & 0 & 1 \\ c & 1 & 0 & 0 & 0 \\ d & 0 & 0 & 0 & 1 \\ e & 1 & 0 & 1 & 0 \end{array} $$

<figure><img src="image_9.png" /></figure>

A

<figure><img src="image_10.png" /></figure>

B

<figure><img src="image_11.png" /></figure>

C

<caption>FIGURE 8 – Treillis A et B non isomorphes ayant le même graphe d'incomparabilité C</caption>

des arêtes est l'union de l'ensemble des arêtes du graphe de recouvrement et du graphe d'incomparabilité correspondants. Bref, beaucoup de travaux portent sur ces questions depuis les années 1980.

Dans leur article, Wasadikar et Survase tracent tous les graphes avec un nombre d'arêtes $n \le 4$ qui sont des graphes d'incomparabilité associés à des treillis et donnent quelques propriétés simples de ces graphes sans les relier à des treillis particuliers. Nous allons au contraire montrer que certains types de treillis permettent de définir des propriétés supplémentaires, notamment les treillis booléens, qui permettent de calculer le nombre d'arêtes du graphe d'incomparabilité qui leur est associé.

## 9 Cas des treillis booléens

Comme on le sait, les structures booléennes (en liaison avec la théorie des ordres) revêtent une importance toute particulière (voir [Ponasse 79]; [Rhodes 15]).

Il est clair que l'ensemble booléen simple $U = \{0, 1\}$, muni de la relation d'ordre strict
< est le treillis booléen $T_1$. Son graphe associé peut être représenté par un segment vertical joignant les sommets 0 et 1. Sa matrice d'adjacence est la complémentaire de la matrice unitaire et son graphe d'incomparabilité (non connexe) se réduit à deux points, le point 0 et le point 1. Les treillis booléens produits donnent lieu à des constructions un peu plus complexes.

## 9.1 Treillis booléen produit à 4 éléments

Considérons maintenant le graphe $T_2$ suivant, qui est, pour $a, \bar{a} \ge 0$, et $a, \bar{a} \le 1$, isomorphe au treillis booléen construit sur l'ensemble $U^2 = \{0, 1\}^2$. Son diagramme de Hasse est représenté sur la Fig. 9.

<figure><img src="image_12.png" /><figcaption>FIGURE 9 – Diagramme de Hasse du treillis $T_2$</figcaption></figure>

En oubliant la relation d'ordre et en considérant son diagramme de Hasse associé comme un simple graphe, la matrice d'adjacence de $T_2$ peut être facilement dressée. Nous la représentons à la suite dans la table 4.

<table><caption>TABLE 4 – Matrice d'adjacence de $T_2$</caption><thead><tr><th></th><th>0</th><th>a</th><th>ā</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><th>a</th><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>ā</th><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>1</th><td>0</td><td>1</td><td>1</td><td>0</td></tr></tbody></table>

On obtient la matrice complémentaire en remplaçant, selon la procédure habituelle,
les 0 par des 1 et les 1 par des 0 sauf sur la diagonale. On obtient alors la matrice
de la Table 5.

$$
M_c(T_2) =
\begin{array}{c|cccc}
 & 0 & a & \bar{a} & 1 \\
\hline
0 & 0 & 0 & 0 & 1 \\
a & 0 & 0 & 1 & 0 \\
\bar{a} & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 0
\end{array}
$$

<caption>TABLE 5 – Matrice d’adjacence du complémentaire de T₂</caption>

Cette matrice est celle d'un graphe non connexe. On peut la représenter facilement en appliquant le théorème 1.2. Le graphe correspondant à $M_c(T)$ est indiqué dans la Fig. 10.

<figure><img src="image_13.png" /><figcaption>FIGURE 10 – Graphe du complémentaire de $T_2$</figcaption></figure>

Le graphe d'incomparabilité de $T_2$ s'obtient à partir de la matrice précédente et de son graphe associé, en éliminant les sommets qui sont dans une relation d'ordre (en l'occurrence les sommets 0 et 1). Le graphe d'incomparabilité du treillis booléen se réduit alors à la composante connexe $(a, \bar{a})$. Comme il n'existe qu'un seul graphe à 2 sommets (noté usuellement $K_2$), on peut voir immédiatement que $K_2 = G(T_2)$ est nécessairement – entre autres – le graphe d'incomparabilité d'un treillis booléen.

## 9.2 Treillis booléen à $2^3 = 8$ éléments

Considérons le diagramme de Hasse du treillis booléen $T_3$ isomorphe à $B^3 = \{0, 1\}^3$, où $|X| = 8$ et $|U| = 12$. Ce treillis très connu est représenté par le graphe de la Fig. 11 dans laquelle, pour tout sommet $x$, $\bar{x}$ signifie le complémentaire de $x$.

La matrice d'incidence sommets-sommets de $T_3$ est représentée sur la table 6 :
<figure><img src="image_14.png" /><figcaption>FIGURE 11 – Diagramme de Hasse de $T_3$</figcaption></figure>

<table><caption>TABLE 6 – Matrice d'adjacence de $T_3$</caption><thead><tr><th></th><th>0</th><th>a</th><th>c</th><th>b&#773;</th><th>b</th><th>c&#773;</th><th>a&#773;</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><th>a</th><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><th>c</th><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><th>b&#773;</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><th>b</th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><th>c&#773;</th><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>a&#773;</th><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>1</th><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td></tr></tbody></table>

Le graphe complémentaire a les propriétés suivantes : le nombre $|X|$ des sommets de $D[X, \bar{U}]$ est évidemment $|X| = 8$. Le nombre $|\bar{U}|$ de ses arcs est :

$$|\bar{U}| = \binom{8}{2} - 12 = 28 - 12 = 16.$$

En remplaçant les 1 par des 0 et les 0 par des 1 sauf sur la diagonale, nous obtenons facilement la matrice $M_c(T_3)$ de $D[X, \bar{U}]$ représentée sur la table 7.

D'où le graphe associé, qui peut prendre plusieurs configurations (voir Fig. 12).

**Graphe d'incomparabilité** On passe au graphe d'incomparabilité comme précédemment, en enlevant les sommets qui sont dans une relation d'ordre (en l'occurrence, 0 et 1), ainsi que les arêtes afférentes. Le graphe étant régulier de degré 4, il y aurait
<table><caption>TABLE 7 – Matrice d'adjacence du complémentaire de $T_3$</caption><thead><tr><th></th><th>0</th><th>a</th><th>c</th><th>b&#773;</th><th>b</th><th>c&#773;</th><th>a&#773;</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><th>a</th><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><th>c</th><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><th>b&#773;</th><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td></tr><tr><th>b</th><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><th>c&#773;</th><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><th>a&#773;</th><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><th>1</th><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

<figure><img src="image_15.png" /><figcaption>FIGURE 12 – Graphe du complémentaire de $T_3$</figcaption></figure>

en principe 8 arêtes à enlever, mais 0 et 1 étant reliés par une relation d'ordre, ils ont une arête en commun. Il faut donc enlever 8 - 1 = 7 arêtes. Etant donné que le graphe complémentaire de $T_3$ possède 8 sommets et 16 arêtes, le graphe d'incomparabilité aura donc 6 sommets et 16 - 7 = 9 arêtes (voir Fig. 13).

Au plan matriciel, cela revient à enlever la première et la dernière ligne, ainsi que la première et la dernière colonne de $M_c(T_3)$ et à remplacer cette matrice par une matrice $M'(T_3)$ à 6 lignes et 6 colonnes (voir Table 8).

## 9.3 Cas du treillis booléen à $2^4 = 16$ éléments

Le treillis booléen $T_4$ isomorphe à $\{0, 1\}^4$ est représenté sur la Fig. 14.

La matrice d'adjacence du graphe associé est celle de la Table 9.
<figure><img src="image_16.png" /><figcaption>FIGURE 13 – Graphe d’incomparabilité de $T_3$</figcaption></figure>

<table><caption>TABLE 8 – Matrice d'adjacence du graphe d'incomparabilité de $T_3$</caption><thead><tr><th></th><th>a</th><th>c</th><th>b&#773;</th><th>b</th><th>c&#773;</th><th>a&#773;</th></tr></thead><tbody><tr><th>a</th><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><th>c</th><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><th>b&#773;</th><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><th>b</th><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><th>c&#773;</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>a&#773;</th><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr></tbody></table>

La matrice du complémentaire du graphe de $T_4$ est représentée dans la Table 10.

Pour trouver le graphe d'incomparabilité de $T_4$, nous allons, cette fois-ci, procéder différemment : dans la matrice précédente – que nous réduisons à la demi-matrice de la Table 11 (puisqu'elle est symétrique par rapport à la deuxième diagonale), nous barrons les 1 qui correspondent à des paires de sommets pris dans une relation d'ordre. Nous comptons alors les 1 barrés et les soustrayons au nombre total d'arêtes du graphe complémentaire pour trouver le nombre d'arêtes du graphe d'incomparabilité. En l'occurrence, nous obtenons : 88 - 33 = 55.
<figure><img src="image_17.png" /><figcaption>FIGURE 14 – Diagramme de Hasse de $T_4$</figcaption></figure>

Nous pouvons alors tracer le graphe d'incomparabilité de $T_4$ qui comprend 14 sommets et 55 arêtes (voir Fig. 15).

<figure><img src="image_18.png" /><figcaption>FIGURE 15 – Graphe d'incomparabilité de $T_4$</figcaption></figure>

## 9.4 Généralisation à tous les treillis booléens ou hypercubes

On généralise aisément la procédure à tous les treillis booléens. À partir de $T_4$, avec $|T_4| = 2^4$ éléments, les graphes associés aux $T_n$ sont ce qu'on appelle des hypercubes.
<table><caption>TABLE 9 – Matrice d'adjacence de $T_4$</caption><thead><tr><th></th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th><th>g</th><th>g&#773;</th><th>f&#773;</th><th>e&#773;</th><th>d&#773;</th><th>c&#773;</th><th>b&#773;</th><th>a&#773;</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>a</th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>b</th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>c</th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>d</th><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>e</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><th>f</th><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><th>g</th><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><th>g&#773;</th><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><th>f&#773;</th><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><th>e&#773;</th><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><th>d&#773;</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><th>c&#773;</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><th>b&#773;</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><th>a&#773;</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><th>1</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr></tbody></table>

**Théorème 9.1.** Le nombre $|U|$ d'arêtes d'un hypercube à $2^n$ sommets est donné par la formule :

$$|U| = n \times 2^{n-1}.$$

**Théorème 9.2.** Le nombre $|U'|$ d'arêtes du graphe d'incomparabilité d'un treillis booléen à $n$ sommets s'obtient en ôtant au cardinal $\overline{U}$ du nombre des arêtes de son graphe complémentaire la somme totale des $n$-faces ($n \ge 2$.) du $n$-cube correspondant.

*Démonstration.* Soit $T_n$ un treillis booléen à $2^n$ éléments, et $|U|$ le nombre d'arêtes de son graphe complémentaire. Pour trouver le nombre $|U'|$ d'arêtes du graphe d'incomparabilité de $T_n$, il faut enlever au graphe $G(X, \overline{U})$ complémentaire de $T_n$ les paires ordonnées de sommets non-adjacents dans $T_n$. Celles-ci correspondent aux $n$-faces successives du $n$-cube associé à $T_n$. Soit $k$ la dimension des faces. Etant donné un $n$ fixé, pour chaque valeur de $k$, le nombre de ces faces est $N_{n,k} = 2^{n-k} \binom{n}{k}$ (voir [Coxeter 73], 122; [Sommerville 29], 29). On a alors :

$$|U'| = |\overline{U}| - \sum N_{n,k}.$$
<table><caption>TABLE 10 – Matrice d'adjacence du complémentaire de $T_4$</caption><thead><tr><th></th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th><th>g</th><th>g&#773;</th><th>f&#773;</th><th>e&#773;</th><th>d&#773;</th><th>c&#773;</th><th>b&#773;</th><th>a&#773;</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>a</th><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>b</th><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>c</th><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>d</th><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>e</th><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><th>f</th><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><th>g</th><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><th>g&#773;</th><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><th>f&#773;</th><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><th>e&#773;</th><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>d&#773;</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td></tr><tr><th>c&#773;</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><th>b&#773;</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><th>a&#773;</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><th>1</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

□

Quelques formules particulières de calcul du nombre de faces d'un $n$-cube :

$$ \text{– 2-faces : } n(n - 1)2^{n-3}; $$

$$ \text{– 3-faces : } n(n - 1)\frac{n-2}{3}2^{n-4}; $$

$$ \text{– 4-faces : } n(n - 1)(n - 2)\frac{n-3}{3}2^{n-7}; $$

Dans le cas général, il suffit de calculer $N_{n,k}$.

Exemples :

Pour le treillis $T_3$ (3-cube), on a, par les formules ci-dessus, 6 2-faces et 1 3-face, ce qui donne $6+1=7$. Comme $|\overline{U}|=16$, on vérifie qu'on obtient $|U'| = 16 - 7 = 9$.

Pour le treillis $T_4$ (4-cube), on a, par les mêmes formules, 24 2-faces, 8 3-faces et 1 4-faces, ce qui donne $24 + 8 + 1 = 33$. Sachant qu'ici $|\overline{U}| = 88$, on obtient $|U'| = 88 - 33 = 55$.

Pour le treillis $T_5$ (5-cube), on obtiendrait : 80 2-faces, 40 3-faces, 10 4-faces et 1
<table><caption>TABLE 11 – Demi-matrice du graphe d’incomparabilité de $T_4$</caption><thead><tr><th>0</th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th><th>g</th><th>g&#773;</th><th>f&#773;</th><th>e&#773;</th><th>d&#773;</th><th>c&#773;</th><th>b&#773;</th><th>a&#773;</th><th>1</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td></tr><tr><td>a</td><td></td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>&#x2219;</td><td>&#x2219;</td><td>1</td><td>&#x2219;</td><td>&#x2219;</td></tr><tr><td>b</td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>&#x2219;</td><td>&#x2219;</td><td>1</td><td>&#x2219;</td><td>&#x2219;</td></tr><tr><td>c</td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>&#x2219;</td><td>1</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td></tr><tr><td>d</td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td><td>&#x2219;</td></tr><tr><td>e</td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>&#x2219;</td></tr><tr><td>f</td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>&#x2219;</td></tr><tr><td>g</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>&#x2219;</td></tr><tr><td>g&#773;</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>&#x2219;</td></tr><tr><td>f&#773;</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>&#x2219;</td></tr><tr><td>e&#773;</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>&#x2219;</td></tr><tr><td>d&#773;</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td></tr><tr><td>c&#773;</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>b&#773;</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>0</td></tr><tr><td>a&#773;</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>0</td></tr><tr><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td></tr></tbody></table>

5-face, ce qui donne : $80+40+10+1 = 131$. Sachant qu’ici $|\overline{U}| = 416$, on obtient $|U'| = 416 - 131 = 285$.

Enfin, pour le treillis $T_6$ (6-cube), on obtiendrait : 240 2-faces, 160 3-faces, 60 4-faces et 12 5-faces et 1 6-faces, ce qui donne : $240+160+60+12+1 = 473$. Sachant qu’ici $|\overline{U}| = 1824$, on obtient $|U'| = 1824 - 473 = 1351$.

Voici (voir Table 12) un récapitulatif des caractéristiques des $T_n$, des graphes complémentaires et des graphes d’incomparabilité correspondants (figurent successivement dans la matrice, les treillis $T_n$, les ensembles booléens produits correspondants $B^n$, le nombre de sommets $|X|$ des graphes associés, le nombre d’arêtes $|U|$, le nombre d’arêtes $\overline{U}$ des graphes complémentaires, enfin, le nombre de sommets $|X'|$ et le nombre d’arêtes $U'$ des graphes d’incomparabilité correspondants.

Notons pour finir que, dans tout poset (et cela vaut, bien sûr, pour les treillis), la connaissance du nombre $N$ d’arêtes du graphe d’incomparabilité du poset permet évidemment de calculer le nombre d’arêtes du graphe de comparabilité. Si nous apportons $V$ le nombre d’arêtes correspondant aux relations d’ordre non explicites dans le poset $P$), il est clair que le nombre total de paires ordonnées dans $P$, autrement
<table><caption>TABLE 12 – Caractéristiques de quelques treillis, graphes complémentaires et graphes d’incomparabilité</caption><thead><tr><th>T<sub>n</sub></th><th>B<sup>n</sup></th><th>|X|</th><th>|U|</th><th>|U&#773;|</th><th>|X'|</th><th>|U'|</th></tr></thead><tbody><tr><td>T<sub>2</sub></td><td>{0, 1}<sup>2</sup></td><td>4</td><td>4</td><td>2</td><td>2</td><td>1</td></tr><tr><td>T<sub>3</sub></td><td>{0, 1}<sup>3</sup></td><td>8</td><td>12</td><td>16</td><td>6</td><td>9</td></tr><tr><td>T<sub>4</sub></td><td>{0, 1}<sup>4</sup></td><td>16</td><td>32</td><td>88</td><td>14</td><td>55</td></tr><tr><td>T<sub>5</sub></td><td>{0, 1}<sup>5</sup></td><td>32</td><td>80</td><td>416</td><td>30</td><td>285</td></tr><tr><td>T<sub>6</sub></td><td>{0, 1}<sup>6</sup></td><td>64</td><td>192</td><td>1824</td><td>62</td><td>1351</td></tr></tbody></table>

dit, le cardinal de l'ensemble *E* des arêtes du graphe de comparabilité de *P* est :

$$|E| = |U| + |V|.$$

Et l'on a évidemment :

$$|U| + |V| = \binom{n}{2} - N.$$

# 10 Incomparabilité dans les treillis modulaires, distributifs, complémentés et pseudocomplémentés

Indépendamment des treillis de Boole, il existe, comme on le sait, différentes classes de treillis, avec chaque fois des propriétés particulières (modularité, distributivité, complémentation ou pseudocomplémentation...). Nous en donnerons quelques échantillons ici en montrant chaque fois, sur des exemples, à quoi ressemblent les structures complémentaires auxquelles ils donnent lieu.

## 10.1 Treillis modulaires

**Définition 10.1** (Treillis modulaire). Un treillis *T* est dit «modulaire» si :

$$\forall x, y, z \in T, (x \leq y) \Rightarrow (x \lor (y \land z) = (x \lor y) \land z).$$

Des exemples de treillis modulaires sont donnés dans la Fig. 16. On vérifie la propriété de modularité pour tous les couples d'éléments de ces treillis.
<figure><img src="image_19.png" /><figcaption>FIGURE 16 – Exemples de treillis modulaires</figcaption></figure>

Les graphes d'incomparabilité des treillis A, B et C sont donnés dans la Fig.17.

Notons qu'une chaîne étant un treillis modulaire, le complémentaire d'un treillis modulaire (lorsqu'il s'agit d'une chaîne) est le graphe vide.

## 10.2 Treillis distributifs mais non complémentés

**Définition 10.2** (treillis distributif). Un treillis $T$ est dit «distributif» si :

$$ \forall x, y, z \in T, x \wedge (y \vee z) \Rightarrow (x \wedge y) \vee (x \wedge z). $$

La Fig. 18 présente un treillis distributif mais non complémenté, le graphe $G(A)$ du complémentaire de A et le graphe d'incomparabilité $G'(A)$.

Les matrices d'adjacences du treillis (A) et de son graphe complémentaire (B) sont données dans les Tables 13 et 14.

## 10.3 Treillis complémentés mais non distributifs

Un treillis $T$ est dit «complémenté» s'il possède un élément nul 0 et un élément universel 1 et si tout élément $x$ de $T$ possède au moins un complément noté $\bar{x}$. Dans
<figure><img src="image_20.png" /><figcaption>FIGURE 17 – Graphes d'incomparabilité de quelques treillis modulaires</figcaption></figure>

<table><caption>TABLE 13 – Matrice d'adjacence du treillis A</caption><thead><tr><th></th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>a</th><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><th>b</th><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><th>c</th><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><th>d</th><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><th>1</th><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td></tr></tbody></table>

les treillis distributifs, quand le complément d'un élément existe, il est unique. Les treillis booléens sont ainsi des treillis distributifs et complémentés. Mais ce n'est pas le cas des autres treillis.

Considérons, par exemple, le treillis $T$ de la Fig. 19, qui n'est pas modulaire, et donc pas distributif (car tous les treillis distributifs sont modulaires). Sa particularité est que l'élément $b$ possède deux compléments $(a$ et $c$).

Le calcul montre que nous avons très exactement :

$$ \bar{a}^1 = b, \quad \bar{b}^1 = a, \quad \bar{b}^2 = c, \quad \bar{c}^1 = b, \quad \bar{0} = 1, \quad \bar{1} = 0. $$

Les matrices d'adjacence de $T$ et de son graphe complémentaire sont données dans les Tables 15 et 16.

Les graphes complémentaires et d'incomparabilité de $T$ sont donnés dans la Fig. 20.
<figure><img src="image_21.png" /><figcaption>FIGURE 18 – Treillis distributif (A), graphe complémentaire G(A) et graphe d'in-
comparabilité G'(A)</figcaption></figure>

<table><caption>TABLE 14 – Demi-matrice d'adjacence du graphe complémentaire du treillis A</caption><thead><tr><th></th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>a</th><td></td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><th>b</th><td></td><td></td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><th>c</th><td></td><td></td><td></td><td>0</td><td>0</td><td>1</td></tr><tr><th>d</th><td></td><td></td><td></td><td></td><td>0</td><td>0</td></tr><tr><th>1</th><td></td><td></td><td></td><td></td><td></td><td>0</td></tr></tbody></table>

On remarque que, dans les treillis complémenté, le graphe d'incomparabilité réunit précisément les compléments qui ne sont pas pris dans la relation d'ordre du treillis.

## 10.4 Treillis pseudo-complémentés

**Définition 10.3 (inf-pseudocomplément).** Soit $T$ un treillis avec un plus petit élé-
ment noté $0$. L'élément $t$ de $T$ possède ce qu'on appelle un «inf-pseudocomplément»,
noté $g(t)$, si $g(t)$ est le plus grand élément de l'ensemble des $x \in T$ tels que $x \wedge t = 0$.

**Définition 10.4.** On dira que $T$ est inférieurement pseudocomplémenté si tout élé-
ment de $T$ a un inf-pseudocomplément.
<figure><img src="image_22.png" /><figcaption>FIGURE 19 – Treillis complémenté</figcaption></figure>

$$ M(T) = \begin{vmatrix} 0 & a & b & c & 1 \\ 0 & 1 & 1 & 0 & 0 \\ a & 1 & 0 & 0 & 1 \\ b & 1 & 0 & 0 & 1 \\ c & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \end{vmatrix} $$

<caption>TABLE 15 – Matrice d'adjacence du treillis A</caption>

**Définition 10.5.** Duailement un treillis $T$, avec un plus grand élément noté $1$, est dit *supérieurement pseudocomplémenté* si pour tout $t \in T$, l'ensemble des $x \in T$ tels que $x \lor t = 1$ a un plus petit élément appelé le *sup-pseudocomplément* de $t$.

**Définition 10.6.** Enfin on appellera *treillis pseudocomplémenté* un treillis $B$ la fois inférieurement et supérieurement pseudocomplémenté$^6$.

Deux classes de treillis inférieurement pseudocomplémentés ont été particulièrement étudiées par les mathématiciens.

1. D'abord, depuis Glivenko (voir [Glivenko 29]), les treillis brouweriens (dits aussi implicatifs, ou de Heyting, ou pseudobooléens). Ce sont les treillis «relativement inférieurement pseudocomplémentés». Ils sont distributifs et, lorsqu'ils sont complets, infiniment inf-distributifs (voir [Birkhoff 40]).

<footnote n="6">6. On notera que, dans la littérature sur les treillis, «treillis pseudocomplémenté» signifie souvent «treillis inférieurement pseudocomplémenté».</footnote>
$$ M(G(T)) = \begin{array}{c|ccccc} & 0 & a & b & c & 1 \\ \hline 0 & 0 & 0 & 0 & \mathcal{I} & \mathcal{I} \\ a & & 0 & 1 & 0 & \mathcal{I} \\ b & & & 0 & 1 & 0 \\ c & & & & 0 & 0 \\ 1 & & & & & 0 \end{array} $$

<figure><img src="image_23.png" /><figcaption>FIGURE 20 – Graphes complémentaire et d'incomparabilité de T</figcaption></figure>

2. Ensuite, après Stone (voir [Stone 37]), les treillis «distributifs inférieurement pseudocomplémentés» vérifiant la condition :

$$ g(x \wedge y) = gx \vee gy. $$

On les appelle souvent «treillis de Stone». On trouvera dans Grätzer (voir [Grätzer 78]) et surtout dans Varlet (voir [Varlet 63]) l'exposé des résultats connus sur les treillis inférieurement pseudocomplémentés et notamment sur les deux classes évoquées ci-dessus (voir [Chamni 92]).

Dans ce qui suit, nous nous bornerons à donner deux exemples de ces treillis avec leurs graphes complémentaires et leurs graphes d'incomparabilité associés. La Fig. 21 donnent les diagrammes de Hasse d'un treillis inf-pseudocomplémenté (A) et d'un treillis pseudocomplémenté (B).

Les Tables 17 et 18 donnent les matrices d'adjacence de (A) et de son graphe complémentaire. Comme d'habitude, les 1 barrés permettent d'ôter les couples d'éléments pris dans une relation d'ordre, ce qui permet, à la suite (voir Fig. 22) de tracer les
<figure><img src="image_24.png" /><figcaption>FIGURE 21 – Treillis inf-pseudocomplémenté (A) et treillis pseudocomplémenté (B) graphes complémentaires et d'incomparabilité de (A).</figcaption></figure>

$$M(A) = \begin{vmatrix} 0 & a & b & c & d & e & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ a & 1 & 0 & 0 & 1 & 1 & 0 \\ b & 1 & 0 & 0 & 0 & 1 & 1 \\ c & 0 & 1 & 0 & 0 & 0 & 1 \\ d & 0 & 1 & 1 & 0 & 0 & 1 \\ e & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 \end{vmatrix}$$

<caption>TABLE 17 – Matrice d'adjacence du treillis A</caption>

Les tables 19 et 20 donnent les matrices d'adjacence du treillis (B) pseudocomplémenté et de son graphe complémentaire.

Les graphes complémentaire et d'incompatibilité de (B) sont donnés dans la Fig. 23.

Au terme de l'étude de ces exemples, nous voyons que les treillis non booléens n'étant pas des hypercubes, il n'est plus possible d'appliquer la formule de calcul du nombre des *n*-faces. Les graphes d'incomparabilité de ces treillis n'en contiennent pas moins des cellules que l'on peut dénombrer. Au final, on peut donc parfaitement calculer le nombre d'arêtes de ces graphes et ainsi préciser leur structure.
$$
M(G(A)) =
\begin{array}{c|cccccc}
 & 0 & a & b & c & d & e & 1 \\
\hline
0 & 0 & 0 & 0 & \mathcal{A} & \mathcal{A} & \mathcal{A} & \mathcal{A} \\
a & & 0 & 1 & 0 & 0 & 1 & \mathcal{A} \\
b & & & 0 & 1 & 0 & 0 & \mathcal{A} \\
c & & & & 0 & 1 & 1 & 0 \\
d & & & & & 0 & 1 & 0 \\
e & & & & & & 0 & 0 \\
1 & & & & & & & 0
\end{array}
$$

<figure><img src="image_25.png" /><figcaption>FIGURE 22 – Graphes complémentaires et d’incomparabilité de (A)</figcaption></figure>

11 Cas des hypergraphes et des matroïdes

On sait que la matrice d'incidence d'un hypergraphe $H(X, \mathcal{E})$ (voir [Berge 70], 373) est une matrice $((a_i^j))$ avec $m$ vecteurs-colonnes représentant les arêtes, $n$ vecteurs-lignes représentant les sommets, et des coefficients :

$$
a_j^i = \begin{cases} 1, & \text{si } x_j \in E_i; \\ 0, & \text{si } x_j \notin E_i. \end{cases}
$$

L'hypergraphe associé à un matroïde peut être défini de la même façon. Soit, par
<table><caption>TABLE 19 – Matrice d'adjacence du treillis A</caption><thead><tr><th></th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>a</th><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><th>b</th><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><th>c</th><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><th>d</th><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><th>e</th><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><th>f</th><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><th>1</th><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td></tr></tbody></table>

<table><caption>TABLE 20 – Demi-matrice d'adjacence du graphe complémentaire du treillis A</caption><thead><tr><th></th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>a</th><td></td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><th>b</th><td></td><td></td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><th>c</th><td></td><td></td><td></td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td></tr><tr><th>d</th><td></td><td></td><td></td><td></td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><th>e</th><td></td><td></td><td></td><td></td><td></td><td>0</td><td>0</td><td>1</td></tr><tr><th>f</th><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>0</td></tr><tr><th>1</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td></tr></tbody></table>

exemple, le matroïde $M(X, \mathcal{E})$ suivant, avec :

$$X = \{x_1, x_2, x_3, x_4, x_5\},$$

$$\mathcal{E} = \{e_1, e_2, e_3, e_4, e_5, e_6\},$$

et :

$$e_1 = \{x_1, x_5\}, \quad e_2 = \{x_1, x_2\}, \quad e_3 = \{x_3, x_4\},$$

$$e_4 = \{x_1, x_2, x_5\}, \quad e_5 = \{x_2, x_3, x_4\}, \quad e_6 = \{x_3, x_4, x_5\}.$$

Ce matroïde est représenté sur la Fig. 24.

La matrice sommets-arêtes associée à $M(X, \mathcal{E})$ est représentée sur la Table 21.

Nous pourrions, bien sûr, remplacer, dans cette matrice, les 1 par des 0 et les 0 par des 1. Mais la matrice du matroïde $M'(X, \mathcal{E})$ obtenue serait, à une permutation des colonnes près, identique à M. On aurait, en l'occurrence :

$$e'_1 = e_5, e'_2 = e_6, e'_3 = e_2, e'_4 = e_3, e'_5 = e_1, e'_6 = e_2.$$
<figure><img src="image_26.png" /><figcaption>FIGURE 23 – Graphes complémentaire et d'incomparabilité de (B)</figcaption></figure>

<table><caption>TABLE 21 – Matrice sommet-arête du matroïde $M(X, \mathcal{E})$</caption><thead><tr><th></th><th>e<sub>1</sub></th><th>e<sub>2</sub></th><th>e<sub>3</sub></th><th>e<sub>4</sub></th><th>e<sub>5</sub></th><th>e<sub>6</sub></th></tr></thead><tbody><tr><th>x<sub>1</sub></th><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><th>x<sub>2</sub></th><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><th>x<sub>3</sub></th><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><th>x<sub>4</sub></th><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><th>x<sub>5</sub></th><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td></tr></tbody></table>

Autrement dit, l'opération reviendrait tout simplement à changer la dénomination des arêtes. À ce changement près, le matroïde obtenu aurait une structure tout à fait comparable au matroïde de départ. Mutatis mutandis, on aurait ici l'équivalent d'un graphe autocomplémenté.

Trouver un véritable complémentaire pour le matroïde $M'(X, \mathcal{E})$ supposerait au contraire l'existence d'autres combinaisons de sommets définissant ainsi d'autres arêtes. On peut facilement calculer que le nombre des 2-arêtes possibles est $\binom{5}{2} = 10$ et que le nombre des 3-arêtes possibles est $\binom{5}{3} = 10$. Le nombre $N$ des matroïdes possibles est alors : $N = 10 \times 10 = 100$. Un matroïde du type de celui de l'exemple étant donné, il y a donc 99 complémentaires !

La notion de «complémentarité», dans ce contexte, n'a donc plus du tout le même sens. Ajoutons que la relation $\text{ordre} \subset$ étant définie sur les arêtes, elle est fixée
<figure><img src="image_27.png" /><figcaption>FIGURE 24 – Le matroïde $M(X, \mathcal{E})$</figcaption></figure>

par leur contenu et ne peut être modifiée. On ne peut donc pas définir de relation
complémentaire d'incomparabilité.

## 12 Note sur les complexes simpliciaux

Excepté dans les cas où le complexe simplicial est un simple graphe (2-complexe),
dans le cas où il est un *-cube et dans celui où il est un complexe d'ordre identifié à
l'ensemble des chaînes d'un poset, il n'est pas possible de trouver un complémentaire
unique et la situation est encore plus complexe que pour les hypergraphes ou les
matroïdes.

## 13 Conclusion

Les structures complémentaires des structures que nous avons coutume de privilégier (graphes, ensembles partiellement ordonnés ou posets, chaînes, treillis...), quoique souvent (mais pas toujours) plus complexes que les structures que nous retenons, ne nous mettent pas pour autant en présence d'un désordre. Elles font plutôt surgir des ordres ou, disons, des organisations complémentaires qui peuvent avoir leur intérêt propre, y compris sur le plan pratique : par exemple, les antichaînes sont d'une très
grande utilité en informatique. Elles constituent des structures de données efficaces en *model checking* (ou «vérification de modèles»). Mais, au-delà, et à l'inverse, ces structures alternatives suggèrent que leur dualité avec les structures plus simples ou plus connues permettent de se ramener à celles-ci par passage à la complémentarité ou à l'incomparabilité. On simplifie alors la représentation (souvent complexe) des relations décelées. Ajoutons qu'on gagne toujours à expliciter des relations inaperçues, qui suggèrent souvent des possibilités inédites de pensée ou d'action.

# 14 Appendice

On peut prolonger ces remarques par des considérations plus philosophiques : la voie d'une connaissance par complémentarité ou négation de l' existant phénoménal a été explorée depuis la plus lointaine antiquité dans ce courant de pensée qu'on appelle la «théologie négative». Selon la remarque de Philon d'Alexandrie (-20-45), le plus célèbre philosophe de l'école judéo-platonicienne, Dieu transcendant toute connaissance reste en principe à jamais indicible (arrêtos) et incompréhensible (akatalêptos). On ne peut donc pas dire ce qu'Il est, on ne peut dire que ce qu'Il n'est pas. On retrouvera cette thèse plus tard chez Clément d'Alexandrie (~150-~215) et chez Grégoire de Nysse (~335-~395), l'un des pères «cappadociens», et elle sera surtout défen-due par le Pseudo-Denys l'Aréopagite, un auteur chrétien du VIe siècle, par ailleurs héritier du néoplatonisme (Plotin, Porphyre de Tyr, Jamblique et Damascios)(voir [Vannier 98]). Se dégage ainsi une voie dite «apophatique» (du grec «apophasis», négation) dont l'origine lointaine est sans doute le *Parménide* de Platon. Comme dans le cas d'un fruit dont on atteint le noyau en en retranchant la chair, elle vise à décrire ce qu'on ne connaît pas et qu'on ne peut pas connaître en alignant des négations de ce qu'on connaît<fnref n="7" />.

<footnote n="7">7. Plusieurs précisions doivent tout de même être apportées à cette présentation : d'abord il ne s'agit pas absolument de chercher à connaître Celui qui transcende toute chose, il s'agit surtout de *s'unir* à Lui; ensuite, l'usage de la négation s'applique non seulement au discours (et à ses structures prédicatives) mais aux mots eux-mêmes, ce qui induit des oxymores ou contradictions dans les termes qui s'approchent de formules poétiques. Ainsi chez Denys l'Aréopagite – qui reprend en cela Grégoire de Nysse –, la fameuse «obscurité très lumineuse d'un silence plein d'enseignements profonds : obscurité merveilleuse qui rayonne en splendides éclairs, et qui, ne pouvant être ni vue ni saisie, inonde de la beauté de ses feux les esprits saintement aveuglés» (voir [Denys L'Aréopagite 46], 276). Cet usage de la contradiction sera ultérieurement systématisé par N. de Cues; enfin, l'idée d'un dieu qui serait le complémentaire du complémentaire (puisqu'il n'est accessible ni aux sens ni à l'entendement) doit être modérée. En réalité, pour le pseudo-Denys, il n'est rien de ce qui est, mais il n'est rien non plus de ce qui n'est pas, et, en ce sens, non seulement au-dessus de toutes</footnote>
Cette tradition de pensée qui conduira ultérieurement à la mystique rhénane des XIIIe-XIVe siècles – notamment Maître Eckhart (1260-1328) et son disciple Tauler – puis à la mystique flamande (Hadewijch d’Anvers, Ruysbroek) a au départ, comme on le voit, un fond de rationalité. La présente étude, cependant, fait apparaître un certain nombre de ses limites, brièvement évoquées dans un précédent ouvrage (voir [Parrochia 91¹]) et que nous nous permettrons, pour finir, d’énumérer.

Admettons, comme le voulait Dipert (voir [Dipert 97], que la structure du monde puisse être celle d'un graphe (asymétrique en l'occurrence). Cette thèse, bien que beaucoup discutée (voir notamment Shackel ([Shackel 11], 11) et [Oderberg 11] permet peut-être d'apprécier plus précisément la démarche de la théologie négative en lui fixant un cadre bien défini. Pour qu'on puisse définir le complémentaire de quoi que ce soit, il faut en effet que ce complémentaire existe, c'est-à-dire que la pensée puisse être associée à un espace bien complémenté. Or la théorie mathématique des ordres révèle ici différents problèmes :

1. Certains graphes, dit auto-complémentés (self-complemented) ont pour complémentaire la même structure à la permutation près des labels indexant les sommets du graphe. Si la structure du monde était ainsi auto-complémentée, non seulement il n'y aurait évidemment nul au-delà possible, mais le mouvement de la connaissance serait pris dans un espace fermé. Le père du structuralisme, Claude Lévi-Strauss, a jadis soutenu une telle thèse avec beaucoup de clarté : «L'Univers ayant signifié bien avant qu'on ne commence à savoir ce qu'il signifiait... il résulte aussi qu'il a signifié, dès le début, la totalité de ce que l'humanité peut s'attendre à en connaître. Ce qu'on apporte le progrès de l'esprit humain et, en tout cas, le progrès de la connaissance scientifique, n'a pu et ne pourra jamais consister qu'à rectifier des découpages, procéder à des regroupements, définir des appartenances et découvrir des ressources neuves, au sein d'une totalité fermée et complémentaire avec elle-même» (voir [Lévi-Strauss 50], 30)<fnref n="8" />. Il est évident que, dans un tel cas, le négatif de ce qui existe n'étant autre que

<footnote>nos affirmations, mais au-dessus de toutes nos négations aussi. En tout cas, «on ne doit faire de
lui ni affirmation ni négation absolue» (voir [Denys L'Aréopagite 46] 286). On voit donc que Denys
oscille ici entre la définition de ce qu'on appellerait aujourd'hui un *ordre faible* et celle de ce que nous
caractérisons désormais comme un *pseudo-complément*, sans qu'on puisse préciser bien davantage.</footnote>

<footnote n="8">8. On n'objectera pas que seule la pensée mythique opère dans cet espace fermé avec des combinaisons comparables à celle du «bricolage», tandis que l'espace scientifique serait tout autre. Certes, le concept est un opérateur d'ouverture un peu plus puissant que l'image et qui semble engager un espace apparemment plus ouvert. Mais, en réalité, comme l'explique très bien Lévi-Strauss, le rôle du concept n'étend ni ne renouvelle vraiment la signification, mais «se borne à obtenir le groupe de ses transformations» ([Lévi-Strauss 62], 30). Ces considérations éclairent la démarche de Jacques Derrida, d'un jour nouveau. La «déconstruction», sorte de théologie négative sans Dieu, suppose</footnote>
l' existant lui-même, ce qui échappe à l' existant autocomplémenté ne peut être que
l' ensemble vide.

2. Les ordres faibles stricts ont pour complémentaires des préordres totaux et vice-
versa. Si la structure du monde était un ordre faible strict (antisymétrique, transitif)
avec transitivité de l'incomparabilité, le complémentaire de ce qui est – différent
de ce qui est, dans un tel cas – serait donc un préordre total (réflexif, transitif).
Inversement, si le monde pouvait se réduire à un préordre total, son complémentaire
serait un ordre faible. D'où, dans les deux cas, l'impossibilité d'ordonner certains
éléments.

3. Si la structure du monde devait être une hiérarchie totalement ordonnée (chaîne),
son complémentaire, comme on l'a vu, serait un graphe vide (null graph) ou une
antichâine, et donc un ensemble d'éléments absolument discontinus<fnref n="9" />. Puisqu'il est
question de discontinuité, on notera que la théorie des graphes donne une définition
élaborée précise de la notion de «trou». Un trou est un cycle impair sans corde
avec au moins 5 sommets, tandis qu'un anti-trou est le graphe complémentaire d'un
trou. Ainsi, le pentagramme pythagoricien est un trou. En revanche, les graphes
d'incomparabilité sont sans trous ni anti-trous. En effet, les graphes d'incomparabilité
sont des graphes parfaits, et un graphe *G* est précisément parfait si et seulement s'il
ne contient aucun trou et aucun anti-trou comme sous-graphe induit<fnref n="10" />.

4. Si le graphe du monde ne devait être qu'un ensemble partiellement ordonné (poset), alors nous devons constater que le complémentaire d'un ordre – même partiel – n'existe pas toujours. Ainsi certains treillis – par exemple, les treillis distributifs – ne sont pas complémentés.

5. Lorsqu’un treillis est complémenté, le complément d’un élément n’est pas forcément unique. Dans le treillis de la Fig. 19, par exemple, un élément a non pas un, mais deux compléments. Le complément de ce qui est pourrait donc ne pas être unique : ce n’est donc pas *une* entité qui apparaîtrait ainsi en creux, mais *plusieurs* : un réel

<footnote>que, par des démontages et des déliaisons opérées au sein du langage philosophique, il serait possible
de faire advenir un autre espace que celui de la métaphysique. Mais cet espoir est voué à l'échec si
l'espace de la métaphysique, qui s'identifie en réalité avec celui de la signification ou du sens, est –
comme le pense Lévi-Strauss – autocomplémenté.</footnote>

<footnote n="9">9. Le discontinu est courant dans l'existence humaine. Nous avions proposé, autrefois, de mondéliser celle-ci en utilisant des graphes d'intervalle (Parrochia 91²], 182-183), qui sont, en fait les complémentaires des graphes de comparabilité.</footnote>

<footnote n="10">10. Cette conjecture, énoncée par Berge en 1960, n’est devenue un théorème que 42 ans plus tard, en mai 2002, grâce à Maria Chudnovsky et Paul Seymour. La démonstration de ce théorème fait aujourd’hui 148 pages.</footnote>
problème pour le monothéisme...

6. Certains ordres partiels, comme les treillis pseudocomplémentés ou relativement pseudocomplémentés, n'admettent que des «pseudocompléments» et non pas des compléments. Dans un treillis $T$ avec un élément inférieur 0, un élément $x \in T$ est dit avoir un pseudocomplément s'il existe un plus grand élément $x^* \in T$, disjoint de $x$ avec la propriété que $x \wedge x^* = 0$. En ce cas, cela signifie seulement que $x^* = \text{Max}\{y \in T \mid x \wedge y = 0\}$. Ceci, là encore, fait surgir une classe dans laquelle on ne fait que privilégier un élément parmi d'autres.

7. Seuls, comme on l'a vu, les treillis booléens (distributifs et complémentés), font apparaître, pour tout élément, un complément et un seul.

8. Dans le cas des matroïdes ou de leurs hypergraphes associés, le passage au complémentaire amène soit une autocomplémentation, soit un nombre extrêmement important de structures alternatives.

9. Dans le cas des complexes simpliciaux, c'est encore pire : mis à part les cas évoqués à la fin de la section précédente, la notion de complémentarité perd son sens et le nombre de structures alternatives devient énorme.

En conséquence – sous l'hypothèse que l'ensemble de ce qui est perçu ou compris se ramène à l'une des structures précédentes – la démarche de la théologie négative (ou de toute autre forme de pensée qui prétendrait définir quelque entité par son complémentaire) ne pourrait valoir que dans cet espace de pensée correspondant à un ordre partiel «bien complémenté», c'est-à-dire de type booléen. Dans toute autre circonstance, cette approche serait vouée à l'échec.

Références

[Berge 70] Berge, C., *Graphes et Hypergraphes*, Dunod, Paris, 1970.

[Berge 84] Berge, C. et Chvátal, V., *Topics on Perfect Graphs*, Elsevier, coll. « Annals of Discrete Mathematics » (No 21), 1984.

[Bergson 38] Bergson, H., *La Pensée et le Mouvant*, P. U. F., Paris, 1938.

[Birkhoff 40] Birkhoff, G., *Lattice Theory*, American Mathematical Society, Providence, R.I., 1940, rééd. 1948, 1967.

[Blyth 05] Blyth, T. S., *Lattices and ordered structure*, Springer Verlag, London, 2005.
[Bollobas 79] Bollobas, B., Rival, I., «The maximal size of the covering graph of a lattice », *Algebra Universalis* 9, 371-373, 1979.

[Bresar 08] Bresar, B., Chhangat, M., Klavzar, S., Kovse, M., Mathews, J., Mathews, A., « Cover-incomparability graphs of posets », *Order* 25, 335-347, 2008.

[Chamni 92] Chamni-Nembua, C., Monjardet, B., « Les treillis pseudocomplémentés finis », *Europ. J. Combinatorics* W, 89-107, 1992.

[Chartland 16] Chartland, G., «Highly Irregular», in Gera, R., Hedetniemi S. et Larson C., *Graph Theory, Favorite Conjectures and Open Problems*, 1-16, Springer International Publishing, Suisse, 2016.

[Coxeter 73] Coxeter, H. S., *Regular Polytopes* (1943), Dover publications, 3e ed., New York, 1973.

[Denys L'Aréopagite 46] Denys L'Aréopagite, «Traité de la Théologie mystique» in *Œuvres de Saint Denys L'Aréopagite*, tr. fr. Mgr Darboy, 275-286, Maison de la Bonne Presse, Paris, 1846.

[Diestel 06] Diestel, R., *Graph Theory*, 3rd edition, Springer, Berlin Heidelberg New York, 2006.

[Dilworth 50] Dilworth, R. P., « A Decomposition Theorem for Partially Ordered Sets », *Ann. Math.*, vol. 51, no 1, 1950, p. 161-166.

[Dipert 97] Dipert, R. R., "The Mathematical Structure of the World : The World as Graph", *The Journal of Philosophy*, Vol. 94, No. 7, 329-358, 329-358, Jul. 1997.

[Duffus 77] Duffus, D., Rival, I., « Path lengths in the covering graph », *Discrete Math.* 19, 139-158, 1977

[Erdös 35] Erdös, P. and Szekeres, G., « A combinatorial problem in geometry », *Compositio Math.* 2, 1935, 463-470.

[Filipov 80] Filipov, N.D., « Comparability graphs of partially ordered sets of different types », *Collq. Maths. Soc. Janos Bolyai*, 33, 373-380, 1980.

[Fulkerson 56] Fulkerson, D. R., « Note on Dilworth's decomposition theorem for partially ordered sets », Proc. Amer. Math. Soc., vol. 7, no 4, ? 1956, p. 701-702 (lire en ligne [archive]).

[Fox 12] Fox, J., Pach, J., « String graphs and incomparability graphs », *Advances in Mathematics*, Vol. 230, Issue 3, 1381-1401, 20 June 2012.

[Fraïssé 00] Fraïssé, R., *Theory of Relations*, North Holland, Amsterdam, 2000.

[Gallai 67] Gallai, T., « Transitive Orientierbare Graphen », *Acta. Math. Hungar.* 18, 25-66, 1967.
[Galvin 94] Galvin, F., « A proof of Dilworth's chain decomposition theorem », Amer. Math. Month., vol. 101, No 4, 1994, p. 352-353.

[Glivenko 29] Glivenko, V., « Sur quelques points de la logique de Brouwer », Bull. Acad. Sci. Befg. 15, 183-188, 1929.

[Golumbic 80] Golumbic, M., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

[Gedenova 80] Gedenova, E., « Lattices, whose covering graphs are s-graphs », Colloq. Maths. Soc. Janos Bolyai. 33, 407-435, 1980.

[Golumbic 83] Golumbic, M., Rotem, D. and Urrutia, J., « Comparability graphs and intersection graphs », Discrete Math. 43, 37-46, 1983.

[Gondran 79] Gondran, M., Minoux, M., Graphes et Algorithmes, Eyrolles, Paris, 1979.

[Grätzer 78] Grätzer, G., General Lattice Theory, Birkhauser-Verlag, Stuttgart, 1978.

[Harzheim 05] Harzheim, E., Ordered sets, Springer, coll. « Advances in Mathematics », No 7, 2005.

[Kaufmann 78] Kaufmann, A., Boulaye, G., Théorie des treillis en vu des applications, Masson, Paris, 1978.

[Kurepa 35] Kurepa, G., Ensembles ordonnés ramifiés, thèse, Paris, 1935; Public. math. de l'Université de Belgrade, 4, 1935, 1-138.

[Lévi-Strauss 50] Lévi-Strauss, C., « Introduction à l'œuvre de Marcel Mauss », in Mauss, M., Sociologie et Anthropologie, PUF, Paris, 1950.

[Lévi-Strauss 62] Lévi-Strauss, C., La Pensée sauvage, Paris, Plon, 1962.

[Lov'asz 83] Lov'asz, L., « Perfect graphs », in Selected Topics in Graph Theory, vol. 2, Academic Press, London, 55-87, 1983.

[Mirsky 79] Mirsky, L., « A dual of Dilworth's decomposition theorem », Amer. Math. Month., vol. 78, No 8, 1971, p. 876-877.

[Nimborkar 10] Nimborkar, S.K., Wasadikar, M.P., Pawar, M.M., « Coloring of lattices », Math. Slovaca 60, 419-434, 2010.

[Oderberg 11] Oderberg, D. S., "The world is not an asymmetric graph", Analysis 71, 3-10, 2011.

[Parrochia 91¹] Parrochia, D., Le Réel, Bordas, Paris, 1991.

[Parrochia 91²] Parrochia, D., Mathématiques et Existence, ordres, fragments, empiétements, Seyssel, Champ Vallon, 1991.
[Parrochia 13] Parrochia, D., Neuville, P., *Towards a general theory of classifications*, Birkhäuser, Bâle, 2013.

[Parrochia 20] Parrochia, D., «On the number of edges of comparability and incomparability graphs», *hal-02972652*, 2020. En ligne : https://hal.archives-ouvertes.fr/hal-02972652.

[Perles 63] Micha A. Perles, « On Dilworth's theorem in the infinite case », *Isr. J. Math.*, vol. 1, No 2, 1963, p. 108-109.

[Ponasse 79] Ponasse, D., Carréga, J.C., *Algèbre et topologie booléennes*, Masson, Paris, 1979.

[Rhodes 15] Rhodes, J., Sylva, P. V., *Boolean Representations of Simplicial Complexes and Matroids*, Springer, Cham Heidelberg New York Dordrecht London, 2015.

[Shackel 11] Shackel, N., "The world as a graph : defending metaphysical graphical structuralism", *Analysis*, Vol. 71, No. 1, 10-21, January 2011.

[Sommerville 29] Sommerville, D. M. Y., *An Introduction to Geometry in n Dimensions*, Methuen, Londres, 1929.

[Stone 37] Stone, M. H., *Topological representations of distributive lattices and Brouwerian togs*, *CasopIs Pest. Mat.*, 67, 1-25, 1937

[Vannier 98] Vannier, Marie-Anne, «Aux sources de la voie négative», *Revue des Sciences Religieuses*, 72-4, 403-419, 1998.

[Varlet 63] Varlet, J., « Contributions à l'étude des treillis pseudo-complementés et des treillis de Stone », *Mém. Soc. Sci. Liège*, 8, 1-71, 1963.

[Wachs 04] Wachs, M. L., « Poset Topology : Tools and Applications », *Lecture notes IAS/Park City Graduate Summer School in Geometric Combinatorics*, July 2004.

[Wasadikar 12] Wasadikar M. P., Survase, P. A., « Incomparability Graphs of Lattices », in *Balasubramaniam, P., Uthayakumar, R. (eds.), International Conference on Mathematical Modelling and Scientific Computation - Mathematical Modelling and Scientific Computation*, ICMMSC 2012, 78-85, Springer, Heidelberg, 2012.