# Classes de ($\leq 3,\omega,\omega^*,\Omega, \Omega^*$)-hypomorphie infinies

Jean Guillaume Hagendorf

Université de Paris, France

Received : December 2013. Accepted : June 2014

## Abstract

Cet article se veut une suite à [23] puisque après l'étude des classes de ($\leq 3$)-hypomorphie à laquelle est consacrée [23] nous allons étudier les classes d'hypomorphie infinies avec des conditions d'hypomorphie infinie. Nous y utiliserons aussi la notion de pavages mais ceux-ci seront différents de ceux de [23] car la problématique n'est plus la même. Au passage nous décrirons les classes de ($\leq 3,4/2$)-hypomorphie. Voir la bibliographie pour d'autres études en rapport avec l'hypomorphie infinie ou finie ou avec la problématique de la reconstruction qui y est liée.

Classification AMS : 05C60.

Mots-clés : Relation, Binaire, Graphe, Reconstruction, Différence, Hypomorphie, Hémimorphie, Pavage, Interdit, Drapeau, Infini.
Rappelons et complétons d'abord les principales définitions et notations
qui figurent dans [23].

§1. Définitions et rappels.

On appelle relation binaire R de base E (base qui sera notée |R|) une
application de E² dans un ensemble arbitraire à deux éléments : {+,-}.
Les éléments de la base pourront être appelés sommets de R. L'assertion
<<R(a,b)=+>> pourra se lire <<R(a,b) est vraie>>. Si F est une partie de
la base de R on note R|F la restriction de R à F. Si a et b sont 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)≠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 encore a|b si l'arête [a,b] est neutre. Un tournoi est une relation
binaire sans arête neutre. On notera <<a<b mod R>> si a≠b avec [a,b]
R-orienté et R(a,b)=+ (et donc R(b,a)= - ) ; on dira que <<b majore a>>
(sous entendu, comme toujours ici, <<strictement>>) ou encore que <<a est
minorant de b>>, 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 à R') si
R(a,b)≠R'(a,b) (et donc R(a,b)=R'(b,a)). On dira qu'un extremum change
s'il est maximum pour une des relations R ou R' et minimum pour l'autre.
De même on parlera de <<minorant ou majorant changeant>> d'un ensemble
pour dire d'un élément qu'il majore cet ensemble modulo une des relations
R ou R' et le minore modulo l'autre.

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 a résidé dans [23] en l'étude du drapeau tricolore qui est la configuration minimale contenant trois arêtes de types différents, une pleine, une vide et une orientée. Mais notre inclination à utiliser le langage des relations (voir [14]) subsitera dans l'étude présente.

Par ailleurs nous utiliserons aussi le langage des graphes plus largement
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 à l'auteur : le pavage. Elle concerne l'organisation des sous-graphes de
la relation de certains types. Dans [23] 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. De fait dans cet article les pavages ne seront plus constitués de drapeaux tricolores mais de 3-cycles et de 3-consécutivités nouvel outil technique nécessaire à l'élaboration de la preuve du théorème principal de cet article.

### Hypomorphie finie :

Soit n un nombre entier, disons que deux relations binaires R et R' de même base E sont n-hypomorphes si pour toute partie F de la base de cardinal n, $R|F$ et $R'|F$ sont isomorphes. On parlera de ($\leq n$)-hypomorphie pour dire qu'il y a p-hypomorphie pour tout entier $p \leq n$ et $\leq \text{card}(R)$.

Dans une relation binaire R appelons chemin de flèches une suite finie d'arêtes $([x_0,x_1],[x_1,x_2],..., [xp-1,xp])$ notée $[x_0,x_1,...,xp]$ où $[xq,xq+1]$ est, pour $0 \leq q < p$, une flèche mod R. Les arêtes $[xp,xq]$ où $p \neq q$ et $|p-q| \neq 1$ sont dites internes au chemin. Etant données deux relations R et R' binaires de même base et $\leq 2$-hypomorphes, G. Lopez a introduit dans [25] 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. Définition évidente d'un chemin monotone. Le chemin 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ù $R(a,b) \neq R'(a,b)$ forment le graphe de différence noté SR,R' associé à R et R'.

### Hémimorphie finie :

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

Une relation binaire R est dite anti-isomorphe à une relation R' si R est isomorphe à la duale de R'. On définit de même l'anti-hypomorphie.

Soit n un nombre entier, disons que deux relations binaires R et R' de même base E sont n-hémimorphes ou n-demi-hypomorphes ou encore $n/2$-hypomorphes si pour toute partie F de la base de cardinal n, $R|F$ et $R'|F$ sont isomorphes ou anti-isomorphes (c'est à dire chacun isomorphe au dual de l'autre). Notation dérivée pour $\leq n/2$, etc...

### Classes d'identité:
Soit R et R' deux relations binaires de même base. On définit la notion de chemin d'identité et de classe d'identité par dualité avec les notions déjà introduites de chemin de différence et de classe de différence : un (R,R')-chemin d'identité est un (R,R')-chemin de différence et une (R,R')-classe d'identité est une (R,R')-classe de différence.

**Appelons** presque-intervalle de R une partie A de la base telle que si x est extérieur à A et si a et b sont dans A alors R(x,a)=R(x,b) et R(a,x)=R(b,x) dès que [x,a] est orientée. Par contre si [x,a] est neutre, [x,b] est neutre mais possiblement de nature différente de [x,a] : un vide l'autre plein. Les classes d'identité de deux relations $\leq 3$-hypomorphes ne sont plus des intervalles, ce sont des presque-intervalles.

**On appelle.** chaîne un ordre total partout irréflexif ou partout réflexif, on appelle conséutivité une restriction sur un intervalle fini de card $>2$ ou infini de $Z$ d'une des quatre relations suivantes : $\ll R(x,y)=(+)$ ssi $y=x+1\gg$ (conséutivités irréflexives à arêtes neutres vides) ou $\ll R(x,y)=(+)$ ssi $y=x+1$ ou $|y-x|\neq 1\gg$ (conséutivités irréflexives à arêtes neutres pleines) et les deux autres conséutivités réflexives associées. Un cycle est une relation binaire définie de la même manière sur $Z/nZ$ ($n\in N$, $n>2$). Un cycle est donc une conséutivité dont les extrémités ont été identifiées. On parlera de p-cycle ou de p-conséutivité pour préciser que le cardinal est p. On parlera abusivement d' $\ll$ intervalle $\gg$ d'une conséutivité pour désigner un intervalle de la chaîne canoniquement engendrée par cette conséutivité.

On appelle type de relation une relation prise à l'isomorphie près. On note $\omega$ le type de n'importe laquelle laquelle des chaîne habituelles sur $N$ qu'elle soit partout réflexive ou partout irréflexive. On note $\Omega$ le type de n'importe laquelle des quatre conséutivités sur $N$ qu'elle soit réflexive ou irréflexive, que les arêtes neutres soient toutes vides ou toutes pleines. On parlera de fini-hypomorphie (encore appelée $(<\omega)$-hypomorphie) pour dire qu'il y a n-hypomorphie pour tout n fini $\leq \text{card}(R)$.

**Hypomorphie infinie :**

Deux relations binaires R et R' de même base E sont par définition $\{\omega,\omega*,\Omega,\Omega*\}$-hypomorphes si pour toute partie F de la base, $R|F$ et $R'|F$ sont isomorphes dès que $R|F$ ou $R'|F$ est du type $\omega$ de la chaîne (partout réflexive ou partout irréflexive) sur $N$, ou son opposée $\omega^*$; ou encore du type $\Omega$ de la conséutivité (partout réflexive ou partout irréflexive, les arêtes neutres étant toutes vides ou toutes pleines) sur $N$, ou son opposée $\Omega^*$. On
convient qu'il y a $\omega$-hypomorphie quand aucune restriction n'est de type $\omega$, idem pour les autres types précédemment définis.

**Hémimorphie infinie :**

La notation $\jmath R$ et $R'$ sont {$\omega/2$}-hypomorphes≫ signifie qu'un R-type $\omega$ devient un R'-type $\omega$ ou $\omega^*$ et réciproquement en échangeant R et $R'$. De même pour le type $\omega^*$ ou $\Omega$ ou $\Omega^*$.

Remarquons que la $\omega/2$-hypomorphie n'entraîne pas la $\omega^*/2$-hypomorphie : prendre pour R l'ordre naturel sur $N^-=\{-1,-2,-3,...\}$ et $R'$ est obtenu en posant $-7<-5<-3<-1<-2<-4<-6<-8<...$.

Disons qu'une relation R est une classe de $\leq n$-hypomorphie s'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 parlera de même de classe de $(\omega)$-hypomorphie ou de $(\leq 3,\Omega)$-hypomorphie etc...

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)$. I est dit un intervalle s'il est z-intervalle pour tout z hors de I. On montre (voir [27]) que les classes de différence de relations $\leq 3$-hypomorphes sont des intervalles.

On appelle dilatée de chaîne une relation binaire R obtenue en dilatant certains sommets d'une chaîne par des intervalles de 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.

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 en [28] (et ce sera rappelé au §3) qu'il n'y a pas de pic dans une classe de $\leq 3$-hypomorphie.

Rappelons 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]$ plein. L'arête $[x,y]$ est appelée flèche ou composante connexe du drapeau.

