Boyan Kolev

Carlyna Bondiombouy

Patrick Valduriez

Ricardo Jiménez-Peris

Raquel Pau

José Pereira

Demonstration of the CloudMdsQL Multistore System

The blooming of different cloud data management infrastructures, specialized for different kinds of data and tasks, has led to a wide diversification of DBMS interfaces and the loss of a common programming paradigm. This has turned multistore systems to a major topic in the nowadays cloud landscape.

In this demonstration, we present Cloud multidatastore query language (CloudMdsQL) [START_REF] Kolev | Cloudmdsql: querying heterogeneous cloud data stores with a common language[END_REF], a functional SQL-like language, designed for querying multiple heterogeneous databases (e.g. relational and NoSQL) within a single query containing nested subqueries. Each subquery addresses directly a particular data store and may contain embedded invocations to the data store's native query interface. Thus, the major innovation is that a CloudMdsQL query can exploit the full power of local data stores, by simply allowing some local data store native queries to be called as functions, and at the same time be optimized based on a simple cost model, e.g. by pushing down select predicates or using bind join.

One of the major challenges in front of the CloudMdsQL language/engine is to allow joins across heterogeneous data stores and to be able to perform them in an efficient way. For this reason, we pay special attention to the use of bind joins and we apply this technique even when native queries are used.

This demonstration concentrates on a CloudMdsQL use case scenario: a social network analysis tool for marketing companies. The use case aims at finding the communities in a social network, for a specific set of topics, with their top influencers. Marketing companies are interested in discovering the people they need to convince about the quality of a specific brand. The dataset of this use case is a sample of Twitter, but it allows working with other social networks like Facebook or blogs. The application runs a Twitter listener of a set of topics in real-time; it modifies the database for each tweet it receives. The schema of this application contains a generic entity called Document to store text-items (tweets, messages, etc.), which can appear copies or refer- ences. An Entity (person or company) is an author of a document or a mention of a social-network account. The people interactions in social networks with copies, references or mentions, can be understood as a set of graph of influences. In other words, we can infer who influences who and about what. These Influences and the Communities are incrementally computed when a new tweet comes to the application and thus, these concepts are part of the application schema.

The specification of the main query the application uses is as follows: given a set of keywords k1, k2, k3, find the 10 biggest communities and, for each community, find the 20 most influencers. For each of these influencers, the system must return the number of influenced entities inside the community, the influencer's id, name and account creation date and the last published document.

In order to implement this use case, we use a graph database (Sparksee) to store the graph of Influences and compute the Communities; a relational database (MonetDB) for all the basic information about Entities and Documents (only metadata); a document database (MongoDB) to store the Document contents; and a key-value data store (HBase) to index communities per keyword. Following the execution plan for the CloudMdSQL query, the query engine first invokes an HBase query to retrieve the communities preliminarily computed for a specific keyword; then, for each community, runs a Sparksee query using the Sparksee Python API to find the top 20 influencers, the number of influenced entities inside the community, and the maximum influence propagation depth. Finally, the basic information of each influencer (id, name, account creation date) and the last published document is retrieved by running queries to Mon-etDB and MongoDB.

For the execution plan, the query optimization plays an important role to assign the bind join method to all the join operations. The reason is that the selected communities relevant to the keywords k1, k2 and k3 are always a few, and thus the Sparksee query is evaluated only for a few communities, which significantly reduces the number of executions of expensive graph computations.

  (c) 2016, Copyright is with the authors. Published in the Proceedings of the BDA 2016 Conference (15-18 November, 2016, Poitiers, France). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. (c) 2016, Droits restant aux auteurs. Publié dans les actes de la conférence BDA 2016 (15 au 18 Novembre 2016, Poitiers, France). Redistribution de cet article autorisée selon les termes de la licence Creative Commons CCby-nc-nd 4.0. BDA 2016, 15 au 18 Novembre, Poitiers, France.


Bernard Monjardet
email: bernard.monjardet@univ-paris1.fr

Acyclic domains of linear orders : a survey

Keywords: acyclic set, alternating scheme, distributive lattice, effet Condorcet, maximal chain, permutoèdre lattice, weak Bruhat order, value restriction. JEL classification number: D71 AMS MSC classification number 05, 06D, 91B

Among the many significant contributions that Fishburn made to social choice theory some have focused on what he has called «acyclic sets», i.e. the sets of linear orders where majority rule applies without the "Condorcet effect" (majority relation never has cycles). The search for large domains of this type is a fascinating topic. I review the works in this field and in particular consider a recent one that allows to show the connections between some of them that have been unrelated up to now.

Notations and preliminaries

A = {1,2...i,j,k…n} is a finite set of n elements that I will generally call alternatives (but which could also be called issues, decisions, outcomes, candidates, objects, etc). The elements of A will be also denoted by letters like x,y,z etc. A subset of cardinality p of A will be called a p-set.

A 2 (respectively, A 3 ) denotes the set of all ordered pairs (x,y) (respectively, ordered triples (x,y,z) written for convenience as xyz) of A. When the elements of A are denoted by the n first integers, P 2 (n) denotes the set of the n(n-1)/2 ordered pairs (i<j).

A binary relation on A is a subset R of A 2 and we write xRy or (x,y) ∈ R when x is in the relation R with y. For l integer ≥ 2, a cycle of length l of R, called also a l-cycle, is a subset {x 1 ,x 2 ,....x l } of A such that x 1 Rx 2 .......x l R x 1 . For B ⊆ A, the restriction of a relation R to B is denoted by R /B .

A strict linear order on A is an irreflexive, transitive and complete (x ≠ y implies xRy or yRx) binary relation on A. Henceforth, we will omit the qualifier strict and sometimes, when there is no ambiguity, the qualifier linear. Linear orders on A are in a one-to-one correspondence with permutations of A. So if L is a linear order on A one can write it as a permutation x 1 ...x k x k+1 ...x n . Then one says that x k has rank k and is covered by x k+1 and that x k and x k+1 are consecutive in L. I denote by τ k the transposition which exchange x k and x k+1 in L: τ k (L) = x 1 ...x k+1 x k ...x n .

The set of all linear orders on A is denoted by L or L n if |A | = n. D denotes any subset of L. In all of this paper the preferences of what I will call a voter (but what could also be called agent, person, individual, criterion, etc) on a set A of alternatives is represented by a linear order L = x 1 x 2 ...x n where x 1 is assumed to be the last preferred alternative, x 2 the next-to-last, etc. So, yLx or (y,x) ∈ L means that alternative x is preferred to alternative y in the linear order L.

Remark

One could consider that the notation yLx should mean that y is preferred to x. But we are working in this paper with posets and, unfortunately, this choice would be not in accordance with the usual convention of poset theory. Indeed in this theory the symbol used for a (strict) order is generally < what means that yLx is interpreted as y<x, and so as y is less than x. The reader must keep in mind a consequence of our choice: in a linear order of preference L = x 1 x 2 ...x n , the worst alternative x 1 (respectively, the best alternative x n ) has rank 1 (respectively, n).

