LA (-5)-DEMI-RECONSTRUCTIBILITÉ DES
RELATIONS BINAIRES CONNEXES FINIES

JAMEL DAMMAK

Université Claude Bernard Lyon 1, Tunisie.

Abstract

Etant donnée une relation binaire $R$, de base $E$, on définit sa duale $R^*$ par $R^*(x,y) = R(y,x)$. La relation $R$ est dite auto-duale si elle est isomorphe à $R^*$. Une relation binaire $R'$ est hémimorphe à $R$, si elle est isomorphe à $R$ ou à $R^*$. Une relation binaire est d-demi-reconstructible, si elle est déterminée par la donnée de ses restrictions de cardinal $d$, à l'hémimorphie près. Dans ce papier, nous montrons que : Les relations binaires connexes finies de cardinal $n \ge 12$ sont $(n-5)$-demi-reconstructibles.

Given a binary relation $R$ of basis $E$, we define its dual $R^*$ by
$R^*(x, y) = R(y, x)$. A relation $R$ is self-dual if it is isomorphic to $R^*$. 
A binary relation $R'$ is hemimorphic to $R$, if it is isomorphic to $R$ or 
to $R^*$. A binary relation $R$ is d-half-reconstructible if it is determined 
by its restrictions of cardinality $d$, up to hemimorphism. In this paper 
we obtain : The finite connected binary relations of cardinality $n \ge 12$
are $(n-5)$-half-reconstructible.

**Mathematics Subject Classification** : 03C60; 04A05; 05C20; 05C38; 05C40.

**Key Words :** Relation de différence, Relation binaire, Graphe, Hémorphe, Hémimorphe, Reconstruction, Connexe.
# 1. Introduction

Soit $E$ un ensemble fini. Le cardinal de $E$ est noté $|E|$. Une relation binaire $R$ de base $E$ est une application du produit $E \times E$ dans $\{+, -\}$. Les éléments de $E$ sont appelés sommets de $R$. Les paires de sommets sont appelées arêtes de $R$. Une arête $\{a, b\}$ est dite neutre si $R(a, b) = R(b, a)$, elle est dite pleine (resp. vide) si $R(a, b) = R(b, a) = +$ (resp. $R(a, b) = R(b, a) = -$). Une arête de $R$ est dite orientée, si elle n'est pas neutre, dans ce cas on dit que $a$ domine $b$ si $R(a, b) = +$. On appelle duale de $R$, la relation $R^*$ définie sur $E$ par : pour tous éléments $x, y \in E$, $R^*(x, y) = R(y, x)$. La relation $R$ est dite auto-duale si elle est isomorphe à $R^*$. L'isomorphie entre deux relations $R$ et $R'$ est notée $R \sim R'$. Une relation binaire $T$ est un tournoi lorsque pour tout élément $x \in E$, $T(x, x) = -$ et pour tous éléments distincts $x, y \in E$, $T(x, y) \neq T(y, x)$. Un 3-cycle $(a, b, c)$ est un tournoi $T$ à 3 éléments défini par $T(a, b) = T(b, c) = T(c, a) = +$. Une $k$-chaîne est un ordre total irréflexif à $k$ éléments. La restriction de $R$ à une partie $X$ de $E$, notée $R/X$, est la relation de base $X$ définie par : pour tous éléments $x, y$ de $X$, $R/X(x, y) = R(x, y)$.

Une relation $R$ de base finie $E$ est dite *connexe*, si pour tous éléments distincts $x, y$ de $E$, il existe une suite $x_0 = x, x_1, ..., x_k = y$, telle que pour tout $i = 0, 1, ..., k-1$, on a $R(x_i, x_{i+1}) \neq R(x_{i+1}, x_i)$.

Soient $R$ et $R'$ deux relations binaires de bases respectives $E$ et $E'$, et $f$ une bijection de $E$ sur $E'$. L'application $f$ est dite un isomorphisme (resp. anti-isomorphisme) de $R$ sur $R'$, si pour tous $x, y$ éléments de $E$, $R'(f(x), f(y)) = R(x, y)$ (resp. $R'(f(x), f(y)) = R^*(x, y)$). Dans ce cas on dit que $R$ et $R'$ sont isomorphes et on note $R' \sim R$ (resp. $R$ et $R'$ sont anti-isomorphes et on note $R' \sim R^*$). Une relation binaire $R'$ est hémimorphe à $R$, si elle est isomorphe à $R$ ou à $R^*$. Une relation binaire $R$ est dite auto-duale si elle est isomorphe à $R^*$. Une relation binaire est dite non auto-duale minimale, si elle est non auto-duale et si toutes ses restrictions strictes sont auto-duales. Une relation binaire $H$ s'abrite dans $R$ si $H$ est isomorphe à une restriction de $R$. Une restriction $R/A$ s'inverse dans $R'$ si $R'/A = R^*/A$. Deux relations binaires $R$ et $R'$ de base commune $E$ de cardinal $n$ sont dites $k$-hémimorphes (resp. $k$-hypomorphes) lorsque pour toute partie $X$ de $E$ de cardinal $k$, $R'/X \sim R/X$ ou $R'/X \sim R^*/X$ (resp. $R'/X \sim R/X$); définition analogue lorsque $card(X) \leq k$, on remplace alors le préfixe ($k$) par ($\leq k$) dans les notations. La $(n-k)$-hémimorphie (resp. $(n-k)$-hypomorphie) est encore notée $(-k)$-hémimorphie (resp. $(-k)$-hypomorphie). Une relation $R$ est dite $k$-demi-reconstructible (resp.
$k$-reconstructible) si toute relation $k$-hémimorphe (resp. $k$-hypomorphe) à $R$, lui est hémimorphe (resp. isomorphe); définition analogue pour la ($\leq k$)-demi-reconstructibilité (resp. ($\leq k$)-reconstructibilité), et aussi de la ($-k$)-demi-reconstruction (resp. ($-k$)-reconstruction).

La problématique de la reconstruction remonte à ULAM (1954). Elle est l'ensemble des questions évoquant la possibilité ou l'impossibilité de déterminer une structure à un isomorphisme près, au moyen d'une collection de sous structures, données elles aussi à un isomorphisme près. Rappelons dans ce domaine le résultat de G.LOPEZ concernant un problème posé par R. FRAÏSSÉ dans les années soixante:

**Lemme 1.1.** [8] Les relations binaires finies sont ($\leq 6$)-reconstructibles.

Notre présent travail, quant à lui, porte sur la demi-reconstruction, problématique due à J. G. HAGENDORF (1992). Il définit la notion d'hémimorphie (voir plus haut) et pose deux problèmes. Le premier est l'analogue du problème de R. FRAÏSSÉ : Existe-t-il un entier $h$ tel que deux relations binaires $R$ et $R'$ de même base finie $E$ de cardinal $> h$ sont hémimorphes dès que leurs restrictions à chaque partie $F$ d'au plus $h$ éléments sont hémimorphes.

