# Caracterisation des classes de ($\leq 3$)-hypomorphie
a l'aide d'interdits

Jean Guillaume Hagendorf

Université de Paris, France

Gérard Lopez

Institut de Mathématiques de Luminy, France
and

Claire Rauzy

(died) Université d'Aix-Marseille I., France

Received : January 2013. Accepted : February 2013

## Abstract

G. Lopez a démontré la ($\leq 6$)-reconstructibilité des relations bi-
naires finies (1972) (voir [1] et [2]) résolvant ainsi un problème de
Roland Fraïssé (voir[3]). Sa preuve repose sur la notion de classe de
différence. Depuis, la notion de classe de différence est un outil ma-
jeur dans bien des travaux en reconstruction et demi-reconstruction
notamment en [4], [5] et [6] et permet de définir la notion de classe
d'hypomorphie. La caractérisation des classes de ($\leq k$)-hypomorphie
finies, pour $k\ge 6$, a été obtenue par Hagendorf et Lopez en 1994 (voir
[4]). La caractérisation des classes de ($\leq 4$)-hypomorphie finies a été
obtenue par G. Lopez et C. Rauzy (1992) (voir [6]). Ensuite, celle des
classes de ($\leq 5$)-hypomorphie finies a été trouvée par Y. Boudabbous
(2000) (voir [7]). Dans cet article nous obtenons une caractérisation,
par interdits, des classes de ($\leq 3$)-hypomorphie finies, puis infinies
dans un prochain article. Ces deux articles sont résumés en [8]. La
reconstruction infinie a été en particulier étudiée en [4], [9] et [11].
D'autres utilisations des classes de différence ou des liens avec elles
se trouvent par exemple dans [12] à [21].

Classification AMS : 05C60.

Mots-clés : Relation, Binaire, Graphe, Reconstruction, Différence, Hypomorphie, Pavage, Interdit, Drapeau.
# 1. Définitions et rappels.

On appelle *relation binaire* $R$ de *base* $E$ (base qui sera notée $|R|$) une application de $E^2$ dans un ensemble arbitraire à deux éléments : $\{+, -\}$. Les éléments de la base pourront être appelés sommets de $R$. L'assertion $\ll R(a, b) = + \gg$ pourra se lire $\ll R(a, b) \text{ est vraie } \gg$. On conviendra de toutes les relations binaires envisagées ici qu'elles sont partout réflexives. Si $F$ est une partie de la base de $R$ on note $R|F$ la restriction de $R$ à $F$. Si $a$ et $b$ sont deux éléments distincts dans la base la paire $\{a, b\}$ sera appelée une *arête* qu'on pourra noter $[a, b]$ (qui ne se distingue alors pas de $[b, a]$). On dit d'une arête $[a, b]$ qu'elle est *orientée* (*mod* $R$) ou qu'elle est une *flèche* si $R(a, b) \neq R(b, a)$. Sinon elle est dite *neutre* : pleine si $R(a, b) = R(b, a) = +$, vide si $R(a, b) = R(b, a) = -$. On notera $\ll a < b \mod R \gg$ si $a \neq b$ avec $[a, b]$ R-orientée et $R(a, b) = +$ (et donc $R(b, a) = -$) ; on dira que $\ll b \text{ majore } a \gg$ (sous entendu, comme toujours ici, $\ll \text{ strictement } \gg$) ou encore que $\ll a \text{ est minorant de } b \gg$, ou encore que $[a, b]$ est orientée de $a$ vers $b$. Soient $R$ et $R'$ deux relations binaires de même base, on dit d'une arête $[a, b]$ orientée (*mod* $R$ et *mod* $R'$) qu'elle *change* ou s'inverse (en passant de $R \to R'$) si $R(a, b) \neq R'(a, b)$ (et donc $R(a, b) = R'(b, a)$).

On appelle *type* de relation une relation prise à l'isomorphie près.

Notre travail s'inscrit dans le cadre de la *théorie des relations binaires* où toute paire de sommets est (par définition) une arête. C'est la principale différence entre la notion de relation et la notion de graphe où "l'arête vide" étant absente, elle n'est pas considérée comme une arête. Notre motivation pour adopter le point de vue relationniste réside dans notre objet d'étude : le drapeau tricolore qui est la configuration minimale contenant trois arêtes de types différents, une pleine, une vide et une orientée.

Par ailleurs nous utiliserons aussi le langage des graphes plus large-
ment répandu dans la littérature. Ainsi nous définirons ultérieurement
avec plus de précision, comme étant un sous-graphe partiel, une structure
générale due à J. G. Hagendorf : le pavage. Elle concerne l'organisation
des sous-graphes de la relation de certains types. Ici elle est relative aux
seuls types des drapeaux tricolores (au nombre de deux), mais la définition
peut s'adapter de façon évidente à n'importe quelle famille de types de
sous-graphes. Le fait que l'arête pleine et l'arête vide jouent des rôles
symétriques permet l'introduction de ces pavages qui constituent un outil
technique indispensable à l'élaboration de la preuve du théorème principal
de cet article.

Soit $n$ un nombre entier. Disons que deux relations binaires $R$ et $R'$ de
même base $E$ sont $\leq n$-hypomorphes si pour toute partie $F$ de la base de cardinal $\leq n$, $R|F$ et $R'|F$ sont isomorphes.