The problem of getting a collective preference from various voters' preferences was tackled by Borda and Condorcet at the end of 18 th century. Condorcet criticized Borda's rank method and proposed the use of the majority rule on the pairs of alternatives. Before we recall the definition of this rule, I introduce some notations. I consider v voters, which express their preferences on the alternatives by linear orders taken in a set D of linear orders (D ⊆ L). The state of their preferences is given by a v-profile # = (L 1 ,..L q ,..,L v ) where L q is the linear order of D representing the preference of voter q. D v denotes the set of all these v-profiles. For a subset B of alternatives, # /B = (L 1 /B ,..L q /B ,..,L v /B ) denotes the profile of voters' preferences restricted to B.

For a v-profile # = (L 1 ,..L q ,..,L v ) and two alternatives x and y, one denotes by v # (y,x) the number of voters preferring x to y in this profile.

In his «Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix» (1785) Condorcet recommended the rule now called Condorcet's majority rule 1 . This rule associates with a profile # the collective preference defined as the strict (simple) majority relation 2 R SMAJ (#):

yR SMAJ (#)x if v # (y,x) > v/2 i.e., alternative x is collectively preferred to alternative y if it is preferred by a (strict) majority of voters. It is clear that this majority relation is asymmetric i.e., has no 2-cycles. But Condorcet discovered that majority relations can have cycles of length l ≥ 3 : x 1 R SMAJ x 2 .......x l R SMAJ x 1 . This fact that was rediscovered for instance by Dodgson, Black and Arrow has been called the «Condorcet effect» by [START_REF] Gth | Les théories de l'intérêt général et le problème logique de l'agrégation[END_REF] and is also known as the «voting paradox» 3 . I prefer the first appellation, which emphasizes the fact that this occurrence of cycles is not really a paradox (see [START_REF] Gth | Les théories de l'intérêt général et le problème logique de l'agrégation[END_REF]or Monjardet 2006).

The simplest cases of the Condorcet effect occur when A = {i,j,k} and v = 3, with the profiles (ijk, jki, kij) and (jik, ikj, kji)) since then majority relations are the 3-cycles iR SMAJ jR SMAJ kR SMAJ i and jR SMAJ iR SMAJ kR SMAJ j. I say that such profiles are 3-cyclic profiles. More generally, for an integer l ≥ 3, I say that a profile like # = (x 1 x 2 x 3 ...x l ; x 2 x 3 ...x l x 1 ; .....; x l x 1 x 2 ....x l-1 ) is a lcyclic profile. The strict majority relation associated with such a profile is a l-cycle. Observe that arbitrary profiles can contain the same linear order several times, but that l-cyclic profiles are subsets of L.

A subset D of the set L of all linear orders on A is an acyclic domain (of linear orders) if for every integer v and every profile # = (L 1 ,L 2 ,..,L v ) ∈ D v , R SMAJ (#) has no cycles 4 . 1 Condorcet uses other terms like «plurality».

2 The (simple) majority relation is the relation defined by yR MAJ (#)x if v # (y,x) ≥ v/2. Observe that since # is a profile of linear orders one has for x≠y (y,x) ∈ R MAJ (#) if and only if (x,y) ∉ R SMAJ (#). 3 Condorcet speaks of the «contradictory case». Dodgson and Black speak of «cyclical majorities» and I do not know who used the term paradox the first time (it appears in Arrow's 1951 book).

4

Acyclic domains have been also called consistent profiles [START_REF] Ward | Majority voting and the alternative forms of public enterprise[END_REF], valuedrestricted domains [START_REF] Kim | Introduction to mathematical consensus theory[END_REF], transitive simple majority domains or Several classical characterizations of acyclic domains are given in the theorem below. I need some definitions. For l integer greater than 2, I say that a set D of linear orders contains a l-cyclic profile if there exists a subset B = {x 1 ,x 2 ,....x l } of A and a subset {L 1 ,…L q ,…,L l } of l linear orders in D such that the profile # /B = (L 1 /B ,..L q /B …L l/B ) is a l-cyclic profile. When a set of three alternatives is linearly ordered as i<j<k, then 5 i has rank 1, j has rank 2 and k has rank 3. I say that a set D of linear orders is valuerestricted if for every subset {i,j,k} of A, there exists an alternative which either never has rank 1 or never has rank 2 or never has rank 3 in the set D /{i,j,k} . Finally in condition 7) of the theorem I use the majority relation defined in footnote 2.

Theorem

Let D be a subset of the set L of all linear orders on a set A. The following conditions are equivalent: 1) D is acyclic (i.e., for every integer v and every profile # ∈ D v , R SMAJ (#) has no cycles), 2) For every integer v and every profile # ∈ D v , R SMAJ (#) is a (strict) partial order, 3) For every odd integer v and every profile # ∈ D v , R SMAJ (#) is a linear order, 4) For every integer l ≥ 3, D does not contain l-cyclic profiles, 5) D does not contain 3-cyclic profiles, 6) D is value-restricted, 7) For every integer v, every profile # ∈ D v and every B ⊆ A, {a ∈ B: for every b ∈ B\{a}, bR MAJ (#)a} ≠ Ø}.

Condition 2) means that when voters' preferences belong to an acyclic domain, the collective preference that is given by majority rule is transitive (and asymmetric) which in particular implies that it can be extended into a linear order. For a given profile I say that an alternative is a Condorcet winner if it is preferred to all other alternatives in the majority relation (see consistent sets [START_REF] Abello | How large are transitive simple majority domains?[END_REF], «états d'opinion fortement condorcéen» (Chameni-Nembua 1989), acyclic sets [START_REF] Fishburn | Notes on Craven's conjecture[END_REF][START_REF] Fishburn | Acyclic sets of linear orders[END_REF], majorityconsistent sets [START_REF] Craven | Majority consistent preference orderings[END_REF] or Condorcet domains (Monjardet 2006).

5 See the Remark on the ranks of linearly ordered alternatives in the previous page.

footnote 2) associated with this profile. Condition 7) means that for every profile and every subset of candidates there exists at least a Condorcet winner. Condition 5) means that D is acyclic if and only if for every subset C = {L 1 ,L 2 ,L 3 } of three different linear orders of D and every subset {i,j,k} of three different alternatives, C is not a 3-cyclic profile on {i,j,k}. It was introduced by [START_REF] Ward | Majority voting and the alternative forms of public enterprise[END_REF] which proved the equivalence of conditions 1), 4) and 5) of the above theorem. He called it the condition of Latin-squarelessness since a 3-cyclic profile forms a Latin square when it is disposed in a 3× 3 array. Condition 6) of value-restriction was introduced by Sen (1966) 6 .