Le principal résultat de cet article dira au §4 que les classes de $(\leq 3,\omega,\omega^*,\Omega,\Omega^*)$-hypomorphie infinies sont les dilatées de chaînes infinies de type $\omega, \omega^*$ ou $\omega^*+\omega$ par des tournois finis ; après qu'au §3 nous ayons caractérisé les classes de $(\leq 3,4/2)$-hypomorphie par le fait qu'elles soient connexes, sans pics ni drapeaux tricolores.
On appelle presque-chaîne de presque-extrémités a et b, une relation binaire de base E contenant a et b qui, sauf peut être pour le couple [a,b], est une chaîne d'extrémités a et b. Par commodité une chaîne sans extrémités ou avec une seule extrémité (donc infinie) sera aussi appelée une presque-chaîne.

On parlera de n-chaîne ($n \in N$), de n-cycle ou de n-consécutivité pour dire que le cardinal de la chaîne (ou du cycle etc ...) est n. Un chemin de n arêtes est dit de longueur n, son nombre de sommets est donc $n+1$.

## §2. Premiers lemmes.

**Petit lemme 1.** Soit R et R' deux relations binaires $\leq \frac{3}{2}$-hypomorphes. Soit x et y deux éléments de la même classe de différence tel que $[x,y]$ soit orientée et non changeante. Alors tout chemin de différence minimal liant x et y est alterné. Les arêtes internes du chemin sont toutes orientées dans le sens de l'orientation de $[x,y]$ et finalement l'ensemble des sommets du chemin est une chaîne.

**Preuve.** Supposons par exemple $x<y \mod R$ et $R'$. Soit $[x,x1, \dots, xp=y]$ un chemin de différence minimal. Si $[x,x1]$ et $[x1,x2]$ sont orientées dans le même sens; l'orientation de $[x,x2]$ est incompatible avec la minimalité car $x2$ constitue un détour inutile. $[x,x2]$ est donc neutre. Du coup le changement de $[x2,x3]$ oblige $[x,x3]$ soit à être neutre soit à être orientée et à changer, mais dans ce dernier cas $[x1,x2]$ constituerait un détour inutile. De proche en proche $[x,xp-1]$ est neutre ce qui donne la contradiction finale.

L'arête $[x,x1]$ étant changeante, $[y,x1]$ ne peut être neutre : par minimalité il faut que $[y,x1]$ soit non changeante et par suite on doit avoir $y>x1$. De même $x<xp-1$ et de proche en proche toutes les arêtes internes sont orientées comme le dit l'énoncé. Il n'y a donc pas de 3-cycle ni d'arête neutre interne et l'ensemble des sommets est bien une chaîne.

**Petit lemme 2.** Soit R et R' deux relations binaires $\leq \frac{3}{2}$-hypomorphes. Tout chemin de différence minimal liant les extrémités d'une arête neutre, a ses arêtes internes neutres.

**Preuve.** Soit $[x0,x1, \dots, xn]$ un tel chemin. Si $[xn-1,x0]$ est orientée cette orientation doit changer. Du coup le chemin donné n'est plus minimal. De proche en proche le résultat est acquis.

Un graphe non orienté est dit localement fini si chaque sommet n'est lié qu'à un nombre fini d'autres.
**Lemme 3 de finitude locale.** Le graphe de différenceSR,R' de deux relations R et R', {$\leq 3,\omega,\omega^*$}-hypomorphes, est localement fini.

**Preuve.** Supposons qu'une infinité d'éléments parcourus sans répétition par une séquence $x\alpha$ soit lié par le graphe à un $x$ différent d'eux. Col- orons les paires {$\alpha,\beta$} (posons $\alpha<\beta$) en trois couleurs suivant que $x\alpha|x\beta$ ou $x\alpha<x\beta$ ou $x\alpha>x\beta$.

S'il existe une infinité de la première couleur on a sur chaque ensemble {$x,x\alpha,x\beta$}, une isomorphie entre R et R' qui est incompatible avec l'inversion de 3 arêtes [x,x$\alpha$], [x,x$\beta$] et [x,x$\gamma$] : au moins un pic apparaît qui n'est pas isomorphe à son dual.

S'il existe une infinité de {$x\alpha$}$\alpha$ de la deuxième couleur alors il existe une infinité {$x\alpha'$}$\alpha'$ telle que $x<x\alpha'$ mod R ou $x>x\alpha'$ mod R. Ainsi comme {$x\alpha'$}$\alpha'$ est de R'-type $\omega$ (par $\omega$-hypomorphie) on a:

ou bien {$x\alpha$}∪{$x\alpha'$} est de R-type $\omega$ et de R'-type $\omega+1$;

ou bien {$x\alpha$}∪{$x\alpha'$} est de R-type $\omega+1$ et de R'-type $\omega$.

Les deux cas contredisent la $\omega$-hypomorphie.

S'il existe une infinité de {$x\alpha$}$\alpha$ de la troisième couleur la preuve est analogue au deuxième cas en se servant de la $\omega$*-hypomorphie au lieu de la $\omega$-hypomorphie. .

Alexandre Mizrahi a démontré la réciproque :

**Proposition 1.** Si le graphe de différence SR,R' de deux relations R et R' ($\leq 3$)-hypomorphes est localement fini elles sont {$\leq 3,\omega,\omega^*$}-hypomorphes.

**Preuve.** En effet si par exemple un $\omega$ mod R n'est pas conservé mod R' on peut en extraire une partie de R-type $\omega$ qui mod R' sera de type $\omega^*$ ou $\omega+1$ ; dans les deux cas un sommet est de degré infini dans SR,R'.

Si $\alpha$ est un type d'ordre la $\alpha$-hypomorphie entre R et R' désignera la propriété qui dit que toute partie de R-type $\alpha$ est encore de R'-type $\alpha$ et réciproquement.

Rappelons que si deux relations de même base sont {$\leq 3,\omega,\omega^*$}-hypomorphes alors elles sont isomorphes sur toute chaine, propriété qu'on nomme {$\leq 3$,chaine}-hypomorphie.

Voir la preuve en [20] p 474.

La $\leq 2$-hypomorphie préserve la connexité. Si les relations binaires R et R' sont $\leq 2$-hypomorphes les (R,R')-classes de différence sont partout irréflexives ou partout réflexives; et la $\leq 3$-hypomorphie suffit pour affirmer que les classes de différence sont des intervalles.
**Rappelons le dans les deux lemmes suivants :**

**Lemme 4.** Si R et R' sont deux relations binaires $\leq 2$-hypomorphes, les $(R,R')$-classes de différence sont entièrement réflexives ou entièrement irréflexives.

**Preuve.** Soit a un élément où R est réflexif et b un élément où R est irréflexif. $R|\{a,b\}$ devant être isomorphe à $R'|\{a,b\}$, $R(a,b)$ est égal à $R'(a,b)$ et a et b ne peuvent être liés par $SR, R'$.

Notons $R|(a,b)$ le couple $(R(a,b),R(b,a))$.

**Lemme 5.** (voir [27]) Si R et R' sont deux relations binaires $\leq 3$-hypomorphes, les $(R,R')$-classes de différence sont des intervalles (mod R et mod R').

**Preuve.** Soit a et b deux éléments successifs d'un $(R,R')$-chemin de différence et c un élément extérieur à la classe de a et b. L'élément c n'étant pas dans la même classe que a et b il faut que $R|(c,a)=R'|(c,a)$ et $R|(c,b)=R'|(c,b)$. On vérifie facilement à la main que l'isomorphie entre $R|\{a,b,c\}$ et $R'|\{a,b,c\}$ impose, $[a,b]$ changeante par passage de R à R', que $R|(c,a)=R'|(c,a)= R|(c,b)=R'|(c,b)$.

