# LE SEUIL DE RECONSTRUCTIBILITÉ PAR LE HAUT MODULO LA DUALITÉ DES RELATIONS BINAIRES 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 à $n$ éléments est $(-k)$-demi-reconstructible, si elle est déterminée à l'hémimorphie près, par la donnée à l'hémimorphie près de ses restrictions de cardinal ($n-k$). L'étude faite en [8] entraîne la $(-d)$-demi-reconstructibilité des relations binaires finies pour tout $d \ge 12$. Nous étabissons la $(-d)$-demi-reconstructibilité des relations binaires finies pour tout $d \in \{11, 10, 9, 8, 7, 6\}$.

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 relation $R$ defined on $n$ elements is $(-k)$-half-reconstructible if it is determined, up to hemimorphism, by its restrictions of cardinality ($n-k$). From [8] follows the $(-d)$-half-reconstructibility of finite binary relations, for all $d \ge 12$. We establish the $(-d)$-half-reconstructibility of finite binary relations, for all $d \in \{11, 10, 9, 8, 7, 6\}$.

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

**Key Words :** Relation de différence, Relation binaire, Graphe, Hémorphe, Hémimorphe, Reconstruction.
# 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).

Dans ce papier nous montrons :

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

Ensuite dans le cas général nous montrons : Pour tout entier $d \geq 6$, les relations binaires finies de cardinal $n \geq 16 + d$ sont ($n-d$)-demi-reconstructibles.

## 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)$.

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

- 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) = + \quad ssi \quad (y = x+1)], [R_2(x, y) = + \quad ssi \quad (y = x+1 \text{ ou } y = x)], [R_3(x, y) = + \quad ssi \quad (y = x+1 \text{ ou } |y - x| > 1)], [R_4(x, y) = + \quad ssi \quad (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) = -\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 [6]. 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.** [9] Les relations binaires finies sont ($\leq 6$)-reconstructibles.

**Lemme 2.2.** [5] Pour tout entier $d \geq 5$, les relations binaires connexes finies de cardinal $n \geq 7+d$ sont $(n-d)$-demi-reconstructibles.

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

**Lemme 2.4.** [4] Pour tout entier $k \geq 2$, les relations binaires finies abritant un non auto-dual de cardinal $k$, sont ($\leq k+6$)-demi-reconstructibles.

**Lemme 2.5.** [12] 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 \leq q \leq n-1$, alors pour tout entier $p \leq \min(q, n-q)$, $R$ et $R'$ sont $p$-hémimorphes (resp. $p$-hypomorphes).

**Lemme 2.6.** [2] Soit $B$ une relation binaire de base $\{1,...,n\}$ (où $n \geq 2$), $i_0 \in \{1,...,n\}$, et $R$ (resp. $R'$) la relation obtenu à partir du relation $B$, en dilatant le sommet $i_0$ par une relation $H$ (reps. $H'$). Si les relations $R$ et $R'$ sont isomorphes, alors les relations $H$ et $H'$ sont aussi isomorphes.

**Lemme 2.7.** [1] Soient $n, d$ et $h$ des entiers naturels avec $1 \leq d \leq n-1$ et $1 \leq h \leq 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.7) $n(R, H, A) = \text{card}\{F \subset E : A \subset \text{Fet}R/F \sim \text{Hou}R/F \sim H^*\}n(R', H, A) = \text{card}\{F \subset E : A \subset \text{Fet}R'/F \sim \text{Hou}R'/F \sim H^*\}$.

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

**Lemme 2.8.** ([5] et [11]). Soient $R$ et $R'$ deux relations binaires de base commune $E$ de cardinal $n$.

i) 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.

ii) Pour tout entier $h \geq 4$, si $R$ et $R'$ sont $(n-h)$-hypomorphes et si $|E| \geq 6+h$, alors $R$ et $R'$ sont isomorphes.
**Relation de différence.** La notion de relation de différence a été introduite par G. Lopez dans [9]. 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.9.** [10] Soient $R$ et $R'$ deux relations binaires ($\leq 3$)-hypomorphes sur une même base finie $E$. Toute classe de l'équivalence $D_{R,R'}$ est un intervalle commun à $R$ et $R'$ sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives

**Lemme 2.10.** [10] 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)$.

Notons que comme conséquence du lemme 2.10, on a :

**Corollaire 2.11.** 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) S'il existe un entier $h$ tel que $R/C \in D(T_h)$, alors $R'/C \in D(T^*_h)$ et $(R'/C \text{ et } R^*/C)$ sont ($\leq 6$)-hypomorphes.

ii) S'il existe un entier $n$ telle que $R/C$ est un élément de $E(S_n)$, alors $R'/C \in E(S_n^*)$, et $(R'/C \text{ et } R^*/C)$ sont ($\leq 6$)-hypomorphes.

iii) $R/C$ et $R'/C$ n'abritent pas de restrictions non auto-dual de cardinal $\leq 4$.

**Relation connexe et fortement connexe.** Une relation $R$ de base finie $E$ est dite connexe (resp. fortement 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)$ (resp. $R(x_i, x_{i+1}) =$
$-R(x_{i+1}, x_i) = +)$. La composante connexe (rep. fortement 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 (resp. $R/D$ soit fortement connexe).

Rappelons les résultats suivants :

**Lemme 2.12.** [5] 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$.

**Lemme 2.13.** [5] 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.

**Lemme 2.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'}$. Si $R/C$ et $R'/C$ sont ($\le 5$)-hypomorphes et si $R/C$ est un élément de $E(S_n)$, alors $R'/C \sim R/C \sim R^*/C$.

Notons que comme conséquence des lemme 2.10 et 2.14 on a :

**Corollaire 2.15.** Soient $R$ et $R'$ deux relations binaires ($\le 5$)-hémimorphes sur une base finie $E$, $D$ une composante connexe de $R$ et $k$ le plus petit cardinal des restrictions non auto-duales de $R$. Si $k=6$ et si $R/D$ n'est pas un tournoi sans diamant, alors $R'/D \sim R/D \sim R^*/D$.

**Corollaire 2.16.** Soient $R$ et $R'$ deux relations binaires ($\le 5$)-hémimorphes sur une base finie $E$, $D$ une composante connexe de $R$ et $k$ le plus petit cardinal des restrictions non auto-duales de $R$.

i) Si $k \in \{5,6\}$ et si $R/D$ n'est ni un tournoi sans diamant ni un élément de $E(S_n)$, alors $R'/D \sim R/D \sim R^*/D$.

ii) Si $k=6$ et si $R/D$ est un élément de $E(S_n)$, alors $R'/D \sim R/D \sim R^*/D$.

**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.17.** [4] Soient $r \ge 2$ un entier, $R$ et $R'$ deux relations binaires ($\le 4$)-hémimorphes sur une base finie $E$. Si $R$ n'abrite aucune restriction non auto-duale à au plus $r$ sommets, alors les relations $R, R^*$ et $R'$ sont deux à deux ($\le r$)-hypomorphes.

**Lemme 2.18.** [4] 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$.

Notons que comme conséquence des lemmes 2.17 et 2.18, on a :

**Corollaire 2.19.** Soit $r$ un entier, $2 \le r \le 6$. 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'}$. Alors $R/C$ et $R'/C$ sont ($\le r$)-hypomorphes ssi $R/C$ n'abrite aucune relation non auto-duale minimale à au plus $r$ sommets.