Le second l'analogue du problème d'ULAM-POUZET : Existe-t-il un entier $h$ minimum tel que deux relations de cardinal $n$, sont hémimorphes dès que leurs restrictions de cardinal $n-h$ sont hémimorphes pour $n$ assez grand.

La réponse au premier problème a été donnée par J. G. HAGENDORF et G. LOPEZ avec :

**Lemme 1.2.** [7] Les relations binaires finies sont ($\leq 12$)-demi-reconstructibles.

Dans le cas des relations binaires connexes ce seuil a été abaissé dans [3] :

**Lemme 1.3.** [3] Les relations binaires connexes finies sont ($\leq 7$)-demi-reconstructibles.

De chacun de ces résultats découle immédiatement, grâce à un théorème combinatoire de POUZET [11] les résultats suivants :

**Lemme 1.4.** *Les relations binaires finies sont ($n-12$)-demi-reconstructibles pour $n \geq 24$.*
**Lemme 1.5.** Les relations binaires connexes finies sont $(n-7)$-demi-reconstructibles pour $n \ge 14$.

En fait le théorème de POUZET [11] permet de relier la demi-reconstruction dite par le bas quand $n$ est assez grand (lemmes 1.2 et 1.3) avec la demi-reconstruction par le haut (lemmes 1.4 et 1.5). Dans ce papier on obtient une amélioration du lemme 1.5 avec les théorèmes suivants :

**Théorème 3.1** *Les relations binaires connexes finies de cardinal $n \ge 13$ sont $(n-6)$-demi-reconstructibles.*

**Théorème 4.1** *Les relations binaires connexes finies de cardinal $n \ge 12$ sont $(n-5)$-demi-reconstructibles.*

On obtient en fait un résultat plus fort, à savoir :

**Théorème 5.1** *Pour tout entier $d \ge 5$, les relations binaires connexes finies de cardinal $n \ge 7+d$ sont $(n-d)$-demi-reconstructibles.*

On montre de plus, à l'aide d'un contre-exemple, que le nombre $7+d$ du théorème 5.1 est optimal.

**Esquisse de la preuve du théorème 3.1**

La démarache est sensiblement la même pour les autres théorèmes de demi-reconstruction. Soient $R$ une relation binaire connexe finie de base $E$ de cardinal au moins égal à 13, et $R'$ une relation binaire $(n-6)$-hémimorphe à $R$. D'après [11] les relations $R$ et $R'$ sont $(\le 6)$-hémimorphes. D'après [3] si l'équivalence $D_{R,R'}$ possède au moins deux classes, alors toute classe $C$ est un intervalle de $R$ et $R'$ sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives de plus $R'/C$ et $R/C$ sont $(\le 5)$-hypomorphes, et par suite le théorème de G. Lopez et C. Rauzy (voir [9]) nous donne la forme de $R/C$ et de $R'/C$, d'après la forme si $R/C$ n'est ni un tournoi sans diamant ni un élément de $E(S_n)$, alors $R'/C \sim R/C$. D'autre part d'après [4] si $R/C$ est un élément de $E(S_n)$, alors $R'/C \sim R/C$. Il s'ensuit que si $R/C$ n'est pas un tournoi sans diamant, alors $R'/C \sim R/C$. Dans la suite on suppose que $R/C$ est un tournoi sans diamant fortement connexe. Dans le cas où $|E-C| \ge 7$, nous montrons que $R'/C \sim R/C$ en utilisant une lemme combinatoire faite dans [1]. Dans le cas où $|E-C| \le 5$, en nous basant sur les théorèmes faite dans [10] nous montrons que $R'/C \sim R/C$. Il s'ensuit que $R' \sim R$. De même $R' \sim R^*$ si l'équivalence $D_{R^*,R'}$ possède au moins deux classes. Si chacune des équivalences $D_{R,R'}$ et $D_{R^*,R'}$ possède une seule classe, nous montrons que $R'$ et $R$ sont des chaînes, et par suite $R' \sim R \sim R^*$.
## 2. Définitions. Notations. Rappels.

**Somme lexicographique.** Etant donnée une relation $S$ de base $I = \{1, ..., k\}$, associons à chaque $i \in I$, une relation $R_i$ de base $I_i$ de telle sorte que les bases $I_i$ soient deux à deux disjointes. La $S$-somme des $R_i$, notée $S(R_1, ..., R_k)$, est la relation définie sur la réunion des $I_i$ de la façon suivante : $S(R_1, ..., R_k)(x, y) = R_i(x, y)$ si $x, y \in I_i$ et $S(R_1, ..., R_k)(x, y) = S(i, j)$ si $x \in I_i$ et $y \in I_j$ et $i \neq j$. Nous dirons aussi que la $S$-somme des $R_i$, est obtenue à partir de la relation $S$ en dilatant chaque $i \in I$ par la relation $R_i$.

**Relations particulières.** Citons les relations irréflexives particulières suivantes :

- Une *presque-chaîne* de longueur $k$ est obtenue à partir d'une $k$-chaîne en rendant neutre l'arête liant son premier et son dernier élément. Une presque-chaîne de longueur 3 est dite aussi une 3-consécutivité.

- Un *pic* est une relation à 3 éléments $a, b$ et $c$ telle que l'arête $\{a, b\}$ est neutre et les arêtes $\{a, c\}, \{b, c\}$ sont orientées avec $R(a, c) = R(b, c)$. Le point $c$ est dit sommet du pic.

- Un *drapeau* est une relation à 3 éléments $a, b$ et $c$ telle que l'arête $\{a, b\}$ est orientée, l'arête $\{b, c\}$ est pleine et l'arête $\{a, c\}$ est vide.

- Un *diamant* positif (resp. négatif) est un tournoi à 4 sommets constitué d'un 3-cycle $(a, b, c)$ et d'un point $d$ dominé par (resp. dominant) $(a, b, c)$. Le point $d$ est dit sommet du diamant.

- Etant donné un entier $h$, $T_h$ est le tournoi à $2h+1$ sommets : $0, 1, ..., 2h$ tel que pour tout sommet $i$, $T_h(i, i + k) = +$ pour $k \in \{1, ..., h\}$, (l'entier $i + k$ étant considéré modulo $2h + 1$). Une relation $R$ est un élément de $D(T_h)$, si $R$ est un tournoi obtenu en dilatant chaque sommet $k$ de $T_h$ par une chaîne $p_k$ de cardinal fini. Rappelons que $D(T_h)$ est la classe des tournois finis sans diamant ([6], [9]).

- Soient un entier naturel $h \ge 3$ et l'ensemble $F = \{1, ..., h\}$.

* On appelle consécutivité $1 < 2 < ... < h$, l'une des quatre relations définies sur $F$ comme suit :

$$ [R_1(x, y) = + ssi (y = x+1)], [R_2(x, y) = + ssi (y = x+1 \text{ ou } y = x)], [R_3(x, y) = + ssi (y = x+1 \text{ ou } |y - x| > 1)], [R_4(x, y) = + ssi (y = x+1 \text{ ou } |y - x| \neq 1)]. $$

* On appelle cycle $1 < 2 < ... < h < 1$, l'une des quatre relations définies sur $F$ comme suit : pour toute consécutivité $R_i$, $(1 \le i \le 4)$, le cycle $R'_i$ coïncide avec $R_i$, sauf peut être sur les couples $(1, h)$ et $(h, 1)$ où
on a $R'_i(h, 1) = +$ et $R'_i(1, h) = -$.

- Etant donné un entier $n \ge 1$, on désigne par $S_n$, l'une des relations définies sur les $2n$ éléments $t_1, ..., t_{2n}$, par : $S_n(t_i, t_{i+n}) = S_n(t_{i+n}, t_i)$ pour $i = 1, ..., n$, $S_n(t_i, t_{i+k}) = -S_n(t_{i+k}, t_i) = +$ pour $k = 1, ..., n-1$ et pour $i = 1, ..., 2n$ (les entiers ici sont considérés modulo $2n$). On notera $\delta_n$ un élément de la famille $E(S_n)$, des extensions de $S_n$ obtenues en augmentant la base de $S_n$ d'ensembles (éventuellement vides) deux à deux disjoints $s_1, ..., s_{2n}$, appelés secteurs de la relation, tels que :

i) Pour tout $i$, $\delta_n/s_i \cup \{t_i, t_{i+1}\}$ est une chaîne de premier élément $t_i$ et de dernier élément $t_{i+1}$.

ii) Pour tout $i$, on a $\delta_n/s_i \cup s_{i+n}$ est un tournoi sans diamant.

