L'Indeformabilite des Relations et Multirelations Binaires

Kous considBrons ici des multirelations binaires, M = (R l , . . . , R , , . . .) c’est Q dire telles que le maximum des aritBs mi des relations R, est &gal b 2, et nous Btablissons le rQsultat suivant: I1 existe un nombre k tel que deux multirelations binaires M et .M’ de m6me base finie E, sont isomorphes si pour toute partie F de E , d’au plus k BlBments, les restrictions de iK et de M’ Q F sont isomorphes. Dans le cas particulier oh V et M sont des relations binaires, on obtient 6 comme plus petite valeur de k ([7] et [S]). Ce r6sultat repond partiellement B la conjecture de FRA~SS$, 6noncBe en [2]: “Existe-t-il pour tout entier m, un entier k(m) tel que: Si R et R’ sont deux relations m-aires de m6me base E de cardinal k(m), si pour toute partie stricte F de E, les restrictions R 1 F et R’ 1 F sont isomorphes, alors R et R’ elles-meme sont isomorphes.” Cette conjecture s’apparente la conjecture d’ULAM [12] sur la reconstruction des graphes par leurs restrictions strictes maxima1es.l) Voir sur cette question GREENWELL et HEMMINGER [6]. En rkponse Q la conjecture de FRAISS~, POUZET [lo] a d6montr6 qu’un tel entier k n’existait pas pour m 2 3. Son r6sultat &ant encore valable pour toute multirelation dont l’une des relations R , est d’arit6 2 3, POUZET pose alors la question pour les multirelations binaires. Nous y r6pondons ici. Comme exemples importants de relations et multirelations d’arit6 quelconque, reconstructibles par leurs restrictions, citons les enchainables, les monomorphes (FRASNAY [5]), les presque-enchainables, les presque-monomorphes (FRAISSB et POUZET [3], [4]), toutes ces relations entrant dans une classe plus g6n6rale, celle des trks belles multirelations (POUZET [9]). La preuve s’6tablit comme suit : nous commenqons par definir une relation d’equivalence T attachBe Q ( M , M ) ; cette relation T nous amhne Q distinguer deux cas, suivant que T prend la valeur + partout ou non. Le premier. cas est trait6 dans la partie I, uniquement lorsque M et M‘ sont rkduites B des relations binaires. Puis B I’aide du ThBorhme 1 Btabli dans cette premiere partie, on achhve en I1 la preuve pour les multirelations binaires, d’arit6 quelconque. Une suggestion de M. JEAN est B l’origine d’une simplification de la preuve du Theoreme 1 par l’emploi des relations ddformables D,. Defini t ions ([l]). Soit R et R‘ des relations. On appelle isomorphisme local de R vers R‘ tout isomorphisme d’une restriction de R sur une restriction de R‘. Un automorphisme local de R est un isomorphisme local de R vers R. On appelle borne de R toute relation finie A telle que A n’est isomorphe Q aucune restriction de R mais toute restriction stricte de A est isomorphe B une restriction de R . Nous utiliserons Bgalement la terminologie suivante de FRASNAY: R et R‘ &ant de m6me arit6 et de mhme base E , on dira que R et R‘ sont semblables si pour toute partie stricte F de E les restrictions R I F et R‘ 1 F sont isomorphes.