**Lemme 2.20.** [4] Soient $R$ et $R'$ deux relations binaires ($\le 6$)-hémimorphes sur une base finie $E$ admettant une restriction non auto-duale, $k$ la plus petite cardinalité des restrictions non auto-duales de $R$, $I_0$ la base d'une de ces restrictions et $C$ une classe de l'équivalence $D_{R,R'}$. Si $R/I_0 \sim R'/I_0$, 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.21.** [4] Soient $R$ et $R'$ deux relations binaires ($\le 6$)-hémimorphes sur une base finie $E$, admettant une restriction non auto-duale, $C$ une classe de l'équivalence $D_{R,R'}$ égale à sa composante connexe, $k$ la cardinalité minimale des restrictions non auto-duales qui s'abritent dans $R$, et $I_0$ la base d'une de ces restrictions. Si $R/I_0 \sim R'/I_0$, alors :

i) Si $R/I_0$ n'est pas un drapeau, alors $I_0 \cap C = \emptyset$.

ii) Si $R/I_0$ est un drapeau, d'arête neutre $\{c, a\}$ et $\{c, b\}$, alors $I_0 \cap C = \emptyset$ ou $I_0 \cap C = \{c\}$.

**Lemme 2.22.** [4] Soient $d$ un entier $\ge 5$, $R$ et $R'$ deux relations binaires ($\le d$)-hémimorphes sur une base finie $E$ admettant une restriction non auto-duale, $k$ la cardinalité minimale des restrictions non auto-duales qui s'abritent dans $R$, $I_0$ la base d'une de ces restrictions et $C$ une classe de l'équivalence $D_{R,R'}$.

i) Si $C$ est différente de sa composante connexe, alors $R/C$ et $R'/C$ sont ($\le d-1$)-hypomorphes.
ii) Si $d \ge 6$, si $R'/I_0 \sim R/I_0$, si $R/I_0$ un drapeau et si $C \cap I_0 \ne \emptyset$, alors $R/C$ et $R'/C$ sont $(\le d-2)$-hypomorphes.

iii) Si $d \ge 6$ et si $R/I_0 \sim R'/I_0$, alors $R/C$ et $R'/C$ sont $(\le \max(k-1, d-k))$-hypomorphes.

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

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

Soient $R$ et $R'$ deux relations binaires $(n-11)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 23 et $k$ le plus petit cardinal des restrictions non auto-duales de $R$. Le lemme 2.5 prouve que les relations $R$ et $R'$ sont $(\le 11)$-hémimorphes. Suivant la valeur de $k$, on a:

-Si $R$ est connexe, alors le lemme 2.2 prouve que $R$ est $(n-11)$-demi-reconstructible.

- Si $2 \le k \le 5$, alors le lemme 2.4 prouve que $R$ est 11-demi-reconstructible et par suite $R$ est $(n-11)$-demi-reconstructible (lemme 2.5).

- Si $k \ge 7$ ou $k = 0$. Dans ce cas $R$ n'admet aucune restriction non auto-duale de cardinal inférieur au égal à 6, alors le lemme 2.1 prouve que $R$ est $(n-11)$-demi-reconstructible.

Dans la suite $k=6$, donc les relations $R, R^*$ et $R'$ sont deux à deux $(\le 5)$-hypomorphes. Soit $D$ la plus grande composante connexe non auto-duale de $R$. D'après le corollaire 2.15 $R/D$ est un tournoi sans diamant, de même le lemme 2.13 prouve que l'une des équivalences $D_{R/D,R'/D}$ ou $D_{R^*/D,R'/D}$ possède au moins deux classes.

La preuve du théorème 3.1 utilise les résultats suivants :

**Proposition 3.2.** Soient $D$ la plus grande composante connexe non auto-duale de $R$. Si l'équivalence $D_{R/D,R'/D}$ possède au moins deux classes, alors $R' \sim R$.

Notons que comme conséquence de la proposition 3.2 on a :

**Corollaire 3.3.** Soient $D$ la plus grande composante connexe non auto-duale de $R$. Si l'équivalence $D_{R^*/D,R'/D}$ possède au moins deux classes, alors $R' \sim R^*$.
Dans la suite de la preuve de la proposition 3.2 $C$ est une classe de l'équivalence $D_{R,R'}$. Comme $k=6$, alors les relations $R$ et $R'$ sont ($\leq 5$)-hypomorphes, et par suite d'après le lemme 2.9 $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.2 utilise les lemmes suivants :

**Lemme 3.4.** i) Si $C$ est différente de sa composante connexe, alors $R'/C \sim R/C$.

ii) Si $R/C$ n'est pas un tournoi sans diamant, alors $R'/C \sim R/C$.

iii) Si $R/C$ est auto-dual, alors $R'/C \sim R/C$.

**Preuve.** i) Si $C$ est différente de sa composante connexe, alors le lemme 2.12 prouve que $R'/C \sim R/C$.

ii) On suppose que $C$ est une composante connexe de $R$. Comme $k=6$ et $R/C$ n'est pas un tournoi sans diamant, alors d'après le corollaire 2.2 $R'/C \sim R/C$.

iii) Comme $R/C$ est connexe, alors le lemme 2.3 prouve que $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R/C$ est auto-dual, alors $R'/C \sim R/C \sim R^*/C$. $\square$

Dans la suite on suppose que $C$ et $D$ sont deux composantes connexes non auto-duales de $R$ qui sont des tournois sans diamant.

**Lemme 3.5.** $R'/D$ et $R/D$ sont ($\leq 6$)-hypomorphes.

**Preuve.** Puisque l'équivalence $D_{R/D,R'/D}$ possède au moins deux classes et les relations $R$ et $R'$ sont ($\leq 7$)-hémimorphes, alors le i) du lemme 2.22 prouve que $R'/D$ et $R/D$ sont ($\leq 6$)-hypomorphes, et par suite d'après le lemme 2.1 $R'/D \sim R/D$. $\square$

**Lemme 3.6.** Si $|E - (C \cup D)| \geq 11$, alors $R'/C \sim R/C$.

**Preuve.** Comme l'équivalence $D_{R/D,R'/D}$ possède au moins deux classes, alors $C \cap D = \emptyset$. D'après le lemme 3.4, on peut supposer que $C$ est une composante connexe de $R$ et que $R/C$ est un tournoi sans diamant non auto-dual, et par suite $R/C$ est fortement connexe. Posons $H = R/(C \cup D)$. Soient $(a,b) \in C \times D$. Considérons les parties $F$ de $E$ contenant $\{a,b\}$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Il n'y en a pas d'autre que $C \cup D$ car $H = R/(C \cup D)$ admet deux composantes connexes $C$ et $D$. Le nombre de parties $F$ de $E$ contenant $\{a,b\}$ telles que $R/F$ est
hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R, H, \{a, b\}) = 1$). D'après le lemme 2.7, le nombre de parties $F$ de $E$ contenant $\{a, b\}$ telles que $R'/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R', H, \{a, b\}) = 1$). Il s'ensuit que $R'(C \cup D) \sim H = R/(C \cup D)$ ou $R'(C \cup D) \sim H^*$. Comme $C$ et $D$ sont les composantes connexes de $R/(C \cup D)$ et $R'/D \sim R/D$, alors $R'/C \sim R/C$. $\square$

