Caracterisation des classes de (≤ 3)-hypomorphie a l’aide d’interdits
DOI:
https://doi.org/10.4067/S0716-09172013000200001Keywords:
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.
[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
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.