Contenu du sommaire : Mathématiques discrètes : théories et usages. Numéro en hommage à Bruno Leclerc

This paper is in no way original. Its aim is purely pedagogical. We show how to construct continuous cumulative distribution functions without density function and discontinuous ones with a set of discontinuities that are dense over their interval of definition.

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.

Bruno Leclerc's mathematical study covers an important number of different fields. Among them, one finds the lattices associated with finite Coxeter groups. The main contribution of B. Leclerc on this subject consists in the (negative) answer to a question raised ten years earlier by Björner: are finite Coxeter lattices symmetric chain partitionable? His proof is based on a sharp observation of the central rank-sets of a particular Coxeter lattice traditionally denoted byH3. This text proposes a presentation of this proof, together with the recollection of a number of strong properties satisfied by Coxeter lattices. All developments in this paper are limited to the finite case.

The bijection of Benzécri and Johnson sets up a one-one correspondence between hierarchical clusterings and ultrametric dissimilarities [Johnson 1967, Benzécri 1973]. New clustering structures, which were introduced during the 1980's, include overlapping clusters and extend this bijection. In this text, we are concerned with a general framework that enablesus to represent and compare several previously proposed extensions of the bijection of Benzécri and Johnson. We consider, more particularly, the extensions of this bijection that exist between certain general types of clustering systems that include overlapping clusters, on one hand, and the set of all the dissimilarities, on the other hand.

In a general framework where the concepts of subdominant/updominated play a crucial role, we give a vast overview of approximations with the supremum norm for many structures of classi-fication: (partial or nonpartial) ultrametrics,k-ultrametrics, convex and isotonic regressions. For tree semi-distances/dissimilarities and Robinsonian dissimilarities, we show how the general approach leads us to algorithms with a constant factor.

Given several X-trees or unrooted phylogenetic trees on the same set of taxa X, we look for a largest subset Y⊂X such that al l the partial trees reduced by Y are topologically identical. This common subtree is called a MAST for Maximum Agreement SubTree. The problem has polynomial complexity when there are only two trees but generally it is NP-hard for more than two. We introduce a polynomial approximation algorithm for the multiple case, which is easy to implement, very efficient and which produces a maximal common subtree. It begins with the computation of an upper bound for its size and designates elements in X that cannot belong to a common subtree of a given size. Simulations on random and real data have shown that this heuristic often provides an optimal solution as soon as the number of trees is larger than 5. Then, we develop a statistical study to evaluate the average size of a MAST corresponding to independent trees. The computed distribution allows to estimate the critical size of a MAST to reveal some congruence between trees.

Let C be a set of classes of elements on a set S. We usually consider that it will contain S and that it will be stable by intersection, i.e. it's a closure system. This article will look at the possibilities of fitting a system of classes to a specific “overhanging” relation (and so, to a specific implicational system). For any natural number p between 1 and   k, we associate to any profile of closure systems the consensus mapping created by the pairs of subsets of S over hanged in at least p families of the profile. It will be shown that this consensus mapping allows us to create a specific closure system when we consider closure systems that are nested, hierarchical, distributive, trees of subsets, topologies or even convex geometries.

This article surveys seven directions of consensus theories: Arrowian results, federation consensus rules, metric consensus rules, tournament solutions, restricted domains, abstract consensus theories, algorithmic and complexity issues. This survey is oriented in the sense that it is mainly – but not exclusively – concentrated on the most significant results obtained, sometimes with other researchers, by a team of French researchers who are or were full or associate members of the Centre d'analyse et de mathématique sociale (CAMS).