**Lemma 3.7.** Si $|E - D| \ge 17$, alors $R/C \sim R'/C$.

**Preuve.** Si $|C| \le 6$, alors le lemme 3.6 prouve que $R/C \sim R'/C$. Dans la suite $|C| \ge 7$. Soient $A$ une partie de $C$ de cardinal $\le 6$, $b \in D$ et $H = R/(A \cup D)$. Si $R/A$ est auto-dual, on a trivalement l'isomorphisme entre $R/A$ et $R'/A$. Dans La suite, $R/A$ n'est pas auto-dual. On va distinguer les cas suivants :

$c_1)$ Cas où $R/C$ et $R/D$ ne sont pas hémimorphes.

Considérons les parties $F$ de $E$ contenant $\{b\} \cup A$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Il n'y en a pas d'autre que $A \cup D$, car $H = R/(A \cup D)$ admet deux composantes connexes $A$ et $D$. Le nombre de parties $F$ de $E$ contenant $\{b\} \cup A$ telles que $R/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R, H, \{b\} \cup A) = 1$). D'après le lemme 2.7, $n(R', H, \{b\} \cup A) = 1$. Il s'ensuit que $R'(A \cup D) \sim H$ ou $R'(A \cup D) \sim H^*$. Comme $A$ et $D$ sont les composantes connexes de $R/(A \cup D)$ et $R'/D \sim R/D$, alors $R'/A \sim R/A$.

$c_2)$ Cas $R/C$ et $R/D$ sont hémimorphes.

Soit $x \in (C - A)$. Considérons alors les parties $F$ de $E - \{x\}$ contenant $\{b\} \cup A$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Il n'y en a pas d'autre que $A \cup D$ car $A$ et $D$ sont les composantes connexes de $H = R/(A \cup D)$. Le nombre de parties $F$ de $E - \{x\}$ contenant $\{b\} \cup A$ telles que $R/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R/(E - \{x\}), H, \{b\} \cup A) = 1$). D'après le lemme 2.7, $n(R'(E - \{x\}), H, \{b\} \cup A) = 1$). Il s'ensuit que $R'(A \cup D) \sim H$ ou $R'(A \cup D) \sim H^*$. Comme $A$ et $D$ sont les composantes connexes de $H = R/(A \cup D)$ et $R'/D \sim R/D$, alors $R'/A \sim R/A$.

Dans les deux cas $R'/A \sim R/A$. Il s'ensuit que $R/C$ et $R'/C$ sont $(\le 6)$-hypomorphes, et par suite d'après le lemme 2.1 $R/C \sim R'/C$. $\square$

**Lemma 3.8.** Si $h \ge 1$ et si $|D| \ge 6+h$, alors il existe une partie $A$ de $D$ de cardinal $h$ tel que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes.

**Preuve.** Soit $h \ge 1$. Si pour toute partie $A$ de $D$ de cardinal $h$, $R^*/(D-A) \sim R/(D-A)$, alors $R^*/D$ et $R/D$ sont $(-h)$-hypomorphes
et comme $R/D$ et $R^*/D$ sont $(\le 4)$-hypomorphes et $|D|\ge 6+h$, alors $R^*/D \sim R/D$ (lemme 2.8), ce qui est impossible. D'ou il existe $A \subset D$ tel que $R/(E-A)$ est non auto-dual. D'après le lemme 3.5 $R/D$ et $R'/D$ sont $(\le 6)$-hypomorphes, alors $R/(D-A)$ et $R'/(D-A)$ sont aussi $(\le 6)$-hypomorphes, et par suite $R'/(D-A) \sim R/(D-A)$ (lemme 2.1). Il s'ensuit que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes.
□

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

**Preuve.** D'après le lemme 3.4 $C$ et $D$ sont deux composantes connexes de $R$ qui sont deux tournois sans diamant. Posons $X = E-(C\cup D)$. D'après le lemme 3.6 on peut supposer que $|X|\le 10$, de même d'après le lemme 3.7 on suppose que $|E-D|\le 16$. Suivant le cardinal de $C$, on a :

Cas 1 Si $|C|\le 6$.

Suivant le cardinal de $X$, on a :

$c_1$) $|X|=10$. D'après le lemme 3.8 il existe une partie $A$ de $D$ de cardinal 1 tel que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A\cup X)$ sur $R'/(E-A\cup X)$. Si $f$ est un isomorphisme, comme $R'/(D-A) \sim R/(D-A)$, alors le lemme 2.6 prouve que $R/C \sim R'/C$. Si $f$ est un anti-isomorphisme. Comme $C$ est connexe, alors d'après le lemme 2.3 $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R'/C \sim R^*/C$, alors d'après le lemme 2.6 $R'/(D-A) \sim R^*/(D-A)$, ce qui est impossible. Donc $R/C \sim R'/C$.

$c_2$) $|X|\le 9$. D'après le lemme 3.8 il existe une partie $A$ de $D$ tel que $|X| + |A| = 11$ et $(R/(D-A)$ et $R'/(D-A))$ sont isomorphes mais non anti-isomorphes. Nous montrons comme dans le cas $c_1$ que $R/C \sim R'/C$.

Cas 2 Si $|C|\ge 7$.

Soient $J$ une partie de $C$ de cardinal $h$ tel que $|C|-h=6$. D'après le lemme 3.8 il existe une partie $A$ de $D$ telle que $|A| + |J| + |X| = 11$ et $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A\cup X\cup J)$ sur $R'/(E-A\cup X\cup J)$.

- Si $f$ est un isomorphisme. Comme $R'/(D-A) \sim R/(D-A)$, alors le lemme 2.6 prouve que $R'/(C-J) \sim R/(C-J)$.

- Si $f$ est un anti-isomorphisme. Comme $|(C-J)|=6$, alors $R'/(C-J) \sim R/(C-J)$ ou $R'/(C-J) \sim R^*/(C-J)$. Si $R'/(C-J) \sim R^*/(C-J)$, alors d'après le lemme 2.6 $R'/(D-A) \sim R^*/(D-A)$ ce qui est impossible. Donc $R'/(C-J) \sim R/(C-J)$.

Dans les deux cas $R'/(C-J) \sim R/(C-J)$. Les restrictions $R/C$ et $R'/C$ sont donc $(4, -h)$-hypomorphes et $|C|-h=6$. Il s'ensuit que
$R/C \sim R'/C$ (lemme 2.8). □

**Optimalité de la valeur 23 du théorème 3.1.**

Dans ce paragraphe, nous donnons un contre-exemple, prouvant l'optimalité de la valeur 23 du théorème 3.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$-chaine. Avec ces notations on peut voir que les relations :

$R = S(R_1, R_1, T_{10})$ et $R' = S(R_1, R_1, T_{10})$ (où $S$ est une relation vide à 3 éléments) sont $(-11)$-hémimorphes, sans être hémimorphes sur un ensemble de cardinal 22.

**4. La $(-10)$-demi-reconstructibilité des relations binaires finies**

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

Soient $R$ et $R'$ deux relations binaires $(n-10)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 22 et $k$ le plus petit cardinal des restrictions non auto-duales de $R$. Le lemme 2.5 prouve que les relations $R$ et $R'$ sont $(\le 10)$-hémimorphes. On a :

-Si $R$ est connexe, alors le lemme 2.2 prouve que $R$ est $(n-10)$-demi-reconstructible.