**Lemme 6.** Si R et R' sont deux relations binaires $\leq 3/2$-hypomorphes, les $(R,R')$-classes de différence sont des presque-intervalles.

**Même preuve.**

Néanmoins :

**Lemme 7.** Soit R et R' deux relations binaires ($\leq 4/2$)-hypomorphes. Les classes de différence D qui sont des b-intervalles orientés pour un b au moins hors de D, sont des intervalles. Cette condition est évidemment réalisée si R (ou/et) R' est connexe.

**Preuve.** Soit $[x,y]$ une flèche changeante d'une classe de différence D et a un élément extérieur lié à x par une arête pleine alors que $[y,a]$ est vide. Un élément b hors de D est lié à x par une flèche $[b,x]$. Si $[a,b]$ est vide, une iso- ou anti-isomorphie, disons f, entre R et R' sur $\{a,b,x,y\}$ se doit de conserver x, seul sommet incident à une arête pleine et à deux flèches, a est donc conservé aussi; observons que f est un isomorphisme ou un anti-isomorphisme entre les deux restrictions $R|\{b,x,y\}$ et $R'|\{b,x,y\}$ et que
ces deux restrictions sont des chaînes; mais x est soit R-2ème et R'-3ème élément soit R-1er et R'-2ème élément (suivant l'orientation de [b,x]) ce qui est irréalisable. Si [b,a] est plein, a est conservé, comme seul sommet de {a,b,x,y} incident à 3 arêtes neutres, et aussi y, lié à a par une arête vide; le même type de raisonnement que précédemment donne la solution. Si [a,b] et orientée, une iso- ou anti-isomorphie entre R et R' sur {a,b,x,y} se doit de conserver a (seul sommet incident à deux arêtes neutres), donc aussi x et y, et la même absurdité apparaît.

**Proposition 2.** Soit R et R' deux relations binaires ($\leq 3/2$, $\omega/2$, $\omega^*/2$)-hypomorphes. Sur chaque classe de différence on a ($\omega,\omega^*$)-hypomorphie ou ($\omega,\omega^*$)-anti-hypomorphie.

**Preuve.** Supposons, pour simplifier les notations, R formée d'une seule classe de différence. Soit A une partie de R-type $\omega$ qui se conserve globalement et B une partie de R-type $\omega$ qui s'inverse globalement, supposée d'abord sans élément commun avec A. Soit $[b,b1,b2,...,a',a]$ un chemin de (R,R')-différence de longueur minimum allant de b dans B à a dans A où on suppose, quitte à inverser le chemin, $a' < a$ mod R, avec $a'$ hors de A sans quoi le chemin pouvait être raccourci. On a soit, -1ère possibilité : existence d'une partie infinie C de A (qui est donc de R-type et de R'-type $\omega$) telle que pour tout x de C, on a $a' < x$ mod R et $[a',x]$ s'inverse; cette possibilité implique l'existence d'une partie de $A \cup \{a'\}$ qui est de R-type $\omega$ et de R'-type $\omega+1$. Soit, -2ème possibilité : existence d'une partie infinie C de A (qui est donc de R-type et de R'-type $\omega$) telle que pour tout x de C, on a $a' < x$ mod R et $[a',x]$ ne s'inverse pas. La 2ème possibilité dit que A peut absorber $a'$ et former avec $\{a'\}$ un nouvel ensemble $A' = A \cup \{a'\}$ possédant la même propriété que A et le chemin a encore été raccourci. De proche en proche on se ramène donc au cas où A et B ont un élément commun a par exemple. Prenons un y dans B assez grand pour être $> a$ mod R et $< a$ mod R', et dans A un $x > a$ mod R et R'. On a donc $y < x$ mod R'. De même pour tout $y' > y$ pour lequel $[y',a]$ s'inverse qui sera identifié à $y+1$, donc $\{x,y,y+1,y+2,...\}$ est de type $\omega^*$ mod R' et doit être de type $\omega$ mod R; par suite $[y,x]$ doit se conserver pour y dans B assez grand mod R. Dans ce cas $\{x,y,y+1,y+2,...\}$ est de R-type $\omega+1$ et de R'-type $\omega^*$. -Absurde.

§3. Classes de ($\leq 3, 4/2$)-hypomorphie.

**Définitions.**
Certains lemmes, obtenus ici par la méthode des pavages, sont connus.

Une relation binaire peut être considérée comme un graphe. Un sous-graphe partiel de R consiste en la donnée d'une partie de l'ensemble des arêtes de R (et de l'ensemble des sommets correspondant). Dans une relation binaire R appelons pavage tout sous-graphe partiel P de R dont l'ensemble des arêtes vérifiera la condition suivante : si u et v sont deux arêtes de l'ensemble il existe une suite C1,C2,...,Cn de 3-cycles ou 3-consécutivités dont les arêtes sont dans le sous-graphe partiel P, chacun adjacent à un précédent par une arête neutre ou orientée, telle que u est une arête de C1 et v une arête de Cn. Les Ci ne sont pas nécessairement tous différents bien que cette éventualité ne change rien. On parlera donc d'arête ou de sommet du pavage, sommet encore dit couvert par le pavage. Les 3-cycles ou 3-consécutivités sont appelés des pavés. Prenons encore garde au fait qu'une flèche reliant deux sommets d'un pavage n'est pas nécessairement arête du pavage. Dans une relation binaire, une restriction est dite payable (ou couverte par un pavage) si l'ensemble de ses sommets est l'ensemble des sommets d'un pavage, (elle doit donc contenir au moins une consécutivité ou un 3-cycle, donc au moins 3 éléments). On voit aisément que le changement de sens d'une flèche du pavage entraîne le changement de toutes les autres si on veut conserver la $\leq 3/2$-hypomorphie: il suffit d'examiner le cas d'une arête neutre dont les extrémités sont reliées par une 3-consécutivité changeante et une autre non changeante. On peut donc dire d'un pavage qu'il est nécessairement changeant ou non changeant quand on passe d'une relation R à une $R' \leq 3$-hémimorphe à R. Les pavages permettent de synthétiser de nombreux résultats de la théorie de l'hypomorphie tout en les simplifiant. L'unicité des pavages arête-maximaux couvrant un ensemble de sommets fixé est un problème ouvert.

**Lemme 0 des pavages interdits.** Soit R et R' deux relations binaires ($\leq 3/2$)-hypomorphes. Une relation binaire M payable par un pavage non changeant ne peut être incluse dans une (R,R')-classe de différence que dans le cas où existe dans la base un minorant ou majorant (R,R')-changeant de M. Plus précisément tout chemin de différence minimal entre éléments de M est alterné et de longueur 2, et passe par un tel minorant ou majorant changeant.

**Scolie 0:** Ce minorant ou majorant changeant est extérieur à M.

Ce lemme se démontera quand M est un 3-cycle puis quand M est une 3-consécutivité, puis sera étendu à toute relation payable. Voyons tout de
suite que l'énoncé ne se maintient pas pour les pics : un pic est une relation R sur $\{x,y,z\}$ où [y,z] est neutre et où [x,y] et [x,z] sont orientées et vérifient $R(x,y)=R(x,z)$ (et donc $R(y,x)=R(z,x)$). Dans l'exemple suivant le pic $\{x,y,z\}$ possède un R-minorant mais pas de R'-majorant. R est de base $\{x,y,z,a,b\}$ avec, mod R, $x<y, x<z, x>a, x<b, y<z, y>a, y<b, z>a, z<b, a<b$. Mod R' on a $x<y, x<z, x<a, x<b, y<z, y>a, y>b, z>a, z>b, a>b$.

**Preuve.**

1er cas. M est un 3-cycle :

**Lemme 1.** Soit R et R' deux relations binaires ($\leq 3/2$)-hypomorphes. Dans une classe de (R,R')-différence, un 3-cycle non changeant possède un majorant ou minorant changeant.

**Scolie 1.** Tout chemin de différence minimal liant les extrémités d'une arête non changeante du 3-cycle est de longueur 2.

**Preuve.** Montrons d'abord la scolie. Soit $\{x,y,z\}$ un tel cycle avec $x>y, y>z, z>x$ mod R et R'.

On considère un chemin de différence minimal $[x,x1,...,xp=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 $a>z$ mod R'. Comme $\{a,x,y\}$ ne peut pas être un R'-cycle il faut $a<x$ mod R. Si le chemin n'était pas de longueur 2 on aurait aussi $a<x$ mod R'. Mais le chemin étant alterné on doit, pour éviter un R-cycle sur $\{xp-1,xp,z\}$, avoir $z<xp-1$ mod R. Supposons dans la suite de l'alinéa qu'on ait $xp-1<z$ mod R', $[xp-1,y]$ serait orientée par $xp-1<y$ mod R'. De même l'examen de $\{xp-1,z,x\}$ montre que $x<xp-1$ mod R. Par minimalité du chemin $[xp-1,y]$ doit ne pas changer ; $[xp-1,y,x]$ est donc un cycle et par suite $x<xp-1$ mod R'. Mais alors $[xp-1,a,x]$ est un cycle mod R' et pas mod R. Cette contradiction prouve que $xp-1>z$ mod R'. On aura de même $z<xp-2$ mod R' et de proche en proche on aboutira à une absurdité. Est donc acquis que tout chemin minimal est de longueur 2. Passons à l'existence du majorant ou minorant changeant.

Soit $[x,m,y]$ un chemin minimal avec par exemple $x>m<y$ mod R et le contraire mod R'. Il faut voir que $m<z$ mod R et le contraire mod R'. L'examen de $\{m,y,z\}$ montre que $m>z$ mod R'. Si on avait $m>z$ mod R $[m,x,z]$ serait un R-cycle et pas un R'-cycle -absurde.

**Application :** Dans une classe de $\leq 4$-hypomorphie les 3-cycles se dualisent. En effet en cas contraire le cycle constituerait avec son majorant
ou minorant changeant, un diamant d'un certain type mod R et d'un type opposé mod R', ce qui est contraire à la $\leq 4$-hypomorphie.

On n'a en fait utilisé que la $\leq 3$-hypomorphie et l'inexistence de diamants.

2ème cas du lemme des pavages interdits. C'est celui de la 3-consécutivité qui se démontre de même :

**Lemme 2.** Soit R et R' deux relations binaires ($\leq 3/2$)-hypomorphes. Dans une classe de (R,R')-différence, une 3-consécutivité non changeante possède un majorant ou minorant changeant.

**Scolie 2.** Tout chemin de différence minimal liant les extrémités d'une flèche non changeante de la 3-consécutivité est de longueur 2.

**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 arête non changeante d'une 3-consécutivité de R est de longueur 2. Soit $\{x,y,z\}$ une telle consécutivité avec $x>y, y>z$ mod R et R'.

On considère un chemin de différence minimal $[x,x1, ..., xp=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 $a>z$ mod R'. Comme $\{a,x,y\}$ ne peut pas être un R'-cycle il faut $a<x$ mod R. Si le chemin n'était pas de longueur 2 on aurait aussi $a<x$ mod R'. On a nécessairement $z<a$ mod R. Mais le chemin étant alterné on doit, pour éviter un R-cycle sur $[xp-1,xp,z]$, avoir $z<xp-1$ mod R. Supposons dans la suite de l'alinéa qu'on ait $xp-1<z$ mod R', $[xp-1,y]$ serait orientée par $xp-1<y$ mod R'. De même l'examen de $\{xp-1,a,x\}$ montre que $x>xp-1$ mod R'. Par suite $x<xp-1$ mod R. Par minimalité du chemin $[xp-1,y]$ doit ne pas changer ; $[xp-1,y,x]$ est donc un R-cycle et pas un R'-cycle. Cette contradiction prouve que $xp-1 >z$ mod R'. On aura de même $z<xp-2$ mod R' et de proche en proche on aboutira à une absurdité. Est donc acquis que tout chemin minimal est de longueur 2. Passons à l'existence du majorant ou minorant changeant.

Soit $[x,m,y]$ un chemin minimal avec par exemple $x>m<y$ mod R et le contraire mod R'. Il faut voir que $m<z$ mod R et le contraire mod R'. L'examen de $\{m,y,z\}$ montre que $m>z$ mod R'. Si on avait $m>z$ mod R $[m,x,z]$ serait un R-cycle et pas un R'-cycle, -absurde.
**Corollaire 1.** Les consécutivités de card $>2$ s'inversent dans une classe de $\leq 3$-hypomorphie.

**Preuve.** Si une consécutivité ne changeait pas elle possèderait, dans $R$, un majorant ou minorant changeant, qui formerait un pic changeant avec l'arête neutre. Absurde.

On passe des 3-cycles et 3-consécutivités aux pavages quelconques grâce à :

**Lemme 3.** Soit $R$ et $R'$ deux relations binaires $\leq 3/2$-hypomorphes. Si une 3-consécutivité ou un 3-cycle non changeant possède un minorant changeant, ce minorant est minorant changeant de chacun des sommets de tout pavage contenant le 3-cycle ou la 3-consécutivité. De même évidemment pour les «majorants», et/ou en échangeant les locutions «changeant» et «non changeant».

Il suffit en fait de voir que si un élément $m$ extérieur à un 3-cycle ou à une 3-consécutivité changeante et disons $< (\text{mod } R \text{ et } R')$ à deux éléments du cycle ou de la consécutivité il est aussi $< (\text{mod } R \text{ et } R')$ au troisième.

Le lemme des pavages interdits est donc démontré. Mais on peut renforcer ce lemme en constatant que le minorant ou majorant changeant dont on a démontré l'existence ne peut qu'être extérieur aux sommets du pavage (non changeant); c'est le contenu de la scolie. Et par suite, l'ensemble $C$ des éléments du pavage $P$ ne peut constituer une seule classe de $(R|C,R'|C)$-différence. De même s'il est minorant ou majorant non changeant, l'ensemble $C$ des éléments du pavage $P$ ne peut constituer une seule classe de $(R|C,R'|C)$-identité.

**Corollaire 2.** Les consécutivités infinies sont interdites dans une classe de ($\leq 3/2, \Omega$)-hypomorphie.

**Preuve.** Dans une telle classe les consécutivités doivent s'inverser, en particulier toute partie de type $\Omega$ ou $\Omega^*$. Ceci est incompatible avec la $\Omega$-hypomorphie.

Pour les drapeaux tricolores on a un énoncé légèrement différent, différence due aux problèmes de connexité :

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

**Preuve.** Soit {$x,y,z$} ce drapeau avec $y<x$. Considérons un chemin de différence $[y=y_0, y_1, ..., y_q=z]$. Notons que $q \ge 2$.

L'examen de {$x,y,y_1$} montre que l'arête $[x,y_1]$ est nécessairement orientée.

Comme $[x,y_1]$ est orientée et $[x,y_q=z]$ neutre il doit y avoir un entier $p$ maximal, avec $1 \le p<q$, tel que $[x,y_p]$ est orientée et $[x,y_{p+1}]$ neutre.

Comme $[y_p,y_{p+1}]$ est orientée changeante et $[x,y_{p+1}]$ neutre alors, $[y_p,x]$ étant orientée, elle doit être aussi changeante (par $\le 3/2$-hypomorphie appliquée à {$x,y_p,y_{p+1}$}).

Ainsi dans {$y,x,y_p$} on a :

- $[y,y_p]$ est neutre comme arête interne d'un chemin minimal liant les extrémités de l'arête neutre $[y,z]$ en invoquant le petit lemme 2 du §2.

- $[y,x]$ est orientée non changeante.

- $[x,y_p]$ est orientée changeante.

Ceci contredit la $\le 3/2$-hypomorphie appliquée sur {$x,y,y_p$}.

En fait on a montré un peu plus que l'énoncé : si une arête neutre d'un drapeau tricolore a ses extrémités dans une classe de (R,R')-différence où R et R' sont ($\le 3/2$)-hypomorphes les extrémités de la flèche du drapeau y sont aussi et possèdent un minorant (ou majorant) changeant. Si ce sont les extrémités de la flèche du drapeau tricolore qui sont dans la classe de ($\le 3/2$)-hypomorphie alors le troisième sommet n'y est pas nécessairement et la conclusion est fausse. Donnons l'exemple suivant : soit {$x,y,z$} le drapeau tricolore où $y<x$. Soit $[y,x2,x1,x]$ un chemin de différence liant y à x avec mod R : $y<x2$, $x2>x1$ et $x1<x$. Soit encore mod R et R' : $y<x1$ et $x2<x$. Enfin les arêtes issues de z sont toutes neutres et la base de R est formée des cinq éléments z,x,x1,x2,y. Les éléments x et y se trouvent dans une même classe de (R,R')-différence mais ne possèdent pas de minorant ou majorant changeant car z n'est pas dans la classe.

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

**Preuve.** Conservons les mêmes notations que dans le précédent énoncé. Grâce à la $\le 3$-hypomorphie le majorant ou minorant m, devrait être tel
que [m,z], s'il était neutre, serait à la fois plein (par examen de {m,z,x}) et vide (par examen de {m,z,y}). On a donc m>z.

Dans cet énoncé l'hypothèse de ($\leq 3/2$)-hypomorphie est insuffisante comme le montre l'exemple suivant :

La base est $E=\{a,b,c,d,e\}$ avec mod R: $a<b$, $[a,c]$ plein, $a>d$, $a<e$, $b>c$, $b>d$, $b>e$, $[c,d]$ plein, $[c,e]$ vide, $d>e$. Pour obtenir R' on inverse toutes les flèches sauf $[a,e]$ et $[d,e]$.

**Corollaire 4.** Dans une classe de ($\leq 3,4/2$)-hypomorphie il n'y a pas de drapeau tricolore.

**Preuve.** En effet le drapeau forme, avec le majorant ou minorant de la partie connexe, un 4-emble sur lequel il n'y a ni iso- ni anti-isomorphie entre R et R'.

Procédons à un rappel en montrant que les pics sont interdits dans les classes de $\leq 3$-hypomorphie.

**Lemme 4 de multiplicité des classes.** Soit R et R' deux relations binaires ($\leq 3/2$)-hypomorphes. Un pic A non changeant ne peut être inclus dans une (R,R')-classe de différence que s'il existe dans la base un pic Â (précisé dans la preuve), non changeant, isomorphe à A, et possédant un minorant ou majorant changeant.

**Preuve.** Posons $A=\{a,b,c\}$ avec par exemple $a<b$ et $a<c$ mod R', $[b,c]$ étant neutre. On a aussi $a<c$ et $a<b$ mod R. Considérons un chemin de différence liant a à b. Appelons a' la première escale du chemin au départ de a et supposons (quitte à échanger les rôles de R et de R') que $a'<a$ mod R' et le contraire mod R. Pour éviter un R'-cycle sur $\{a,a',b\}$ irréalisable mod R, il faut que $a'<b$ mod R'. De même $a'<c$ mod R'. De deux choses l'une : Ou bien $R|\{a',b,c\}$ est anti-isomorphe à $R'|\{a',b,c\}$ et $Â=\{a,b,c\}$ est doté d'un R-majorant changeant $a'$ ; Ou bien $R|\{a',b,c\}$ est isomorphe à $R'|\{a',b,c\}$ et on recommence alors le même raisonnement avec $\{a',b,c\}$, de proche en proche on aboutit à une contradiction qui assure l'existence d'un $Â=\{a',b,c\}$ où â est sur le chemin liant a à b.

**Corollaire 5 (voir [28]).** Les pics sont interdits dans une classe de $\leq 3$-hypomorphie.
**Preuve.** La $\leq 3$-hypomorphie contraint les pics à se conserver. Un pic (le Â du lemme) a donc un majorant ou minorant changeant; lequel forme avec l'arête neutre du pic, un nouveau pic changeant. Absurde.

Le même énoncé subsiste pour les diamants et la preuve se calque sur la précédente où on n'utilise que le fait que $\{b,c\}$ est un intervalle. On obtient donc comme plus haut :

**Corollaire 6 (voir [28]).** Les diamants sont interdits dans une classe de $\leq 4$-hypomorphie.

On en déduit:

**théorème 1.** Une classe de ($\leq 3,4/2$)-hypomorphie est caractérisée par le fait d'être connexe, sans pic et sans drapeau tricolore.

§4.

On se propose de démontrer les théorèmes suivants grâce aux lemmes qui vont venir.

**théorème 1.** Toute classe de ($\leq 3,\omega,\omega^*,\Omega,\Omega^*$)-hypomorphie infinie est dilatée de chaîne infinie de type $\omega$, $\omega^*$ ou $\omega^*+\omega$ par des tournois finis.

Et plus généralement après avoir introduit la notion de classe d'identité :

**théorème 2.** Soit $R$ et $R'$ deux relations binaires ($\leq 3,\omega,\omega^*$)-hypomorphes ne formant qu'une classe d'identité et une classe de différence. Alors $R$ est dilaté d'une chaîne de cardinal $>3$.

On peut prouver la possibilité de remplacer $\leq 3$ par $\leq 3/2$ dans ce dernier énoncé.

On tirera du précédent théorème :

**théorème 3.** Les classes de ($\leq 3,5/2,\omega,\omega^*,\Omega,\Omega^*$)-hypomorphies infinies sont des chaînes infinies de type $\omega$, $\omega^*$ ou $\omega^*+\omega$.

En particulier les classes de ($\leq 4,\omega,\omega^*,\Omega,\Omega^*$)-hypomorphies infinies sont des chaînes infinies de type $\omega$, $\omega^*$ ou $\omega^*+\omega$.

Ce sera l'aboutissement des lemmes et définitions qui vont suivre.

**Lemme 00.** $\omega+1$ est interdit dans une classe de ($\leq 3/2,\omega,\omega^*$)-hypomorphie.
Introduisons un petit lemme préalable :

**Petit lemme 1.** La ($\leq 3/2,\omega$)-hypomorphie entraîne la ($\omega+1$)-hypomorphie.

**Preuve.** Raisonnons par l'absurde en supposant l'existence dans la base d'un ensemble noté $N+\{a\}$ où $NN$, de R-plus grand élément a, de R-type $\omega+1$ et dont le R'-type serait différent de $\omega+1$. Par $\omega$-hypomorphie ce R'-type contiendrait un R-type $\omega$. Toujours en vertu de la $\omega$-hypomorphie, un ensemble de R'-type $\omega$ ne peut contenir de R-type $\omega$. Donc une partie de R'-type $\omega$ de $N+\{a\}$, ne peut contenir de R-type $\omega$, mais pas non plus de R-type $\omega$, puisque $N+\{a\}$ est de R-type $\omega+1$. Cette absurdité montre qu'aucune partie de $N+\{a\}$ ne peut être de R'-type $\omega$. Donc, par $\leq 3/2$-hypomorphie, $N\cup\{a\}$ ne peut être que de R'-type $\geq\omega+2$ et possède par conséquent une partie U de R'-type $\omega+2$. Un des deux R'-derniers éléments de U est l'élément a -sans quoi l'ensemble $U-\{a\}$ serait de R'-type $\omega+2$, et de R-type $\omega$ puisque inclus dans N. L'ensemble $U-\{a\}$ est donc de R'-type $\omega+1$ et de R-type $\omega$. Absurde.

**Preuve du lemme d'interdiction de $\omega+1$.** On suppose qu'existe une partie de R-type $\omega+1$. Considérons un chemin de longueur minimum reliant le plus grand élément a à un autre x de N, supposé être le premier du chemin (dans l'ordre d'acheminement de a vers N) à être dans N.

Ce chemin ne peut être de longueur 1 car si tel était le cas un $[a,x]$ pour $x\in N$ s'inverserait dans R'. Mais alors dans $N\cup\{a\}$ n'est pas de R'-type $\omega+1$. Or dans $\omega+1$, seul le dernier élément possède une infinité de minorants. $N\cup\{a\}$ ne pourrait donc pas être de type $\omega+1$ contrairement à ce qu'affirme le petit lemme 1. Le chemin est donc de longueur au moins 2.

Notons y l'élément du chemin qui précède juste x dans le chemin, avec par exemple $x<y$ mod R. Pour tout x' de N qui est $>x$ mod R, $[y,x']$ est orientée (par $\leq 3/2$-hypomorphie). Prenons un $x'$ ($>x$ mod R) suffisamment grand (mod R) pour que $[y,x']$ ne change pas. C'est possible car s'il y avait une infinité de changements, pour un $N'\subset N$, $\{y\}\cup N'$ serait de type $\omega+1$ mod R' et pas mod R. Pour éviter un cycle sur $\{x,x',y\}$ il faut que $y<x'$ mod R' (et R). De même pour $x'+1$ (suivant de x' dans N), $x'+2$ etc...; $\{y, x'+1, x'+2, \dots, a\}$ est alors de type $\omega+1$ mod R et R', et un chemin plus court pour une configuration analogue est obtenu en restreignant le chemin initial à la portion qui va de a à y.

**Proposition 1.** Si deux relations binaires R et R' sont ($\leq 3/2,\omega,\omega^*$)-hypomorphes, alors elles sont ($\omega^*+\omega$)-hypomorphes.
**Preuve.** Supposons d'abord la $\leq 3$-hypomorphie après quoi nous montrerons, qu'on peut se passer de cette hypothèse (laquelle n'est pas une conséquence de la ($\leq 3/2, \omega, \omega^*$)-hypomorphie). Supposons l'existence d'une partie $N^+ = \{1,2,3,\dots\}$ de type $\omega$ et d'une partie $N^- = \{-1,-2,-3,\dots\}$ de type $\omega^*$ telle que $N^+ \cup N^-$ ne soit pas de R'-type $\omega^*+\omega$. Par $\leq 3$-hypomorphie $N^+ \cup N^-$ est un R'-ordre total. Trois cas se présentent alors

a) $-1 < 1 \bmod R'$. Alors $N^+ \cup N^-$ doit nécessairement être de type $\omega^*+\omega$.

b) $1 < N^-$ mod $R'$. Alors $\{1\} \cup N^-$ est de R'-type $1+\omega$ et de R-type $\omega$, absurde.

c) $-1 > N^+$ mod $R'$. Idem.

d) Dans les autres cas on peut écrire $N^+ \cup N^- = \text{pnc} [N^-, 1\text{pnc} [+\text{pnc}] 1, -1\text{pnc} [+\text{pnc} [-1, N^+ \text{pnc}] \approx \omega^* + \text{fini} + \omega \approx \omega^* + \omega]$.

Où $\text{pnc} [N^-, 1\text{pnc} [\cdot, \cdot, \text{par exemple, désigne évidemment comme dans [17]} \text{ l'ensemble des } x \text{ qui sont } <1 \text{ et plus grand qu'un } n \text{ de } N^-]$.

Montrons maintenant que la seule $\leq 3/2$-hypomorphie entraîne la $\leq 3$-hypomorphie sur $N^+ \cup N^-$. Un 3-emble $\{x,y,z\}$ de $N^+ \cup N^-$ est inclus dans le R-intervalle final de $N^+ \cup N^-$ que ce 3-emble engendre, intervalle qui est de R-type $\omega$. Ce 3-emble est donc inclus dans une R'-chaîne de type $\omega$, et par suite est un R'-ordre total isomorphe à $R|\{x,y,z\}$.

On démontre facilement le :

**Petit lemme 2.** Les classes d'identité de deux relations $\leq 3/2$-hypomorphes sont des presque-intervalles. De même pour les classes de différence.

On appelle presque-consécutivité une relation qui est une consécutivité à ceci près que les arêtes neutres ne sont pas toutes nécessairement de même nature.

**Petit lemme 3.** Dans une classe de $\leq 3$-hypomorphie tout chemin de différence minimal liant les extrémités d'une arête neutre, est une consécutivité.

**Preuve.** Les pics étant interdits il s'agit d'une presque consécutivité, et on vérifie, avec les mêmes notations que dans l'énoncé précédent, que $[xn-1,x0]$ est de même nature que $[xn,x0]$.

On démontre de même :

**Petit lemme 4.** Dans une classe de $\leq 3$-hypomorphie tout chemin d'identité minimal liant les extrémités d'une arête neutre, est une presque-consécutivité.
**Lemme technique 0.** Dans un graphe non orienté connexe (au sens de la théorie des graphes non orientés), infini, localement fini, il existe une branche infinie.

**Preuve.** On part d'un x fixé. Soit $V_{x_0}$ l'ensemble des éléments liés à x0. A chaque élément u de $V_{x_0}$ faisons correspondre l'ensemble Gu des éléments z ($\neq u, \neq x_0$) du graphe, qu'on peut atteindre par un chemin $[x_0, u, ..., z]$ ne repassant jamais par le même sommet (et où chaque élément est lié au suivant). Un des Gu est infini, notons x1 cet u. Puis recommandons : pour chaque u lié à x1, considérons le nouvel ensemble Gu des sommets z ($\neq u, \neq x_0, \neq x1$) du graphe $G_{x_1}$ qu'on peut atteindre par un chemin $[x_0, x_1, u, ..., z]$ ne repassant pas deux fois par le même sommet. De nouveau un des Gu est infini, notons x2 ce u. L'opération peut continuer indéfiniment. On obtient une branche infinie $[x_0, x_1, x_2, ...]$.

**Lemme 1.** Une classe de ($\leq 3,\omega,\omega^*$)-hypomorphie infinie contient soit une chaîne infinie soit une conséutivité infinie qui s'inverse.

**Preuve.** Soit R et R' deux relations binaires ($\leq 3,\omega,\omega^*$)-hypomorphes et C une (R,R')-classe de différence. Considérons un (R,R')-chemin de différence recouvrant la base de C et évidemment contenu dans cette base. On sait que le graphe de (R,R')-différence est localement fini; le lemme technique ci-dessus nous apprend qu'il existe alors dans ce graphe une branche infinie $B=[x_0,x_1,x_2,x_3,...]$ (qu'on identifie à $[0,1,2,3,...]$) qui est donc un (R,R')-chemin. Montrons maintenant qu'un élément de B par exemple x n'est lié par une flèche qu'à un nombre fini d'autres éléments de B. Si une infinité de tels liens existait, la technique de Ramsey nous permettrait d'extraire une infinité de flèches orientée toutes depuis x ou toutes vers x0. Plaçons nous dans un de ces cas. Les autres extrémités des dites flèches formeraient, les pics étant interdits dans les classes de ($\leq 3,\omega,\omega^*$)-hypomorphie, un tournoi infini duquel on pourrait extraire une chaîne infinie. Est donc maintenant acquis que de toutes les flèches $[x_0,x]$ il y en a une où x est d'indice maximum dans la liste $x_0,x_1,x_2,x_3,...$; appelons $X_1$ ce $\llcorner \text{maximum}\rrcorner$ (qui peut d'ailleurs coïncider avec $x_0+1$). Pour éviter les pics il est nécessaire que $[x_0,X_1,X_1+1]$ soit une conséutivité puisque, par maximalité de x, ce triplet ne peut être un tournoi. On recommence la même opération avec $X_1$ au lieu de $x_0$ : on obtient un $X_2$ sur lequel on peut réutiliser l'argument qui a servi pour $X_1+1$; on peut donc affirmer que $\{x_0,X_1,X_2\}$ est une conséutivité. On recommence indéfiniment jusqu'à obtenir une relation $B^\infty=\{x_0,X_1,X_2,X_3,\dots\}$ qui ne diffère d'une conséutivité de type $\Omega$ (si on
a supposé par exemple $R|(x0,X1)=(+,−))$ que par le fait que les arêtes neutres ne sont peut-être pas toutes de même nature : nous allons maintenant montrer qu'en fait elles le sont.

Comme $[X1,X1+1]$ s'inverse il en va de même $[x0,X1]$ et finalement de toutes les flèches de la (presque) consécutivité $B∞$. En raisonnant sur $R|\{0,X1,Xn\}$ on voit que $[0,Xn]$ est de même nature (mod R et R') que $[X1,n]$. De même pour $[X1,Xn]$ et $[X2,Xn]$ et tous les $[Xi,Xn]$ (pour $i<n$). En raisonnant sur $R|\{0,Xn-1,Xn\}$ on voit de même que la $(\le 3)$-hypomorphie exige que $[Xn-1,Xn]$ soit de même nature que $[X0,Xn]$. La réitération de ce procédé permet d'affirmer que toutes les arêtes neutres de $B∞$ sont de même nature et que $R|B∞$ est de type par exemple $\Omega$.

**Lemme 2.** Une classe de $(\le 3, \omega, \omega^*, \Omega, \Omega^*)$-hypomorphie infinie contient une chaîne infinie.

**Preuve.** La $(\Omega, \Omega^*)$-hypomorphie entraîne la conservation de la consécutivité alors que le lemme 1 impose son inversion. De cette contradiction on tire que la classe contient une chaîne infinie.

**Petit lemme 5.** Dans une classe de différence entre deux relations binaires $(\le 3)$-hypomorphes, tout chemin de différence minimal reliant les extrémités d'une arête neutre fixée est une consécutivité changeante.

Dans une classe d'identité entre deux relations binaires $(\le 3)$-hypomorphes, le chemin d'identité minimal reliant les extrémités d'une arête neutre fixée est une presque-consécutivité non changeante.

**Preuve.** Raisonnons par l'absurde. Soit, dans une $(R, R')$-classe de différence, $[x,y]$ une paire neutre et $[x,x1,x2, ..., xn-2=y1,xn-1=y]$ un $(R, R')$-chemin de différence minimal reliant $x$ à $y$ qui ne serait pas une consécutivité et qui serait donc de longueur $\ge 3$. Si $[x1, ..., y]$ n'est pas une consécutivité alors, par minimalité, $[x1,y]$ est orientée, et par hypomorphie sur $\{x,x1,y\}$, dans un sens faisant de $[x,x1,y]$ une consécutivité changeante -contraire aux hypothèses de départ. De même $[x,x1, ..., y1]$ est une consécutivité changeante et donc tout le chemin $[x,x1,x2, ..., y1,y]$ est une presque-consécutivité. La $\le 3$-hypomorphie entre $R$ et $R'$ sur $\{x,x1,y\}$ montre que $[y,x1]$ est de même nature que $[y,x]$ et le même raisonnement sur $\{y,y1,x\}$ montre que $[x,y1]$ est de même nature que $[y,x]$ et du coup $[x,x1, ..., y1]$ est une vraie consécutivité.

La deuxième partie de l'énoncé est duale de la première sans qu'on puisse démontrer que le chemin est une vraie consécutivité.
**Lemme 3.** Une classe de (R,R')-différence infinie n'est formée que d'une seule classe d'identité dès que R et R' sont ($\leq 3,\omega,\omega^*,\Omega,\Omega^*$)-hypomorphes.

**Preuve.** Une classe de différence infinie contient une chaîne infinie C (lemme 1) de type par exemple $\omega$. Laquelle contient une partie infinie d'une classe d'identité infinie obtenue en prenant un $x_0$ puis un $x_1 > x_0$ mod R et R' puis un $x_2 > x_1$ mod R et R'.

S'il existe plusieurs (R,R')-classes d'identité, alors, ces classes d'identité étant des presque-intervalles l'une d'elles contient un presque-intervalle infini I de R-type $\omega$ de C, et sa réunion $I \cup \{x\}$ avec un singleton $\{x\}$ bien choisi de la classe de différence (le premier après la sortie d'un chemin de différence hors de la classe d'identité) donne un ensemble de R-type $\omega$ et de R'-type $\omega+1$ (ou le contraire).

**Lemme 4.** Soit R et R' deux relations binaires $\leq 3$-hypomorphes dont la base n'est formée que d'une seule classe de différence. Toute (R,R')-classe d'identité est alors un tournoi.

**Preuve.** Considérons, parmi toutes les arêtes neutres, supposées exister, et tous les chemins d'identité reliant les extrémités de ces arêtes neutres, un chemin de longueur minimum. Soit $[x,y]$ l'arête et $[x,x_1,x_2,\dots,y]$ le chemin avec par exemple $x < x_1$ mod R et $R'$. $[x_1,y]$ ne peut, par argument de minimalité, être neutre. Les pics étant interdits on doit avoir $x_1 < y$ mod R et mod R'. Le chemin d'identité est donc une consécutivité formée de deux arêtes. Considérons maintenant un chemin de différence de longueur minimum parmi tous ceux reliant les extrémités d'une consécutivité non changeante formée de deux arêtes. A son tour ce chemin va être formé d'une consécutivité changeante $[x,x',y]$. Si $[x',x_1]$ est neutre, l'ensemble $\{x,x',x_1\}$ formera un pic modulo R ou modulo R' ce qui est interdit ; et si $[x,x_1]$ est orientée un des ensembles $\{x',x_1,x\}$ ou $\{y,x',x_1\}$ formera un cycle modulo une des relations R ou R' et pas modulo l'autre.

Une relation binaire est dite fortement connexe si pour tous x et y de cette relation il existe un chemin monotone allant de x à y, formé de flèches orientées dans le sens du chemin. Il va de soi que, dans un tournoi, l'ensemble des sommets d'un pavage est fortement connexe.

La forte connexité d'un tournoi R est préservée par ($\leq 3/2$)-hypomorphie: prendre un R-chemin monotone minimal $[x,x_1,x_2,\dots]$, $[x,x_1,x_2]$ est un cycle globalement conservé par $\leq 3/2$-hypomorphie et donc $[x,x_1,x_2,\dots]$ ou $[x,x_2,\dots]$ est un R'-chemin monotone si R' est $\leq 3/2$-hypomorphe à R.
Un pavage P est dit maximal si l'ensemble des arêtes de ce pavage ne peut être prolongé par un pavage P' contenant en plus d'autres sommets que ceux déjà dans P.

**Lemme 5.** Si C est un pavage maximal d'un tournoi R, l'ensemble de ses sommets est un R-intervalle.

**Preuve.** Soit a un élément extérieur à C et $[x,y,z]$ un cycle du pavage. Supposons par exemple $x<y$, $y<z$, $z<x$ et $a<x$. Si on avait $y<a$ le pavage pourrait être prolongé par le cycle $[c,y,a]$ et contenir a. De proche en proche l'énoncé est démontré.

**Lemme 6.** (avec Gérard Lopez) Soit R est un tournoi fortement connexe, tout intervalle propre est proprement inclus dans l'ensemble des sommets d'un pavage.

**Preuve.** Soit C un intervalle propre. X l'ensemble des minorants de C, Y l'ensemble des majorants de C. R étant fortement connexe X et Y doivent être non vides. Il doit aussi exister un x de X et un y de Y tels que $y<x$. Les cycles $[c,x,y]$ engendrent donc, quand c parcourt C, un pavage dont l'ensemble des sommets $CU\{x,y\}$ contient proprement C.

**Corollaire 1.** Un tournoi sans diamant qui n'est pas une chaîne est payable.

**Preuve.** Un pavage maximal est un intervalle, qui s'il est propre doit être sans 3-cycle - absurde.

**Proposition 2.** Un tournoi T est fortement connexe si et seulement si tout intervalle propre de T est proprement inclus dans l'ensemble des sommets d'un pavage.

**Preuve.** La preuve de la condition nécessaire est fournie par le lemme 6. Démontrons la condition suffisante par contraposition. Supposons que T est non fortement connexe et soit C une composante fortement connexe de T. Comme tout pavage est fortement connexe et comme toute partie X de sommets incluant proprement C n'est pas fortement connexe alors X n'est pas l'ensemble des sommets d'un pavage. Ainsi C est un intervalle propre qui n'est inclus proprement dans aucun pavage.

En particulier un tournoi fortement connexe fini est payable.
L'exemple suivant est classique. R est construite ainsi : elle ne diffère de $(Z,<)$, que par les relations $n<\dots<n$ (quand n parcourt $N-\{0\}$). La relation R bien que fortement connexe n'est pas payable car infinie.

Associons à R une relation $R'$ obtenue à partir de R en inversant les cycles $\{0,-n,n\}$ où n est pair ainsi que les cycles dont l'inversion est nécessaire pour maintenir la ($\leq 3$)-hypomorphie. Sur $|Z|$, $R'(x,y)$ est donc défini ainsi : si x et y négatifs ou nuls et $x<y$ mod $Z$ alors $R'$ vaut (-) si x est pair et (+) si x est impair. Si x et y sont positifs ou nuls on pose $R'(x,y)=R'(-y,-x)$. Si $x<0<y$ mod $Z$ et si $\sup(|x|,|y|)$ est pair alors $R'$ vaut l'inverse de R aussi bien pour $(x,y)$ que pour $(y,x)$. Si $x<0<y$ mod $Z$ et si $\sup(|x|,|y|)$ est impair alors $R'$ vaut comme R aussi bien pour $(x,y)$ que pour $(y,x)$. Alors la base n'est formée que d'une seule classe de $(R,R')$-différence et une seule classe de $(R,R')$-identité sans être un dilaté de chaine car R et $R'$ ne sont pas $(\omega,\omega^*)$-hypomorphes (voir ce que dit le lemme 8).

Cet exemple montre que dans la thèse de Boussaïri ([8]) p.4 prop. 3.1.3 l'hypothèses (tacite) de finitude ne doit pas être omise sans quoi l'énoncé est inexact.

Dans un tournoi introduisons la relation $x\sim y$ signifiant (il s'agit d'une notation locale) qu'il existe une suite $C1,C2,\dots,Cp$ de 3-cycles, chacun adjacent à un précédent par une arête, telle que $x$ est une arête de $C1$ et $y$ une arête de $Cp$. Cette relation $\sim$ est transitive : si $x\sim y$ et $y\sim z$ la réunion des sommets des cycles allant de $x$ à $y$ et des cycles allant de $y$ à $z$ est un tournoi évidemment fortement connexe et fini donc payable; l'exemple précédent n'est formé que d'une seule $\sim$-classe. Néanmoins la réunion des arêtes de deux pavages n'est pas nécessairement un pavage ni même incluse (en tant qu'ensemble d'arêtes) dans un pavage, simplement la réunion des sommets, si elle est finie, est payable. On peut se demander ce qui se passe dans le cas où cette réunion est infinie.

**Lemme 7.** Un tournoi fortement connexe ne peut être une classe de $(R,R')$-différence et une classe de $(R,R')$-identité pour un $R'$ ($\leq 3,\omega,\omega^*$)-hypomorphe à R.

**Preuve.** Raisonnons par l'absurde et partons d'un 3-cycle du tournoi. Ce cycle est contenu dans un pavage maximal P, par exemple non changeant, supposé ne pas contenir tous les sommets. L'ensemble C de ses sommets constituent donc un intervalle propre non trivial qui ne peut être inclus dans une $(R,R')$-classe de différence que si C possède un majorant ou minorant changeant m qui, par construction du pavage (par des 3-cycles), est en
dehors de l'ensemble C des sommets couverts par le pavage. Soit c un élément de C, supposons par exemple que m est majorant (changeant) de tout C. Comme au lemme 6 on prouve donc l'existence d'un pavage, cette fois-ci changeant, dont l'ensemble des sommets contient $C \cup \{m\}$. Ce dernier pavage est contenu dans un pavage maximal P' avec lequel nous reprenons le même raisonnement qu'avec P : [a,m] est changeante et le pavage P' ne peut être dans une même classe d'identité que si existe hors de $C \cup \{m\}$ un m' qui est minorant ou majorant non changeant de l'ensemble C' des sommets couverts par P', [a,m'] sera alors non changeante. Mais à l'étape suivante apparaîtra un m tel que [a,m] sera de nouveau changeante. On termine en constatant que dans le graphe de différence a est de degré infini ce qui est contraire à la finitude locale imposée par la $(\leq 3, \omega, \omega^*)$-hypomorphie.

**Lemme 8.** Soit R et R' deux relations binaires ($\leq 3, \omega, \omega^*$)-hypomorphes ne formant qu'une classe d'identité et une classe de différence. R est dilaté d'une chaîne de cardinal $>3$.

**Preuve.** Les lemmes 1 à 7 montrent que R ne peut être fortement connexe. On voit facilement que chaque composante fortement connexe est un intervalle. Le quotient est donc une chaîne. On voit facilement qu'une chaîne de cardinal $\leq 3$ ne peut être une classe de $\leq 3$-différence et une classe de $\leq 3$-identité.

On conclut

**Théorème 1.** Toute classe de $(\leq 3, \omega, \omega^*, \Omega, \Omega^*)$-hypomorphie infinie est dilatée de chaîne infinie de type $\omega$, $\omega^*$ ou $\omega^*+\omega$ par des tournois finis.

**Preuve.** L'application du lemme 3 montre que cette classe d'hypomorphie est une classe de différence et une classe d'identité. Elle est donc d'après le lemme 8 une dilatée de chaîne. Si celle-ci était finie une des composantes serait infinie et contiendrait par exemple une chaîne de type $\omega$. Mais alors, si ce n'est pas la dernière composante (i.e. la plus grande), apparaîtrait $\omega+1$ dans la classe, ce qui est interdit. Le cas où la composante est la dernière se traite directement avec facilité.

La réciproque est immédiate grâce à la technique de la guirlande ([20] p482-483): on appelle guirlande la donnée de R et du graphe de différence S de deux relations R et R' qui sont $(\leq 3, \omega, \omega^*, \Omega, \Omega^*)$-hypomorphes de type $\omega$, $\omega^*$ ou $\omega^*+\omega$, dont la base n'est formée que d'une seule (R, R')-classe de différence. Une classe de $(\leq 3, \omega, \omega^*, \Omega, \Omega^*)$-hypomorphie peuvent effective-ment être de type $\omega$ ou $\omega^*$ ou $\omega^*+\omega$. L'exemple extrait de [20] (p482-483),
l'illustre: R est la chaîne des entiers naturels muni de l'ordre habituel, R'
est le même ordre avec les inversions $0>1, 0>3$ puis translation itérée de 2
soit $1<3<0<5<2<7<4<9<6<11<8<...$.

Tout dilaté de chaîne infinie de type $\omega$, $\omega^*$ ou $\omega^*+\omega$ par des tournois finis, est une classe de ($\leq 3,\omega,\omega^*,\Omega,\Omega^*$)-hypomorphie.

Grâce à [23] on conclut avec une hypothèse de réflexivité par exemple:
**Théorème 4.** Les classes de ($\leq 3,\omega,\omega^*,\Omega,\Omega^*$)-hypomorphie sont les relations infinies dilatées de chaîne infinie de type $\omega$, $\omega^*$ ou $\omega^*+\omega$ par des tournois finis, et les relations finies connexes sans pics ni interdits rauziens.

References

[1] Y. Boudabbous, La 5-reconstruction et lindécomposabilité des relations binaires, European J. Combin. 23, pp. 507-522, (2002).

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

[3] Youssef Boudabbous and Christian Delhommé, ($\leq k$)-reconstuctibles binary relations, European Journal of Combinatorics 37, pp. 43-67, (2014).

[4] 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).

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

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

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

[8] 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.
[9] 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).

[10] 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).