Dans une relation binaire $R$ appelons chemin de flèches une suite $[x_0, x_1, ..., x_p]$ où $[x_q, x_{q+1}]$ est, pour $0\leq q < p$, une flèche mod $R$. Etant données deux relations $R$ et $R'$ binaires de même base et $\leq 2$-hypomorphes, G. Lopez a introduit dans [1] la relation binaire $T$ d'équivalence, appelée relation de différence, définie sur la même base par $T(x, y)$ vraie (c.-à-d. vaut +) si et seulement si $x$ et $y$ sont identiques ou bien sont reliés par un chemin de flèches, mod $R$ et $R'$, (appelé chemin de différence) qui s'inversent en passant de $R$ à $R'$, l'orientation de chacune des flèches étant indépendante du sens du chemin. Ce chemin est dit alterné si chaque arête est orientée à l'opposée de la suivante. Il est dit minimal s'il est de longueur minimum, la longueur étant le nombre d'arêtes c.-à-d. le nombre de sommets moins 1. Les classes d'équivalence associées à $T$ sont appelées classes de $(R, R')$-différence. Les paires $\{a, b\}$ où $T(a, b) = +$ forment le graphe de différence associé à $R$ et $R'$.

Une relation binaire est dite *connexe* si un chemin de flèches (appelé chemin de connexité) relie deux sommets quelconques. Une partie de la base de cette relation sera dite *connexe* si la restriction de la relation à cette partie l'est.

Disons qu'une relation $R$ est une classe de $\leq n$-hypomorphie si il existe $R'$ de même base que $R$, $\leq n$-hypomorphe à $R$, pour laquelle cette base commune ne forme qu'une seule classe de $(R, R')$-différence.

On appelle *duale* d'une relation binaire $R$ la relation notée $R^*$ vérifiant $R^*(a,b)=R(b,a)$ pour tous $a$ et $b$.

Une partie $I$ de la base d'une relation binaire $R$ est dite un *z-intervalle* pour un $z$ hors de $I$ si pour tous $x$ et $y$ dans $I$ on a $R(z, x) = R(z, y)$ et $R(x, z) = R(y, z)$. La partie $I$ est dite un *intervalle* si elle est z-intervalle pour tout $0<z$ hors de $I$. On montre (voir [1]) que les classes de différence de relations $\leq 3$-hypomorphes sont des intervalles.

Un *pic* est par définition une relation de base à 3 élément $a, b, c$, telle que $[a, b]$ et $[c, b]$ sont des flèches orientées toutes deux vers $b$ ou toutes deux issues de $b$ et où $[a, c]$ est neutre. On montre qu'il n'y a pas de pic dans une classe de $\leq 3$-hypomorphie (voir [6] ou [11]).

Introduisons encore une définition. Un *drapeau tricolore* est par définition une relation $\{x, y, z\}$ à trois éléments où $[x, y]$ est orientée, $[x, z]$ vide et $[y, z]$ pleine. On montre qu'il n'y a pas de drapeau tricolore dans une classe de $\leq 4$-hypomorphie (voir [6] ou [11]).

Disons que $t$ sépare fortement $a$ et $b$ ($a, b \neq t$) si l'une des arêtes $[t, a]$
ou [t, b] est neutre et pas l'autre. C. Rauzy a introduit les interdits dits rauziens : appelons *interdit rauzien* toute relation R sur 4 éléments, formée d'un drapeau tricolore {$x, y, z$}, où $[x, y]$ est orientée, et d'un quatrième élément t séparant fortement x et y.

Donnons un exemple de classe de $\leq 3$-hypomorphie finie $R$: la base est formée de quatre éléments $x, y, z, u$, $[z, x]$ est vide, $[z, y]$ pleine $[y, x]$ orientée (disons $x < y$ mod $R$) et on a $z < u \mod R$, $u < x$ mod $R$ et $u < y$ mod $R$. On obtient $R'$ en inversant les arêtes $[z, u]$, $[x, u]$ et $[y, u]$ de $R$ et en conservant $[y, x]$, $[x, z]$ et $[z, y]$. $R$ forme (avec $R'$) une classe de $\leq 3$-hypomorphie (contenant du coup le drapeau tricolore {$x, y, z$}).

On se propose de démontrer le théorème suivant qui caractérise les classes de ($\leq 3$)-hypomorphie par l'usage d'interdits rauziens. La preuve est résumée dans [8].

**Théorème.** *Une relation binaire est une classe de ($\leq 3$)-hypomorphie si et seulement si elle est connexe, sans pic et sans interdit rauzien.*

**Lemme 1 :** *Une classe de $\leq 3$-hypomorphie ne contient ni interdit rauzien ni pic.*

**Preuve.** Par le corollaire du sous-lemme suivant que nous précédons d'une définition.

**Définition :** on dit qu'un sommet *majore* (resp. *minore*) une flèche s'il majore (resp. minore) chaque sommet de la flèche. Ce majorant (resp. minorant) mod $R$ est dit *changeant* en passant de $R$ à $R'$ s'il est devient minorant (resp. majorant) mod $R'$ de chaque sommet de la flèche. Il est dit *non changeant* s'il reste majorant (resp. minorant) mod $R'$.

Sous-lemme des drapeaux tricolores. Soit $R$ et $R'$ deux relations binaires ($\leq 3$)-hypomorphes. Dans une classe de $(R, R')$-différence, la flèche d'un drapeau tricolore possède un majorant (ou minorant) *changeant*.