iii) Pour tout $i$, pour tout $x$ de $s_i$, pour tout $y$ de $s_{i+j}$, ($j = 1, ..., n-1$), on a $\delta_n(x, y) = -$, $\delta_n(y, x) = +$, $\delta_n(t_i, y) = -\delta_n(y, t_i) = +$, et pour tout $y$ de $s_{i+j}$, ($j = n, ..., 2n-1$), on a $\delta_n(t_i, y) \neq \delta_n(y, t_i) = -$.

**Intervalle, Décomposabilité.** La notion suivante d'intervalle d'une relation binaire a été introduite par R. Fraïssé en [5]. Etant donnée une relation binaire $R$ de base $E$, une partie $I$ de $E$ est un $R$-intervalle, lorsque pour tous éléments $a, b \in I$, tels que $R(a, a) = R(b, b)$, et pour tout élément $x \in E - I$, on a $R(a, x) = R(b, x)$ et $R(x, a) = R(x, b)$. Clairement, l'ensemble vide, les singletons et l'ensemble $E$ sont des intervalles de $R$, appelés intervalles triviaux. Une relation ayant au moins trois sommets sera dite *indécomposable* lorsque tous ses intervalles sont triviaux, elle est dit *décomposable* dans le cas contraire. Si $I$ et $J$ sont deux $R$-intervalles, la valeur $R(a, b)$ est une constante quand $a$ (resp. $b$) décrit l'ensemble $I$ (resp. $J$) et on note $R(I, J)$ cette constante.

Rappelons les résultats suivants :

**Lemme 2.1.** [11]. Soient $R$ et $R'$ deux relations binaires de même base $E$ de cardinal fini $n$. Si $R$ et $R'$ sont $q$-hémimorphes (resp. $q$-hypomorphes) où $1 \le q \le n-1$, alors pour tout entier $p \le \min(q, n-q)$, $R$ et $R'$ sont $p$-hémimorphes (resp. $p$-hypomorphes).

**Lemme 2.2.** [1]. Soient $n, d$ et $h$ des entiers naturels avec $1 \le d \le n-1$ et $1 \le h \le n-d$, $H$ une relation binaire à $h$ sommets, et $R$ et $R'$ deux relations binaires $(n-d)$-hémimorphes et de base commune $E$ à $n$ éléments. Alors, pour toute partie $A$ de $E$ à au plus $d$ éléments, le nombre de parties $F$ de $E$ contenant $A$ telle que $R/F$ est hémimorphe à $H$, est égal au nombre de parties $F$ de $E$ contenant $A$ telle que $R'/F$ est hémimorphe à $H$.
**Notation.** Dans la suite, on utilisera les notations suivantes (faites sous les hypothèses du lemme 2.2) $n(R, H, A) = \text{card}\{F \subset E : A \subset \text{FetR}/F \sim \text{HouR}/F \sim H^*\}$.

$$n(R', H, A) = \text{card}\{F \subset E : A \subset \text{FetR}'/F \sim \text{HouR}'/F \sim H^*\}.$$

Sous ces notations, le lemme 2.2 dit que : $n(R, H, A) = n(R', H, A)$.

**Relation de différence.** La notion de relation de différence a été introduite par G. Lopez dans [8]. Soient deux relations binaires $R$ et $R'$ de même base $E$, qui sont ($\leq 2$)-hémimorphes. On définit la relation $D_{R,R'}$ de base $E$ par : pour tout élément $x$ de $E$, $D_{R,R'}(x,x) = +$ et pour tous éléments distincts $x, y$ de $E$, $D_{R,R'}(x,y) = +$ lorsqu'il existe une suite $x = x_0, x_1, ..., x_k = y$ d'éléments de $E$ telle que $R(x_i, x_{i+1}) \neq R'(x_i, x_{i+1})$ pour tout $i$ élément de $\{0, 1, ..., k-1\}$. La relation $D_{R,R'}$ est une relation d'équivalence appelée relation de différence dont les classes sont appelées classes de différence.

Rappelons les résultats suivants :

**Lemme 2.3.** [9] Soient $R$ et $R'$ deux relations binaires ($\leq 3$)-hypomorphes sur une même base finie $E$, alors :

i) Toute classe de l'équivalence $D_{R,R'}$ est un intervalle commun à $R$ et $R'$.

ii) Les restrictions de $R$ et $R'$ à une classe de l'équivalence $D_{R,R'}$ sont toutes deux, réflexives ou irréflexives.

**Lemme 2.4.** [9] Soient $R$ et $R'$ deux relations binaires ($\leq 4$)-hypomorphes sur une base finie $E$, et $C$ une classe de l'équivalence $D_{R,R'}$. Alors :

i) Si $R/C$ est un tournoi, alors il existe un entier $h$ tel que $R/C$ est un $D(T_h)$.

ii) Si $R/C$ n'abrite pas de 3-cycle, alors $R/C$ est soit une chaîne, soit une presque-chaîne, soit une consécutivité, soit un cycle.