- Si $2 \le k \le 4$, alors le lemme 2.4 prouve que $R$ est 10-demi-reconstructible et par suite $R$ est $(n-10)$-demi-reconstructible (lemme 2.5).

- Si $k \ge 7$ ou $k = 0$. Dans ce cas $R$ n'admet aucune restriction non auto-duale de cardinal inférieur au égal à 6, alors le lemme 2.1 prouve que $R$ est $(n-10)$-demi-reconstructible.

Dans la suite $k \in \{5, 6\}$ donc les relations $R, R^*$ et $R'$ sont deux à deux $(\le 4)$-hypomorphes. Soit $D$ la plus grande composante connexe non auto-duale de $R$. D'après le $i$) du corollaire 2.16 $R/D$ est un tournoi sans diamant ou un élément de $E(S_n)$, de même le lemme 2.13 prouve que l'une des équivalences $D_{R/D,R'/D}$ ou $D_{R^*/D,R'/D}$ possède au moins deux classes.

La preuve du théorème 3.1 utilise les résultats suivants :

**Proposition 4.2.** Soient $D$ la plus grande composante connexe non auto-duale de $R$. Si l'équivalence $D_{R/D,R'/D}$ possède au moins deux classes, alors $R' \sim R$.
Notons que comme conséquence de la proposition 4.2 on a :

**Corollaire 4.3.** Soient $D$ la plus grande composante connexe non auto-duale de $R$. Si l'équivalence $D_{R^*/D,R'/D}$ possède au moins deux classes, alors $R' \sim R^*$.

Dans la suite de la preuve de la proposition 4.2 $C$ est une classe de l'équivalence $D_{R,R'}$. Comme $k \in \{5,6\}$, alors les relations $R$ et $R'$ sont $(\leq 4)$-hypomorphes, et par suite d'après le lemme 2.9 $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) Si $C$ est différente de sa composante connexe, alors $R'/C \sim R/C$.

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$.

iii) Si $R/C$ est auto-dual, alors $R'/C \sim R/C$.

**Preuve.** i) Si $C$ est différente de sa composante connexe, alors le lemme 2.12 prouve que $R'/C \sim R/C$.

ii) On suppose que $C$ est une composante connexe de $R$. Comme $k \in \{5,6\}$ et $R/C$ n'est ni un tournoi sans diamant ni un élément de $E(S_n)$, alors d'après le lemme 2.10 $R'/C \sim R/C$.

iii) Comme $R/C$ est connexe, alors le lemme 2.3 prouve que $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R/C$ est auto-dual, alors $R'/C \sim R/C \sim R^*/C$. $\square$

Dans la suite on suppose que $C$ et $D$ sont deux composantes connexes non auto-duales de $R$ qui sont des tournois sans diamant ou des éléments de $E(S_n)$.

**Lemme 4.5.** Si $|E - (C \cup D)| \geq 10$, alors $R'/C \sim R/C$.

**Preuve.** La preuve est analogue à la preuve du lemme 3.6. $\square$

**Lemme 4.6.** Si $|E - D| \geq 16$, alors $R/C \sim R'/C$.

**Preuve.** La preuve est analogue à la preuve du lemme 3.7. $\square$

**Lemme 4.7.** $R/C \sim R'/C$.
**Preuve.** La preuve est analogue à la preuve du lemme 3.9. □

**Optimalité de la valeur 22 du théorème 4.1.**

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

$R = S(R_1, R_1, T_9)$ et $R' = S(R_1, R_1^*, T_9)$ (S est une relation vide à 3 éléments) sont $(-10)$-hémimorphes, sans être hémimorphes sur un ensemble de cardinal 21.

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

**Théorème 5.1.** *Les relations binaires finies de cardinal $n \ge 21$ sont (n – 9)-demi-reconstructibles.*

Soient $R$ et $R'$ deux relations binaires (n – 9)-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 21 et $k$ le plus petit cardinal des restrictions non auto-duales de $R$, et $I_0$ la base d'une de ces restrictions. Le lemme 2.5 prouve que les relations $R$ et $R'$ sont (≤ 9)-hémimorphes. On a :

- Si $R$ est connexe, alors le lemme 2.2 prouve que $R$ est (n – 9)-demi-reconstructible.

- Si $2 \le k \le 3$, alors le lemme 2.4 prouve que $R$ est 9-demi-reconstructible et par suite $R$ est (n – 9)-demi-reconstructible (lemme 2.5).

- Si $k \ge 7$ ou $k = 0$. Dans ce cas $R$ n'admet aucune restriction non auto-duale de cardinal inférieur ou égal à 6, alors le lemme 2.1 prouve que $R$ est (n – 9)-demi-reconstructible.

- Si $k \in \{5, 6\}$, alors les relations $R, R^*$ et $R'$ sont deux à deux (≤ 4)-hypomorphes. Soient $D$ la plus grande composante connexe non auto-duale de $R$, nous montrons comme dans la proposition 3.2 que si l'équivalence $D_{R/D,R'/D}$ (resp. $D_{R^*/D,R'/D}$) possède au moins deux classes, alors $R' \sim R$ (resp. $R' \sim R^*$).

Dans la suite $k = 4$, donc les relations $R, R^*$ et $R'$ sont deux à deux (≤ 3)-hypomorphes, et par suite d'après le lemme 2.9 toute classe $C$ de l'équivalence $D_{R,R'}$ est un intervalle de $R$ et $R'$, sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

La preuve du théorème 5.1 utilise les résultats suivants :
**Proposition 5.2.** Si $R'/I_0 \sim R/I_0$, alors $R' \sim R$.

Notons que comme conséquence de la proposition 5.2 on a :

**Corollaire 5.3.** Si $R'/I_0 \sim R^*/I_0$, alors $R' \sim R^*$.

Dans la suite de la preuve de la proposition 5.2, $C$ est une classe de l'équivalence $D_{R,R'}$, la preuve utilise les lemmes suivants :

**Lemme 5.4.** i) Si $C$ est différente de sa composante connexe, alors $R'/C \sim R/C$.

ii) Si $R/C$ est auto-dual, alors $R'/C \sim R/C$.

**Preuve.** i) Si $C$ est différente de sa composante connexe, alors le lemme 2.12 prouve que $R'/C \sim R/C$.

ii) Comme $R/C$ est connexe, alors le lemme 2.3 prouve que $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R/C$ est auto-dual, alors $R'/C \sim R/C \sim R^*/C$. $\square$

Dans la suite on suppose $C$ est une composante connexe non auto-duale de $R$.

**Lemme 5.5.** $I_0 \cap C = \emptyset$.

**Preuve.** Puisque $R/I_0$ n'est pas un drapeau, et $R'/I_0 \sim R/I_0$, alors d'après le i) du lemme 2.21 $I_0 \cap C = \emptyset$. $\square$

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

ii) Si $R/C$ n'est pas un tournoi sans diamant, alors $R'/C \sim R/C$.

**Preuve.** i) Comme $R$ et $R'$ sont $(\le 9)$-hémimorphes et $R'/I_0 \sim R/I_0$, et $|I_0| = 4$, alors le lemme 2.13 prouve que $R'/C$ et $R/C$ sont $(\le 5)$-hypomorphes.