**Preuve.** Montrons d'abord que dans une classe de $(R, R')$-différence tout chemin de différence minimal liant les extrémités d'une flèche (nécessairement non changeante) d'un drapeau tricolore de $R$ est de longueur 2. Démontrons que dans une classe de $(R, R')$-différence tout chemin de différence minimal liant les extrémités d'une flèche d'un drapeau tricolore de $R$ ne peut pas être de longueur 2. Soit {$x, y, z$} un tel drapeau avec $y < x$, $[y, z]$ pleine et $[z, x]$ vide mod $R$ et $R'$.
On considère un chemin de différence minimal $[x, x_1, \dots, x_p = a, y]$ allant de $x$ à $y$ et dont la dernière escale avant d'arriver sur $y$ est $a$. Supposons sans perte de généralité $a < y$ mod $R$ et le contraire mod $R'$. L'examen de $\{a, y, z\}$ montre que soit $[a, z]$ est pleine soit elle est orientée changeante. Le chemin n'étant pas de longueur 2 on aurait $a < x$ mod $R$ (sinon $\{a, y, x\}$ ferait un cycle dans $R$ et pas dans $R'$) et aussi $a < x$ mod $R'$. L'examen de $\{a, x, z\}$ exclut pour $[a, z]$ la possibilité d'être orientée changeante. Donc $[a, z]$ est pleine. Nous allons voir que ce caractère plein se propage tout au long du chemin. L'ensemble $\{a, x_{p-1}, z\}$ montre de même que $[x_{p-1}, z]$ est pleine ou orientée changeante. Considérons $\{x, a, x_{p-1}\}$ : $[x_{p-1}, a]$ est orientée changeante et $[a, x]$ est orientée non changeante donc $[x_{p-1}, x]$ est orientée. Si $[x_{p-1}, z]$ est orientée changeante l'examen de $\{z, x, x_{p-1}\}$ montre que $[x_{p-1}, x]$ est orientée changeante et $\{x_{p-1}, y, x\}$ montre alors que $[x_{p-1}, y]$ est orientée et, de plus, orientée changeante par l'examen de $\{x_{p-1}, y, z\}$. Contre l'hypothèse de minimalité. Donc $[x_{p-1}, z]$ est pleine.

Ainsi de proche en proche en remontant le long du chemin jusqu'à $x_1$. On obtient alors : l'arête $[x_1, z]$ est pleine, l'arête $[x, z]$ vide et l'arête $[x_1, x]$ est orientée changeante. Contradiction. Le chemin est bien de longueur 2. Achevons la preuve en montrant l'alternance du chemin de diffrence not $[x, x_1, y]$. S'il ne l'tait pas, par argument de minimalit, la flèche $[x, y]$ devrait tre non changeante. Mais alors $x, y, x_1$ serait, sans cette alternance, un cycle modulo une des relations $R$ ou $R'$ et une chaine modulo l'autre.

**Corollaire.** Soit $R$ et $R'$ deux relations binaires ($\leq 3$)-hypomorphes. Dans une classe de $(R, R')$-différence, la flèche d'un drapeau tricolore possède un majorant (ou minorant), nécessairement changeant, qui est minorant (resp. ou majorant) changeant du troisième élément du drapeau.

**Preuve.** Conservons les mêmes notations que dans la précédente preuve dont nous notons m le $x_1$. Grâce à la $\leq 3$-hypomorphie le majorant (ou minorant) m, devrait être tel que $[m, z]$, si elle était neutre, serait à la fois vide (par examen de $\{m, z, x\}$) et pleine (par examen de $\{m, z, y\}$). On a donc $m < z$ mod $R$ (ou resp. $m > z$ mod $R$).

**Vocabulaire.** Pour alléger l'écriture on dira si $D=\{x, y, z\}$ est un drapeau tricolore où $y < x$ et t un élément extérieur à $D$ que $(t, D)$ est fortement orienté si t est majorant (ou minorant) de la flèche du drapeau $\{x, y, z\}$ et minorant (resp. ou majorant) du sommet $z$ ; tout chemin de connexité minimal liant $y$ et $z$ (ou $x$ et $z$) étant alors une 3-consécutivité.

**Lemme 2 :** Soit $R$ une relation binaire connexe sans pic ne contenant pas
d'interdit rauzien. Soit $D = \{x, y, z\}$ un drapeau tricolore de $R$ où $y < x$. Tout chemin de connexité minimal, parmi ceux reliant les extrémités d'une arête neutre fixée du drapeau, est de longueur 2 et passe par un élément $z_1$ qui est lié par une flèche à chaque sommet du drapeau et tel que ($z_1, D$) est fortement orienté.

**Preuve.** Soit $D = \{x, y, z\}$ le drapeau tricolore où $y < x$. Considérons un plus court chemin de connexité $[z = z_0, z_1, \dots, z_k = y]$ liant $z$ à $y$ tous les $z_i$ étant distincts de $x$. Montrons que l'hypothèse “$k \ge 3$” débouche sur une absurdité. Par minimalité les arêtes internes du chemin (c'est-à-dire celles reliant des sommets non consécutifs) sont neutres, ce qui veut dire que $[y, z_i]$ est neutre si $i \neq k-1$.

$z_{k-1}$ ne doit pas séparer fortement $y$ de $x$ donc $[z_{k-1}, x]$ est orientée.