iii) Si $R/C$ abrite un 3-cycle, et si $R/C$ n'est pas un tournoi, alors il existe un entier $n$ tel que $R/C$ est un élément de $E(S_n)$.

**Lemme 2.5.** [4] Soient $R$ et $R'$ deux relations binaires ($\leq 5$)-hémimorphes sur une base finie $E$ et $C$ une classe de l'équivalence $D_{R,R'}$.

Si $R/C$ et $R'/C$ sont ($\leq 5$)-hypomorphes et si $R/C$ est un élément de $E(S_n)$, alors $R'/C \sim R/C \sim R^*/C$.

**Relation connexe.** Une relation $R$ de base finie $E$ est dite connexe, si pour tous éléments distincts $x, y$ de $E$, il existe un chemin orienté reliant $x$ à $y$, (c'est à dire une suite $x_0 = x, x_1, ..., x_k = y$, telle que pour tout
$i = 0, 1, ..., k - 1$, on a $R(x_i, x_{i+1}) \neq R(x_{i+1}, x_i)$. La composante connexe d'une partie $A$ de $E$, telle que $R/A$ est connexe, est la plus grande partie $D$ de $E$ telle que $D$ contient $A$ et la restriction $R/D$ soit connexe.

**Relation fortement connexe.** Une relation $R$ de base finie $E$ est dite fortement connexe, si pour tous éléments distincts $x, y$ de $E$, il existe un chemin monotone orienté reliant $x$ à $y$, c'est à dire une suite $x_0 = x, x_1, ..., x_n = y$, telle que pour tout $i = 0, 1, ..., n - 1$, on a $R(x_i, x_{i+1}) \neq R(x_{i+1}, x_i)$ et $R(x_i, x_{i+1}) = +$. La composante fortement connexe de $R$ contenant $x$ est la plus grande partie $D(x)$ de $E$ telle que $D(x)$ contienne $x$ et la restriction $R/D(x)$ soit fortement connexe.

**Relations binaires non auto-duales minimales.** Une relation binaire est dite non auto-duale minimale si elle est non auto-duale et toutes ses restrictions propres sont auto-duales.

Rappelons les résultats suivants :

**Lemme 2.6.** [3] Soient $R$ et $R'$ deux relations binaires ($\leq 4$)-hémimorphes sur une base finie $E$ et $C$ une classe de l'équivalence $D_{R,R'}$.

Si $C$ est différente de sa composante connexe, alors $C$ est un intervalle de $R$ et $R'$, sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

**Lemme 2.7.** [3] Soient $d$ un entier $\geq 5$, $R$ et $R'$ deux relations binaires ($\leq d$)-hémimorphes sur une base finie $E$ et $C$ une classe de l'équivalence $D_{R,R'}$.

Si $C$ est différente de sa composante connexe, alors $R/C$ et $R'/C$ sont ($\leq d - 1$)-hypomorphes.

**3. La (-6)-demi-reconstructibilité des relations binaires connexes finies**

Dans ce paragraphe nous obtenons :

**Théorème 3.1.** *Les relations binaires connexes finies de cardinal $n \geq 13$ sont $(n-6)$-demi-reconstructibles.*

La preuve du théorème 3.1 se base sur les propositions suivantes :

**Proposition 3.2.** *Soient $R$ et $R'$ deux relations binaires de base commune $E$ de cardinal $n$. Pour tout entier $h \geq 1$, si $R$ et $R'$ sont $(4, n - h)$-hypomorphes et si $|E| \geq 6 + h$, alors $R$ et $R'$ sont isomorphes.*
La preuve de la proposition 3.2 utilise les lemmes suivants :

**Lemme 3.3.** [10] Les relations binaires finies de cardinal $n \ge 7$ sont, (4, $n-1$)-reconstructibles.

**Lemme 3.4.** *Les relations binaires finies de cardinal $n \ge 8$ sont, (4, $n-2$)-reconstructibles.*

**Preuve.** Soient $R$ et $R'$ deux relations binaires $(4, -2)$-hypomorphes sur une base finie $E$ de cardinal $n$ au moins égal à 8, et $x$ un point quelconque de $E$. D'après l'hypothèse, les relations $R'/(E-\{x\})$ et $R/(E-\{x\})$ sont $(4, -1)$-hypomorphes et $|E-\{x\}| \ge 7$ (car $|E| \ge 8$), alors le lemme 3.3 prouve que $R'/(E-\{x\}) \sim R/(E-\{x\})$. Il s'ensuit que $R$ et $R'$ sont $(-1)$-hypomorphes. Comme $R$ et $R'$ sont 4-hypomorphes, alors $R$ et $R'$ sont $(4, -1)$-hypomorphes et par suite $R' \sim R$ d'après le lemme 3.3. $\square$

**Lemme 3.5.** *Les relations binaires finies de cardinal $n \ge 9$ sont, (4, $n-3$)-reconstructibles.*

**Preuve.** Soient $R$ et $R'$ deux relations binaires $(4, -3)$-hypomorphes sur une base finie $E$ de cardinal $n$ au moins égal à 9, et $x$ un point quelconque de $E$. D'après l'hypothèse, les relations $R'/(E-\{x\})$ et $R/(E-\{x\})$ sont $(4, -2)$-hypomorphes et $|E-\{x\}| \ge 8$ (car $|E| \ge 9$), alors d'après le lemme 3.4 $R'/(E-\{x\}) \sim R/(E-\{x\})$. Il s'ensuit que $R$ et $R'$ sont $(4, -1)$-hypomorphes et par suite le lemme 3.3 prouve que $R' \sim R$. $\square$

**Lemme 3.6.** [10] Les relations binaires finies de cardinal $n$ sont, $(n-h)$-reconstructibles dès que $h \ge 4$ et $n-h \ge 6$.

**Preuve de la proposition 3.2.** Soient $R$ et $R'$ deux relations binaires $(4, n-h)$-hypomorphes sur une base finie $E$ de cardinal $n$ au moins égal à $6+h$. Alors $R' \sim R$ provient du lemme 3.3 si $h=1$, du lemme 3.4 si $h=2$, du lemme 3.5 si $h=3$, et du lemme 3.6 si $h \ge 4$.

**Proposition 3.7.** *Soient $R$ et $R'$ deux relations binaires $(-6)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 13, et $C$ une classe de l'équivalence $D_{R,R'}$. Si $C$ est différente de sa composante connexe, alors:*

i) $C$ est un intervalle de $R$ et $R'$ sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

ii) $R'/C \sim R/C$.
Notons que comme conséquence de la proposition 3.7 on a :

**Corollaire 3.8.** Soient $R$ et $R'$ deux relations binaires $(-6)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 13, et $I$ une classe de l'équivalence $D_{R^*,R'}$. Si $I$ est différente de sa composante connexe, alors :

i) $I$ est un intervalle de $R^*$ et $R'$ sur lequel les restrictions de $R^*$ et $R'$ sont réflexives ou irréflexives.

ii) $R'/C \sim R^*/C$.

Soient $R$ et $R'$ deux relations binaires $(-6)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 13, et $C$ une classe de l'équivalence $D_{R,R'}$ différente de sa composante connexe. D'après le lemme 2.1 les relations $R$ et $R'$ sont ($\leq 6$)-hémimorphes. Comme $C$ est différente de sa composante connexe, alors le lemme 2.6 prouve que $C$ est un intervalle de $R$ et $R'$ sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

La preuve de la proposition 3.7 utilise les lemmes suivants :

**Lemme 3.9.** $R'/C$ et $R/C$ sont ($\leq 5$)-hypomorphes.

**Preuve.** D'après le lemme 2.1 les relations $R$ et $R'$ sont ($\leq 6$)-hémimorphes. Comme $C$ est différent de sa composante connexe, alors le lemme 2.7 prouve que $R'/C$ et $R/C$ sont ($\leq 5$)-hypomorphes. $\square$

**Lemme 3.10.** Si $R/C$ n'est pas un tournoi sans diamant, alors $R'/C \sim R/C$.

**Preuve.** D'après le lemme 3.9 $R'/C$ et $R/C$ sont ($\leq 5$)-hypomorphes, et par suite le lemme 2.4 de G. Lopez et C. Rauzy nous donne la forme de $R/C$ et de $R'/C$, d'après la forme si $R/C$ n'est ni un tournoi sans diamant ni un élément de $E(S_n)$, alors $R'/C \sim R/C$. Dans le cas où $R/C$ est un élément de $E(S_n)$, le lemme 2.5 prouve que $R'/C \sim R/C$. Il s'ensuit que si $R/C$ n'est pas un tournoi sans diamant, alors $R'/C \sim R/C$. $\square$

**Lemme 3.11.** Si $|E-C| \geq 7$, alors $R'/C \sim R/C$.

**Preuve.** Comme $C$ est différente de sa composante connexe, alors il existe un élément $x$ de $E-C$, tel que $R(x, C) \neq R(C, x)$. D'après le lemme 3.10, on peut supposer que $R/C$ est un tournoi sans diamant et par suite $R/C$ est soit une chaîne soit fortement connexe.

Cas 1 : Si $R/C$ est une chaîne. D'après le lemme 3.9 les restrictions $R'/C$ et $R/C$ sont 3-hypomorphes, et par suite $R'/C$ est une chaîne. Donc $R'/C \sim R/C$.
Cas 2 : Si $R/C$ est un tournoi sans diamant fortement connexe, posons $H = R/(C \cup \{x\})$. Comme $C$ est un intervalle, alors pour tout $y \in C$, l'arête $\{x, y\}$ est orientée et par suite $H$ est un tournoi. Soient $a, b, c \in C$ tels que $R/\{a, b, c\}$ est un 3-cycle. Considérons alors les parties $F$ de $E$ contenant $\{x, a, b, c\}$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Montrons qu'il n'y en a pas d'autre que $C \cup \{x\}$. Par l'absurde, supposons qu'il existe une telle partie $F$ différente de $C \cup \{x\}$. Puisque $H$ est un tournoi, alors $R/F$ est aussi un tournoi. Comme $F \neq C \cup \{x\}$, alors il existe $y \in F$ et $y \notin C \cup \{x\}$, d'autre part $C$ est un intervalle, donc $R/\{a, b, c, y\}$ est un diamant de sommet $y$ et $R/\{a, b, c, x\}$ est un diamant de sommet $x$. Puisque $C$ est un intervalle et $R/C$ est un tournoi sans diamant, alors n'importe quel diamant de $R/(C \cup \{x\})$ a pour sommet $x$, mais dans $R/F$ il y'a des diamants de sommet $x$ et d'autres de sommet $y$. Il s'ensuit que $R/(C \cup \{x\})$ et $R/F$ ne sont pas hémimorphes. Donc $F = C \cup \{x\}$. Le nombre de parties $F$ de $E$ contenant $\{x, a, b, c\}$ telles que $R/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R, H, \{x, a, b, c\}) = 1$). D'après le lemme 2.2, le nombre de parties $F$ de $E$ contenant $\{x, a, b, c\}$ telles que $R'/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R', H, \{x, a, b, c\}) = 1$). Il s'ensuit que $R'/(C \cup \{x\}) \sim H$ ou $R'/(C \cup \{x\}) \sim H^*$. Comme $C$ est un intervalle et $R(x, C) = R'(x, C)$ et que $H = R/(C \cup \{x\})$ admet deux composantes fortement connexes $x$ et $C$, alors $R'/(C \cup \{x\}) \sim R/(C \cup \{x\})$ et par suite $R'/C \sim R/C$.

**Lemme 3.12.** $R'/C \sim R/C$.

**Preuve.** La classe $C$ étant différente de sa composante connexe, alors il existe un élément $x$ de $E - C$, tel que $R(x, C) \neq R(C, x)$. D'après le lemme 3.10, on peut supposer que $R/C$ est un tournoi sans diamant. Posons $X = E - (C \cup \{x\})$, on a les cas suivants :

$c_1$ Si $|X| \geq 6$, alors $|E - C| \geq 7$, et par suite le lemme 3.11 prouve que $R'/C \sim R/C$.

$c_2$ Si $|X| = 5$. Soit $a_1$ un point quelconque de $C$. Comme $R/C$ est un tournoi sans diamant, alors $R/(C - \{a_1\})$ soit fortement connexe, soit une chaîne. Si $R/(C - \{a_1\})$ est une chaîne, alors $R'/(C - \{a_1\}) \sim R/(C - \{a_1\})$. Dans la suite $R/(C - \{a_1\})$ est un tournoi sans diamant fortement connexe. Soit $f$ un hémimorphisme de $R/(E - X \cup \{a_1\})$ sur $R'/(E - X \cup \{a_1\})$. Comme $C$ est un intervalle et $R/(E - X \cup \{a_1\})$ admet deux composantes fortement connexes $x$ et $C - \{a_1\}$ et que $R(x, C) = R'(x, C)$, alors $f$ est une isomorphisme avec $f(x) = x$ et $f(C - \{a_1\}) = C - \{a_1\}$. Il s'ensuit
que $R'/(C - \{a_1\}) \sim R/(C - \{a_1\})$. Donc $R/C$ et $R'/C$ sont $(4, -1)$-hypomorphes et $|C| \ge 7$, et par suite d'après le lemme 3.3 $R'/C \sim R/C$.

$c_3$ Si $|X| = 4$. Soient $a_1$ et $a_2$ deux points de $C$, de la même façon qu'en $c_2$ nous montrons que $R'/(C - \{a_1, a_2\}) \sim R/(C - \{a_1, a_2\})$. Donc $R/C$ et $R'/C$ sont $(4, -2)$-hypomorphes et $|C| \ge 8$, et par suite $R'/C \sim R/C$ (lemme 3.4).

$c_4$ Si $|X| = 3$. Soient $a_1, a_2$ et $a_3$ trois points de $C$, de la même façon qu'en $c_2$ nous montrons que $R'/(C - \{a_1, a_2, a_3\}) \sim R/(C - \{a_1, a_2, a_3\})$. Donc $R/C$ et $R'/C$ sont $(4, -3)$-hypomorphes et $|C| \ge 9$, et par suite d'après le lemme 3.5 $R'/C \sim R/C$.

$c_5$ Si $|X| = 2$. Soient $a_1, a_2, a_3$ et $a_4$ quatre points de $C$ de la même façon qu'en $c_2$ nous montrons que $R'/(C - \{a_1, a_2, a_3, a_4\}) \sim R/(C - \{a_1, a_2, a_3, a_4\})$. Donc $R/C$ et $R'/C$ sont $(-4)$-hypomorphes et $|C| \ge 10$, et par suite d'après le lemme 3.6 $R'/C \sim R/C$.

$c_6$ Si $|X| = 1$. Soient $a_1, a_2, a_3, a_4$ et $a_5$ cinq points de $C$ de la même façon qu'en $c_2$ nous montrons que $R'/(C - \{a_1, a_2, a_3, a_4, a_5\}) \sim R/(C - \{a_1, a_2, a_3, a_4, a_5\})$. Donc $R/C$ et $R'/C$ sont $(-5)$-hypomorphes et $|C| \ge 11$, et par suite d'après le lemme 3.6 $R'/C \sim R/C$.

$c_7$ Si $|X| = 0$. Soient $a_1, a_2, a_3, a_4, a_5$ et $a_6$ six points de $C$, de la même façon qu'en $c_2$ nous montrons que $R'/(C - \{a_1, a_2, a_3, a_4, a_5, a_6\}) \sim R/(C - \{a_1, a_2, a_3, a_4, a_5, a_6\})$. Donc $R/C$ et $R'/C$ sont $(-6)$-hypomorphes et $|C| \ge 12$, et par suite d'après le lemme 3.6 $R'/C \sim R/C$. $\square$

**Preuve de la proposition 3.7.** Comme $C$ est différent de sa composante connexe, alors le lemme 2.6 prouve que $C$ est un intervalle commun à $R$ et $R'$ sur lequel $R$ et $R'$ sont réflexives ou irréflexives. Le lemme 3.12 prouve que $R'/C \sim R/C$.

**Proposition 3.13.** Soient $R$ et $R'$ deux relations binaires ($\le 5$)-hémimorphes sur une base finie $E$. Si chacune des équivalences $D_{R,R'}$ et $D_{R^*,R'}$ possède une seule classe, alors $R$ et $R'$ sont des chaînes.

La preuve de la proposition 3.13 utilise les lemmes suivants :

**Lemme 3.14.** [3] Soient $R$ et $R'$ deux relations binaires ($\le 5$)-hémimorphes sur une base finie $E$, et $C$ une classe de l'équivalence $D_{R,R'}$, admettant une restriction non auto-duale, $k$ la plus petite cardinalité des restrictions non auto-duales de $R/C$ et $I_0$ la base d'une de ces restrictions. Alors la restriction $R'/I_0$ est isomorphe à $R^*/I_0$.
**Lemme 3.15.** Soient $R$ et $R'$ deux relations binaires ($\leq 5$)-hémimorphes sur une base finie $E$. Si chacune des équivalences $D_{R,R'}$ et $D_{R^*,R'}$ possède une seule classe, alors $R'$, $R$ et $R^*$ sont donc deux à deux ($\leq 5$)-hypomorphes.

**Preuve.** Il suffit de montrer que $R$ n'admet aucune restriction non auto-duale. Par l'absurde supposons que $R$ admet une restriction non auto-duale, soit $K$ une restriction de cardinal minimal parmi les restrictions non auto-duales de $R$ et soit $X$ sa base. Le lemme 3.14 entraîne que $R'/X \sim R/X$ et $R'/X \sim R^*/X$, et par suite $R/X \sim R^*/X$ ce qui est absurde. Il s'ensuit que la relation $R$ n'abrite aucune restriction non auto-duale. Les relations $R'$, $R$ et $R^*$ sont donc deux à deux ($\leq 5$)-hypomorphes. $\square$

**Lemme 3.16.** [9] Soient $R$ et $R'$ deux relations binaires ($\leq 3$)-hypomorphes sur une même base finie $E$, et $C$ une classe de l'équivalence $D_{R,R'}$. Si $R/C$ n'est pas un tournoi, alors $R/C$ admet une 3-consécutivité.

**Lemme 3.17.** [9] Soient $R$ et $R'$ deux relations binaires ($\leq 3$)-hypomorphes sur une même base finie $E$, et $C$ une classe de l'équivalence $D_{R,R'}$. Les 3-consécutivités de $R/C$ s'inversent dans $R'/C$.

**Lemme 3.18.** Soient $R$ et $R'$ deux relations binaires ($\leq 5$)-hémimorphes sur une base finie $E$. Si chacune des équivalences $D_{R,R'}$ et $D_{R^*,R'}$ possède une seule classe, alors $R$ est un tournoi.

**Preuve.** Par l'absurde, si $R$ n'est pas un tournoi alors, d'après le lemme 3.16, $R$ admet une 3-consécutivité de base $\{a_1, a_2, a_3\}$. D'après le lemme 3.17, la 3-consécutivité $R'/\{a_1, a_2, a_3\}$ s'inverse dans $R$ et dans $R^*$, ce qui est absurde. Donc $R$ est un tournoi. $\square$

**Lemme 3.19.** [9] Soient $R$ et $R'$ deux relations binaires ($\leq 4$)-hypomorphes sur une base finie $E$, et $C$ une classe de l'équivalence $D_{R,R'}$. Les 3-cycles de $R/C$ s'inversent dans $R'/C$.

**Preuve de la proposition 3.13.** D'après le lemme 3.18, $R$ est un tournoi. Par l'absurde si $R$ admet une 3-cycle de base $\{b_1, b_2, b_3\}$, alors le lemme 3.19 prouve que le 3-cycle $R'/\{b_1, b_2, b_3\}$ s'inverse dans $R$ et dans $R^*$, ce qui est absurde. Donc $R$ est une chaîne.

**Preuve du théorème 3.1.** Soient $R$ une relation binaire connexe finie de base $E$ de cardinal $n$ au moins égal à 13, et $R'$ une relation binaire $(n-6)$-hémimorphe à $R$. Le lemme 2.1 prouve que les relations $R$ et $R'$ sont ($\leq 6$)-hémimorphes. On a les cas suivants :
- Si l'équivalence $D_{R,R'}$ possède au moins deux classes, alors d'après le i) de la proposition 3.7, les classes de l'équivalence $D_{R,R'}$ sont des intervalles communs à $R$ et $R'$. D'autre part, les restrictions de $R$ et $R'$ à chacune de ces classes sont isomorphes (proposition 3.7). Il s'ensuit que $R'$ et $R$ sont isomorphes.

- Si l'équivalence $D_{R^*,R'}$ possède au moins deux classes, alors d'après le i) du corollaire 3.8, les classes de l'équivalence $D_{R^*,R'}$ sont des intervalles communs à $R^*$ et $R'$. D'autre part, les restrictions de $R^*$ et $R'$ à chacune de ces classes sont isomorphes (corollaire 3.8). Il s'ensuit que $R'$ et $R^*$ sont isomorphes.

- Si chacune des équivalences $D_{R,R'}$ et $D_{R^*,R'}$ possède une seule classe, on peut voir à l'aide de la proposition 3.13, que $R'$ et $R$ sont des chaînes, et par suite $R' \sim R \sim R^*$.

**4. La (-5)-demi-reconstructibilité des relations binaires connexes finies**

Dans ce paragraphe nous obtenons :

**Théorème 4.1.** *Les relations binaires connexes finies de cardinal $n \ge 12$ sont $(n-5)$-demi-reconstructibles.*

La preuve du théorème 4.1 est une conséquence des résultats suivants :

**Proposition 4.2.** *Soient $R$ et $R'$ deux relations binaires $(-5)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 12, et $C$ une classe de l'équivalence $D_{R,R'}$. Si $C$ est différente de sa composante connexe, alors:*

i) $C$ est un intervalle de $R$ et $R'$ sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

ii) $R'/C \sim R/C$.

Notons que comme conséquence des proposition 3.13 et 4.2 on a :

**Corollaire 4.3.** *Soient $R$ une relation binaire connexe finie de base $E$ de cardinal $n$ au moins égal à 12, et $R'$ une relation binaire $(n-5)$-hémimorphe à $R$, alors :*

- Si l'équivalence $D_{R,R'}$ possède au moins deux classes, alors $R'$ et $R$ sont isomorphes.

- Si l'équivalence $D_{R^*,R'}$ possède au moins deux classes, alors $R'$ et $R^*$ sont isomorphes.

- Si chacune des équivalences $D_{R,R'}$ et $D_{R^*,R'}$ possède une seule classe, alors $R'$ et $R$ sont des chaînes, et par suite $R' \sim R \sim R^*$.
Soient $R$ et $R'$ deux relations binaires $(-5)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 12, et $C$ une classe de l'équivalence $D_{R,R'}$ différente de sa composante connexe. D'après le lemme 2.1 les relations $R$ et $R'$ sont ($\le 5$)-hémimorphes. Comme $C$ est différente de sa composante connexe, alors le lemme 2.6 prouve que $C$ est un intervalle de $R$ et $R'$ sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

La preuve de la proposition 4.2 utilise les lemmes suivants :

**Lemme 4.4.** i) $R'/C$ et $R/C$ sont ($\le 4$)-hypomorphes.

ii) Si $R/C$ n'est ni un tournoi sans diamant ni un élément de $E(S_n)$, alors $R'/C \sim R/C$.

**Preuve.**

i) D'après le lemme 2.1, $R$ et $R'$ sont ($\le 5$)-hémimorphes. Comme $C$ est différent de sa composante connexe, alors le lemme 2.7 prouve que $R'/C$ et $R/C$ sont ($\le 4$)-hypomorphes.