In what follows I will use Fishburn's formulation of the condition of value restriction. One assumes that the n alternatives of A are ranked in an arbitrary linear order, which in fact will be the natural order 1<2<...i<j<k<….n. There are two 3-cyclic profiles on a 3-element set {i,j,k}, namely {ijk, jki, kij} and {jik, ikj, kji}. In each of these 3-cyclic profiles each element h of {i,j,k} appears at rank 1, 2 and 3 in one of the three linear orders of the profile. In order to avoid a 3-cyclic profile on {i,j,k}, it suffices to assume that one of the linear orders in {ijk, jki, kij} and one in {jik, ikj, kji} never occurs. There are 3×3 = 9 different ways to do that. But each of these ways comes back to assume that an element h of {i,j,k} never appears at rank 1, 2 or 3 in a linear order on{i,j,k}. For instance, to exclude ijk and jik comes back to assume that k never has rank 3 in the restrictions to {i,j,k} of the linear orders of D. I will write this condition kN {i,j,k} 3. More generally for h in {i,j,k} and r in {1,2,3}, the Never Condition hN {i,j,k} r means that h never has rank r in the restrictions to {i,j,k} of the linear orders of D. With these definitions a set of linear orders is an acyclic domain if and only if for every ordered triple i<j<k there exists h ∈ {i,j,k} and r ∈ {1,2,3} such that hN {i,j,k} r. Since 1<2...<n contains n(n-1)(n-2)/6 ordered triples and that for each ordered triple i<j<k, one can choose one of the nine possible Never Condition hN {i,j,k} r, one sees that there are many ways to get acyclic domains 7 . I will say that an acyclic domain satisfies the Never Condition hNr if for every ordered triple i<j<k, the same Never Condition hN {i,j,k} r is satisfied. For instance D satisfies jN1 if for every ordered triple i<j<k, j never has rank 1 (i.e. is never last) in the restrictions to {i,j,k} of the orders of D. I will say that an acyclic domain satisfies the Never Condition ijkNr if for every ordered triple i<j<k, one has either iNr or jNr or kNr (one of the three alternatives never has rank r).

An obvious but useful observation is that the Never Conditions are «hereditary». Now the interesting problem is: how large can domains of linear orders where Condorcet's majority rule works well be? Or more concisely, how large can acyclic domains be? Observe that the problem becomes a purely combinatorial problem: to construct large sets of linear orders satisfying the above restriction conditions. I introduce some definitions and notations. An acyclic domain D is maximal if for any linear order L not in D, D∪{L} is no longer an acyclic domain. Moreover a (maximal) acyclic domain contained in L n is maximum if it has the maximum size, denoted by f(n), among all acyclic domains in L n . An acyclic domain D ⊂ L n is connected if there always exists a path 8 of L n included in D between any two linear orders in D ; such a connected domain is of diameter d if the maximum length of a shortest path between two linear orders of D is d.

One can observe that the diameter of L n is n(n-1)/2. I denote by g(n) the linear order satisfying jN2 for every ordered triple i<j<k (and that this condition is satisfied by only four orders for n = 4).

8 A path in L n is a sequence of different linear orders L 1 …L k L k+1 …L s such that for k = 1,2…s-1, L k and L k+1 differ only by a transposition (of two consecutive elements). In fact it is a path in the «permutoèdre graph» defined in section 3.

maximum size of a connected acyclic domain of diameter n(n-1)/2 contained in L n . It has been shown that g(n) = f(n) for n ≤ 6, but it seems to be less than f(n) for n ≥ 16.

The problem of determining f(n) or g(n) for all n is daunting. Up to now these numbers are known only for n ≤ 6 (where they are equal). Then one has to search good lower or upper bounds for them instead. Lower bounds are obtained by producing (maximal) acyclic domains. The first maximal connected acyclic domain obtained by Black contains only 2 n-1 linear orders (compare to the n! possible linear orders). For a long time the other maximal acyclic domains found were also connected and contained no more orders. I will present some of them in section 2. This perhaps raised up the conjecture f(n) = 2 n-1 ; but this was unfortunate since it can be disproved for n = 4 (see footnote 13 and Figure 4). Breakthroughs came first in the eighties with Abello and Chameni-Nembua's works which I will present in sections 3 and 4. They use the order on the «permutoèdre» and do not explicitly use Never Conditions. For instance for n = 6, maximal connected acyclic domains with 44 or 45 linear orders were obtained (instead of 32 = 2 5 ). A clever use of the Never Conditions by Fishburn and Craven allowed them to find larger maximal connected acyclic domains for n > 6 (all of diameter n(n-1)/2). They will be presented in section 5 along with Fishburn's construction that allows still larger, but not connected, maximal acyclic domains. Finally in section 6, I will state Galambos and Reiner's work which allows to get a unified version of almost all the known results on maximal connected acyclic domains of diameter n(n-1)/2. In the conclusion I will point out two conjectures. The Appendix contains a Table giving numerical results on lower or upper bounds of f(n) and g(n).

The beginnings : small maximal acyclic domains

As already noted the first maximal (connected) acyclic domain was produced by [START_REF] Black | On the rationale of group decision-making[END_REF][START_REF] Black | The Theory of Committees and Elections[END_REF] who called it the domain of the single peaked preferences. Assume that the set of alternatives is linearly ordered as 1 <2<…<p…<n by a «reference» order. Let L be a linear order of preference on A for which p is the preferred alternative. L is said single-peaked (with respect to the reference order <) if i<j<p implies iLjLp and p<q<r implies rLqLp. This condition means that given that p is the preferred alternative of the voter, he prefers alternative x to alternative y if x is «closer» to p than y in the reference order (for instance such a condition can be satisfied for political preferences, when the political parties can be ranked from extreme left to extreme right). Now it is not difficult to see that a linear order L is single-peaked (w.r.t. <) if and only if for every ordered triple i<j<k, jLi implies kLj and jLk implies iLj, which is true if and only if L satisfies the condition jN1, i.e. for every ordered triple i<j<k, jN {i,j,k} 1 (in other words, the middle alternative of the triple is never the least preferred). Then the domain of single-peaked (w.r.t. <) linear orders is the domain of all linear orders satisfying jN1. It is also easy to see that for n alternatives its size is 2 n-1 (see for instance Kreweras (1962) who used the fact, already observed by Ward that no more than two alternatives can have rank 1 in these single-peaked linear orders). The set of the eight single-peaked linear orders on {1,2,3,4} w.r.t. the linear order 1234 (= 1<2<3<4) is {1234,1243, 1423,1432,4123,4132,4312,432}. The permutoèdre L 4 is represented at Figure 4 and on this figure a black square is attached to each of these eight orders.