$1^{\text{er}}\text{cas}[z_{k-1}, z]$ vide. On raisonne sur le drapeau tricolore $\{z_{k-1}, z_k = y, z\}$ dont la flèche $[z_{k-1}, y]$ est fortement séparée par $z_{k-2}$.

$2^{\text{ème}}\text{cas}[z_{k-1}, z]$ pleine alors on réitère le même raisonnement avec $z_{k-2}$ au lieu de $z_{k-1}$ :

$[z_{k-2}, y]$ doit être neutre (arête interne), donc $[z_{k-2}, x]$ aussi (pour ne pas séparer fortement la flèche $[y, x]$ du drapeau $\{x, y, z\}$) alors que $[z_{k-2}, z_{k-1}]$ doit être orienté et donc aussi $[z_{k-2}, x]$, pour ne pas séparer fortement, par $z_{k-2}$, la flèche $[z_{k-1}, x]$ du drapeau tricolore $\{z, z_{k-1}, x\}$ -absurde.

On arrive donc finalement à un chemin $[z, z_1, y]$ de longueur 2. Le drapeau $\{x, y, z\}$ ne devant pas être fortement séparé par $z_1$ il faut que $[z_1, x]$ soit orientée. Cette orientation doit éviter un pic sur $\{z, z_1, x\}$ donc $z_1$ majore ou minore les deux éléments $y$ et $x$ et l'inverse pour $z$.

Etant donnée une relation binaire $R$ appelons *pavage tricolore* tout ensemble $P$ (non vide) d'arêtes de $R$ vérifiant la condition suivante : si $u$ et $v$ sont deux arêtes de l'ensemble $P$ il existe une suite $C_1, C_2, \dots, C_n$ de drapeaux tricolores formés d'arêtes de $P$, chacun adjacent à un précédent par une arête neutre ou orientée, telle que $u$ est une arête de $C_1$ et $v$ une arête de $C_n$. Les $C_p$ ne sont pas nécessairement tous distincts bien que cette éventualité ne change rien. On note $|P|$ l'ensemble des extrémités des arêtes du pavage $P(c. \to a. \to d.)$ les éléments des paires constituant le pavage), celles-ci sont dites *couvertes* par le pavage. Par abus de langage on appellera encore $\ll$ pavage $\gg$ la restriction de $R$ à l'ensemble $|P|$ des sommets couverts par le pavage, mais on prendra garde au fait qu'alors une arête reliant deux sommets du $\ll$ pavage $\gg$ n'est pas nécessairement dans le pavage. On commettra un nouvel abus de langage en parlant de drapeau
contenu dans un pavage pour dire que les arêtes du drapeau sont dans le pavage.

On appelle pavage *rauzien* un pavage tricolore sans interdit rauzien (ou, pour le dire sans abus de langage, un pavage tricolore tel que la restriction de $R$ à l'ensemble des sommets couverts par le pavage ne contient pas d'interdit rauzien).

**Lemme 2** : bis. Soit $R$ une relation binaire sans pic ne contenant pas d'interdit rauzien. Soit $D = \{x, y, z\}$ un drapeau tricolore de $R$ où $y < x$, dans un pavage rauzien $P$ dont l'ensemble des sommets $|P|$ est connexe. Tout chemin de connexité minimal liant les extrémités d'une arête neutre du drapeau $D$ et ne passant que par des sommets du pavage $P$ est de longueur 2 et passe par un élément $z_1$ dupavage $P, z_1$ étant lié par une flèche à chaque sommet du drapeau. ($z_1, D$) est donc fortement orienté. Tout chemin de connexité minimal liant $y$ et $z$ (ou $x$ et $z$) et ne passant que par des sommets du pavage est donc une 3-consécutivité.

**Preuve.** On applique le lemme 2 à la restriction de $R$ à $|P|$.

On verra au lemme suivant qu'en fait il n'existe pas de tel chemin de connexité formé de seuls sommets du pavage. On montrera plus précisément que : - Si dans une relation sans pic un sommet $u$ est relié par des arêtes orientées aux extrémités d'une arête neutre d'un drapeau d'un pavage rauzien alors il est relié par des arêtes orientées à tous les sommets du pavage.

**Lemme 3** : Dans une relation binaire sans pic ni interdit rauzien soit $D$ un drapeau tricolore $\{x, y, z\}$ avec $y < x$, $[z, y]$ pleine et $[z, x]$ vide. Soit $P$ un pavage rauzien contenant $D$. Soit $v$ un sommet tel que $y < v$ et $v < z$ alors pour tout drapeau tricolore $T$ formé d'arêtes de $P$, $(v, T)$ est fortement orienté. De ce fait $v$ n'est pas dans le pavage.