ii) Comme $R'/C$ et $R/C$ sont ($\le 4$)-hypomorphes, alors le lemme 2.4 de G. Lopez et C. Rauzy nous donne la forme de $R/C$ et de $R'/C$, d'après la forme si $R/C$ n'est ni un tournoi sans diamant ni un élément de $E(S_n)$, alors $R'/C \sim R/C$. $\square$

**Lemme 4.5.** Si $|E-C| \ge 6$, alors $R'/C \sim R/C$.

**Preuve.** Comme $C$ est différente de sa composante connexe, alors il existe un élément $x$ de $E-C$, tel que $R(x, C) \neq R(C, x)$. D'après le lemme 4.4, on peut supposer que $R/C$ est un tournoi sans diamant ou un élément de $E(S_n)$, et par suite $R/C$ est soit une chaîne, soit une presque-chaîne, soit fortement connexe.

- Si $R/C$ est un tournoi sans diamant, on montre comme dans le lemme 3.11 que $R'/C \sim R/C$.

- Si $R/C$ est une presque-chaîne. D'après le lemme 4.4 les restrictions $R'/C$ et $R/C$ sont 3-hypomorphes, et par suite $R'/C$ est une presque-chaîne. Donc $R'/C \sim R/C$.

- Si $R/C$ est un élément de $E(S_n)$ fortement connexe, posons $H = R/(C \cup \{x\})$. Soit $a, b, c \in C$ tels que $R/\{a, b, c\}$ est une 3-consécutivité d'arête neutre $\{a, b\}$. Comme $C$ est un intervalle, alors pour tout $y \in C$, l'arête $\{x, y\}$ est orientée, d'autre part $R/C$ est un élément de $E(S_n)$, alors toutes les arêtes neutres de $R/C$ sont disjointes. Il s'ensuit que toutes les arêtes neutres de $H = R/(C \cup \{x\})$ sont disjointes. Considérons alors les parties $F$ de $E$ contenant $\{x, a, b, c\}$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$.
Montrons qu’il n’y en a pas d’autre que $C \cup \{x\}$. Par l’absurde, supposons qu’il existe une telle partie $F$ différente de $C \cup \{x\}$, et par suite il existe $y \in F$ et $y \notin C \cup \{x\}$. Comme $C$ est un intervalle et toutes les arêtes neutres de $H$ sont disjointes, alors $R/\{a, b, y\}$ est un pic de sommet $y$ et $R/\{a, b, x\}$ est un pic de sommet $x$. Puisque $C$ est un intervalle et que $R/C$ est un élément de $E(S_n)$, alors n’importe quel pic de $R/(C \cup \{x\})$ a pour sommet $x$, mais dans $R/F$ il y’a des pics de sommet $x$ et d’autres de sommet $y$. Il s’ensuit que $R/(C \cup \{x\})$ et $R/F$ ne sont pas hémimorphes. Donc $F = C \cup \{x\}$. Le nombre de parties $F$ de $E$ contenant $\{x, a, b, c\}$ telles que $R/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R, H, \{x, a, b, c\}) = 1$). D’après le lemme 2.2, le nombre de parties $F$ de $E$ contenant $\{x, a, b, c\}$ telles que $R'/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R', H, \{x, a, b, c\}) = 1$). Il s’ensuit que $R'/(C \cup \{x\}) \sim H$ ou $R'/(C \cup \{x\}) \sim H^*$. Comme $C$ est un intervalle et que $R/(C \cup \{x\})$ admet deux composantes fortement connexes $x$ et $C$, alors $H = R/(C \cup \{x\}) \sim R'/(C \cup \{x\})$ et par suite $R'/C \sim R/C$. $\square$