Black's single-peakedness condition is a subcase of Arrow-Black's single-peakedness condition 9 (1951), which is the condition ijkN1 i.e., for every 3-subset {i,j,k}, there exists h in {i,j,k} such that h N {i,j,k} 1). An acyclic domain satisfying Arrow-Black's single-peakedness condition does not necessarily satisfy Black's single-peakedness condition. But such an acyclic domain contains also at most 2 n-1 linear orders. This results immediately from the point already mentioned that a Never Condition is hereditary and from another easy observation: the set of elements ranked 1 in the linear orders belonging to a domain satisfying Arrow-Black's singlepeakedness condition has size at most 2. Some other interesting domains satisfying Arrow-Black's condition have been investigated. For instance let be L and L' denote two linear orders which rank the alternatives of A according two different criteria. A decision maker can rank the alternatives from the last by using alternatively the two criteria: he gives rank 1 to an alternative ranked 1 by one of the criteria (i.e. to the worst alternative according to this criteria) ; then he 9 The terminology of these conditions depends on authors. For instance what I call Black's single-peakedness condition (respectively, Arrow-Black's singlepeakedness condition) has been called unimodality condition by Romero 1978 (respectively, pseudo-unimodality condition by Romero and single-peakedness on the triples by Kelly 1978). In fact, as it was observed by [START_REF] Inada | A Note on the Simple Majority Decision Rule[END_REF], Arrow-Black's single-peakedness appears only implicitly in the proof of Theorem 4 in Arrow's book. This condition appears also in [START_REF] Dumett | Stability in voting[END_REF]. What is somewhat confusing is that the term single-peakedness condition is sometimes used without making it clear as to which of the two contexts above the term is being used. deletes this alternative from the two linear orders and he uses the same procedure on the restrictions obtained to determine his next to last alternative, and so on. [START_REF] Romero | Variation sur l'effet Condorcet. Third cycle thesis, Université scientifique et médicale de Grenoble Sen AK[END_REF] said that a set of linear orders obtained by this procedure satisfies the quasi-unimodality condition and he proved that this set satisfies Arrow-Black's single-peakedness condition. When the two linear orders L and L' are dual (xLy if and only if yL'x) one gets again the set of all single-peaked linear orders (w.r.t. L).

It is obvious that the dual of an acyclic domain is also an acyclic domain. For instance the dual of Black's (respectively, Arrow-Black's) single-peaked linear orders, i.e., the set of linear orders satisfying jN3 (respectively, ijkN3) was called by Vickrey (1961) the domain of singletroughed (respectively, by [START_REF] Inada | A Note on the Simple Majority Decision Rule[END_REF] the domain of single-caved) linear orders. One can find a systematic study of the domains of linear orders satisfying one of the Never Conditions in Arrow and Raynaud's book (1986, see also Kohler 1978[START_REF] Romero | Variation sur l'effet Condorcet. Third cycle thesis, Université scientifique et médicale de Grenoble Sen AK[END_REF][START_REF] Raynaud | Conditions for transitivity of majority rule with algorithmic interpretations[END_REF][START_REF] Raynaud | The individual freedom allowed by the value restriction conditions[END_REF].

Another type of acyclic domains was discovered by [START_REF] Blin | The general concept of multidimensional consistency: some algebraic aspects of the aggregation problem[END_REF] under the name of multidimensional consistency: the chains of the «permutoèdre lattice». It will be described in the following section but one can already mention that the size of such a domain is at most n(n-1)/2 +1 and so less than 2 n-1 (for n > 3).

Abello's work

I begin with Abello's contributions that are contained in his doctoral dissertation (1981) and several papers (1981[START_REF] Björner | Orderings of Coxeter groups[END_REF]( with Johnson, 1985[START_REF] Abello | Algorithms for consistent sets[END_REF][START_REF] Abello | An extremal problem on S n[END_REF]( , 1991[START_REF] Abello | The Majority Rule and Combinatorial Geometry (via the Symmetric Group)[END_REF]. In all these papers Abello works with S n the set of all permutations on a set of cardinality n. I will describe some of his results but I will continue to rather speak of linear orders belonging to L n . These results use the partial order known as the weak Bruhat order (on S n )10 . Let L be an arbitrary linear order of L n ; it will be convenient to take L = 1<2<….n. For L' ∈ L n , one sets InvL' = {{i,j} ⊆ A such that iLj and jL'i} (i.e., the set of pairs {i,j} on which L and L' «disagree»). For L', L'' ∈ L n , one sets L'' ≤ L' if InvL' ⊆ InvL''. It has been shown by [START_REF] Gth | Analyse algébrique d'un scrutin[END_REF] that the poset (L n , ≤) denoted henceforth simply by L n is a lattice 11 called the " permutoèdre" lattice in French tradition (see for i nstance [START_REF] Barbut | Ordre et Classification, Algèbre et Combinatoire, tomes I et II. Hachette, Paris Bartholdi III JJ, Trick MA[END_REF]. Its maximum element is 1<2<…n denoted by ϖ, and its minimum element is the dual linear order n<…2<1 denoted by α.

The lattice L 4 is represented on Figure 1 by a (Hasse) diagram giving its covering relation. The undirected covering relation of this lattice is the adjacency relation between linear orders where a linear order is adjacent to another one if they differ on a unique pair of elements. The set of all linear orders endowed with this adjacency relation is called the permutoèdre graph. 11 That is two linear orders have a least upper bound and a greatest lower bound in this partial order. Some authors attribute this result to [START_REF] Yanagimoto | Partial orderings of permutations and monotonicity of a rank correlation statistic[END_REF]. One can admit than a paper published in French will be less known that a paper written in English. But Guilbaud and Rosenstiehl's paper which precedes Yanagimoto and Okamoto's paper has been quoted in many English-written papers ; moreover its proof that S n is a lattice is reproduced in Principles of combinatorics [START_REF] Berge | Principles of Combinatorics[END_REF]) and above all Yanagimoto and Okamoto's paper does not contain a real proof of their assertion (read it !). One can add that properties of the permutoèdre lattice are studied in [START_REF] Barbut | Ordre et Classification, Algèbre et Combinatoire, tomes I et II. Hachette, Paris Bartholdi III JJ, Trick MA[END_REF], Le Conte de Poly- Barbut (1990), [START_REF] Duquenne | On permutation lattices[END_REF], [START_REF] Markowsky | Permutation lattices revisited[END_REF] and [START_REF] Caspard | The lattice of permutations is bounded[END_REF] and that more generally [START_REF] Björner | Orderings of Coxeter groups[END_REF] proved that all finite Coxeter groups partially ordered by the weak Bruhat order are lattices.

Come back to acyclic domains. The first easy observation is that the set of ordered triples ijk contained in the linear orders of an acyclic domain D of L n has size at most 4n(n-1)(n-2)/6 (if not D contains a 3-cyclic profile).

So when one adds to an acyclic domain D all the linear orders, which do not increase the set of ordered triples already present in D one gets a maximal acyclic domain. More generally the map, which adds to an arbitrary set of linear orders all the linear orders that do not increase the set of ordered triples, is a closure operator on the subsets of L n 12 .