ii) Puisque $R'/C$ et $R/C$ sont $(\le 5)$-hypomorphes, alors le lemme 2.10 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.14 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 5.7.** Si $|E - (C \cup I_0)| \ge 9$, alors $R'/C \sim R/C$.
**Preuve.** D'après le lemme 5.4 on suppose que $C$ est une composante connexe non auto-duale de $R$, de même d'après le lemme 5.6 on suppose que $R/C$ est un tournoi sans diamant, et par suite $R/C$ est fortement connexe. Soient $H = R/(I_0 \cup C)$, et $a \in C$. Considérons alors les parties $F$ de $E$ contenant $I_0 \cup \{a\}$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Il n'y en a pas d'autre que $I_0 \cup C$ car $I_0$ et $C$ sont les composantes connexes de $H = R/(I_0 \cup C)$. Le nombre de parties $F$ de $E$ contenant $I_0 \cup \{a\}$ telles que $R/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R, H, I_0 \cup \{a\}) = 1$). D'après le lemme 2.7, le nombre de parties $F$ de $E$ contenant $I_0 \cup \{a\}$ telles que $R'/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R', H, I_0 \cup \{a\}) = 1$). Il s'ensuit que $R'/(C \cup I_0) \sim H$ ou $R'/(C \cup I_0) \sim H^*$. Comme $R/(C \cup I_0)$ admet deux composantes connexes $I_0$ et $C$, et $R'/I_0 \sim R/I_0$, alors $R/C \sim R'/C$. $\square$

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

**Preuve.** D'après le lemme 2.17, on peut supposer que $R/C$ est un tournoi sans diamant. Posons $X = E - (C \cup I_0)$, suivant le cardinal de $x$, on les cas suivants :

- $c_1$ Si $|X| \ge 9$, alors le lemme 3.4 prouve que $R/C \sim R'/C$.

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

- $c_3$ Si $|X| = 7$. Soit $J$ une partie de $C$ de cardinal 2. Nous montrons comme dans le cas $c_2$ que $R'/(C - J) \sim R/(C - J)$. Donc $R/C$ et $R'/C$ sont $(4, -2)$-hypomorphes et $|C| \ge 8$, et par suite d'après le lemme 2.8 $R'/C \sim R/C$.

- $c_4$ Si $|X| \le 6$. Soit $J$ une partie de $C$ de cardinal $h$ tel que $h+|X|=9$. Nous montrons comme dans le cas $c_2$ que $R'/(C - J) \sim R/(C - J)$. Donc $R/C$ et $R'/C$ sont $(4, -h)$-hypomorphes et $|C| \ge 6+h$, et par suite d'après le lemme 2.8 $R'/C \sim R/C$. $\square$

**Optimalité de la valeur 21 du théorème 5.1.**
Dans ce paragraphe, nous donnons un contre-exemple, prouvant l'optimalité de la valeur 21 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. Avec ces notations on peut voir que les relations :

$R = S(R_1, R_1, T_8)$ et $R' = S(R_1, R^*_1, T_8)$ (où $S$ est une relation vide à 3 éléments) sont $(-9)$-hémimorphes, sans être hémimorphes sur un ensemble de cardinal 20.

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

**Théorème 6.1.** *Les relations binaires finies de cardinal $n \ge 20$ sont (n – 8)-demi-reconstructibles.*

Soient $R$ et $R'$ deux relations binaires (n – 8)-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 20 et $k$ le plus petit cardinal des restrictions non auto-duales de $R$, et $I_0$ la base d'une de ces restrictions. Le lemme 2.5 prouve que les relations $R$ et $R'$ sont (≤ 8)-hémimorphes. On a :

-Si $R$ est connexe, alors le lemme 2.2 prouve que $R$ est (n – 8)-demi-reconstructible.

- Si $k = 2$, alors le lemme 2.4 prouve que $R$ est 8-demi-reconstructible et par suite $R$ est (n – 8)-demi-reconstructible (lemme 2.5).

- Si $k \ge 7$ ou $k = 0$. Dans ce cas $R$ n'admet aucune restriction non auto-duale de cardinal inférieur au égal à 6, alors le lemme 2.1 prouve que $R$ est (n – 8)-demi-reconstructible.

- Si $k \in \{5, 6\}$, alors les relations $R, R^*$ et $R'$ sont deux à deux (≤ 4)-hypomorphes. Soient $D$ la plus grande composante connexe non auto-duale de $R$, nous montrons comme dans la proposition 3.2 que si l'équivalence $D_{R/D,R'/D}$ (resp. $D_{R^*/D,R'/D}$) possède au moins deux classes, alors $R' \sim R$ (resp. $R' \sim R^*$).

- Si $k = 4$. Nous montrons comme dans la proposition 5.2 que si $R'/I_0 \sim R/I_0$ (resp. $R'/I_0 \sim R^*/I_0$), alors $R' \sim R$ (resp. $R' \sim R^*$).

Dans la suite $k = 3$.

La preuve du théorème 6.1 utilise la proposition suivante :

**Proposition 6.2.** *Si $R'/I_0 \sim R/I_0$, alors $R \sim R'$.*

Notons que comme conséquence de la proposition 6.2 on a :
**Corollaire 6.3.** Si $R'/I_0 \sim R^*/I_0$, alors $R' \sim R^*$.

**Preuve de la proposition 6.2** Soit $C$ une classe de l'équivalence $D_{R,R'}$. Comme $R'/I_0 \sim R/I_0$, alors d'après le lemme 2.21, $I_0 \cap C = \emptyset$ ou $I_0 \cap C = \{c\}$ avec $R/I_0$ est un drapeau, d'arête neutre $\{c,a\}$ et $\{c,b\}$.

i) Si $I_0 \cap C = \emptyset$, nous montrons comme dans la proposition 5.2 que si $R'/I_0 \sim R/I_0$, alors $R/C \sim R'/C$.

ii) Si $R/I_0$ est un drapeau, d'arête neutre $\{c,a\}$ et $\{c,b\}$ et $I_0 \cap C = \{c\}$, alors le ii) du lemme 2.21 prouve que $R/C$ et $R'/C$ sont $(\le 6)$-hypomorphes, et par suite $R'/C \sim R/C$ (d'après le lemme 2.1).

**Optimalité de la valeur 20 du théorème 6.1.**

Dans ce paragraphe, nous donnons un contre-exemple, prouvant l'optimalité de la valeur 20 du théorème 6.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. Avec ces notations on peut voir que les relations :

$R = S(R_1, R_1, T_7)$ et $R' = S(R_1, R_1^*, T_7)$ (où $S$ est une relation vide à 3 éléments) sont $(-8)$-hémimorphes, sans être hémimorphes sur un ensemble de cardinal 19.

**7. La (-7)-demi-reconstructibilité des relations binaires finies.**

**Théorème 7.1.** *Les relations binaires finies de cardinal $n \ge 25$ sont (n - 7)-demi-reconstructibles.*

Soient $R$ et $R'$ deux relations binaires $(n-7)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 25 et $k$ le plus petit cardinal des restrictions non auto-duales de $R$, et $I_0$ la base d'une de ces restrictions. Le lemme 2.5 prouve que les relations $R$ et $R'$ sont $(\le 7)$-hémimorphes. On a :

- Si $R$ est connexe, alors le lemme 2.2 prouve que $R$ est $(n-7)$-demi-reconstructible.