**Lemme 4.6.** $R'/C \sim R/C$.

**Preuve.** La classe $C$ étant différente de sa composante connexe, il existe un élément $x$ de $E-C$, tel que $R(x, C) \neq R(C, x)$. D’après le lemme 4.4, on peut supposer que $R/C$ est un tournoi sans diamant ou un élément de $E(S_n)$, et par suite toute restriction de $R/C$ est soit fortement connexe, soit une chaîne, soit une presque-chaîne. Posons $X = E - (C \cup \{x\})$, suivant le cardinal de $X$, on a les cas suivants :

- Si $|X| \geq 5$, alors $|E-C| \geq 6$, et par suite le lemme 4.5 prouve que $R'/C \sim R/C$.

- Si $|X| \in \{0, 1, 2, 3, 4\}$, on montre comme dans le lemme 3.12 que $R'/C \sim R/C$. $\square$

**Preuve de la proposition 4.2.** Comme $C$ est différent de sa composante connexe, alors le lemme 2.6 prouve que $C$ est un intervalle commun à $R$ et $R'$. Le lemme 4.6 prouve que $R'/C \sim R/C$.

**5. La (-d)-demi-reconstructibilité des relations binaires connexes finies**

Dans ce paragraphe nous obtenons :

**Théorème 5.1.** Pour tout entier $d \geq 5$, les relations binaires connexes finies de cardinal $n \geq 7+d$ sont $(n-d)$-demi-reconstructibles.
La preuve du théorème 5.1 est une conséquence des résultats suivants :

