Caracterisation des classes de (≤ 3)-hypomorphie a l’aide d’interdits

Authors

  • Jean Guillaume Hagendorf Université de Paris.
  • Gerard Lopez Institut de Mathématiques de Luminy.
  • Claire Rauzy Université d’Aix-Marseille.

DOI:

https://doi.org/10.4067/S0716-09172013000200001

Keywords:

Relation, Binaire, Graphe, Reconstruction, Différence, Hypomorphie, Pavage, Interdit, Drapeau.

Abstract

G. Lopez a démontréla(<6)-reconstructibilitédes relationsbi-naires finies (1972) (voir [1] et [2]) résolvant ainsi un probleme de Roland Fraissé (voir[3]). Sa preuve repose sur la notion de classe de difference. Depuis, la notion de classe de difference est un outil ma-jeur dans bien des travaux en reconstruction et demi-reconstruction notammenten[4], [5] et [6]etpermet dedefinir la notion de classe d'hypomorphie. La caracterisation des classes de (<k)-hypomorphie finies, pour k>6, a été obtenue par Hagendorf et Lopez en 1994 (voir [4]). La caracterisation des classes de (<4)-hypomorphie finies a ete obtenue par G. Lopez et C. Rauzy (1992) (voir [6]). Ensuite, celle des classes de (<5)-hypomorphie finies a etetrouvee par Y. Boudabbous (2000) (voir [7]). Dans cet article nous obtenons une caracterisation, par interdits, des classes de (<3)-hypomorphie finies, puis infinies dans un prochain article. Ces deux articles sont resumes en [8]. La reconstruction infinie a ete en particulier etudiee en [4], [9] et [11]. D'autres utilisations des classes de difference ou des liens avec elles se trouvent par exemple dans [12] a [21].

References

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

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

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

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

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

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

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

[8] J. G. Hagendorf, G. Lopez et C. Rauzy, Pavages d’une relation binaire. C. R. Acad. Sci. Paris, t. 321 S´erie I, pp. 1281-1286, (1995).

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

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

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

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

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

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

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

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

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

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

[19] Jamel Dammak, Le seuil de reconstructibilité par le haut modulo la dualité des relations binaires finies, Proyecciones Vol. 22, No 3, pp. 209-236, December 2003. Universidad Católica del Norte Antofagasta – Chile.

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

[21] N. El Amri, La (<k)-demi-reconstructibilit´e des graphes pour 7<k<12, to appear in Ars Combinatoria.

How to Cite

[1]
J. G. Hagendorf, G. Lopez, and C. Rauzy, “Caracterisation des classes de (≤ 3)-hypomorphie a l’aide d’interdits”, Proyecciones (Antofagasta, On line), vol. 32, no. 2, pp. 91-105, 1.

Issue

Section

Artículos