no. 7-8
Logique/Combinatoire
Ordres indécomposables critiques

Présenté par : Jean-Yves Girard

Zaguia, Imed1
1 Department of Mathematics & Statistics, Sultan Qaboos University, P.O. Box 36, Al-Khoud 123 Muscat, Sultanate of Oman
Comptes Rendus. Mathématique, Tome 346 (2008) no. 7-8, pp. 369-374.

Un ordre indécomposable sur au moins quatre sommets est critique si toutes ses extensions immédiates sont décomposables. Nous montrons qu'il y a exactement 12 ordres indecomposables critiques finis et de hauteur au plus trois. Nous donnons une liste infinie d'ordres indecomposbales critiques ayant une hauteur, largeur et dimension arbitrairement grandes. Nous montrons aussi qu'un ordre d'intervalles indécomposable, sur au moins quatre sommets et éventuellement une infinité, est critique si et seulement si il est de largeur deux.

An order on at least four vertices is critically prime if it is prime and has no prime upper cover. We prove that there are only twelve finite prime orders of height at most three which do not have a prime upper cover. Moreover, we provide examples of prime orders of arbitrarily width, height and dimension which do not have a prime upper cover. We also prove that a prime interval order, on at least four vertices, but possibly infinitely many, has no prime upper cover if and only if it has width two.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2008.02.004
Zaguia, Imed 1

1 Department of Mathematics & Statistics, Sultan Qaboos University, P.O. Box 36, Al-Khoud 123 Muscat, Sultanate of Oman 
@article{CRMATH_2008__346_7-8_369_0,
     author = {Zaguia, Imed},
     title = {Ordres ind\'ecomposables critiques},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {369--374},
     publisher = {Elsevier},
     volume = {346},
     number = {7-8},
     year = {2008},
     doi = {10.1016/j.crma.2008.02.004},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2008.02.004/}
}
TY  - JOUR
AU  - Zaguia, Imed
TI  - Ordres indécomposables critiques
JO  - Comptes Rendus. Mathématique
PY  - 2008
SP  - 369
EP  - 374
VL  - 346
IS  - 7-8
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2008.02.004/
DO  - 10.1016/j.crma.2008.02.004
LA  - fr
ID  - CRMATH_2008__346_7-8_369_0
ER  - 
%0 Journal Article
%A Zaguia, Imed
%T Ordres indécomposables critiques
%J Comptes Rendus. Mathématique
%D 2008
%P 369-374
%V 346
%N 7-8
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2008.02.004/
%R 10.1016/j.crma.2008.02.004
%G fr
%F CRMATH_2008__346_7-8_369_0
Zaguia, Imed. Ordres indécomposables critiques. Comptes Rendus. Mathématique, Tome 346 (2008) no. 7-8, pp. 369-374. doi : 10.1016/j.crma.2008.02.004. http://www.numdam.org/articles/10.1016/j.crma.2008.02.004/

[1] Brualdi, R.A.; Jung, H.C.; Trotter, W.T. On the poset of all posets on a n elements set, Discrete Appl. Math., Volume 50 (1994), pp. 11-123

[2] Dean, R.A.; Keller, G. Natural partial orders, Canad. J. Math., Volume 20 (1968), pp. 535-554

[3] J. Demetrovics, M. Miyakawa, I.G. Rosenberg, D.A. Simovici, I. Stojmenović, Intersections of isotone clones on a finite set, in: Proc. 20th Internat. Symp. Multiple valued Logic, Charlotte, NC, 1990, pp. 248–253

[4] Fishburn, P.C. Interval Orders and Interval Graphs, John Willey & Sons, 1985

[5] Fraïssé, R. L'intervalle en théorie des relations, ses généralisations, filtre intervallaire et clôture d'une relation, Annals of Discrete Mathematics, Volume 23 (1984), pp. 343-358

[6] M. Pouzet, I. Rival, Structural arithmetic of the extension lattice of an order, Technical report TR-91-11, University of Ottawa

[7] Pouzet, M.; Reuter, K.; Rival, I.; Zaguia, N. A generalized permutahedron, Algebra Universalis, Volume 34 (1995), pp. 496-509

[8] Rival, I.; Zaguia, N. Perpendicular orders, Discrete Math., Volume 137 (1995), pp. 303-313

[9] I. Zaguia, Ordres perpendiculaires, Thèse de Doctorat, Université Claude Bernard, Lyon 1, Nr. 215-97, 1997

Cité par Sources :