**Proposition 5.2.** Soient $d$ un entier $\ge 5$, $R$ et $R'$ deux relations binaires $(-d)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à $7+d$, et $C$ une classe de l'équivalence $D_{R,R'}$. Si $C$ est différente de sa composante connexe, alors :

i) $C$ est un intervalle de $R$ et $R'$ sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

ii) $R'/C \sim R/C$.

Notons que comme conséquence des proposition 3.13 et 5.2 on a :

**Corollaire 5.3.** Soient $d$ un entier $\ge 5$, $R$ une relation binaire connexe finie de base $E$ de cardinal $n$ au moins égal à $7+d$, et $R'$ une relation binaire $(n-d)$-hémimorphe à $R$, alors :

**Corollaire 5.4.** - Si l'équivalence $D_{R,R'}$ possède au moins deux classes, alors $R'$ et $R$ sont isomorphes.

- Si l'équivalence $D_{R^*,R'}$ possède au moins deux classes, alors $R'$ et $R^*$ sont isomorphes.

- Si chacune des équivalences $D_{R,R'}$ et $D_{R^*,R'}$ possède une seule classe, alors $R'$ et $R$ sont des chaînes, et par suite $R' \sim R \sim R^*$.

**Preuve de la proposition 5.2.** Le lemme 2.1 prouve que les relations $R$ et $R'$ sont ($\le d$)-hémimorphes.