The second -also easy but significant-observation is that a maximal chain of L n is an acyclic domain (a fact already observed by [START_REF] Blin | The general concept of multidimensional consistency: some algebraic aspects of the aggregation problem[END_REF] as noted above) which contains exactly 4n(n-1)(n-2)/6 ordered triples. So by applying the above closure operator to a maximal chain one obtains a maximal acyclic set. Now Abello has proved several significant results and in particular the following ones: 1) a maximal acyclic domain D obtained by the closure operator applied to a maximal chain of L n is a connected subset of L n of diameter n(n-1)/2 and an upper semimodular sublattice of the permutoèdre lattice ; 2) for any maximal connected acyclic domain of L n of diameter n(n-1)/2, there exists a maximal acyclic domain with the same size obtained by the closure of a maximal chain ; 3) let us say that two maximal chains of the permutoèdre lattice L n are equivalent if they have the same closure (and so are two maximal chains of the associated lattice). One goes from one of these chains to the other by «quadrangular transformations» of linear orders: let L = x 1 …x k x k+1 …x i x i+1 …x n be a linear order such that x k x k+1 and x i x i+1 are four different alternatives ; then L is transformed into

L ' = x 1 …x k+1 x k …x i+1 x i …x n (= τ i τ k (L) = τ k τ i (L)).
Property 2 means that to search maximal connected acyclic domains of diameter n(n-1)/2 with large size, it suffices to consider those obtained by the closure of a maximal chain. Abello gives an algorithm to get the maximal connected acyclic domain obtained from a maximal chain L 0 p L 1 ...pL n(n-1)/2 of L n . The algorithm constructs a sequence D 0 = {L 0 },D 1 ,…D n(n-1)/2 of acyclic domains. One goes from D s to D s+1 by adding to D s the linear order L k+1 and the set of linear orders obtained by ap-plying to all the linear orders of a subset E s of D s the transposition τ i (of x i and x i+1 ) used to obtain L k+1 from L k ; a linear order M is in E s if there exists in D s ∪{L k+1 } a maximal chain from M to L k+1 , for which none of the transpositions along this chain act on x i or x i+1 .

A similar algorithm can be used with other acyclic domains to get maximal connected acyclic domains. With this algorithm [START_REF] Abello | How large are transitive simple majority domains?[END_REF] show that f(n) ≥ 3(2 n-2 )-4 (for n ≥ 4). Except for n = 4, where one gets a lower bound of 8 and where a maximal acyclic domain of size 9 has been already found 13 , the acyclic domains so found were the first of size greater than 2 n-1 . One will see in the following sections that there exist maximal connected acyclic domains with a much greater size.

Chameni-Nembua's work

Chameni-Nembua's work on acyclic domains is contained in his 1970 «thèse de 3 ème cycle» and in a paper that appeared the same year. I was his thesis' director and his work has answered some questions that I had asked him to investigate. The origin of these questions comes back to Guilbaud's paper in 1952. In this paper one finds an analysis of Black's domain showing that the set of single-peaked linear orders has a distributive lattice structure and that the majority relation of a profile taken in this domain is the median of the elements of the profile in this lattice 14 . In particular one finds (page 289 of the English translation) a figure showing the distributive lattice of the sixteen single-peaked linear orders on a set of five alternatives. This figure is reproduced below at Figure 2a. One can observe that this lattice is a covering sublattice of the permutoèdre lattice L 5 that means that the covering relation in this sublattice is the same as the covering relation in L 5 . Indeed, a single-peaked linear order is covered by another single-peaked linear order if and only if they differ on a unique pair of elements. 13 An acyclic domain of size 9 in L 4 is given in Kim and Roush's book (1980) or in [START_REF] Raynaud | The individual freedom allowed by the value restriction conditions[END_REF]. Such an acyclic domain is represented Figure 4 as AS(4) (see section 5). 14 The fact that in this case majority relation is both a metric and an algebraic median is a special case of median's theory in distributive lattices (or more generally in median semilattices). One will find elements of this theory and references in [START_REF] Barthélemy | The Median Procedure in Cluster Analysis and Social Choice Theory[END_REF], Monjardet (2006a) and in Day and McMorris's 2005 book.

BACDE → ΑBCDE ↑ CBADE → BCADE (A<B) ← (A<C) ← (A<D) ← (A<E) ↑ ↑ ↑ ↑ ↑ DCBAE → CDBAE→ CBDAE→ BCDAE (B<C) ← (B<D) ← (B<E) ↑ ↑ ↑ ↑ ↑ DCBEA → CDBEA→ CBDEA→ BCDEA (C<D) ← (C<E) ↑ ↑ ↑ DCEBA → CDEBA (D<E) ↑ EDCBA →DECBA 2a 2b
Fig. 2. The distributive lattice of the 16 single-peaked linear orders on a 5set and the associated poset of the ordered pairs Several other acyclic domains that are covering distributive sublattices of the permutoèdre lattice were given in [START_REF] Frey | Parties distributives du treillis des permutations, In Ordres totaux finis[END_REF] and in Frey and Barbut's 1971 book. For instance, the so-called «fuseaux bipolaires d'insertions» which are in fact the sets of all linear orders containing a partial order formed by the (cardinal) sum of two unrelated chains. Figure 3 So I asked Chameni-Nembua to answer the following question: is any covering distributive sublattice of the permutoèdre lattice an acyclic domain ? His answer based on the properties of meet and join in this lattice and the fact that a distributive lattice must not contain some sublattices (see any book on lattice theory and Monjardet 1971 for the case of L n ) was positive. Moreover, he showed that maximal covering distributive sublattices are maximal acyclic domains which contain the minimum and the maximum elements of L n (i.e. n<…2<1 and 1<2<….n) and so a maximal chain of L n . These results led us to search such large maximal covering distributive sublattices of L n . For n = 4, one founds the sublattice AS(4), of size 9 represented on Figure 4 (the linear orders with a black ellipsoid). For n = 5, we found such a sublattice of size 20, and for n = 6, I found a sublattice of size 45 which is the last Figure in Chameni-Nembua's paper and which is reproduced here at Figure 5 (with integers instead of letters for the elements of A). This last sublattice showed that it was possible to surpass the best Abello and Johnson's lower bound known at this date (f(6) ≥ 45 > 44 = 3(2 6 -2)-4). I was pretty sure that there was a general construction to get such large acyclic domains but since I didn't find it, I sent these examples to Peter who was already working on the topic and (obviously) found the construction described in the next section 16 . 16 I should be ashamed to have not having found this construction since as it will seen in section 5 it was sufficient to look the triples, and in fact it was also found by Dridi (1994 private letter). But Fishburn achieved a much more difficult task: to compute the size of the corresponding acyclic domains for n up to 25 (Dridi computed this size up to n = 8 with the exact values for n ≤ 7 but he found 220 instead of 222 for n = 8). By the way, it is worthwhile to mention here Fishburn's practice, which should be more wide-spread in our scientific world. In his works on acyclic domains, he always quoted the example that I sent to him. He always did the same in other circumstances and/or for some other authors when I indicated to him a result that preceded one of his works.