- Si $k \ge 7$ ou $k=0$. Dans ce cas $R$ n'admet aucune restriction non auto-duale de cardinal inférieur ou égal à 6, alors le lemme 2.1 prouve que $R$ est $(n-7)$-demi-reconstructible.

- Si $k \in \{5,6\}$, alors les relations $R, R^*$ et $R'$ sont deux à deux $(\le 4)$-hypomorphes. Soient $D$ la plus grande composante connexe non auto-duale de $R$, nous montrons comme dans la proposition 3.2 que si l'équivalence $D_{R/D,R'/D}$ (resp. $D_{R^*/D,R'/D}$) possède au moins deux classes, alors $R' \sim R$ (resp. $R' \sim R^*$).
- Si $k \in \{2,3\}$. Nous montrons comme dans la proposition 5.2 que si $R'/I_0 \sim R/I_0$ (resp. $R'/I_0 \sim R^*/I_0$), alors $R' \sim R$ (resp. $R' \sim R^*$).

Dans la suite $k = 4$, donc les relations $R, R^*$ et $R'$ sont deux à deux ($\le 3$)-hypomorphes, et par suite d'après le lemme 2.9 toute classe $C$ de l'équivalence $D_{R,R'}$ est un intervalle de $R$ et $R'$, sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

La preuve du théorème 7.1 se base sur la proposition suivante :

**Proposition 7.2.** Soient $D$ la plus grande composante connexe non auto-duale de $R$. Si l'équivalence $D_{R/D,R'/D}$ possède au moins deux classes, alors $R' \sim R$.

Notons que comme conséquence de la proposition 7.2 on a :

**Corollaire 7.3.** Soient $D$ la plus grande composante connexe non auto-duale de $R$. Si l'équivalence $D_{R^*/D,R'/D}$ possède au moins deux classes, alors $R' \sim R^*$.

Dans la suite de la preuve de la proposition 7.2, $C$ est une classe de l'équivalence $D_{R,R'}$, la preuve utilise les lemmes suivants :

**Lemme 7.4.** i) Si $C$ est différente de sa composante connexe, alors $R'/C \sim R/C$.

ii) Si $R/C$ est auto-dual, alors $R'/C \sim R/C$.

**Preuve.** i) Si $C$ est différente de sa composante connexe, alors le lemme 2.12 prouve que $R'/C \sim R/C$.

ii) Comme $R/C$ est connexe, alors le lemme 2.3 prouve que $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R/C$ est auto-dual, alors $R'/C \sim R/C \sim R^*/C$.

□

Dans la suite $C$ est une composante connexe non auto-duale de $R$.

**Lemme 7.5.** Si $|E - (C \cup D)| \ge 7$, alors $R/C \sim R'/C$.

**Preuve.** La preuve est analogue à la preuve du lemme 3.6. □

**Lemme 7.6.** Si $|E - D| \ge 13$, alors $R/C \sim R'/C$.
**Preuve.** La preuve est analogue à la preuve du lemme 3.7. □

**Lemme 7.7.** Si $h \ge 4$ et si $|D| \ge 6+h$, alors il existe une partie $A$ de $D$ de cardinal $h$ tel que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes.

**Preuve.** Soit $h \ge 4$. Si pour toute partie $A$ de $D$ de cardinal $h$, $R^*/(D-A) \sim R/(D-A)$, alors $R^*/D$ et $R/D$ sont $(-h)$-hypomorphes et $|D| \ge 6+h$, alors $R^*/D \sim R/D$ (lemme 2.8), ce qui est impossible. D'ou il existe $A \subset D$ telle que $R/(E-A)$ est non auto-dual. D'après le $i$) du lemme 2.22 $R/D$ et $R'/D$ sont $(\le 6)$-hypomorphes, alors $R/(D-A)$ et $R'/(D-A)$ sont aussi $(\le 6)$-hypomorphes, et par suite $R'/(D-A) \sim R/(D-A)$ (lemme 2.1). Il s'ensuit que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. □

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

**Preuve.** Posons $X = E - (C \cup D)$. D'après le lemme 7.5 on peut supposer que $|X| \le 6$, de même d'après le lemme 7.6 on suppose que $|E - D| \le 12$, et par suite $|C| \le 12$. Suivant le cardinal de $X$, on a :

$c_1)$ $|X| = 0$. D'après le lemme 7.7 il existe une partie $A$ de $D$ de cardinal 7 telle que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A)$ sur $R'/(E-A)$.

- Si $f$ est un isomorphisme, comme $R'/(D-A) \sim R/(D-A)$, alors le lemme 2.6 prouve que $R/C \sim R'/C$.

- Si $f$ est un anti-isomorphisme. Comme $C$ est connexe, alors d'après le lemme 2.3 $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R'/C \sim R^*/C$, alors d'après le lemme 2.6 $R'/(D-A) \sim R^*/(D-A)$, ce qui est impossible. Donc $R/C \sim R'/C$.

$c_2)$ $|X| = 1$. D'après le lemme 7.7 il existe une partie $A$ de $D$ de cardinal 6 tel que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A \cup X)$ sur $R'/(E-A \cup X)$.

- Si $f$ est un isomorphisme, comme $R'/(D-A) \sim R/(D-A)$, alors le lemme 2.6 prouve que $R/C \sim R'/C$.

- Si $f$ est un anti-isomorphisme. Comme $C$ est connexe, alors d'après le lemme 2.3 $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R'/C \sim R^*/C$, alors d'après le lemme 2.6 $R'/(D-A) \sim R^*/(D-A)$, ce qui est impossible. Donc $R/C \sim R'/C$.

$c_3)$ $|X| = 2$. D'après le lemme 7.7 il existe une partie $A$ de $D$ de cardinal 5 telle que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A \cup X)$ sur $R'/(E-A \cup X)$. Nous montrons comme dans le cas $c_2$ que $R/C \sim R'/C$.
$c_4) \mid X \mid= 3$. D'après le lemme 7.7 il existe une partie $A$ de $D$ de cardinal 4 telle que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A \cup X)$ sur $R'/(E-A \cup X)$. Nous montrons comme dans le cas $c_2$ que $R/C \sim R'/C$.

$c_5) 4 \leq |X| \leq 6$. D'après le lemme 7.7 il existe une partie $A$ de $D$ de cardinal 4 telle que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soient $B$ une partie de $X$ de cardinal 3 et $f$ un hémimorphisme de $R/(E-A \cup X \cup B)$ sur $R'/(E-A \cup X \cup B)$. Nous montrons comme dans le cas $c_2$ que $R/C \sim R'/C$. $\square$

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

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

Soient $R$ et $R'$ deux relations binaires $(n-6)$-hémimorphes sur une base finie $E$ de cardinal $n$ au moins égal à 23 et $k$ le plus petit cardinal des restrictions non auto-duales de $R$, $I_0$ la base d'une de ces restrictions, et $C$ une classe de l'équivalence $D_{R,R'}$. Le lemme 2.5 prouve que les relations $R$ et $R'$ sont $(\le 6)$-hémimorphes. On a :

-Si $R$ est connexe, alors le lemme 2.2 prouve que $R$ est $(n-6)$-demi-reconstructible.

- Si $k \ge 7$ ou $k = 0$. Dans ce cas $R$ n'admet aucune restriction non auto-duale de cardinal inférieur au égal à 6, et par suite le lemme 2.1 prouve que $R$ est $(n-6)$-demi-reconstructible.

