Navigation – Plan du site

Des chaînes et des antichaînes dans les ensembles ordonnés finis

About chains and antichains in finite posets
Nathalie Caspard
p. 19-40

Résumés

L’un des nombreux domaines dans lesquels Bruno Leclerc a travaillé et publié est celui des ensembles ordonnés. Plus précisément, il s’est fortement intéressé à des propriétés d’ensembles ordonnés relatives à des sous-structures bien particulières, les chaînes et les antichaînes. Beaucoup de problèmes de tri, de recherche et d’ordonnancement que l’on rencontre par exemple en informatique et en recherche opérationnelle, sont liés à la détermi-nation du cardinal maximum d’une antichaîne d’un ensemble ordonné, c’est-à-dire de sa largeur.
Cet article se repenche sur ces centres d’intérêts de l’oeuvre de Bruno, en rappelant d’une part certains grands théorèmes classiques relatifs à ces notions et, d’autre part, des résultats de Bruno sur ces sujets. Nos développements se restreignent au cas fini.

About chains and antichains in finite posets

One of the numerous fields investigated by Bruno Leclerc is the theory of finite posets. More precisely, he was very interested in properties of posets relative to some particular substructures, the so-called chains and antichains. Many problems in sorting, search and scheduling, that one can find for instance in computer science and operational research, are connected with the computing of the maximum cardinality of an antichain of a poset, that is, of its width.
This paper looks into those centers of interest of Bruno’s work, recalling on one hand some strong and classical theorems relating to these notions and, on the other hand, some results by Bruno on these subjects. Our developments only concern the finite case.

Haut de page

Pour citer cet article

Référence électronique

Nathalie Caspard, « Des chaînes et des antichaînes dans les ensembles ordonnés finis », Mathématiques et sciences humaines [En ligne], 190 | Eté 2010, mis en ligne le 16 octobre 2010, consulté le 01 mai 2017. URL : http://msh.revues.org/11716

Haut de page

Auteur

Nathalie Caspard

Laboratoire d’algorithmique, complexité et logique, Université Paris-Est Créteil, 60 avenue du Général de Gaulle 94010 Créteil, caspard@univ-paris12.fr

Articles du même auteur

Haut de page

Droits d’auteur

© École des hautes études en sciences sociales

Haut de page