**Preuve.** Nous faisons l'hypothèse que $(v,D)$ est fortement orienté. A ce drapeau $D$ nous adjoignons par adjacence un nouveau drapeau tricolore $D'$ et nous montrerons que $(v,D')$ est fortement orienté. De proche en proche $(v,T)$ sera fortement orienté pour tout drapeau tricolore $T$ dont les arêtes sont dans $P$. Ce $v$ ne peut donc être dans le pavage $P$ faute d'arête neutre qui $y$ soit incidente.

Adjoignons un drapeau tricolore à $\{x,y,z\}$ qui lui sera adjacent par une arête et montrons que le nouveau sommet $u$ rajouté est lié à $v$ par une arête orientée.

1° cas : Adjoignons un nouveau drapeau tricolore $\{z, x, u\}$ avec $[z, u]$ pleine et par exemple $x < u$. Si $[v, u]$ n'est pas orientée v sépare fortement
la flèche $[x, u]$ du drapeau tricolore $\{u, z, x\}$. Cette orientation de $u$ vers $v$ (pour éviter un pic sur $\{z, u, v\}$) permet de poursuivre l'induction avec un nouveau drapeau tricolore adjacent à$\{z, u, x\}$. Le cas où $u < x$ est analogue.

2° cas : Adjoignons un nouveau drapeau tricolore $\{z, x, u\}$ avec $[x, u]$ pleine et par exemple $u < z$. La flèche $\{z, u\}$ du drapeau tricolore $\{z, u, x\}$ ne pouvant être fortement séparé par $v$ il faut que $[v, u]$ soit orientée. L'absence de pic sur $\{v, u, x\}$ impose le sens de cette orientation.

3° cas : Adjoignons un nouveau drapeau tricolore $\{z, y, u\}$ avec $[u, z]$ vide. $v$ ne devant pas séparer fortement la flèche $[y, u]$ du drapeau tricolore $\{z, y, u\}$ il faut que $[v, u]$ soit orientée.

4° cas : Adjoignons un nouveau drapeau tricolore $\{z, y, u\}$ avec $[u, y]$ vide et par exemple $u < z$. L'élément $v$ ne devant pas séparer fortement la flèche $[u, z]$ du drapeau tricolore $\{z, y, u\}$ il faut que $[v, u]$ soit orientée.

5° cas : Adjoignons un nouveau drapeau tricolore $\{x, y, u\}$ avec $[u, x]$ vide. Si $[v, u]$ était vide $z$ séparerait fortement la flèche $[v, y]$ du drapeau tricolore $\{v, y, u\}$. Si $[v, u]$ était pleine le drapeau tricolore $\{v, x, u\}$ verrait sa flèche $[v, x]$ fortement séparée par $z$. $[v, u]$ est donc orientée.

6° cas : Adjoignons un nouveau drapeau tricolore $\{x,y,u\}$ avec $[u,x]$ pleine. 1ère éventualité : $[v,u] \in \text{estpleine, alors sledrapeau}\{v,y,u\}$ voit sa flèche $[v, y]$ fortement séparée par $z$. 2ème éventualité : $[v, u]$ est vide, alors le drapeau tricolore $\{v, u, x\}$ voit sa flèche $[v, x]$ fortement séparée par $z$. L'arête $[v, u]$ est donc orientée.

**Lemme 4** : Si l'ensemble des sommets couverts par un pavage rauzien est sans pic alors il est non connexe.

**Preuve.** Supposons, par l'absurde, ce pavage connexe. Considérons un $v = z_1$ dont la présence est conséquence de la connexité d'après le lemme 2 bis et utilisons le lemme 3.

Donnons un exemple de pavage rauzien P dont l'ensemble $|P|$ des sommets possède un pic et qui du coup est connexe : $|P| = \{x, y, z, z', u\}$ avec $y < x, x < u, u < y, u < z, z' < z, [x, z]$ et $[x, z']$ pleines, $[y, z], [y, z'], [u, z']$ vides. Les drapeaux tricolores successifs $\{y, x, z\}, \{y, x, z'\}$, et $\{x, u, z'\}$ sont chacun adjacent au précédent. Or $\{u, y, z\}$ est un pic. Evidemment les arêtes orientées du pic (ici $[u, y]$ et $[u, z]$) ne peuvent faire partie du pavage car les extrémités d'une quelconque arête orientée du pic seraient fortement séparées par le troisième sommet du pic. Par contre l'arête neutre $[z', u]$ du pic $\{z', z, u\}$ est dans le pavage P. Et u n'est pas lié par une arête orientée à tous les sommets du pavage P, $[z', u]$ étant neutre.
Donnons maintenant un exemple de pavage dont l'ensemble des sommets est sans pic et connexe et qui possédera donc un interdit rauzien. Comme base prenons $|P| = \{x, y, z, u\}$ avec $y < x, u < y, z < u, [y, z]$ et $[u, x]$ pleines et $[x, z]$ vide. Les drapeaux tricolores $\{x, y, z\}$ et $\{u, z, x\}$ sont adjacents faisant de $\{[u, y], [y, x], [u, x], [z, x], [u, z]\}$ un pavage dont la base est connexe mais où u sépare fortement y et x.

Un pavage tricolore P est dit maximal si l'ensemble des arêtes de ce pavage ne peut être prolongé par un pavage $P'$ couvrant en plus d'autres sommets que ceux déjà couverts par P.

**Lemme 5 :** *Supposons qu'il n'existe pas d'interdit rauzien ni de pic dans une relation binaire R. Soit $[x,y]$ une flèche d'un des drapeaux d'un pavage tricolore maximal P dans R. Pour tout sommet $t$ qui n'est pas élément de $|P|$, $\{x,y\}$ est un t-intervalle.*

**Preuve.** Supposons que $x$ et $y$ font partie d'un drapeau tricolore $\{x,y,u\}$. Raisonnons par l'absurde en supposant que $\{x,y\}$ n'est pas un t-intervalle.