Fishburn's and Craven's works

It seems that Peter's interest for acyclic domains was motivated by Craven's conjecture that was reported in Kelly's 1991 paper. In his 1992 book Craven conjectures that f(n) = 2 n-1 and he gives an example of an acyclic domain of size 8 for n = 4 (but see 17 ). Kelly exhibits for n ≥ 4 a maximal acyclic domain of size 2 n -1 generalizing Craven's example (in fact, this domain is a maximal Arrow-Black's single-peaked domain). In his 1992 note Fishburn mentions that the above conjecture is false for n ≥ 4 (see footnote 13) and that in fact f(n)/2 n-1 → ∞. This is proved by using an iterative construction of acyclic domains where the first one is the domain of size 9 on a 4-element set and one goes from an acyclic domain of size p on a n-set to an acyclic domain of size 2p 2 on a 2n-set. Fishburn's paper also contains a replacement construction which for n = 2m and m ≥ 4 that gives a much better lower bound than Abello and Johnson's lower bound: f( 16) ≥ 59049 > 3(2 14 -2)-4 = 49148. In fact when Peter wrote his Notes on Craven's conjecture he didn't remember that Abello had worked on the topic. He remembered only after he read Kim, Roush and Intriligator's 1992 Overview of Mathematical Social Sciences where the problem to find f(n) was mentioned. Therefore, when (in January 1993) I sent him Chameni-Nembua's paper with my example of Figure 5 they were welcomed. A week later he sent me a seven page memo containing the first elements of what became his 1996 and 1997's papers (for which I was referee or editor) and the personal details mentioned above. These papers contain many significant results.

Firstly, Peter defines the alternating scheme which is the construction allowing a generalization of my example. Let 1 <2…<p…<n be a linear order on A. An acyclic domain D of L n satisfies the alternating scheme, if for all i<j<k either (1) jN1 if j is even and or (2) jN3 if j is even and jN3 if j is odd. jN1 if j is odd (observe that these two domains are dual). So to define such a domain, denoted by AS(n), one combines the Never Conditions used for the singlepeaked and single-troughed domains. The size of AS(n) is computed by recursion up to n = 25. Concerning these sizes, Peter writes that he was unable to find a closed formula for them. Such a formula has been since obtained by Galambos and Reiner (2006 see next section). The number of linear orders satisfying the alternating scheme is:

2 n-3 (n+3) -C(n-2, n/2-1) (n-3/2), for even n > 2 2 n-3 (n+3) -C(n-1, (n-1)/2) (n-1)/2), for odd n > 1 where C(p,q) = p!/(p-q)!q! is the binomial coefficient.
Secondly, Fishburn proves that f(4) = 9, f(5) = 20 and that for n ≤ 5, an acyclic domain is maximum if and only if satisfies the alternating scheme. He conjectured the same for n = 6 and 7 the first conjecture having been proved in his 2002 paper (a difficult task!).

Thirdly, it is shown that at least for n ≥ 16, the alternating scheme is not optimal since the replacement scheme is better. This scheme uses two acyclic domains D defined on {0,1,2…m } and D ' defined on {m+1, …m+p}. For every order in D one replaces 0 by each of the orders in D'. It is easy to check that the domain of linear orders obtained on {0,1,2…m, m+1,…m+p} is acyclic. Hence one gets f(m+p) ≥ f(p)f(m+1) and in particular f( 16) ≥ 108336 > 105884 the size of the acyclic domain given by the alternating scheme. Another result allows to show that f(n) > (2.17) n for all large n and that |AS(n)|/ f(n) → 0 as n → ∞ i.e., that the lower bound given by the alternating scheme becomes more and more inaccurate.

Finally, the paper attacks the «major challenge» to find good upper bounds for f(n). The only upper bound already known 2[(n-1)!] had been given in Arrow and Raynaud's book, but for instance it gives f(9) ≤ 103.698 whereas a clever Fishburn's Lemma allows us to obtain f(9) ≤ 22.680. The paper raises two conjectures. The first one is f(n+m) ≤ f(n+1)f(m+1) for all n, m ≥1 and in Fishburn's 2002 paper it is shown that it would imply f(n) < (2.591) n-2 . The second conjecture is f(n) ≤ (c) n for some constant c and this was proved later by [START_REF] Raz | VC-dimension of sets of permutations[END_REF].

I come back now to Craven's works. In his 1994 note he gives a partition scheme which generalizes a construction given in Fishburn's 1992 note and which in a particular case is equivalent to Fishburn's replacement scheme. So he obtains the same formula f(m+p) ≥ f(p)f(m+1) allowing him to improve some lower bounds of Fishburn's note. In his 1996 paper, after reproving the fact that there are 2 n-1 single-peaked linear orders on a n-set (see section 2), he studies the acyclic domains that are generated by Fishburn's alternating scheme. In particular he makes the linear orders that are generated by this scheme more precise and he gives some recurrence relations allowing him to obtain the sizes of the corresponding acyclic domains up to n = 15.

Galambos and Reiner's work

In this section I consider the problem of computing g(n) or rather good lower bounds to this number, i.e., to provide large connected acyclic domains. We have seen that Abello had constructed such domains by applying a closure operator to some maximal chains of the permutoèdre lattice. I gave an example showing that it was possible to find larger such domains that are covering distributive sublattices of the permutoèdre lattice (shown to be acyclic domains by Chameni-Nembua). Generalizing this example by means of his alternating scheme using the two Never Conditions jN3 and jN1, Fishburn obtained the up to now best lower bound known for g(n). I present now the link between these various results, as it is established in recent [START_REF] Galambos | Acyclic Sets of Linear Orders via the Bruhat Order[END_REF]Reiner's 2006 work (andanticipated in Guilbaud's 1952 paper;see Remark later).

Abello constructs maximal connected acyclic domains which are (upper) semimodular sublattices of the permutoèdre lattice by using the fact that the maximal chains of these lattices have an invariant, namely the set of the ordered triples of elements appearing in the orders of the chain. Galambos and Reiner show that these lattices are the same as Chameni-Nembua's lattices, i.e., that they are (maximal) covering distributive sublattices of the permutoèdre lattice and that their maximal chains have another invariant, namely a poset defined on P 2 (n) (the set of n(n-1)/2 ordered pairs (i<j)). The fact that Abello's maximal connected acyclic domains are distributive lattices is significant since it allows to use the wellknown Birkhoff's duality between posets and distributive lattices.