[11] 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 Catolica del Norte Antofagasta - Chile

[12] J. Dammak, Caractérisation des relations binaires finies d-demi-reconstructibles, Proyecciones, Volume 22, No 1, pp. 31-61, (2003).

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

[14] R. Fraïssé, Theory of relations, Studies in Logic vol 145, North-Holland (2000).

[15] 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).

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

[17] J.G. Hagendorf, Extensions respectueuses de chaînes, Z. Math. Logik Grundlag. Math., 25, pp. 423-444, (1979).

[18] J.G. Hagendorf, Extensions immédiates de chaînes, Z. Math. Logik Grundlag. Math., 28, pp. 15-44, (1982).

[19] J.G. Hagendorf, Reconstruction des ordres totaux, Z. Math. Logik Grundlag. Math., 34, pp. 193-200, (1988).

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

[21] J.G. Hagendorf et G. Lopez, Un théorème de demi-reconstruction des relations binaires de cardinal $>12$, Prépublications d'Orsay, pp. 1-300, (1994) ; (non publié).
[22] J.G. Hagendorf et G. Lopez. La demi-reconstructibilité des relations binaires dau moins 13 éléments. C. R. Acad. Sci. Paris, t. 317, Série I, pp. 7-12, (1993).

[23] J. Hagendorf, G. Lopez et C. Rauzy, Caractérisation des classes de ($\leq 3$)-hypomorphie à laide dinterdits. Proyecciones Journal of Mathematics Vol. 32, No 2, pp. 91-105, June (2013). Universidad Catolica del Norte Antofagasta - Chile.

[24] 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).

[25] Lopez Gérard, Deux résultats concernant la détermination d'une relation par les types disomorphie de ses restrictions, C. R. Acad. Sci. Paris Sér. A 274, p1525-1528, (1972).

[26] Lopez Gérard, Sur la détermination d'une relation par les types disomorphie de ses restrictions, C. R. Acad. Sci. Paris Sér. A 275, pp. 951-953, (1972).

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

[28] 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, (1992), 27-37. et II, Z. Math. Logik Grundlag. Math., 38, pp. 157-168, (1992).

[29] K. B. Reid and C. Thomassen, Strongly self-complementary and hereditarily isomorphic tournaments, Monatshefte für Mathematik 81, pp. 291-304 (1976).

Jean G. Hagendorf

14 allée de l'Oseraie,
94260 Fresnes
France

e-mail : jean.hagendorf@sfr.fr