Supposons en première hypothèse que $[t,x]$ est neutre, $[t,y]$ ne peut être orientée sous peine de voir apparaitre un interdit rauzien sur $\{t,x,y,u\}$ et donc $[t,y]$ est neutre et, puisque nous raisonnons par l'absurde, de nature différente de $[t,x]$. Dans ce premier cas $\{t,x,y\}$ est un drapeau tricolore ce qui contre la maximalité de P.

Supposons en seconde hypothèse que $[t,x]$ et $[t,y]$ sont orientées par exemple $t < x$ et $ty$. Dans ce second cas montrons que $[t,u]$ ne peut être neutre car une des deux restrictions $\{t,x,u\}$ (ou resp. $\{t,y,u\}$) serait un drapeau tricolore suivant que $[t,u]$ est pleine (ou resp. vide) ; ceci contre la maximalité de P. On conclut donc que $[t,u]$ est orientée, mais cette orientation quelle qu'elle soit fait apparaitre un pic, soit sur $\{t,x,u\}$ si $t < u$, soit sur $\{t,y,u\}$ si $u < t$, ce qui contre encore l'hypothèse.

**Lemme 6 :** *Soit une relation binaire sans pic ni interdit rauzien dans laquelle D est un drapeau tricolore $\{x, y, z\}$ où $[y, z]$ est pleine, $[x, z]$ est vide et où $y < x$. Soit $t$ un quatrième élément hors de D. Si D est le seul drapeau tricolore contenu dans $\{x, y, z, t\}$ alors soit $t$ est relié aux trois sommets de D par une arête neutre, soit $t$ est relié aux trois sommets de D par une arête orientée. De plus dans ce deuxième cas $(t, D)$ est fortement orienté.*

**Preuve.** D'après le lemme 5 les arêtes $[t, x]$ et $[t, y]$ sont de même nature et, si orientées, dans le même sens. Examinons les trois cas.
1° cas : Les arêtes [t,x] et [t,y] sont pleines. Si l'arête [t,z] est orientée alors {$t,z,x$} est un drapeau autre que D, contraire à l'hypothèse. Donc t est relié aux trois sommets de D par une arête neutre.

2° cas : Les arêtes [t,x] et [t,y] sont vides. Si l'arête [t,z] est orientée alors {$t,z,y$} est un drapeau autre que D, contraire à l'hypothèse. Donc t est relié aux trois sommets de D par une arête neutre.

3° cas : Les arêtes [t,x] et [t,y] sont orientées. Si [t,z] est pleine (resp. vide) alors {$t,z,x$} (resp. {$t,z,y$}) est un nouveau drapeau. Dans ce cas t est relié aux trois sommets de D par une arête orientée. De plus {$x,y$} étant un t-intervalle d'après le lemme 5 et par ailleurs les pics devant être interdits (t,D) doit être fortement orienté.

**Lemme 7 :** Soit D un drapeau tricolore {$x,y,z$} dans une relation binaire sans pic ni interdit rauzien. Soit P un pavage maximal contenant D. Soient t et w deux éléments hors de $|P|$ tels que l'arête [t,w] soit orientée. Alors (t,D) est fortement orienté si et seulement si (w,D) est aussi fortement orienté.

**Preuve.** Supposons que (t,D) est fortement orienté avec (sans perdre en généralité) : $t < x$, $t < y$ et $z < t$. Si $t < w$, les flèches $[t,w]$ et $[t,x]$ formeraient un pic si l'arête $[x,w]$ était neutre, donc $[x,w]$ est orientée.

Si $w < t$ c'est {$z,t,w$} qui serait un pic si l'arête $[z,w]$ était neutre, donc $[z,w]$ est orientée. Par suite quel que soit le cas, $(w,D)$ est fortement orienté d'après le lemme 6 qu'on peut appliquer à {$x,y,z,w$}, car si {$w,x,z$} était un autre drapeau tricolore de {$x,y,z,w$} il serait contigu à D et w serait dans $|P|$. On conclut en invoquant la symétrie des rôles de t et w.

**Lemme 8 :** Soit D un drapeau tricolore {$x,y,z$} avec $y < x$, $[z,y]$ pleine et $[z,x]$ vide dans une relation binaire connexe sans pic ni interdit rauzien. Soit P un pavage maximal contenant D. Soit u un élément de la base hors de $|P|$. Les liens entre u et les éléments de $|P|$ sont orientés.

**Preuve.** Soit C un chemin de connexité reliant x à u. Soit v le dernier élément de C à être dans $|P|$. Soit $v'$ le successeur de v dans C. Le sommet v' est hors de $|P|$ et l'arête $[v',v]$ est orientée donc pour un drapeau tricolore $D'$ dont v est sommet ($v'$, D) est fortement orienté. Par contiguïté des drapeaux du pavage et d'après le lemme 3 ($v'$, T) est fortement orienté pour tous les drapeaux T du pavage de proche en proche, en particulier D. Il en est de même de tous les successeurs éventuels jusqu'à u.

Le chemin de connexité minimal reliant x à u est réduit à une arête unique orientée.
Donnons un exemple. Définissons une relation binaire à 6 éléments réunion de deux drapeaux tricolores $D = \{x, y, z\}$ avec $y < x$, et $D' = \{x', y', z'\}$ avec $y' < x'$. Et posons $z < z', zy', zx', y < y', yz', y < x', x < x', x < y', xz'$. P est réduit aux arêtes de $D$.