i) Comme $C$ est différente de sa composante connexe, alors le lemme 2.6 prouve que $C$ est un intervalle de $R$ et $R'$ sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

ii) Suivant la valeur de $d$ on a :

- Si $d=5$, la proposition 4.2 prouve que $R/C \sim R'/C$.

- Si $d=6$, la proposition 3.7 prouve que $R/C \sim R'/C$.

- Si $d \ge 7$. Comme $C$ est différente de sa composante connexe, alors le lemme 2.7 prouve que $R/C$ et $R'/C$ sont ($\le d-1$)-hypomorphes. D'autre part $d \ge 7$, alors $R/C$ et $R'/C$ sont ($\le 6$)-hypomorphes et par suite $R/C \sim R'/C$ d'après le lemme 1.1.

**Optimalité de la valeur $7+d$ du théorème 5.1.**

Dans ce paragraphe, nous donnons un contre-exemple, prouvant l'optimalité de la valeur $7+d$ du théorème 5.1. On considère : La relation $R_1 = C_3(T_1, T_2, T_3)$ où $C_3$ est un 3-cycle de base $\{1,2,3\}$ et pour tout $i$, $T_i$ est une $i$-chaîne irréflexive.
Sous ces notations, on peut voir que les relations :

$R = T_2(R_1, T_d)$ et $R' = T_2(R^{*1}, T_d)$ sont $(-d)$-hémimorphes, sans être hémimorphes sur un ensemble de cardinal $d + 6$.

References

[1] Y. BOUDABBOUS et J. DAMMAK : Sur la (-k)-demi-reconstructibilité des tournois finis, CRAS, Série I 326, pp. 1037-1040, (1998).

[2] A. BOUSSAIRI : Thèse de doctorat de mathématiques. Soutenue à l'Université Claude Bernard, le 12 Juin (1995).

[3] J. DAMMAK : La dualité dans la demi-reconstruction des relations binaires finies, CRAS, Série I 327, pp. 861-864, (1998).

[4] J. DAMMAK : Caractérisation des relations binaires finies d-demi-reconstructibles, Proyecciones, Volume 22, N° 1, (2003).

[5] R. FRAÏSSÉ : L'intervalle en théorie des relations, in orders, descriptions and roles, M. Pouzet et D. Richard éd. North-Holland, pp. 313-342, (1984).

[6] C. GNANVO et P. ILLE : La reconstruction des tournois. C. R. Acad. Sci. Paris, t. 306, série I, pp. 577-580, (1988).

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

[8] G. LOPEZ : L'indéformabilité des relations et multirelations binaires. Zeitschrift. Math. Logik Grundlagen Math. 24, pp. 303-317, (1978)

[9] G. LOPEZ et C. RAUZY : Reconstruction of binary relations from their restrictions of cardinality 2,3,4 and (n-1), I. Zeitschr. f. Math. Logik und Grundlagen d. Math. Bd. 38, S. 27-37, (1992).

[10] G. LOPEZ et C. RAUZY : Reconstruction of binary relations from their restrictions of cardinality 2,3,4 and (n-1), II. Zeitschr. f. Math. Logik und Grundlagen d. Math. Bd 38, S. 157-168, (1992).
[11] M. POUZET : Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux relations. Math. Zeitschr. 150, pp. 117-134, (1976).

[12] S. M. ULAM : A collection of mathematical Problems (Interscience Publisher, New-York, (1960).

Received : April, 2003.

Jamel Dammak

Département de Mathématiques
Faculté des Sciences de Sfax
Université Claude Bernard Lyon 1
B. P. 802, 3018 Sfax
Tunisie
e-mail : jdammak@yahoo.fr
Fax : 216 74 274437