We need some notions of lattice theory. A join-irreducible element of a lattice is an element covering a unique element and an ideal (respectively, a filter) of a poset (X,<) is a subset I of X such that x ∈ I and y < x implies y ∈ I (respectively, a subset F of X such that x ∈ F and x < y implies y ∈ F). Now by Birkhoff's duality between posets and distributive lattices, a distributive lattice D is isomorphic to the set ordered by inclusion of all the ideals of the poset J D of its join-irreducible elements (or to the set ordered by ⊇ of all the filters of J D ). It is well-known that in this duality the maximal chains of a distributive lattice are in a one-to-one correspondence with the linear extensions of the poset J D (i.e. with the linear orders containing the partial order between the join-irreducible elements) ; indeed when x k is covered by x k+1 in a maximal chain of a distributive lattice then there exists a unique join-irreducible element j k such that x k+1 = x k ∨j k ; so the covering relation x k p x k+1 , can be labeled by j k and the linear order j 1 j 2 ....j |JD| obtained on J D is a linear extension of the poset J D .

What are the join-irreducible elements of a covering distributive sublattice of the permutoèdre lattice? I consider a covering distributive sublattice D containing a maximal chain of L n (then containing the maximum element ϖ = 1<2<…n and the minimum element α = n<…2<1 of the permutoèdre lattice). A linear order L is a join-irreducible element of D if it covers a unique other element L' of D. Then one has L = x 1 ...x k x k+1 ...x n = τ k (L' = x 1 ...x k+1 x k ...x n ) with x k <x k+1 (in the order 1<2<….n). Yet, since on a maximal chain between α and ϖ any of the n(n-1)/2 ordered pairs j>i of α has to be transposed exactly once to get ϖ, the transposition of the elements x k and x k+1 appears for the first time in any maximal chain between α and x 1 ...x k x k+1 ...x n . So we can identify the join-irreducible L = x 1 ...x k x k+1 ...x n with the ordered pair (x k ,x k+1 ), and finally the poset of joinirreducible elements of D is isomorphic to a poset P D = [P 2 (n), < D ] defined on the set P 2 (n) of all the ordered pairs i<j. Now, any linear order L in D corresponds to an ideal of P D : L is obtained from α = n<…2<1 by applying all the transpositions of the ordered pairs belonging to this ideal. And any maximal chain of D corresponds to a linear order on P 2 (n), which is a linear extension of the poset P D .