Remarque préliminaire : Quelque soit la partition A, B de l'ensemble des sommets d'un pavage tricolore, il existe toujours, en raison de l'adjacence des drapeaux, un drapeau à cheval sur A et sur B, c'est-à-dire ayant un sommet dans A et les deux autres dans B ou l'inverse.

**Lemme 9 :** Deux pavages rauziens maximaux dans une relation binaire connexe sans pic ni interdit rauzien couvrent des ensembles de sommets identiques ou disjoints.

**Preuve.** Soit $P$ et $P'$ deux tels pavages vérifiant la condition $\ll |P'| - |P|$ est non vide $\gg$. Soit $D$ undrapeautricolore de $P'$ ayant unsommethorsde $|P|$. Soit a un élément supposé exister de $|P| \cap |P'|$ et $D$ un drapeau de $P$ ayant a pour sommet. Dans la suite $D_0 = D', D_1, \dots, D_p, \dots, D_n = D$ de drapeaux tricolores chacun adjacent à un précédent il doit y en avoir un $D_k$ ayant 1 ou 2 sommets dans $|P'| - |P|$ et le(s) autre(s) dans $|P|$. Mais le lemme 8 imposerait à ce drapeau $D_k$ d'avoir deux arêtes orientées ce qui est impossible.

La connexité est indispensable dans l'hypothèse. En effet prenons deux drapeaux tricolores qui n'ont en commun qu'un sommet incident à aucune flèche; les autres liens entre les deux drapeaux étant pleins. La relation obtenue n'est pas connexe et chacun des deux drapeaux est un pavage maximal avec un élément en commun mais pas d'arête commune.

Théorème. Une relation binaire connexe est une classe de $\leq 3$-hypomorphie si et seulement si elle est sans pic et sans interdit rauzien.

**Preuve.** Soit $R$ une relation connexe, sans pic et sans interdit rauzien. Grâce au lemme 9 sa base se partitionne en pavages rauziens maximaux $P, P'...$ (éventuellement aucun tel pavage) et en un ensemble $F$ (éventuellement vide) de singletons n'appartenant à aucun drapeau tricolore (c'est-à-dire que $|R| = |P| \cup |P'| \cup \dots \cup F$).