- Si $k \in \{5,6\}$, alors les relations $R, R^*$ et $R'$ sont deux à deux ($\le 4$)-hypomorphes. Soient $D$ la plus grande composante connexe non auto-duale de $R$, nous montrons comme dans la proposition 3.2 que si l'équivalence $D_{R/D,R'/D}$ (resp. $D_{R^*/D,R'/D}$) possède au moins deux classes, alors $R' \sim R$ (resp. $R' \sim R^*$).

- Si $k \in \{2,3\}$, nous montrons comme dans la proposition 5.2 que si $R'/I_0 \sim R/I_0$ (resp. $R'/I_0 \sim R^*/I_0$), alors $R' \sim R$ (resp. $R' \sim R^*$).

Dans la suite $k = 4$, donc les relations $R, R^*$ et $R'$ sont deux à deux ($\le 3$)-hypomorphes, et par suite d'après le lemme 2.9 toute classe $C$ de l'équivalence $D_{R,R'}$ est un intervalle de $R$ et $R'$, sur lequel les restrictions de $R$ et $R'$ sont réflexives ou irréflexives.

La preuve du théorème 8.1 se base sur la proposition suivante :
**Proposition 8.2.** Soient $C$ une classe de l'équivalence $D_{R,R'}$, et $D$ la plus grande composante connexe non auto-duale de $R$. Si l'équivalence $D_{R/D,R'/D}$ possède au moins deux classes, alors $R'/C \sim R/C$.

Notons que comme conséquence de la proposition 8.2 on a :

**Corollaire 8.3.** Soient $D$ la plus grande composante connexe non auto-duale de $R$. Si l'équivalence $D_{R^*/D,R'/D}$ possède au moins deux classes, alors $R' \sim R^*$.

Dans la suite de la preuve de la proposition 8.2, $C$ est une classe de l'équivalence $D_{R,R'}$, la preuve utilise les lemmes suivants :

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

**Preuve.** d'après le lemme 2.12 on suppose que $C$ est une composante connexe de $R$. Soient $H = R/C$, et $a \in C$. Considérons alors les parties $F$ de $E$ contenant $a$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Comme $C$ est une composante connexe de $R$, alors il n'y en a pas d'autre que $C$. Le nombre de parties $F$ de $E$ contenant $a$ telle que $R/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R, H, \{a\}) = 1$). D'après le lemme 2.7, le nombre de parties $F$ de $E$ contenant $a$ telles que $R'/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R', H, \{a\}) = 1$). Il s'ensuit que $R/C \sim R'/C$ ou $R'/C \sim R^*/C$. $\square$

**Lemme 8.5.** Si $|E - C \cup D| \ge 7$, alors $R'/C \sim R/C$.

**Preuve.** La preuve est analogue à la preuve du lemme 3.6. $\square$

**Lemme 8.6.** Si $|E - D| \ge 12$, alors $R/C \sim R'/C$.

**Preuve.** La preuve est analogue à la preuve du lemme 3.7. $\square$

Dans la suite $|E - D| \le 11$, et par suite $|C| \le 11$.

**Lemme 8.7.** i) Si l'équivalence $D_{R/D,R'/D}$ possède une classe fortement connexe de cardinal $\ge 10$, alors $R/C \sim R'/C$.

ii) Si toute classe fortement connexe de l'équivalence $D_{R/D,R'/D}$ est de cardinal $\le 9$, alors $R/D$ et $R'/D$ sont ($\le 6$)-hypomorphes.
**Preuve.** Soit $K$ une classe de l'équivalence $D_{R/D,R'/D}$. Puisque $K$ est différente de $D$, alors il existe $x \in D - K$ tel que $R(x, K) \neq R(K, x)$.

Montrons que $K$ est un tournoi sans diamant.

On va raisonner par l'absurde supposons qu'il existe une arête neutre $\{a, b\}$ de $K$. D'ou $R/\{x, a, b\}$ est un pic, ce qui est impossible, donc $K$ est un tournoi. Comme $K \neq D$, alors le i) du lemme 2.22 prouve que $R/K$ et $R'/K$ sont ($\leq 5$)-hypomorphes, et par suite d'après le lemme 2.10 $R/K$ est un tournoi sans diamant.

i) D'après le lemme 2.12 on suppose que $C$ est une composante connexe de $R$ et par suite $C \cap D = \emptyset$, de même d'après le lemme 8.6 on suppose que $|C| \leq 11$. Soient $H = R/(C \cup K \cup \{x\})$ et $Y = E - H$. On va distinguer les cas suivants :

$$c_1) \text{ Si } |Y| \geq 6.$$

Soient $a$ un point de $C$ et $b, c, d$ trois points de $K$, avec $R/\{b, c, d\}$ est un 3-cycle. Considérons alors les parties $F$ de $E$ contenant $\{x, a, b, c, d\}$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Il n'y en a pas d'autre que $C \cup K \cup \{x\}$, car $C$ et $K \cup \{x\}$ sont les composantes connexes de $H = R/(C \cup K \cup \{x\})$ et $|C| \leq |K \cup \{x\}|$. Le nombre de parties $F$ de $E$ contenant $\{x, a, b, c, d\}$ telles que $R/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R, H, \{x, a, b, c, d\}) = 1$). D'après le lemme 2.7, le nombre de parties $F$ de $E$ contenant $\{x, a, b, c, d\}$ telle que $R'/F$ est hémimorphe à $H$ est donc égal à 1 (c.a.d $n(R', H, \{x, a, b, c, d\}) = 1$). Il s'ensuit que $R/C \sim R'/C$.

$$c_2) \text{ Si } |Y| = 5.$$

Soient $J$ une partie de $K$ de cardinal 1 tel que $R/(K - J)$ est un tournoi sans diamant fortement connexe. Comme $C$ et $\{x\} \cup K - J$ sont les composantes connexes de $R/(E - Y \cup J)$, et $R/(\{x\} \cup K - J) \sim R'/(\{x\} \cup K - J)$, alors $R'/(E - Y \cup J) \sim R/(E - Y \cup J)$, et par suite $R/C \sim R'/C$.

$$c_3) \text{ Si } |Y| = 4.$$

Soient $J$ une partie de $K$ de cardinal 2 tel que $R/(K - J)$ est un tournoi sans diamant fortement connexe. Nous montrons comme dans $c_2$ que $R'/(E - Y \cup J) \sim R/(E - Y \cup J)$, et par suite $R/C \sim R'/C$.

$$c_4) \text{ Si } |Y| \leq 3.$$

Soient $J$ une partie de $K$ tel que $|Y| + |J| = 6$ et $R/(K - J)$ est un tournoi sans diamant fortement connexe. Nous montrons comme dans $c_2$ que $R'/(E - Y \cup J) \sim R/(E - Y \cup J)$, et par suite $R/C \sim R'/C$.

ii) Si $R/K$ est une chaîne, on a triviallement $R/K$ et $R'/K$ sont ($\leq 6$)-hypomorphes. Dans la suite on suppose que $R/K$ est un tournoi sans diamant fortement connexe et $6 \leq |K| \leq 9$. Comme $K \neq D$, alors le i) du
lemme 2.22 prouve que $R/K$ et $R'/K$ sont $(\leq 5)$-hypomorphes. Suivant le cardinal de $K$, on a :