Using more general results on Bruhat orders [START_REF] Ziegler | Higher Bruhat orders and cyclic hyperplanes arrangements[END_REF]) Galambos and Reiner characterize the linear orders on P 2 (n) which are admissible i.e., which correspond to the sequence of transpositions of a maximal chain C of L n : a linear order λ on P 2 (n) is admissible if and only if it contain only triples (of ordered pairs) ordered in the lexicographic order or in its dual, i.e., triples of the form ij<ik<jk or jk<ik<ij. Moreover, these two sets of ordered triples are the same for the linear orders corresponding to any maximal chain of the distributive lattice D closure of the chain C. For instance, a maximal chain of the domain of single peaked-linear orders of L 4 is 4321p4312p4132p1432p1423p1243p1234, the associated linear order on P 2 (4) is 12p13p14p23p24p34 and the set of ordered triples corresponding to any of the maximal chains in this domain is {(12,13,23), (12,14,24), {(13,14,34), {(23,24,34)} (so it does not contain triples dually lexicographically ordered). The domain AS(4) contains the maximal chain 4321p4231p4213p2413p2143p2134p1234; the associated linear order on P 2 (4) is 23p13p24p14p34p12; the associated set of lexicographically (respectively, dually lexicographically) ordered triples is { (13,14,34), {(23,24,34)} (respectively, {(23,13,12), (24,14,12)}).

When one takes an arbitrary maximal chain C = α p L 1 p L 2 …p ϖ of L n it is a maximal chain in a maximal covering distributive sublattice D of the permutoèdre lattice. In order to determine D it suffices to determine the poset P D associated to this maximal chain. Galambos and Reiner constructs P D by using a notion of «arrangement of pseudolines» allowing to represent P D and its ideals and so to recover the linear orders in D. Another algorithm to get P D is proposed in Monjardet (2006b).

When P D is known, computing the size of D comes back to computing the numbers of ideals of this poset, a difficult task in general, since this computation is known to be #P-complete [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF]. In the case when D is given by the alternating scheme, the corresponding poset has a very regular structure (its covering relation is given in Monjardet 2006b). Galambos and Reiner describe it by means of a certain arrangement of pseudolines and show that computing the ideals of this poset comes back computing some lattice paths. By cleverly using path enumeration techniques they get the formula for |AS(n)| given in the previous section.

Another significant Galambos and Reiner's result is the characterization of the maximal covering distributive sublattices D of L n by a set of Never Conditions. Let C be a maximal chain of D and λ be the corresponding linear order admissible on P 2 (n), i.e. the linear order corresponding to the sequence of transpositions of this maximal chain. It has been noted above that the restrictions of λ to any subset {(ij), (ik),(jk)} of three ordered pairs are ordered either lexicographically (ij<ik<jk) or dually lexicographically (jk<ik<ij). Let us denote by LEX 3 λ (respectively, ALEX 3 λ) the set of triples ijk for which the set {(ij), (ik),(jk)} is lexicographically ordered (respectively, dually lexicographically ordered) in λ. As also already noted, LEX 3 λ and ALEX 3 λ are the same for any other maximal chain of D .

Then, D is the set of all linear orders satisfying the following Never Conditions:

jN1, ∀ i<j<k with ijk ∈ LEX 3 λ jN3, ∀ i<j<k with ijk ∈ ALEX 3 λ For instance, for any linear order λ associated to a maximal chain of |AS(4), LEX 3 λ = {134,234} and ALEX 3 λ = {123,124} and one gets again the Never Conditions 3N1 and 2N3 of formula (2) in Section 5.

Remark

As noted before, Guilbaud's paper contains an anticipation of a Galambos and Reiner's result in a particular case. Indeed Guilbaud not only pointed out the distributive lattice structure of the domain of single-peaked linear orders but he also gave an explanation for it. He writes (page 286, English translation): «These remarks focus attention on a sort of hierarchy of the judgments 18 ; one judgment dominates several others…This subord ination is easy to designate in the form of an ordered network» (he adds in note: «This is a partially ordered structure, called a lattice» 19 ). He represents this partial order by a triangular tableau for the domain of singlepeaked linear orders on a 6-element set (this tableau is reproduced here Figure 2b) and he adds below it: «Note that the affirmation of any one of these judgments implies the affirmation of all the «consequents» ; that is, the affirmation of those located either in the same row and to the left, or in the same column and thus of all the judgments located to the left and above». He concludes that single-peaked orders corresponds to frontiers separating judgments + (i.e., x>y) and judgments -(i.e., x<y) in the triangular tableau. In other terms he shows that single-peaked orders correspond to filters in the partial order defined between the ordered pairs.

Conclusion

The search for large acyclic domains appears as a fascinating quest all the more that I have not said all. For instance, maximal chains of the permutoèdre lattice are in one-to-one correspondence with other significant combinatorial objects the standard Young tableaux and the balanced tableaux (see [START_REF] Edelman | Balanced tableaux[END_REF]Greene 1987, Abello 2004) and this allows other interpretations of the problems that have been raised 20 .

There are also interesting algorithmic problems to answer the question of recognizing acyclic domains. Someanswers have been given -especially for Black's single peaked domains-by [START_REF] Romero | Variation sur l'effet Condorcet. Third cycle thesis, Université scientifique et médicale de Grenoble Sen AK[END_REF], see also Arrow and Raynaud 1986), Bartholdi and Trick (1986) and [START_REF] Doignon | A polynomial algorithm for unidimensional unfolding representations[END_REF]. 19 Indeed in the case of the covering distributive sublattice corresponding to single-peaked orders, it is not difficult to prove that the associated poset on P 2 (n) is the lattice where (i,j)∨(k,l) = (max(i,k), max(j,l)) and (i,j)∧(k,l) = (min(i,k), min(j,l)). See also Monjardet (2006b). 20 A balanced tableau is a staircase tableau T of n(n-1)/2 cases -corresponding to the ordered pairs (i<j)-containing the integers from 1 to n(n-1)/2 and satisfying for every i<j<k, t(i,k) between t(i,j) and t(k,j). Such a tableau codes a maximal chain of L n by coding the linear order λ on P 2 (n) associated to this chain: the integer in the case corresponding to (i,j) is the rank of (i,j) in λ. Conversely a balanced tableau induces the maximal chain obtained by effecting the sequence of transpositions of the ordered pairs in the order of the cases of the tableau. The much more sophisticated bijection between maximal chains of L n and standard Young tableaux allows to Edelman and Greene to give a formula for computing the number of these chains.

I end this paper by mentioning a last result and two conjectures. Instead of searching for the maximal covering distributive sublattices of the permutoèdre lattice which have a maximum size, one can ask what are those that have a minimum size. Since such a sublattice is the closure of a maximal chain, one gets the answer if there exist maximal chains that are closed. It's actually the case as it is shown in Monjardet (2006b). This paper contains also some results on the distributive lattices given by Fishburn's alternating scheme and by Black's single-peakedness condition21 .

Conjecture 1 [START_REF] Fishburn | Decision theory and discrete mathematics[END_REF][START_REF] Fishburn | Acyclic sets of linear orders[END_REF] f(n+m) ≤ f(n+1)f( m+1) for all n, m ≥1 The proof of this conjecture would imply (2.17) n < f(n) < (2.591) n-2 for all large n since [START_REF] Fishburn | Acyclic sets of linear orders[END_REF][START_REF] Fishburn | Acyclic sets of linear orders: A progress report[END_REF] proved the lower bound and the implication for the upper bound. Then, if true, it would give a much better upper bound that the bound 4 n-1 conjectured by [START_REF] Abello | The weak Bruhat order of S n , consistent sets, and Catalan numbers[END_REF]. In the same paper Abello conjectures g(n) ≤ 3 n-1 for which the conjectured upper bound (2.591) n-2 would still be much better.

Let |AS(n)| be the size of the acyclic domain given by the alternating scheme. Conjecture 2 [START_REF] Galambos | Acyclic Sets of Linear Orders via the Bruhat Order[END_REF])

g(n) = |AS(n)|
This conjecture is true for n ≤ 6 since in this case f(n) = |AS(n)| and Galambos and Reiner checked it for n = 7.

  Firstly if a set D of linear orders satisfies a set of Never Conditions any subset of D satisfies the same set of Never Conditions. Secondly if a set D of linear orders defined on A satisfies a set of Never Conditions then for every B ⊆ A, D /B (the set of linear orders restrictions to B of the linear orders of D) satisfies the same set of Never Conditions. It is also interesting to mention the following fact on these conditions. Let us denote by L d the dual linear order of the linear order L: xL d y if and only if yLx, and for D ⊆ L, call D d = {L d , L ∈ D} the dual domain of D. Then a domain satisfies the Never Condition hNr if and only if its dual satisfies the Never Condition hN(4-r).

Fig. 1

 1 Fig.1The permutoèdre lattice L 4

Fig. 3 .

 3 Fig. 3. The distributive lattice of the linear extensions of a poset sum of two chains

Fig. 4 .

 4 Fig. 4. Two distributive lattices acyclic domains on a 4-set

Fig. 5 .

 5 Fig.5. AS(6), a distributive lattice acyclic domain of size 45 on a 6-set

In fact Sen's value-restriction condition is more general since it bears on the case where voters' preferences are represented by weak orders (transitive and complete binary relations). But Sen has immediately pointed out that when voters' preferences are represented by linear orders his condition is equivalent to Ward's Latin-square-lessness condition. In this case Ward's result and Arrow's theorem are «dual» (see[START_REF] Monjardet | An axiomatic theory of tournament aggregation[END_REF].

But the set of Never Conditions chosen must be satisfied by at least a linear order. For instance,[START_REF] Raynaud | Conditions for transitivity of majority rule with algorithmic interpretations[END_REF] has shown that for n≥5 there does not exist a

S n the symmetric group of all permutations on { 1,2…,n} is an example of a finite Coxeter group. All Coxeter groups can be partially ordered by the so-called weak Bruhat order (and also by the strong Bruhat order).

This closure operator appears already inKim and Roush's 1980 book (see Definition 5.12)

Like the «fuseaux bipolaires», the «faisceaux d'indifférence» are also the set of linear extensions of some posets P of width 2 (where the width is the maximum number of incomparable elements of P). More generally the set of linear extensions of any poset of width 2 is a covering distributive sublattice of L n (Chameni-Nembua 1989).

This is another example of the bad circulation of some scientific results, since this conjecture had already been made by[START_REF] Johnson | Remarks on mathematical social choice[END_REF] and disproved at least since 1980 (see footnote 13 and Figure4).

In Guilbaud's paper a (simple) judgment is an ordered pair of alternatives expressing a preference between them; for example, x>y (see page 285 of the translation)

But in this paper the conjecture on the size of the covering distributive sublattices of L n is false as soon as n = 5 (contrary to what is written): indeed, there does not exist such sublattices of L 5 with size 13 or 18.

Acknowledgements. I warmly thank the anonymous referee and William Gehrlein as editor for their suggestions and corrections on the first version of the paper.

APPENDIX

Table . Exact values and bounds for g(n) (maximum size of a connected acyclic domain of maximum diameter) and f(n) (maximum size of an acyclic domain)

For all large n, (2.17) n < f(n) [START_REF] Fishburn | Acyclic sets of linear orders[END_REF]) UPPER BOUNDS F: g(n) < C(n) = Catalan number 2 n!/ n!(n +1)! [START_REF] Abello | The weak Bruhat order of S n , consistent sets, and Catalan numbers[END_REF] For all n, f(n) < c n for some n > 0 [START_REF] Raz | VC-dimension of sets of permutations[END_REF]