Définissons $R$ ainsi : sur $F$ prenons pour $R$ le dual de $R$. Entre éléments d'un même pavage maximal $R$ est définie comme identique à $R$. Entre un élément dans un pavage maximal, et un élément extérieur, $R$ est définie comme le dual de $R$.
Remarquons que pour tous x et y dans la base il existe un chemin de connexité les reliant et qui s'inverse. Si x et y sont dans un P la base étant connexe il existe d'après le lemme 4 un élément z hors de P. [x,z,y] est d'après le lemme 8 un tel chemin vu la construction de R'. Si x est dans P et y ailleurs, [x,y] est un tel chemin. Si x et y sont dans F le chemin s'inverse tant qu'il reste dans F; s'il sort par un z hors de F, [x,z,y] est un tel chemin. La base de R ne forme donc qu'une seule classe de (R,R')-différence. Il reste à voir que R' est $\leq 3$-hypomorphe à R en raisonnant par l'absurde.

1.° cas : Plaçons-nous dans le cas où F est toute la base de R. Les seules relations à 3 éléments non autoduales (c.-à-d. non isomorphes à leur duale) sont les pics (exclus) et les drapeaux tricolores (il n'y en a pas dans $R|F$). $R'estdoncbiendanscecas \leq 3$-hypomorphe à R

2.° cas : R contient un drapeau tricolore donc au moins un pavage tricolore (ne couvrant pas nécessairement toute la base) et donc R possède au moins un pavage rauzien maximal P. R, étant connexe, ne peut, d'après le lemme 4, être couverte par ce seul pavage rauzien P. Assurons-nous de la $\leq 3$-hypomorphie entre R et R'. Celle-ci ne serait mise en défaut que dans deux éventualités :

- 1ère éventualité : celleòùpourunx'etunx"de$|P|$ et un t hors de $|P|$ l'ensemble $\{x',x''\}$,t} serait d'un type différent mod R et mod R'. Les arêtes [t,x'] et [t,x''] étant orientées (lemme 8) ce ne serait possible, vu l'absence de pic, que si $[x',x'']$ est orientée. Or dans ce cas $\{x',x''\}$ doit être un t-intervalle (lemme 5) et $\{x,y,t\}$ est alors du même type mod R et mod R' (un ordre total).

- 2ème éventualité : celleòùpourunx'dans$|P|$ et deux t et t' hors de $|P|$, $\{x',t,t'\}$ serait d'un type différent mod R et mod R'. Vu l'absence de pics ce n'est possible, les arêtes [t,x'] et [t',x'] étant orientées que si $\{x',t,t'\}$ était un cycle mod R par exemple et pas mod R'. Les arêtes [t,x'] et [t',x'] étant changeantes il faudrait que [t,t'] ne le soit pas, donc que t et t' sont dans le même pavage rauzien maximal P'. On est ramené à la 1ère éventualité : $[t,t']estarêteorientéedupavageP'et\{t,t'\}doitêtreunx' - intervale - auquelcas\{x',t,t'\}estbiendumêmetypemodRetmodR'$.

On a achevé la démonstration du théorème. Dans un article à venir on verra qu'on peut définir, à coté de l'hypomorphie sur des ensembles à $\leq 3$ éléments, des hypomorphies sur des ensembles infinis, les cas intéressants étant les types de l'ordre et de la consécutivité sur N et leurs duaux.
Un pavage tricolore est dit *arête-maximal* si aucun autre pavage tricolore ne couvre les mêmes sommets en ayant des arêtes en plus. Par exemple sur $\{a, b, c, d\}$ posons $a < b, c < d, [b, d]$ et $[a, c]$ pleines et $[b, c]$ et $[a, d]$ vides. Le pavage tricolore $\{[a, b], [b, d], [c, d], [a, c], [b, c]\}$ n'est pas arête-maximal car on peut lui rajouter l'arête $[a,d]$ qui lui fait couvrir le même ensemble de sommets.

Problème d'unicité des pavages tricolores :

*Deux pavages tricolores arête-maximaux couvrant le même ensemble de sommets sont-ils identiques ?*

References

[1] G. Lopez, L'indéformabilité des relations et multirelations binaires, Z. Math. Logik Grundlag. Math., 24, pp. 303-317, (1978).

[2] R. Fraïssé et G. Lopez, La reconstruction d'une relation dans l'hypothèse forte: isomorphie des restrictions à chaque partie stricte, Les Presses de l'Université de Montréal, no 109, (1990).

[3] R. Fraïssé, Abritement entre relations et spécialement entre Chaînes, Symposia Math., Instituto Nazionale di Alta Matematica, 5, pp. 203-251, (1970).

[4] J. G. Hagendorf et G. Lopez, Un théorème de demi-reconstruction des relations binaires de cardinal 12, Prépublications d'Orsay 1994 p1-300; (non publié).

[5] J. G. Hagendorf et G. Lopez. La demi-reconstructibilité des relations binaires d'au moins 13 éléments. C. R. Acad. Sci. Paris, t. 317, Série I, pp. 7-12, (1993).

[6] G. Lopez and C. Rauzy, Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n-1), I, Z. Math. Logik Grundlag. Math., 38, pp. 27-37, (1992). et II, Z. Math. Logik Grundlag. Math., 38, pp. 157-168, (1992).

[7] Y. Boudabbous, La 5-reconstruction et l'indécomposabilité des relations binaires, European J. Combin., 23, pp. 507-522, (2002).
[8] J. G. Hagendorf, G. Lopez et C. Rauzy, Pavages d'une relation binaire. C. R. Acad. Sci. Paris, t. 321 Série I, pp. 1281-1286, (1995).

[9] J. G. Hagendorf, Restriction respectueuse et reconstruction des chaînes et des relations infinies. Z. Math. Logik Grundlag. Math., 38, pp. 457-490, (1992).

[10] Y. Boudabbous et G. Lopez, La relation différence et l'anti-isomorphie. Math. Log. Quart. 41, pp. 268-280, (1995).

[11] Youssef Boudabbous and Christian Delhommé, ($\leq k$)-reconstuctibles binary relations, à paraître dans le numéro spécial du Journal Européen de Combinatoire, pour la Conférence Internationale "ROGIC'S 08".

[12] Y. Boudabbous and C. Delhommé, Prechains and self duality, Discrete Math. 312, pp. 1743-1765, (2012).

[13] Y. Boudabbous, A. Boussaïri, A. Chaïcha et N. El Amri, Les tournois ($\leq k$)-demi-reconstructibles pour $k\leq 6$, C. R. Acad. Sci. Paris, Série I t. 346, pp. 919-924, (2008).

[14] Y. Boudabbous and G. Lopez, The minimal non-($\leq k$)-reconstructible relations, Discrete Math. 291, pp. 19-40 (2005).

[15] Y. Boudabbous and H. Si Kaddour, {-1,2}-hypomorphы and hereditarily hypomorphы coincide for posets, Contributions to Discrete Math. 4, pp. 12-20, (2009).

[16] A. Boussaïri, P. Ille, G. Lopez, S. Thomassé, Hypomorphie et inversion locale entre graphes, C. R. Acad. Sci. Paris, Sér. I t. 317, pp. 125-128, (1993).

[17] A. Boussaïri : Décomposabilité, dualité et groupes finis en théorie des relations, Thèse de doctorat de mathématiques. Soutenue à l'Université Claude Bernard, le 12 Juin 1995.

[18] J. Dammak. La dualité dans la demi-reconstruction des relations binaires finies. C.R.A.S, Série I t. 327, pp. 861-864, (1998).

[19] Jamel Dammak, Le seuil de reconstructibilité par le haut modulo la dualité des relations binaires finies, Proyecciones Vol. 22, No 3, pp. 209-236, December 2003. Universidad Católica del Norte Antofagasta - Chile
[20] J. Dammak, Caractérisation des relations binaires finies d-demi-reconstructibles, Proyecciones, Volume 22, No 1, pp. 31-61, (2003).

[21] N. El Amri, La ($\leq k$)-demi-reconstructibilité des graphes pour $7\leq k\leq 12$, to appear in Ars Combinatoria.

**Jean G. Hagendorf**

14 all'ee de l'Oseraie

94260 Fresnes

France

e-mail : jean.hagendorf@sfr.fr

**Gerard Lopez**

retired of Institut de Math'ematiques de Luminy

13288 Marseille

France

e-mail : gerardlopez@free.fr

and

Claire Rauzy

died of Université d'Aix-Marseille

France

e-mail : décédée.