$c_1)$ Si $|K|=6$. Comme $K$ est différente de sa composante, alors le lemme 2.12 prouve que $R'/K \sim R/K$, d'autre part $(R/K$ et $R'/K)$ sont $(\leq 5)$-hypomorphes. Il s'ensuit que $R/K$ et $R'/K$ sont $(\leq 6)$-hypomorphes.

$c_2)$ Si $|K|=7$. Soient $A$ une partie de $K$ de cardinal $6$ et $\{a\} = K-A$. Les relations $R/(E - \{a\})$ et $R'/(E - \{a\})$ sont $(-5)$-hémimorphes et $A$ est différente de sa composante, alors le lemme 2.12 prouve que $R/A \sim R'/A$. Il s'ensuit que $R/K$ et $R'/K$ sont $(\leq 6)$-hypomorphes.

$c_3)$ Si $|K|=8$. Soient $A$ une partie de $K$ de cardinal $6$ et $\{a, b\} = K-A$. Les relations $R/(E - \{a, b\})$ et $R'/(E - \{a, b\})$ sont $(-4)$-hémimorphes. Si $R/A$ est une chaîne, on a $R/A \sim R'/A$. Si $R/A$ est fortement connexe. Soient $H = R/(\{x\} \cup A)$, et $(y, z, t) \in A^3$ avec $R/\{y, z, t\}$ est un 3-cycle. Considérons alors les parties $F$ de $E$ contenant $\{x, y, z, t\}$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Il n'y en a pas d'autre que $\{x\} \cup A$, car $\{x\}$ et $A$ sont les composantes fortement connexes de $H = R/(\{x\} \cup A)$. Le nombre de parties $F$ de $E$ contenant $\{x, y, z, t\}$ telle que $R/F$ est hémimorphe à $H$ est donc égal à $1$ (c.a.d $n(R/(E - \{a, b\}), H, \{x, y, z, t\}) = 1$). D'après le lemme 2.7, le nombre de parties $F$ de $E$ contenant $\{x, y, z, t\}$ telles que $R'/F$ est hémimorphe à $H$ est donc égal à $1$ (c.a.d $n(R'/(E - \{a, b\}), H, \{x, y, z, t\}) = 1$). Il s'ensuit que $R'/A \sim R/A$, et par suite $(R/K$ et $R'/K)$ sont $(\leq 6)$-hypomorphes.

$c_4)$ Si $|K|=9$. Soient $A$ une partie de $K$ de cardinal $6$ et $\{a, b, c\} = K-A$. Les relations $R/(E - \{a, b, c\})$ et $R'/(E - \{a, b, c\})$ sont $(-3)$-hémimorphes. Si $R/A$ est une chaîne, on a $R/A \sim R'/A$. Si $R/A$ est fortement connexe. Soient $H = R/(\{x\} \cup A)$, et $(y, z, t) \in A^3$ avec $R/\{y, z, t\}$ est un 3-cycle. Considérons alors les parties $F$ de $E$ contenant $\{x, y, z\}$ et telles que : $R/F \sim H$ ou $R/F \sim H^*$. Il n'y en a pas d'autre que $\{x\} \cup A$, car $\{x\}$ et $A$ sont les composantes fortement connexes de $H = R/(\{x\} \cup A)$. Le nombre de parties $F$ de $E$ contenant $\{x, y, z\}$ telle que $R/F$ est hémimorphe à $H$ est donc égal à $1$ (c.a.d $n(R/(E - \{a, b, c\}), H, \{x, y, z\}) = 1$). D'après le lemme 2.7, le nombre de parties $F$ de $E$ contenant $\{x, y, z\}$ telles que $R'/F$ est hémimorphe à $H$ est donc égal à $1$ (c.a.d $n(R'/(E - \{a, b, c\}), H, \{x, y, z\}) = 1$). Il s'ensuit que $R'/A \sim R/A$, et par suite $(R/K$ et $R'/K)$ sont $(\leq 6)$-hypomorphes. $\square$

**Lemme 8.8.** Si $h \geq 4$ et $|D| \geq 6+h$ et si $(R/D$ et $R'/D)$ sont $(\leq 6)$-hypomorphes, alors il existe une partie $A$ de $D$ de cardinal $h$ tel que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes.
**Preuve.** La preuve est analogue à la preuve du lemme 7.7. □

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

**Preuve.** Posons $X = E - (C \cup D)$. D'après le lemme 8.5 on peut supposer que $|X| \le 5$, de même d'après le lemme 8.6 on suppose que $|E - D| \le 11$, et par suite $|C| \le 11$, aussi d'après le lemme 8.7 on suppose que $(R/D \text{ et } R'/D)$ sont $(\le 6)$-hypomorphes. Suivant le cardinal de $X$, on a :

$c_1)$ $|X| = 0$. D'après le lemme 8.8 il existe une partie $A$ de $D$ de cardinal 6 telle que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A)$ sur $R'/(E-A)$.

- Si $f$ est un isomorphisme, comme $R'/(D-A) \sim R/(D-A)$, alors le lemme 2.6 prouve que $R/C \sim R'/C$.

- Si $f$ est un anti-isomorphisme. D'après le lemme 8.4 $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R'/C \sim R^*/C$, alors d'après le lemme 2.6 $R'/(D-A) \sim R^*/(D-A)$, ce qui est impossible. Donc $R/C \sim R'/C$.

$c_2)$ $|X| = 1$. D'après le lemme 8.8 il existe une partie $A$ de $D$ de cardinal 5 telle que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A \cup X)$ sur $R'/(E-A \cup X)$.

- Si $f$ est un isomorphisme, comme $R'/(D-A) \sim R/(D-A)$, alors le lemme 2.6 prouve que $R/C \sim R'/C$.

- Si $f$ est un anti-isomorphisme. D'après le lemme 8.4 $R'/C \sim R/C$ ou $R'/C \sim R^*/C$. Si $R'/C \sim R^*/C$, alors d'après le lemme 2.6 $R'/(D-A) \sim R^*/(D-A)$, ce qui est impossible. Donc $R/C \sim R'/C$.

$c_3)$ $|X| = 2$. D'après le lemme 8.8 il existe une partie $A$ de $D$ de cardinal 4 telle que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soit $f$ un hémimorphisme de $R/(E-A \cup X)$ sur $R'/(E-A \cup X)$. Nous montrons comme dans $c_2$ que $R/C \sim R'/C$.

$c_4)$ $3 \le |X| \le 5$. D'après le lemme 8.8 il existe une partie $A$ de $D$ de cardinal 4 telle que $R/(D-A)$ et $R'/(D-A)$ sont isomorphes mais non anti-isomorphes. Soient $B$ une partie de $X$ de cardinal 2 et $f$ un hémimorphisme de $R/(E-A \cup X \cup B)$ sur $R'/(E-A \cup X \cup B)$. Nous montrons comme dans $c_2$ que $R/C \sim R'/C$. □
References

[1] Y. BOUDABBOUS et J. DAMMAK : Sur la (-k)-demi-recon-
structibilité 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 : Caractérisation des relations binaires finies d-demi-reconstructibles. Proyecciones, Volume 22, N 1, (2003).

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

[5] J. DAMMAK : La (-5)-demi-reconstructibilité des relations binaires connexes finies. Proyecciones, Volume 22, N 3, (2003).

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

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

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

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

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

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

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